Статья

Название статьи ГИБРИДНЫЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА
Автор А.В. Мартынов, В.М. Курейчик
Рубрика РАЗДЕЛ I. МОДЕЛИРОВАНИЕ И ПРОЕКТИРОВАНИЕ
Месяц, год 04, 2015
Индекс УДК 004.023
DOI
Аннотация Целью данной работы является разработка эффективного гибридного метода для решения задачи коммивояжера на основе эволюционного и роевого методов. Муравьиный и генетический алгоритмы являются альтернативами для решения задач дискретной оптимизации. Генетический алгоритм – это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе, а муравьиный, в свою очередь, использует поведенческие инструменты децентрализованной самоорганизующейся колонии муравьев для поиска оптимального маршрута в графовой модели. Предложен гибридный алгоритм решения задачи коммивояжера на основе муравьиного и генетического алгоритмов, при этом гибридизация заключается не только в последовательном использовании операторов муравьиного и генетического алгоритмов, но и учетом генетической информации агентом муравьиного алгоритма при принятии решения в процессе построения пути. Операторы генетического алгоритма используются для рекомбинации решений-кандидатов, полученных в ходе работы муравьиного алгоритма. Представлена эвристика оценки найденных решений агентами муравьиного алгоритма для дальнейшей их селекции генетическим алгоритмом. В ходе проделанной работы была разработана программа ЭВМ, реализующая описанный алгоритм. Представлено сравнение результатов тестирования муравьиного и гибридного алгоритмов на международных бенчмарках. Полученные в ходе экспериментов результаты показали, что гибридный алгоритм осуществляет поиск решений более качественно, чем обычный муравьиный алгоритм.

Скачать в PDF

Ключевые слова Муравьиный алгоритм; генетический алгоритм; роевой интеллект; коммивояжер; дискретная оптимизация.
Библиографический список 1. Dorigo M., Stutzle T. Ant Colony Optimization // Bradford Books, 2004.
2. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem // BioSystems. – July 1997. – Vol. 43, No. 2. – P. 73-81.
3. Hahsler M., Hornik K. TSP – Infrastructure for the Traveling Salesperson Problem // Journal of Scientific Software. – 2007. – Vol. 32, Issue 2. – P. 1-21.
4. Paschos V., Monnot J., Toulouse S. The travelling salesman problem and its variations // Paradigms of Combinatorial Optimization. – 2014. – P. 173-214.
5. Борознов В.О. Исследование решения задачи коммивояжера // Вестник Астраханского государственного технического университета. Управление, вычислительная техника и информатика. – 2009. – C. 147-151.
6. Кажаров А.А. Курейчик В.М. Муравьиные алгоритмы для решения транспортных задач // Известия РАН. Теория и системы управления. – 2010. – № 1. – C. 32-45.
7. Штовба Д.С. Муравьиные алгоритмы: теория и применение // Математика в приложениях. – 2004. – C. 70-75.
8. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning, USA: Addison-Wesley Publishing Company, Inc., 1989.
9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит, 2006. – 320 c.
10. Goldberg D.E., Lingle R. Alleles, Loci, and the Traveling Salesman Problem // Proceedings of the First International Conference on Genetic Algorithms and Their Application. – 1985. – P. 154-159.
11. Чернышев Ю.О., Басова А.В., Полуян А.Ю. Решение задач транспортного типа генетическими алгоритмами. – Ростов-на-Дону: Изд-во ЮФУГОУ, 2008. – 73 c.
12. Kumar N., Karambir, Kumar R. A comparative analysis of PMX, CX and OX Crossover operators for solving traveling salesman problem // International Journal of Latest Research in Science and Technology. – 2012. – P. 98-101.
13. Курейчик В.М., Лебедев Б.К., Лебедев О.К. Поисковая адаптация: теория и практика. – М.: Физматлит, 2006. – 272 c. – ISBN 5-9221-0749-6.
14. Abdoun O., Abouchakaba J, Tajani C. Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem // CoRR. Vol. abs/1203.3099. – 2012. – P. 66-77.
15. Параметры и классы протоколов маршрутизации [Электронный ресурс]. – Режим доступа: http://skif.bas-net.by/bsuir/base/node360.html. – Заглавие с экрана. – (Дата обращения 23.01.2015).
16. TSPLIB [Электронный ресурс]. – Режим доступа: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95 /tsp/. – Заглавие с экрана. – (Дата обращения 23.01.2015).
17. Ciba M., Sekaj I. Ant colony optimization with re-initialization // Automation, Control and Intelligent Systems. – 2013. – № 1 (3). – P. 53-66.
18. Dai Q., Junzhong J., Chunnian L., An effective initialization strategy of pheromone for ant colony optimization // Bio-Inspired Computing, 2009.
19. Zhu Q.B., Yang Z.J. An Ant Colony Optimization Algorithm Based on Mutation and Dynamic Pheromone Updating // Journal of Software. – 2004. – № 2 (15). – P. 185-192.
20. Solomon M.M. Algorithms for the vehicle routing and scheduling problems with time windows constraints // Operations Research. – 1987. – № 35. – P. 254-265.

Comments are closed.