[Перевод] Муравьиная оптимизация и сетевые алгоритмы
Как вы могли заметить, у нас тут затишье. Но наш творческий поиск не прекращается, и первая октябрьская публикация будет посвящена ACO (Ant Colony Optimization)
Отдавая должное автору, мы не будем публиковать здесь последнюю часть статьи, содержащую пример на JavaScript, а предложим вам опробовать его на сайте оригинала. Под катом же вы найдете перевод теоретической части, доступно рассказывающей о тонкостях муравьиной оптимизации в различных сценариях.
Оптимизация по алгоритму муравьиной колонии (ACO) была впервые предложена Марко Дориго в 1992 году. Эта техника оптимизации строится на основании той стратегии, которой придерживаются муравьи, прокладывая путь в поисках пищи. Кроме того, ACO — это частный случай роевого интеллекта. Роевой интеллект — это разновидность искусственного интеллекта, где для решения задач применяется децентрализованное коллективное поведение. Муравьиные алгоритмы шире всего применяются для комбинаторной оптимизации, например, при решении задачи коммивояжера, хотя они применимы и в качестве разнообразных решений в области планирования и маршрутизации.
Важное преимущество муравьиных алгоритмов по сравнению с другими алгоритмами оптимизации — это присущая им возможность адаптации к динамическим средам. Именно поэтому они столь незаменимы при сетевой маршрутизации, где обычны частые изменения, к которым приходится приспосабливаться.
Муравьи в природе
Чтобы полностью понять ACO, важно хорошо представлять себе поведение муравьев в природе, которое и послужило основой для алгоритма.
При поисках пищи муравьи следуют сравнительно простому набору правил. При всей простоте эти правила позволяют муравьям коммуницировать и совместно оптимизировать пути к добыче. Одно из основных свойств всех этих правил — это использование феромонных следов. Именно при помощи феромонов одни муравьи сообщают другим, где найдена пища, и как к ней попасть. Как правило, если муравей набредает на феромонный след, то может рассчитывать, что по нему он найдет пищу. Однако муравьи не бегут по первому попавшемуся феромонному следу. В зависимости от его пахучести муравей может отправиться по другой дорожке или вообще избрать случайный путь, где никакого феромона нет. В среднем же, чем сильнее пахнет феромонный след, тем вероятнее, что муравей решит на него свернуть.
Со временем феромонный след постепенно улетучивается, если другие муравьи не обновляют его. Таким образом, феромонные следы, не ведущие к еде, рано или поздно забрасываются, и муравьям приходится прокладывать новые маршруты к новым источникам пищи.
Чтобы понять, как этот процесс развивается со временем, и как колония оптимизирует собственное поведение, рассмотрим следующий пример:
Это путь, по которому муравей отправился к пище. С нашей точки зрения, этот путь явно не оптимален, хотя и возможен. Но здесь начинается самое интересное. Далее другие муравьи из той же колонии натыкаются на феромонный след первого. Большинство из них следуют по исходному маршруту, но некоторые избирают другой, более прямой путь:
Хотя первый феромонный след в данной точке может быть более пахуч, начинает развиваться и второй след — соответствующий той дорожке, на которую случайно сворачивают некоторые муравьи. В этом сценарии важно, что второй путь предпочтительнее, поскольку избравшие его насекомые добегут до пищи и достанут ее быстрее, чем муравьи, последовавшие по первому пути. Например, один муравей может потратить 3 минуты, чтобы добежать по первой дорожке от муравейника до источника пищи и обратно, но другой муравей за то же время пробежит по другому маршруту вдвое быстрее и, соответственно, успеет оставить там два феромонных следа. По этой причине краткий путь вскоре становится более пахучим, чем первый. Соответственно, первый след используется все реже, пока, наконец, не исчезает, а остается только новый, более короткий путь.
Именно по этой причине самые густые феромонные следы обычно откладываются по самым выгодным маршрутам, которые постепенно становятся предпочтительными для всех муравьев из данного муравейника.
Вкратце отметим, что это — упрощенная картина поведения муравьев в природе; кроме того, разные виды муравьев пользуются феромонами немного по-своему.
Алгоритм
В этой статье будет рассмотрено применение алгоритма ACO для решения задачи коммивояжера. Если вы пока не знакомы с сутью этой задачи, отсылаем вас к статье Applying a genetic algorithm to the traveling salesman problem.
Основная часть алгоритма ACO состоит всего из нескольких этапов. Во-первых, каждый муравей из колонии выстраивает решение, исходя из имеющихся феромонных следов. Далее муравьи оставляют следы по отрезкам выбранного маршрута, в зависимости от качества выработанного решения. В примере с задачей коммивояжера это были бы ребра (или отрезки пути между городами). Наконец, когда все муравьи завершат прокладку маршрута и феромонных следов, феромон начинает стабильно испаряться на каждом отрезке. Затем такая последовательность этапов многократно прогоняется до получения адекватного решения.
Разработка решения
Как было указано выше, при прокладке маршрута муравей обычно бежит по самому пахучему феромонному следу. Однако если муравей начинает рассматривать иные решения, кроме того, которое в данный момент считается оптимальным, то в процесс принятия решения привносится доля случайности. Вдобавок рассчитывается и учитывается эвристическая ценность решений, благодаря чему поиск развивается в сторону оптимальных вариантов. В примере с задачей коммивояжера эвристика обычно связана с длиной ребра до следующего города, в который планируется попасть. Чем короче ребро, тем вероятнее, что маршрут продолжится по нему.
Рассмотрим, как это реализуется математически:
В данном уравнении вычисляется вероятность выбора конкретного компонента решения. Здесь tij означает количество феромона на отрезке между состояниями i и j, а nij — его эвристическую ценность. α и β — параметры, при помощи которых контролируется важность феромонного следа и эвристическая информация при выборе компонента.
В коде эту информацию принято выражать как выбор в стиле рулеточного алгоритма:
rouletteWheel = 0
states = ant.getUnvisitedStates()
for newState in states do
rouletteWheel += Math.pow(getPheromone(state, newState), getParam('alpha'))
* Math.pow(calcHeuristicValue(state, newState), getParam('beta'))
end for
randomValue = random()
wheelPosition = 0
for newState in states do
wheelPosition += Math.pow(getPheromone(state, newState), getParam('alpha'))
* Math.pow(calcHeuristicValue(state, newState), getParam('beta'))
if wheelPosition >= randomValue do
return newState
end for
В контексте задачи коммивояжера состояние соответствует конкретному городу в графе. В нашем случае муравей будет выбирать следующий пункт в зависимости от расстояния, которое придется преодолеть, и от количества феромона на данном отрезке.
Локальное обновление феромона
Процесс локального обновления феромона задействуется всякий раз, когда муравей получает успешное решение. Данный шаг имитирует прокладку феромонных следов, оставляемых муравьями в природе на пути к пище. Как вы помните из вышесказанного, в природе наиболее успешные маршруты получают больше всего феромонов, поскольку преодолеваются муравьями быстрее. В ACO эта характеристика воспроизводится так: количество феромона на отрезке пути будет варьироваться в зависимости от того, насколько успешно то или иное решение. Если взять для примера задачу коммивояжера, то феромон откладывался бы на дорогах между городами в зависимости от общей дистанции.
На схеме показаны феромонные следы, оставляемые на отрезках между точками («городами») в типичной задаче коммивояжера.
Прежде чем рассмотреть реализацию в коде, обратимся к математике:
Здесь Ck определяется как общая стоимость решения, в задаче коммивояжера это была бы общая длина пути. Q — просто параметр, помогающий откорректировать количество оставляемого феромона, обычно он задается равным 1. Мы суммируем Q/Ck для каждого решения, использовавшего компонент(i, j), затем это значение принимается за количество феромона, которое будет оставлено на компонент(i, j).
Чтобы прояснить ситуацию, давайте рассмотрим простой пример данного процесса применительно к задаче коммивояжера…
Здесь мы имеем типичный граф из задачи коммивояжера и хотим рассчитать, сколько феромона должно быть на отрезке A. Предположим, что по этому ребру при прокладке маршрутов прошли три муравья. Также допустим, что общие длины трех маршрутов получились такими:
Tour 1: 450
Tour 2: 380
Tour 1: 460
Чтобы вычислить, сколько феромона должно быть на каждом из них, просто суммируем:
componentNewPheromone = (Q / 450) + (Q / 380) + (Q / 460)
Затем приплюсуем это значение к имеющемуся значению феромона на отрезке:
componentPheromone = componentPheromone + componentNewPheromone
Теперь — простой пример с кодом:
for ant in colony do
tour = ant.getTour();
pheromoneToAdd = getParam('Q') / tour.distance();
for cityIndex in tour do
if lastCity(cityIndex) do
edge = getEdge(cityIndex, 0)
else do
edge = getEdge(cityIndex, cityIndex+1)
end if
currentPheromone = edge.getPheromone();
edge.setPheromone(currentPheromone + pheromoneToAdd)
end for
end for
В данном примере мы просто перебираем маршруты всей колонии, извлекая каждый маршрут и применяя феромонное значение к каждому ребру маршрута.
Глобальное обновление феромона
Глобальное обновление феромона — это этап, на котором феромон улетучивается с отрезков пути. Данный этап применяется после каждой итерации алгоритма, когда каждый муравей успешно выстроил маршрут и применил правило локального обновления.
Глобальное обновление феромона математически описывается так:
τij←(1−ρ)⋅τij
где τij – это феромон на отрезке, пролегающем между состояниями i и j, а ρ – параметр, при помощи которого корректируется скорость улетучивания.
В коде ситуацию можно представить так:
for edge in edges
updatedPheromone = (1 - getParam('rho')) * edge.getPheromone()
edge.setPheromone(updatedPheromone)
end for
Оптимизация
Алгоритм ACO допускает много вариантов оптимизации, важнейшие из которых — элитарная (elitist) и MaxMin. В зависимости от задачи эти вариации вполне могут оказаться более работоспособными, чем стандартная система ACO, рассмотренная выше. К счастью, нам не составит труда расширить алгоритм так, чтобы он учитывал две эти модификации.
Элитарная разновидность
В элитарных ACO-системах наиболее успешная вереница муравьев, а также наиболее результативный муравей из всех на этапе локального обновления оставляют чуть больше феромона, чем все остальные. Поэтому колония адаптирует принимаемые решения по образцу тех, которые обладают наилучшей историей достижений. Если все идет нормально, то качество поиска при этом повышается.
С математической точки зрения элитарная процедура локального обновления практически аналогична обычной, с одним небольшим дополнением:
Где e — параметр, используемый для коррекции дополнительного объема феромона, откладываемого при наилучшем (или «элитарном») решении.
MaxMin
Алгоритм MaxMin напоминает элитарный вариант ACO в том, что отдает приоритет «высокорейтинговым» решениям. Однако MaxMin не просто присваивает дополнительный вес элитарным решениям, но разрешает оставлять феромонный след лишь самой работоспособной веренице, соответствующей наилучшему глобальному решению. Кроме того, MaxMin требует, чтобы феромонные следы укладывались в диапазоне между определенным минимальным и максимальным значением. В основе алгоритма лежит идея о том, что если количество феромона на любой конкретной дорожке относится к определенному диапазону, то удастся избежать преждевременного схождения на неоптимальных решениях.
Во многих реализациях MaxMin наиболее успешным считается тот муравей, который оставляет феромонные следы. Затем этот алгоритм видоизменяется таким образом, что возможность оставлять след сохраняется только у «глобально» лучшего муравья. Этот процесс стимулирует такой поиск, который изначально распределен по всему имеющемуся пространству, но впоследствии сосредотачивается на оптимальных маршрутах, допуская, возможно, минимальные поправки.
Наконец, минимальное и максимальное значение можно либо передавать в виде параметров, либо адаптивно устанавливать в коде.
Интересное практическое решение TSP на JavaScript — на сайте автора
