Муравьиные алгоритмы

Материал из MachineLearning.

Содержание

1 Постановка задачи коммивояжера
2 Принцип работы алгоритма
3 Основные алгоритмические шаги
4 Результаты экспериментов
5 Литература
6 Ссылки

Муравьиные алгоритмы серьезно исследуются европейскими учеными с середины 1990-х годов. Уже получены хорошие результаты муравьиной оптимизации для многих сложных комбинаторных задач: задачи коммивояжера, оптимизации маршрутов грузовиков, раскраски графа, квадратичной задачи о назначениях, оптимизации сетевых графиков, задачи календарного планирования и других. Особенно эффективны муравьиные алгоритмы при on-line оптимизации процессов в распределенных нестационарных системах, например трафиков в телекоммуникационных сетях. Рассмотрим применение муравьиных алгоритмов на примере задачи коммивояжера.

Постановка задачи коммивояжера

В классической постановке коммивояжер должен объехать N городов по замкнутому маршруту, посетив каждый из них лишь однажды, таким образом, чтобы полная длина его маршрута была минимальной. Если решать задачу коммивояжера „в лоб“ - перебором всех замкнутых путей, связывающих города, то придется проверить все (N-1)!/2 возможных маршрутов, то есть простой метод перебора всех вариантов чрезвычайно неэффективный при большом N. Эффективными же признаются решения, гарантирующие получение ответа за время, ограниченное полиномом от размерности задачи. С помощью муравьиных алгоритмов находятся субоптимальные решения, локальные минимумы целевой функции, приближающиеся к абсолютному минимуму.

Принцип работы алгоритма

Поведение колонии

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

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

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

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

Основные алгоритмические шаги

Любой муравьиный алгоритм, независимо от модификаций, представим в следующем виде

Пока (условия выхода не выполнены)

Создаём муравьёв
Ищем решения
Обновляем феромон
Дополнительные действия (опционально)

Теперь рассмотрим каждый шаг в цикле более подробно

Создаём муравьёв
- Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи. Потому что для каждой задачи способ размещение муравьёв является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.
- На этом же этапе задаётся начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.
Ищем решения
- Вероятность перехода из вершины i в вершину j определяется по следующей формуле $$P_{ij,k}(t) = \frac{[\tau_{ij}(t)]^{\alpha} \cdot [\eta_{ij}]^{\beta}}{\sum_{l \in J_{i,k}} [\tau_{il}(t)]^{\alpha} \cdot [\eta_{il}]^{\beta}}$ , где τ _ij(t) – уровень феромона, η_ij – эвристическое расстояние, α, β – константные параметры. Необходим компромисс между этими величинами (чтоб смягчать жадность алгоритма и не застревать в локальных минимумах), который находится экспериментально.
Обновляем феромон
- Уровень феромона обновляется в соответствии с приведённой формулой $$\tau_{ij}(t+1) = (1-\rho)\tau_{ij}(t)+\sum_{k \in \{used (i,j)\}}{\frac{Q}{L_k(t)}}$ , где ρ – интенсивность испарения, L_k(t) – цена текущего решения для k-ого муравья, а Q – параметр, имеющий значение порядка цены оптимального решения, то есть Q/L_k(t) - феромон, откладываемый k-ым муравьём, использующим ребро (i,j).
Дополнительные действия
- Обычно здесь используется алгоритм локального поиска, однако он может также появиться и после поиска всех решений.

Результаты экспериментов

По сравнению с точными методами, например динамическим программированием или методом ветвей и границ, муравьиный алгоритм находит близкие к оптимуму решения за значительно меньшее время даже для задач большой размерности (n > 20). В табл. 1 из [2] сравниваются три метода оптимизации маршрутов грузовиков для задач большой размерности. Время решения задач пересчитано для компьютера с процессором Pentiumm - 900MHz. Полужирным шрифтом выделены наилучшие на сегодняшний день решения.