Магистерская диссертация на тему: Идея алгоритма. Пошаговое описание общей схемы. Муравей. Начальная популяция

Введение

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

Мы рассмотрим общий случай алгоритма муравьиной колонии.

Оглавление

- Введение

- Идея алгоритма

- Пошаговое описание общей схемы

- Муравей

- Начальная популяция

- Движение муравья

- Путешествие муравья

- Испарение фермента

- Повторный запуск

- Блок-схема алгоритма

- Демонстрационный пример

- Характерные особенности

- Области применения Заключение

- Список литературы

Заключение

Рассмотрены механизмы реализации эвристических алгоритмов муравьиной колонии. Они могут быть успешно применены для решения сложных комбинаторных задач оптимизации. Основная идея, лежащая в основе алгоритмов муравьиной колонии, заключается в использовании механизма положительной обратной связи, который помогает найти наилучшее приближенное решение в сложных задачах оптимизации. То есть, если в данном узле муравей должен выбрать между различными вариантами и если фактически выбранные результаты будут хорошими, то в будущем такой выбор будет более желателен, чем предыдущий. Этот подход является многообещающим из-за его общности и эффективности в обнаружении очень хороших решений сложных проблем.

Список литературы

1. Джонс М.Т. Программирование искусственного интеллекта в приложениях / Пер. с англ. Осипов А.И. - Москва 2004

2. Журнал "Мир ПК". - №3. -2002

3. Сборник научных трудов СевКавГТУ. Серия "Естественнонаучная". 2006. №2

4. Штовба С.Д. Муравьиные алгоритмы. Exponenta Pro. Математика в приложениях, 2003, №4, стр. 70-75.

5. МакКоннелл Дж. Основы современных алгоритмов. - М.: Техносфера, 2004. - 368 с.