Реферат: Алгоритм муравья

Вероятность того, что муравей выберет нижний путь (представленный количеством феромона 0,28) составляет:

При сопоставлении двух вероятностей оба муравья выберут нижний путь, который является наиболее оптимальным.

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

Для алгоритма муравьиной колонии необходимо указать:

· закон выделения феромона,

· закон испарения феромона,

· количество агентов,

· места размещения.

Все эти характеристики выбираются с учетом особенности задачи на основе экспериментальных исследований (эвристики).

Алгоритм:

· реализует поиск приближенных решений,

· имеет полиномиальную сложность,

· является одним из видов вероятностных алгоритмов (законы выделения испарения – вероятностные законы).

12. Области применения

Алгоритм муравья может применяться для решения многих задач, таких как распределение ресурсов и работы.

При решении задачи распределения ресурсов необходимо задать группу ресурсов n для ряда адресатов m и при этом минимизировать расходы на перераспределение (то есть функция должна найти наилучший способ распределения ресурсов). Обнаружено, что алгоритм муравья дает решения такого же качества, как и другие, более стандартные способы.

Намного сложнее проблема распределения работы. В этой задаче группа машин М и заданий J (состоящих из последовательности действий, осуществляемых на машинах) должны быть распределены таким образом, чтобы все задания выполнялись за минимальное время. Хотя решения, найденные с помощью алгоритма муравья, не являются оптимальными, применение алгоритма для данной проблемы показывает, что с его помощью можно решать аналогичные задачи.

Алгоритм муравья применяется для решения других задач, например, прокладки маршрутов для автомобилей, расчета цветов для графиков и маршрутизации в сетях. Более подробно способы использования алгоритма муравья описываются в книге Марко Дориго «Алгоритмы муравья для абстрактной оптимизации»

Заключение

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

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

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

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

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

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

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