Метод роя частиц (МРЧ) — метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции.
МРЧ был изначально предложен Кеннеди, Эберхартом и Ши для имитации социального поведения. После упрощения алгоритма, было замечено, что он решает оптимизационную задачу. Книга Кеннеди и Эберхарта описывает многие философские аспекты МРЧ и так называемого роевого интеллекта. Обширное исследование приложений МРЧ сделано Поли. МРЧ оптимизирует функцию, поддерживая популяцию возможных решений, называемых частицами, и перемещая эти частицы в пространстве решений согласно простой формуле. Перемещения подчиняются принципу наилучшего найденного в этом пространстве положения, которое постоянно изменяется при нахождении частицами более выгодных положений.
Алгоритм Пусть — целевая функция, которую требуется минимизировать, — количество частиц в рое, каждой из которых сопоставлена координата в пространстве решений и скорость . Пусть также — лучшее из известных положений частицы с индексом , а — наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.
Для каждой частицы сделать: Сгенерировать начальное положение частицы с помощью случайного вектора , имеющего многомерное равномерное распределение, где и — нижняя и верхняя границы пространства решений соответственно. Присвоить лучшему известному положению частицы его начальное значение: . Если , то обновить наилучшее известное состояние роя: . Присвоить значение скорости частицы: . Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять: Для каждой частицы сделать: Сгенерировать случайные векторы . Обновить скорость частицы: , где операция означает покомпонентное умножение. Обновить положение частицы переносом на вектор скорости: . Этот шаг выполняется вне зависимости от улучшения значения целевой функции. Если , то: Обновить лучшее известное положение частицы: . Если , то обновить лучшее известное состояние роя в целом: . Теперь содержит лучшее из найденных решений.
Параметры , и выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований.
Подбор параметров Выбор оптимальных параметров метода роя частиц — тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта, Карлайла и Дозера, ван ден Берга, Клерка и Кеннеди, Трелеа, Браттона и Блеквэлла, а также Эверса.
Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.
Варианты алгоритма Постоянно предлагаются новые варианты алгоритма роя частиц для улучшения производительности метода. Существует несколько тенденций в этих исследованиях, одна из которых предлагает создать гибридный оптимизационный метод, использующий МРЧ в комбинации с иными алгоритмами, см. например. Другая тенденция предлагает каким-либо образом ускорить работу метода, например, отходом назад или переменой порядка движения частиц (об этом см.). Также есть попытки адаптировать поведенческие параметры МРЧ в процессе оптимизации.
См. также Алгоритм пчелиной колонии Роевой интеллект Многочастичный фильтр Derivative-free optimization
Примечания
Ссылки
Particle Swarm Central. Новости, люди, места, программы, статьи и др. В частности, см. текущий стандарт МРЧ. Ссылки на исходные коды реализаций алгоритмов МРЧ
Категория:Алгоритмы оптимизации Категория:Эвристические алгоритмы