Алгоритм PSO (называемый также методом роя частиц) первоначально был описан применительно к задачам математической биологии в 1987 г. [1]. Сведения об алгоритмах и результатах решения с помощью методов PSO ряда задач оптимизации приведены, например, в [2,3].
В методе PSO (Particles Swarm Optimization) имитируется поведение множества агентов, стремящихся согласовать свое состояние с состоянием наилучшего агента. Положение -го агента описывается вектором Xj=(,,…), где -й параметр -го агента, а состояние -го агента характеризуется значением целевой функции =(Xj). Согласование происходит в многошаговом процессе путем корректировки на каждом шаге вектора Xj с учетом положения Xgl наилучшего агента, собственного наилучшего положения X*j на траектории предыдущего перемещения -го агента в пространстве параметров и фактора случайности.
Базовый алгоритм PSO в случае задачи непрерывной оптимизации заключается в итерационном вычислении значений Xj по формулам:
Vj := Vj + (XglXj) + (X*jXj), (1)
Xj := Xj +Vj;
где Vj – вектор корректировок -го агента, – коэффициент инерционности в поведении агентов, , – случайные коэффициенты, параметры распределения которых подбираются экспериментально.
В задачах дискретной оптимизации пространство параметров часто оказывается неметризованным и формула (1) оказывается неприменимой. Однако использование идей PSO становится возможным, благодаря следующему способу выбора дискретных значений генов: ген в формируемой хромосоме Xj выбирается равным -му гену одной из хромосом-родителей. Выбор конкретного родителя происходит случайным образом. В качестве хромосомы-родителя могут выступать или наилучшая хромосома Xgl всей популяции, или хромосома X*j, наилучшая среди хромосом с номером всех предшествующих поколений, или -я хромосома Xj предыдущего поколения. Соответствующие вероятности , , выбора каждого из этих вариантов подбираются экспериментально. Кроме того, добавляется вариант случайного выбора значения с вероятностью .
Список литературы
1. Deneubourg J.-L., Goss S., Pasteels J.M., Fresneau D. and Lachaud J.-P. Self-organization mechanisms in ant societies (II): learning in foraging and division of labor. In: From Individual to Collective. Behavior in Social Insects. — Basel: Birkhauser, 1987.
2. Eberhart, R. C., and Kennedy, J. A New Optimizer Using Particles Swarm Theory, Proc. Sixth International Symposium on Micro Machine and Human Science. // IEEE Service Center, Piscataway, 1995.
3. Eberhart, R. C., Dobbins, R. W., and Simpson, P. Computational Intelligence PC Tools. — Boston: Academic Press , 1996.