Алгоритмы роя частиц (PSO) и муравьиные колонии (ACO) в численной оптимизации

Коллективный интеллект на службе математики

В области глобальной стохастической оптимизации генетические алгоритмы (ГА) и дифференциальная эволюция (DE), основанные на теории естественного отбора, десятилетиями удерживали лидерство. Однако в конце 1990-х годов возникла мощная альтернативная парадигма эвристического поиска, вдохновленная не эволюцией видов, а социальным поведением животных. Как стая птиц находит лучшее место для кормежки в огромном лесу? Как муравьи без единого лидера строят оптимальные кратчайшие маршруты от муравейника к источнику пищи? Оказалось, что математическая формализация этих природных механизмов дает потрясающе быстрые численные алгоритмы оптимизации сложных недифференцируемых функций.

Этот класс алгоритмов получил название Swarm Intelligence (Роевой интеллект). В отличие от генетических алгоритмов, где особи (решения) безжалостно уничтожаются и заменяются мутантами (дарвиновская философия), в алгоритмах роевого интеллекта элементы популяции не умирают. Они сохраняют свою жизнь на протяжении всего процесса вычислений, перемещаясь в пространстве параметров и обмениваясь социальной информацией со своими соседями. Эта кооперативная природа алгоритмов делает их сходимость более плавной и управляемой.

Оптимизация роем частиц (Particle Swarm Optimization, PSO)

Алгоритм PSO был разработан в 1995 году Кеннеди и Эберхартом. Пространство поиска заполняется «частицами» (математическими векторами возможных решений). Каждая частица имеет свою координату и вектор скорости. На каждом шаге частица оценивает значение целевой функции в своей точке. Направление ее следующего шага (новая скорость) вычисляется как векторная сумма трех составляющих.

Первая составляющая — инерция: частица склонна двигаться туда, куда летела на предыдущем шаге. Вторая составляющая — личная (когнитивная) память: частица всегда помнит ту точку пространства, где она лично находила наилучший результат (наименьший минимум), и ее притягивает к этой точке. Третья составляющая — социальный опыт: частицу притягивает к той точке, которая является наилучшей среди всей стаи (глобальный лидер). Коэффициенты доверия к себе и к социуму являются настроечными параметрами. В результате этого простого математического взаимодействия частиц возникает невероятно сложный и целенаправленный танец роя, который быстро стягивается в самые глубокие минимумы сложных ландшафтов (функций Розенброка, Растригина и др.). PSO превосходно подходит для настройки весов в системах управления и проектирования СВЧ-антенн.

Муравьиные алгоритмы (Ant Colony Optimization, ACO)

Если PSO отлично работает в непрерывных пространствах, то для сложнейших задач дискретной комбинаторной оптимизации (например, задача коммивояжера, разводка печатных плат, маршрутизация пакетов в интернете) Марко Дориго в 1992 году создал Муравьиные алгоритмы (ACO). Идея заимствована из механизма стигмергии: непрямой коммуникации муравьев через отложение химических следов (феромонов).

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