Возможности использования элитных особей при решении задачи коммивояжера моделью Гольдберга

Целью данной работы является исследование актуальной задачи коммивояжера, которая является NP сложной задачей дискретной оптимизации. Показано, что для достижения поставленной цели пригодны лишь эвристические методы. Для решения задачи представлен результат совместного использования муравьиного (МА) и генетического (ГА) алгоритмов. Особенностью предложенного генетического алгоритма является то, что задача решается только с помощью различных мутаций (без кроссовера). Исследуемый ГА был улучшен введением элитарной стратегии. Испытания проводились на графах средней и большой размерности. Элитная особь, получаемая с помощью муравьиного алгоритма, в среднем улучшалась на 11 %. Показано, что эффективность генетического алгоритма напрямую зависит от количества особей в поколении и количества итераций алгоритма. Ввод элитарной стратегии улучшил получаемые значения целевой функции более чем в 2 раза. Увеличение числа запусков МА при выборе элиты позволило повысить эффективность алгоритма приблизительно на 2 %.

задача коммивояжера, генетический алгоритм, граф, модель Гольдберга, мутация, кроссовер, муравьиный алгоритм, элитная особь, феромон, природные вычисления, traveling salesman problem, genetic algorithm, graph, Goldberg model, mutation, crossover, ant colony algorithm, elite sample, pheromone, natural computing

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.