Использование муравьиных алгоритмов в задачах оптимизации

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

Основные черты искусственных муравьев, взяты из их естественной модели:
1. искусственные муравьи существуют в колониях, сотрудничая друг с другом;
2. они общаются косвенным путем;
3. они используют последовательность локальных движений, чтобы найти кратчайший путь из начальной точки, в пункт назначения (то есть оптимальное решение данной проблемы);
4. они применяют стохастические решения, с использованием текущей информации (то есть они не смотрят вперед), чтобы найти оптимальное решение. В случае необходимости, чтобы решить конкретную проблему оптимизации, искусственные муравьи могут быть обогащены некоторыми дополнительными возможностями, не присутствующиими в их природных аналогах.

Конечное число муравьев объединяются в колонию для поиска решения данной задачи оптимизации. Каждый муравей может, уже сам по себе найти решение, или по крайней мере частичное решение задачи оптимизации, но только вместе они найти оптимальное решение. Так как оптимальное решение может быть найдено только в рамках сотрудничества всех муравьев колонии, оно возникает в результате такого сотрудничества. В поисках решения муравьи не общаются напрямую, а косвенно, добавляя феромоны в окружающую среду. На основе конкретной проблемы муравью задается исходное состояние и затем он проходит через последовательность соседних позиций , пытаясь найти кратчайший путь. Он движется основываясь на свое внутреннее состояние (личная информация) и следы феромонов, несущую информацию, закодированную в окружающей среде (общая информация информации). Такие личные и общие сведения используются также чтобы решить, когда муравью сохранять феромон. В большинстве случаев количество сохраненных феромонов пропорционально качеству движений муравья. Таким образом, чем больше феромонов, тем лучшее решение найдено. После того как муравей нашел решение он умирает, то есть удаляется из системы.

Применение муравьиных алгоритмов может быть разделено на два класса: для статических и динамических задач комбинаторной оптимизации. В статических задачах ключевые точки задачи определены в начале и не изменяются, в ходе решения. В динамических задачах цель изменяется в зависимости от своего состояния, поэтому алгоритмы, используемые для решения этих задач должны быть в состоянии адаптировать алгоритм в соответствии с внесенными изменениями.

Примерами приложений для первого класса задач, то есть статических задач комбинаторной оптимизации являются:
•  Задача коммивояжера, где продавец должен найти кратчайший маршрут, по которому посетить заданное число городов, в каждом городе побывав только один раз;
•  Квадратичные задачи о распределении, проблема распределения n средств в n мест так, что расходы на распределение были сведены к минимуму;
•  Задачи календарного планирования - с учетом множества оборудования и множества целей – все цели должны быть назначены на временные интервалы таким образом, что два задание не выполняются в одно и то же время на одном оборудовании, а времени завершения всех операции сведено к минимуму;
•  Механизм маршрутизации — найти минимальную стоимость маршрутов транспортных средств, таких, что (а) каждый клиент посетил один автомобиль ровно один раз, (б) для каждого транспортного средства общего спроса не превышает вместимость транспортного средства (в) общее тур длина каждого транспортного средства не превышает заданный лимит, и (г) каждое транспортное средство начинает и заканчивает свой тур в том же положении (депо);
•  Кратчайшая общая последовательность — учитывая множество — найти строку минимальной длины, которая будет включать все остальные строки
•  Проблема раскраски графа — проблема нахождения раскраски графа так, что количество цветов, используемых минимальна.

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