Сравнительный анализ эффективности работы генетического алгоритма при модификации оператора мутации в задаче коммивояжера
Авторы: Доманов К.И. | |
Опубликовано в выпуске: #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.