Рой частиц

Оптимизация роя частиц

Кеннеди и Эберхарт предложили оптимизацию роя частиц (PSO). Этот метод вдохновлен социальным поведением животных, развивающихся стаями.

Первоначально они стремились смоделировать способность птиц летать синхронно и их способность внезапно менять направление, оставаясь при этом в оптимальном строю.

Частицы — это люди, и они движутся через поисковое гиперпространство на основе ограниченной информации:

  1. Каждая частица имеет память, которая позволяет ей запоминать лучшую точку, через которую она уже прошла, и стремится вернуться в эту точку.
  2. Каждой частице сообщается о наиболее известной точке в ее окрестности, и она будет стремиться к этой точке.

Таким образом, каждый человек использует не только свою собственную память, но и локальную информацию о своих ближайших соседях, чтобы принять решение о своем собственном движении. Простые правила, такие как: двигаться с той же скоростью, что и другие, двигаться в том же направлении или оставаться рядом с соседями, являются примерами поведения, которого достаточно для поддержания сплоченности стаи.

На движение частицы влияют три типа поведения:

  1. Физическая составляющая: частица стремится следовать своей траекторией;
  2. Когнитивный компонент: частица стремится вернуться на лучший участок, через который она уже прошла;
  3. Социальный компонент: частица стремится двигаться к лучшему месту, уже достигнутому ее соседями.

Алгоритм оптимизации роя частиц

В Рнет, частица i роя моделируется ее вектором положения xя = (хi1, …, Иксв) и его вектором скорости vя = (vi1, …, вв).

Эта частица сохраняет в памяти наилучшее положение, через которое она уже прошла, отмеченное п.я = (рi1, …, пв). Наилучшее положение, достигнутое всеми частицами роя, обозначается pграмм = (рg1, …, пролевая игра).

В момент времени t+1 вектор скорости вычисляется по формуле A:

Оптимизация роя частиц

с с1 так далее2 две константы, называемые коэффициентами ускорения; р1 и р2 два случайных числа, равномерно нарисованные в [0,1].

Три добавленных члена формулы объясняются следующим образом:

  • вij(t) соответствует физической составляющей смещения;
  • следующий член соответствует когнитивному компоненту движения с c1 который взвешивает тенденции частицы следовать своему инстинкту самосохранения и двигаться к лучшему известному положению;
  • последний термин соответствует социальной составляющей поездки. против2 контролирует социальные способности частицы, приближаясь к лучшему положению своих информаторов.

Положение частицы i определяется формулой B:

Оптимизация роя частиц

Псевдокод оптимизации роя частиц

Критерий остановки может быть различным в зависимости от поставленной задачи и требований пользователя. Если глобальный оптимум известен априори, допустимая ошибка может быть определена как критерий остановки. В противном случае можно зафиксировать максимальное количество итераций или максимальное количество оценок целевой функции.
Оптимизация роя частиц

Варианты

  • Наложение положительной и отрицательной максимальной скорости
  • Примените коэффициент инерции к первому члену формулы A -> Shi and Eberhart 1998.
  • Применение коэффициента ограничения в формуле A вместо констант -> Clerc and Kennedy 2002
  • Применение топологии соседства, чтобы узнать, с какой частицей я буду общаться → Кеннеди, 1999 г.
Делиться
ru_RURU
%d такие блоггеры, как: