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