Приминение муравьиных алгоритмов для задачи коммивояжера.

Введение

Каждый, кто хоть раз в жизни наблюдал за муравьями, обязательно должен был заметить: вся деятельность этих насекомых имеет ярко выра-женную групповую окраску. Работая вместе, группа муравьев способна затащить в муравейник кусок пищи или строительного материала, в 10 раз больше них самих. Организацию муравьев можно применять и людям в решении некоторых задач. Сам по себе муравей - достаточно примитивное существо. Все его действия, по сути, сводятся к элементарным инстинктивным реакциям на окружающую обстановку и своих собратьев. Однако несколько муравьев вместе образуют сложную систему. Например, группа муравьев прекрасно умеет находить кратчайшую дорогу к пище. Если какое-нибудь препятствие - палка, камень, нога человека - встает на пути, они быстро находят новый оптимальный маршрут. Муравьи решают проблемы поиска путей с помощью химической регуляции. Каждый муравей выделяет феромоны, и их след образует, таким образом, путь муравья. Другой муравей, почуяв след на земле, устремляется по нему. Чем больше по одному пути прошло муравьев - тем явнее след, а чем явнее след - тем большее «желание» пойти в ту же сторону возникает у муравьев. Поскольку муравьи, нашедшие самый короткий путь к цели, тратят меньше времени на путь туда и обратно, их след быстро становится самым заметным. Он привлекает большее число муравьев, и круг замыкается. Остальные пути - менее используемые - потихоньку пропадают. Алгоритмы муравья (Ant algorithms), или оптимизация по принципу муравьиной колонии (это название было придумано изобретателем алгоритма, Марко Дориго (Marco Dorigo)), основаны на применении не-скольких агентов и обладают специфическими свойствами, присущими му-равьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, в изменяющихся сетях.
В дипломной работе будет изучено и реализовано применение муравьиных алгоритмов для задачи коммивояжера.

Введение 2 1. Задача коммивояжера 4 1.1. Содержательное описание 4 1.2. Математическая модель 4 1.3. Постановка оптимизационной задачи 6 1.4. Методы решения задачи коммивояжера 7 1.4.1. Метод ветвей и границ 7 1.4.2. Алгоритм Дейкстры 10 1.4.3. Генетические алгоритмы 12 2. Муравьинные алгоритмы 13 2.1. История создания муравьиных алгоритмов 13 2.2. Концепция муравьиных алгоритмов 14 2.3. Обобщённый алгоритм 15 2.4. Этапы решения задачи при помощи муравьиных алгоритмов 17 3. Применение муравьиных алгоритмов для задачи коммивояжёра 19 4. Реализация муравьинного алгоритма 27 4.1. Выбор средства разработки 27 4.2. Разработка экранной формы приложения 28 4.3. Тестирование 34 5. Сравнение методов решения задачи коммивояжера 38 Заключение 41 Литература 43 Приложение 45

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., «Мир», 1965, 174 с.
2. В. П. Сигорский. Математический аппарат инженера. - К., «Техніка», 1975, 768 с.
3. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математиче-ское программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.
4. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. – М., Наука, 1979, 345 с.
5. Е. П. Липатов. Теория графов и её применения. - М., Знание, 1986, 32 с.
6. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы про-граммирования. – Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.
7. Ф. А. Новиков Дискретная математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с.
8. Bonavear E., DorigoM. Swarm Intelligence: from Natural to Artificial Systems.— Oxford University Press, 1999.— 307 p.
9. Corne D., Dorigo M., Glover F. New Ideas in Optimization.— McGrav Hill, 1999.
10. Dorigo M. Swarm Intelligence, Ant Algorithms and Ant Colony Optimization // Reader for CEU Summer University Course «Complex System».— Budapest, Central European University, 2001.— P. 1–38
11. http://irida.ulb.ac.de/ACO/ACO.html.
12. http://www.iwr.uniheidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
13. Reimann M. Ant Based Optimization in Good Transportation. PhD Thesis. University of Vienna.— Vienna, Austria, 2002.— 149 p.
14. Caro G. D., DorigoM. Anet: a Mobile Agents Approach to Adaptive Routing. Technical Report IRIDA 97 12. IRIDA— Universite Libre de Brusseles.— Brussels, Belgium, 1997.— 27 p.
15. http://www.swarm.org.
16. Cherix D. Note preliminaire sur la structure, la phenologie et le regime alimentaire d\'une super colonie de Formica lugubris Zett. // Insects Sociaux 27, 1980.— P. 226–236.