Метод роя частиц (МРЧ) — метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции.
МРЧ был изначально предложен Кеннеди, Эберхартом и Ши[1][2] для имитации социального поведения. После упрощения алгоритма, было замечено, что он решает оптимизационную задачу. Книга Кеннеди и Эберхарта[3] описывает многие философские аспекты МРЧ и так называемого роевого интеллекта. Обширное исследование приложений МРЧ сделано Поли[4][5].
МРЧ оптимизирует функцию, поддерживая популяцию возможных решений, называемых частицами, и перемещая эти частицы в пространстве решений согласно простой формуле. Перемещения подчиняются принципу наилучшего найденного в этом пространстве положения, которое постоянно изменяется при нахождении частицами более выгодных положений.
Пусть — целевая функция, которую требуется минимизировать, — количество частиц в рое, каждой из которых сопоставлена координата в пространстве решений и скорость . Пусть также — лучшее из известных положений частицы с индексом , а — наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.
Для каждой частицы сделать:
Сгенерировать начальное положение частицы с помощью случайного вектора , имеющего многомерное равномерное распределение, где и — нижняя и верхняя границы пространства решений соответственно.
Присвоить лучшему известному положению частицы его начальное значение: .
Если , то обновить наилучшее известное состояние роя: .
Присвоить значение скорости частицы: .
Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
Обновить положение частицы переносом на вектор скорости: . Этот шаг выполняется вне зависимости от улучшения значения целевой функции.
Если , то:
Обновить лучшее известное положение частицы: .
Если , то обновить лучшее известное состояние роя в целом: .
Теперь содержит лучшее из найденных решений.
Параметры , и выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований➤.
Подбор параметров
Выбор оптимальных параметров метода роя частиц — тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта[6][7], Карлайла и Дозера[8], ван ден Берга[9], Клерка и Кеннеди[10], Трелеа[11], Браттона и Блеквэлла[12], а также Эверса[13].
Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами[14][15]. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.
Варианты алгоритма
Постоянно предлагаются новые варианты алгоритма роя частиц для улучшения производительности метода. Существует несколько тенденций в этих исследованиях, одна из которых предлагает создать гибридный оптимизационный метод, использующий МРЧ в комбинации с иными алгоритмами, см. например[16][17]. Другая тенденция предлагает каким-либо образом ускорить работу метода, например, отходом назад или переменой порядка движения частиц (об этом см.[13][18][19]). Также есть попытки адаптировать поведенческие параметры МРЧ в процессе оптимизации[20].
↑
Kennedy, J.; Eberhart, R. (1995). "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks. Vol. IV. pp. 1942—1948.
↑
Shi, Y.; Eberhart, R.C. (1998). "A modified particle swarm optimizer". Proceedings of IEEE International Conference on Evolutionary Computation. pp. 69—73.
↑
Shi, Y.; Eberhart, R.C. (1998). "Parameter selection in particle swarm optimization". Proceedings of Evolutionary Programming VII (EP98). pp. 591—600.
↑
Eberhart, R.C.; Shi, Y. (2000). "Comparing inertia weights and constriction factors in particle swarm optimization". Proceedings of the Congress on Evolutionary Computation. Vol. 1. pp. 84—88.
↑
Carlisle, A.; Dozier, G. (2001). "An Off-The-Shelf PSO". Proceedings of the Particle Swarm Optimization Workshop. pp. 1—6.
↑van den Bergh, F. An Analysis of Particle Swarm Optimizers (неопр.). — University of Pretoria, Faculty of Natural and Agricultural Science, 2001.
↑Clerc, M.; Kennedy, J. The particle swarm - explosion, stability, and convergence in a multidimensional complex space (англ.) // IEEE Transactions on Evolutionary Computation[англ.] : journal. — 2002. — Vol. 6, no. 1. — P. 58—73.
↑Trelea, I.C. The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection (англ.) // Information Processing Letters[англ.] : journal. — 2003. — Vol. 85. — P. 317—325.
↑Bratton, D.; Blackwell, T. A Simplified Recombinant PSO (неопр.) // Journal of Artificial Evolution and Applications. — 2008.
↑
Lovbjerg, M.; Krink, T. (2002). "The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers". Proceedings of Parallel Problem Solving from Nature VII (PPSN). pp. 621—630.
↑Niknam, T.; Amiri, B. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis (англ.) // Applied Soft Computing : journal. — 2010. — Vol. 10, no. 1. — P. 183—197.
↑
Lovbjerg, M.; Krink, T. (2002). "Extending Particle Swarm Optimisers with Self-Organized Criticality". Proceedings of the Fourth Congress on Evolutionary Computation (CEC). Vol. 2. pp. 1588—1593.
↑Xinchao, Z. A perturbed particle swarm algorithm for numerical optimization (неопр.) // Applied Soft Computing. — 2010. — Т. 10, № 1. — С. 119—124.
↑Zhan, Z-H.; Zhang, J.; Li, Y; Chung, H.S-H. Adaptive Particle Swarm Optimization (неопр.) // IEEE Transactions on Systems, Man, and Cybernetics. — 2009. — Т. 39, № 6. — С. 1362—1381.