Подробнее

Оригинальная идея исходит от наблюдения за муравьями в процессе поиска кратчайшего пути от колонии до источника питания.

1. Первый муравей находит источник пищи (F) любым способом (а), а затем возвращается к гнезду (N), оставив за собой тропу из феромонов (b).

2. Затем муравьи выбирают один из четырёх возможных путей, затем укрепляют его и делают привлекательным.

3. Муравьи выбирают кратчайший маршрут, так как у более длинных феромоны сильнее испарились.

Среди экспериментов по выбору между двумя путями неравной длины, ведущих от колонии к источнику питания, биологи заметили, что, как правило, муравьи используют кратчайший маршрут.^[6][10]. Модель такого поведения заключается в следующем:

· Муравей (так называемый «Блиц») проходит случайным образом от колонии

· Если он находит источник пищи, то возвращается в гнездо, оставляя за собой след из феромона

· Эти феромоны привлекают других муравьёв находящихся вблизи, которые вероятнее всего пойдут по этому маршруту

· Вернувшись в гнездо они укрепят феромонную тропу

· Если существует 2 маршрута, то по более короткому, за то же время, успеют пройти больше муравьёв, чем по длинному

· Короткий маршрут станет более привлекательным

· Длинные пути, в конечном итоге, исчезнут из-за испарения феромонов

Муравьи используют окружающую среду как средство общения. Они обмениваются информацией косвенным путём, через феромоны, в ходе их «работы». Обмен информации имеет локальный характер, только те муравьи, которые находятся в непосредственной близости, где остались феромоны — могут узнать о них. Такая система называется «Stigmergy» и справедлива для многих социальных животных (был изучен в случае строительства столбов в гнёздах термитов). Данный механизм решения проблемы очень сложен и является хорошим примером самоорганизации системы. Такая система базируется на положительной (другие муравьи укрепляют феромонную тропу) и отрицательной (испарение феромонной тропы) обратной связи. Теоретически, если количество феромонов будет оставаться неизменным с течением времени по всем маршрутам, то невозможно будет выбрать путь. Однако из-за обратной связи, небольшие колебания приведут к усилению одного из маршрутов и система стабилизируется к кратчайшему пути.

Вариации алгоритма

Вот одни из самых популярных вариаций муравьиного алгоритма: