The article presents the theoretical basis of ant algorithms optimization. The traveling salesman problem is solved by using ant algorithms.
the traveling salesman problem, ant algorithms, optimization.
УДК: 621.395.8
ПРИМЕНЕНИЕ МУРАВЬИНЫХ АЛГОРИТМОВ ДЛЯ РЕШЕНИЯ
ЗАДАЧИ КОММИВОЯЖЕРА
THE APPLICATION OF ANT ALGORITHMS FOR SOLVING
TRAVELING SALESMAN PROBLEM
КанищеваО.И.,
Пристинский К.В.
ВУНЦ ВВС «Военно-воздушная академия
им. проф. Н.Е. Жуковского и Ю.А. Гагарина»
г.Воронеж, Россия
oleka_olesya@mail.ru
DOI: 10.12737/15975
Аннотация: В работе приведены теоретические основы муравьиных алгоритмов оптимизации. Описанорешениемуравьинымиалгоритмамизадачикоммивояжера.
Summary: The article presents the theoretical basis of ant algorithms optimization. The traveling salesman problem is solved by using ant algorithms.
Ключевые слова: задача коммивояжера, муравьиные алгоритмы, оптимизация.
Keywords: the traveling salesman problem, ant algorithms, optimization.
В последние годы интенсивно разрабатывается научное направление «Природные вычисления» (Natural Computing), объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений. Среди так называемых «Soft computing techniques», разработанных за последние десять лет для трудно решаемых задач дискретной оптимизации, числятся
- генетические алгоритмы, основанные на естественном отборе и генетике;
- муравьиные алгоритмы (Ant Colony Optimization – ACO, Ant Systems – AS), моделирующие поведение муравейника.
Целью настоящего исследования является изучение работы муравьиных алгоритмов и их практическое применение для решения задачи коммивояжера.
Теоретическая часть статьи базируется на книгах [1, 2], лекции изобретателя муравьиных алгоритмов доктора Марко Дориго в летней школе по сложным системам [3].
1. Bonavear E., Dorigo M. Swarm Intelligence: from Natural to Artificial Systems. - Oxford University Press, 1999. - 307 p.
2. Corne D., Dorigo M., Glover F. New Ideas in Optimization. - McGrav_Hill, 1999.
3. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization. Reader for CEU «Complex System». - Budapest, 2001. - P. 1-38.
4. Shtovba S. D. Murav´inye algoritmy. Matematika v prilozheniyakh, 2003, №4, S. 70-75.
