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

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

Метод роя частиц (МРЧ) — метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[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]. Другая тенденция предлагает каким-либо образом ускорить работу метода, например, отходом назад или переменой порядка движения частиц (об этом см. [18] [19] [13]). Также есть попытки адаптировать поведенческие параметры МРЧ в процессе оптимизации [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. ↑ Swarm Intelligence. — Morgan Kaufmann, 2001.
  4. ↑ Poli, R. (2007). «An analysis of publications on particle swarm optimisation applications». Technical Report CSM-469 (Department of Computer Science, University of Essex, UK).
  5. ↑ Poli, R. (2008). «Analysis of the publications on the applications of particle swarm optimisation». Journal of Artificial Evolution and Applications: 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. ↑ (2002) «The particle swarm - explosion, stability, and convergence in a multidimensional complex space». IEEE Transactions on Evolutionary Computation 6 (1): 58-73.
  11. ↑ Trelea, I.C. (2003). «The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection». Information Processing Letters 85: 317-325.
  12. ↑ (2008) «A Simplified Recombinant PSO». Journal of Artificial Evolution and Applications.
  13. ↑ 1 2 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.
  15. ↑ Pedersen, M.E.H.; Chipperfield, A.J. (2010). «Simplifying particle swarm optimization». Applied Soft Computing 10: 618-628.
  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. ↑ (2010) «An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis». Applied Soft Computing 10 (1): 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. (2010). «A perturbed particle swarm algorithm for numerical optimization». Applied Soft Computing 10 (1): 119-124.
  20. ↑ (2009) «Adaptive Particle Swarm Optimization». IEEE Transactions on Systems, Man, and Cybernetics 39 (6): 1362-1381.

Ссылки

 Просмотр этого шаблона Методы оптимизации
Одномерные Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск
Прямые методы Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка
Первого порядка Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта
Второго порядка Метод Ньютона • Метод Ньютона — Рафсона
Стохастические Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц
Методы линейного
программирования		 Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов
Методы нелинейного
программирования		 Последовательное квадратичное программирование

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Полезное


Смотреть что такое "Метод роя частиц" в других словарях:

  • Метод Ньютона — Метод Ньютона, алгоритм Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном… …   Википедия

  • Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… …   Википедия

  • Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия …   Википедия

  • Метод Хука — Дживса (англ. Hooke  Jeeves), также как и алгоритм Нелдера Мида, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две… …   Википедия

  • Метод потенциалов — является модификацией симплекс метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Содержание… …   Википедия

  • Метод Гаусса (оптимизация) — У этого термина существуют и другие значения, см. Метод Гаусса. Метод Гаусса[1] прямой метод решения задач многомерной оптимизации. Содержание 1 Описание 2 Примечания …   Википедия

  • Метод Нелдера — …   Википедия

  • Метод перебора — У этого термина существуют и другие значения, см. Перебор. Метод перебора (метод равномерного поиска)  простейший из методов поиска значений действительно значных функций по какому либо из критериев сравнения (на максимум, на минимум, на… …   Википедия

  • Симплекс-метод — Не путать с «симплекс методом»  методом оптимизации произвольной функции. См. Метод Нелдера Мида Симплекс метод  алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в… …   Википедия

  • Разложение Данцига-Вулфа — Метод декомпозиции Данцига и Вульфа представляет собой специализированный вариант симплекс метода. В 1960 г. Данциг и Вульф разработали метод декомпозиции для решения задач высокой размерности со специальной структурой матрицы ограничений [1].… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»