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