История создания муравьиных алгоритмов

Началось всё с изучения поведения реальных муравьёв. Эксперименты с Argentine ants, проводимые Госсом в 1989 и Денеборгом в 1990 году послужили отправной точкой для дальнейшего исследования роевого интеллекта. Исследования применения полученных знаний для дискретной математики начались в начале 90-х годов XX века, автором идеи является Марко Дориго из Университета Брюсселя, Бельгия. Именно он впервые сумел формализовать поведение муравьёв и применить стратегию их поведения для решения задачи о кратчайших путях. Позже при участии Гамбарделлы, Тайлларда и Ди Каро были разработаны и многие другие подходы к решению сложных оптимизационных задач при помощью муравьиных алгоритмов. На сегодняшний день эти методы являются весьма конкурентоспособными по сравнению с другими эвристиками и для некоторых задач дают наилучшие на сегодняшний день результаты.

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

Имитация самоорганизации муравьиной колонии составляет основу муравьиных алгоритмов оптимизации. Колония муравьев может рассматриваться как многоагентная система, в которой каждый агент (муравей) функционирует автономно по очень простым правилам. В противовес почти примитивному поведению агентов, поведение всей системы получается на удивление разумным. [14].

Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 90-х годов. На сегодняшний день уже получены хорошие результаты для оптимизации таких сложных комбинаторных задач, как задача коммивояжера, задача оптимизации маршрутов грузовиков, задача раскраски графа, квадратичная задача о назначениях, задача оптимизации сетевых графиков, задача календарного планирования и многие другие.

Особенно эффективны муравьиные алгоритмы при динамической оптимизации процессов в распределенных нестационарных системах, например, трафиков в телекоммуникационных сетях. [1].