Целью данной работы является исследование актуальной за-дачи коммивояжера, которая является NP сложной задачей дискретной оптимизации. Показано, что для достижения по-ставленной цели пригодны лишь эвристические методы. Для решения задачи представлен результат совместного использо-вания муравьиного (МА) и генетического (ГА) алгоритмов. Особенностью предложенного генетического алгоритма явля-ется то, что задача решается только с помощью различных мутаций (без кроссовера). Исследуемый ГА был улучшен вве-дением элитарной стратегии. Испытания проводились на графах средней и большой размерности. Элитная особь, получаемая с помощью муравьиного алгоритма, в среднем улучшалась на 11 %. Показано, что эффективность генетического алгоритма напрямую зависит от количества особей в поколении и количества итераций алгоритма. Ввод элитарной стратегии улучшил получаемые значения целевой функции более чем в 2 раза. Увеличение числа запусков МА при выборе элиты позволило повысить эффективность алгоритма приблизительно на 2 %.
задача коммивояжера, генетический алгоритм, граф, модель Гольдберга, мутация, кроссовер, муравьиный алгоритм, элитная особь, феромон, природные вычисления.
Задача коммивояжера (ЗК) является NP сложной задачей дискретной оптимизации и определяется следующим образом: для заданного полного взвешенного графа G = (V, E, D) с множеством вершин V = {vi}n, множеством ребер E и матрицей весов D = {di,j}nxn необходимо найти Гамильтонов цикл (vi1, vi2,…,vin), где (i1,…,in) — перестановка на множестве {1,2,…,n}, а vi
V, с минимальной суммой весов дуг [1]
Вершины графа G часто называются городами, а любой Гамильтонов цикл называется маршрутом коммивояжера. Очевидным решением задачи является метод полного перебора. Выйдя из первого города, коммивояжер может направиться в один из (n – 1) городов, откуда в (n – 2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число маршрутов, подлежащих просмотру, составляет (n – 1) · (n – 2) … 2 · 1 = (n – 1) всевозможных вариантов. С увеличением количества городов это значение быстро возрастает и уже при 15 городах достигает астрономических цифр. Поиск точных и приближенных способов решения задачи о коммивояжере остается актуальным и с теоретической, и с практической точки зрения, так как не найдено, а возможно, и не существует точных алгоритмов, решающих ЗК за короткое (полиномиальное) время. Поэтому для решения задачи коммивояжера эффективнее использовать не точные, а эвристические методы. Применение эвристических алгоритмов к какой-либо практической задаче обычно позволяет сформулировать рекомендации, которые намного лучше произвольного решения и которые наиболее близки к лучшему варианту.
1. Гладков, Л. А. Генетические алгоритмы / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик — Москва : Физ-матлит, 2007. — 272 с.
2. Gambardella, L.-M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem [Электрон-ный ресурс] / L.-M. Gambardella, M. Dorigo. — Режим доступа: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.4846 (дата обращения: 16.09.15).
3. Dorigo, M. The Ant System: Optimization by a colony of cooperating agents [Электронный ресурс] / M. Dorigo, V. Maniezzo, A. Colorni. — Режим доступа: ftp://iridia.ulb.ac.be/pub/mdorigo/journals/IJ.10-SMC96.pdf (дата обращения: 20.09.15).
4. Gambardella, L.-M. Solving symmetric and asymmetric TSPs by ant colonies [Электронный ресурс] / L.-M. Gambardella, M. Dorigo. — Режим доступа: http://ceit.aut.ac.ir/~meybodi/Learning%20Automata%20papers/LA-Papers-Ebdali/00542672.PDF (дата обращения: 27.09.15).
5. Чураков, М. Муравьиные алгоритмы. / М. Чураков, А. Якушев. — Режим доступа: http://rain.ifmo.ru/cat/ (дата обращения: 25.09.2015).
6. Штовба, С. Д. Муравьиные алгоритмы [Электронный ресурс] / С. Д. Штовба. — Режим доступа: http://www.serhiyshtovba.narod.ru/doc/Shtovba_Ant_Algorithms_Exponenta Pro_2003_3.pdf (дата обращения: 25.09.15).
7. Емельянов, В. В. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик. — Москва : Физматлит, 2003. — 432 с.
8. Кобак, В. Г. Сравнительный анализ модифицированной модели Гольдберга и муравьиного алгоритма при решении задачи коммивояжера / В. Г. Кобак, И. Ш. Рудова, А. Г. Жуковский // Тр. Сев.-Кавк. филиала Моск. техн. ун-та связи и информатики. — Ростов-на-Дону, 2015. — T. 1. — С. 362–365.
9. Кобак, В. Г. Решение задачи коммивояжера модифицированной моделью Гольдберга с использованием различных сильных мутаций / В. Г. Кобак, И. Ш. Рудова // Сб. тр. юбилейной конф. студентов и молодых ученых, посвященной 85-летию ДГТУ. — Ростов-на-Дону, 2015. — С. 146–156.
10. Решение задачи коммивояжера модифицированной моделью Гольдберга с помощью различного вида мутаций / В. Г. Кобак [и др.] // Тр. Сев.-Кавк. филиала Моск. техн. ун-та связи и информатики. — Ростов-на-Дону, 2014. — T. 1. — С. 258–261.
