Сумбурное описание алгоритма роя частиц

В последнее время я готовлю статейку для выкладывания на сайт про метод оптимизации, который называется метод роя частиц. И пока я думал, как этот алгоритм можно описать на пальцах или каких-то жизненных аналогиях, то воспаленный мозг родил вот такое описание. Я что-то сомневаюсь, что его стоит включать в конечный вариант статьи, но пусть он останется хотя бы здесь для истории.

Чтобы понять алгоритм роя частиц, представте себе большую поляну с земляникой (это наша область поиска решения), и нам надо найти то место на поляне, где земляники больше всего (глобальный экстремум). Будем считать, что сама земляника не кончается, и при съедении ягоды, она вырастает снова. Теперь представьте себе, что по этой поляне случайным образом (с вертолета) разбросали бабушек-собирателей земляники (агентов алгоритма). Сначала каждая бабушка идет в случайном направлении и с каждым шагом замечают, сколько земляники находится вокруг нее. Но с каждым новым шагом скорость и направление движения бабушки изменяют так, чтобы с одной стороны направиться в ту сторону, где она сама видела больше всего земляники (авторы алгоритма назвали этот аспект поведения «ностальгией»), а с другой — старается приблизиться к наилучшей области с наибольшим числом земляники, найденной среди всех бабушек (глобальное лучшее значение). В идеале через некоторое количество шагов все бабушки должны собраться в одной области с наибольшим числом земляники. В реальности кто-то может остаться в области, достаточно хорошей, но не в глобально лучшей, но главное, чтобы глобальный экстремум был найден хотя бы одной бабушкой.

Ну и, если этот ужас вы дочитали до конца, то в качестве компенсации вот вам анимация, иллюстрирующая работу алгоритма роя бабушек частиц.

particleswarm

UPD: После написания поста родилась еще одна аналогия — с тараканами на грязном столе. Но не будем развивать эту идею. 🙂

Вы можете подписаться на новости сайта через RSS, Группу Вконтакте или Канал в Telegram.

Пожалуйста, оцените запись

УжасноПлохоТак себеХорошоОтлично (Нет оценок)
Загрузка...

комментария 3

  1. ks1v:

    ждем более детальную статью)

  2. Денис Сепетов:

    Весьма забавная аналогия (с тараканами, между прочим, тоже).

    Жду подробной статьи 🙂 Спасибо!

  3. Jenyay:

    Уффф. Дописал нормальную статью — http://jenyay.net/Programming/ParticleSwarm

Leave a comment

Subscribe without commenting