Сравнительный анализ эффективности работы генетического алгоритма при модификации оператора мутации в задаче коммивояжера

Авторы: Доманов К.И.
Опубликовано в выпуске: #1(66)/2022
DOI: 10.18698/2541-8009-2022-1-760
Раздел: Информатика, вычислительная техника и управление | Рубрика: Системный анализ, управление и обработка информации, статистика
Ключевые слова: задача коммивояжера, генетический алгоритм, граф, многоточечная мутация, поколение, экстремум, вершины, эффективность алгоритма, Python
Опубликовано: 31.01.2022

Исследовано влияние многоточечной мутации на результат работы генетического алгоритма при решении задачи коммивояжера. В данной работе применена «жадная» стратегия оператора кроссовера и операторы мутации двух видов: точечной и многоточечной. Точечная мутация представляет собой тип мутации, при котором осуществляется выбор случайной вершины и вставка ее в случайное место последовательности. Суть многоточечной мутации заключается в динамическом изменении количества вершин, подверженных операции мутации, в зависимости от количества вершин рассматриваемой задачи и порядкового номера текущей популяции. Разработано программное обеспечение, реализующее данный алгоритм. Проведенные исследования показали, что на задачах малой размерности алгоритмы с различными типами мутаций работают примерно одинаково. Однако при увеличении количества вершин и числа поколений предложенный механизм многоточечной мутации показал большую эффективность.

Литература

[1] Колесников А.В., Кириков И.А., Листопад С.В. и др. Решение сложных задач коммивояжера методами функциональных гибридных интеллектуальных систем. М., ИПИ РАН, 2011.

[2] Мудров В.И. Задача о коммивояжере. М., Знание, 1969.

[3] Кобак В.Г., Рудова И.Ш. Исследование влияния сильных мутаций при решении задачи коммивояжера модифицированной моделью Голдберга. Известия ЮФУ. Технические науки, 2017, № 3, с. 140–148.

[4] Why we are transposing or reversing the directions of all arcs (edges) in the Kosaraju two pass algorithm? quora.com: веб-сайт. URL: https://www.quora.com/Why-we-are-transposing-or-reversing-the-directions-of-all-arcs-edges-in-the-Kosaraju-two-pass-algorithm (дата обращения: 13.11.2021).

[5] Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М., Физматлит, 2006.

[6] Панченко Т.В. Генетические алгоритмы. Астрахань, Астраханский университет, 2007.

[7] Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации. Нижний Новгород, ННГУ, 2007.

[8] Вороновский Г.К., Махотило К.В. Петрашев С.Н. и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков, Основа, 1997.

[9] Джонс М.Т. Программирование искусственного интеллекта в приложениях. М., ДМК Пресс, 2004.

[10] Протодьяконов А.В., Фомин А.Н. Швец С.Е. и др. Влияние параметров генетического алгоритма на результаты решения задачи коммивояжера. Вестник Кузбасского государственного технического университета, 2009, с. 105–111.