×

Вы используете устаревший браузер Internet Explorer. Некоторые функции сайта им не поддерживаются.

Рекомендуем установить один из следующих браузеров: Firefox, Opera или Chrome.

Контактная информация

+7-863-218-40-00 доб.200-80
ivdon3@bk.ru

  • Решение задачи коммивояжера с использованием двухэтапного генетического алгоритма

    • Аннотация
    • pdf

    В статье рассмотрено применение модифицированного двухэтапного генетического алгоритма к решению задачи коммивояжера. Задача коммивояжера является NP-сложной. При количестве городов 66 и более ее невозможно решить методом полного перебора. Для проверки предложенного подхода к решению рассматривается граф с 51 вершиной. На первом этапе работает модифицированная модель Голдберга с небольшими значениями параметров для получения первого поколения второго этапа с лучшими показателями, чем при случайном формировании особей. Второй этап работает с увеличенными значениями параметров генетического алгоритма. Эти значения варьируются от эксперимента к эксперименту, результаты которых представлены на диаграммах. Также результаты работы двухэтапного алгоритма сравниваются с результатами одноэтапного алгоритма. Используется модифицированная модель Голдберга генетического алгоритма. В генетическом алгоритме применяется путевое представление маршрута коммивояжера с двухточечным упорядоченным кроссовером и «жадной» мутацией. Результаты экспериментов показали эффективность предлагаемого подхода. Модифицированный двухэтапный алгоритм позволяет получить решение близкое к оптимальному.

    Ключевые слова: задача коммивояжера, генетический алгоритм, модель Голдберга, кроссовер, мутация, особь, маршрут, гамильтонов цикл, матрица расстояний

    05.13.01 - Системный анализ, управление и обработка информации (по отраслям)