Метод роя частиц

Метод роя частиц (МРЧ) — метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции.

Рой частиц, ищущий глобальный минимум функции

МРЧ был доказан Кеннеди, Эберхартом и Ши[1][2] и изначально предназначался для имитации социального поведения. Алгоритм был упрощён, и было замечено, что он пригоден для выполнения оптимизации. Книга Кеннеди и Эберхарта[3] описывает многие философские аспекты МРЧ и так называемого роевого интеллекта. Обширное исследование приложений МРЧ сделано Поли[4][5]. МРЧ оптимизирует функцию, поддерживая популяцию возможных решений, называемых частицами, и перемещая эти частицы в пространстве решений согласно простой формуле. Перемещения подчиняются принципу наилучшего найденного в этом пространстве положения, которое постоянно изменяется при нахождении частицами более выгодных положений.

Алгоритм

Пусть f: ℝn → ℝ — целевая функция, которую требуется минимизировать, S — количество частиц в рое, каждой из которых сопоставлена координата xi ∈ ℝn в пространстве решений и скорость vi ∈ ℝn. Пусть также pi — лучшее из известных положений частицы i, а g — наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.

  • Для каждой частицы i = 1, …, S сделать:
    • Сгенерировать начальное положение частицы с помощью случайного вектора xi ~ U(blo, bup), имеющего многомерное равномерное распределение. blo и bup — нижняя и верхняя границы пространства решений соответственно.
    • Присвоить лучшему известному положению частицы его начальное значение: pi ← xi.
    • Если (f(pi) < f(g)), то обновить наилучшее известное состояние роя: g ← pi.
    • Присвоить значение скорости частицы: vi ~ U(-(bup-blo), (bup-blo)).
  • Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
    • Для каждой частицы i = 1, …, S сделать:
      • Сгенерировать случайные векторы rp, rg ~ U(0,1).
      • Обновить скорость частицы: vi ← ω vi + φp rp × (pi-xi) + φg rg × (g-xi), где операция × означает покомпонентное умножение.
      • Обновить положение частицы переносом xi на вектор скорости: xi ← xi + vi. Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.
      • Если (f(xi) < f(pi)), то делать:
        • Обновить лучшее известное положение частицы: pi ← xi.
        • Если (f(pi) < f(g)), то обновить лучшее известное состояние роя в целом: g ← pi.
  • Теперь g содержит лучшее из найденных решений.

Параметры ω, φp, и φg выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований (см. ниже).

Подбор параметров

Выбор оптимальных параметров метода роя частиц — тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта[6][7], Карлайла и Дозера[8], ван ден Берга[9], Клерка и Кеннеди[10], Трелеа[11], Браттона и Блеквэлла[12], а также Эверса[13].

Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами.[14][15] Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.

Варианты алгоритма

Постоянно предлагаются новые варианты алгоритма роя частиц для улучшения производительности метода. Существует несколько тенденций в этих исследованиях, одна из которых предлагает создать гибридный оптимизационный метод, использующий МРЧ в комбинации с иными алгоритмами, см. например[16][17]. Другая тенденция предлагает каким-либо образом ускорить работу метода, например, отходом назад или переменой порядка движения частиц (об этом см.[13][18][19]). Также есть попытки адаптировать поведенческие параметры МРЧ в процессе оптимизации[20].

См. также

Примечания
  1. (1995) «Particle Swarm Optimization». Proceedings of IEEE International Conference on Neural Networks IV: 1942-1948.
  2. (1998) «A modified particle swarm optimizer». Proceedings of IEEE International Conference on Evolutionary Computation: 69-73.
  3. Kennedy, J.; Eberhart, R.C. Swarm Intelligence (неопр.). — Morgan Kaufmann, 2001. — ISBN 1-55860-595-9.
  4. Poli, R. An analysis of publications on particle swarm optimisation applications (англ.) // Technical Report CSM-469 : journal. — Department of Computer Science, University of Essex, UK, 2007. Архивировано 16 июля 2011 года.
  5. Poli, R. Analysis of the publications on the applications of particle swarm optimisation (англ.) // Journal of Artificial Evolution and Applications : journal. — 2008. — P. 1—10. — doi:10.1155/2008/685175.
  6. (1998) «Parameter selection in particle swarm optimization». Proceedings of Evolutionary Programming VII (EP98): 591-600.
  7. (2000) «Comparing inertia weights and constriction factors in particle swarm optimization». Proceedings of the Congress on Evolutionary Computation 1: 84-88.
  8. (2001) «An Off-The-Shelf PSO». Proceedings of the Particle Swarm Optimization Workshop: 1-6.
  9. van den Bergh, F. An Analysis of Particle Swarm Optimizers (неопр.). — University of Pretoria, Faculty of Natural and Agricultural Science, 2001.
  10. 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.
  11. Trelea, I.C. The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection (англ.) // Information Processing Letters : journal. — 2003. — Vol. 85. — P. 317—325.
  12. Bratton, D.; Blackwell, T. A Simplified Recombinant PSO (неопр.) // Journal of Artificial Evolution and Applications. — 2008.
  13. Evers, G. An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization (англ.). — The University of Texas - Pan American, Department of Electrical Engineering, 2009.
  14. Pedersen, M.E.H. Tuning & Simplifying Heuristical Optimization (англ.). — University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group, 2010. Архивированная копия (недоступная ссылка). Дата обращения: 3 июня 2010. Архивировано 26 июля 2011 года.
  15. Pedersen, M.E.H.; Chipperfield, A.J. Simplifying particle swarm optimization (неопр.) // Applied Soft Computing. — 2010. — Т. 10. — С. 618—628. Архивировано 24 января 2014 года.
  16. (2002) «The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers». Proceedings of Parallel Problem Solving from Nature VII (PPSN): 621-630.
  17. 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.
  18. (2002) «Extending Particle Swarm Optimisers with Self-Organized Criticality». Proceedings of the Fourth Congress on Evolutionary Computation (CEC) 2: 1588-1593.
  19. Xinchao, Z. A perturbed particle swarm algorithm for numerical optimization (неопр.) // Applied Soft Computing. — 2010. — Т. 10, № 1. — С. 119—124.
  20. 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.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.