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

В этом разделе мы представляем основу концепции метаэвристики оптимизации методом роя частиц (ОМРЧ).

Оптимизация методом роя частиц [KEN 95] происходит по аналогии с коллективным поведением передвижений животных. В некоторых группах животных, таких как стаи рыб или стаи птиц, мы можем наблюдать относительно сложную динамику движения, в то время как сами индивиды имеют доступ только к ограниченной информации, такой как положение и скорость их ближайших соседей.

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

Авторы оптимизации методом роя частиц были вдохновлены такой моделью внедрения социально-психологической теории в перспективу обработки информации и принятия решений в социальных группах. Способ включает в себя большие группы частиц в виде векторов, движущихся в пространстве поиска. Каждая частица / характеризуется своей позицией 5с,- и вектором с изменяемой позицией (называемым скоростью) Vj. При каждой итерации частица движется. Скорость обновляется на основе социально-когнитивной карты роя. Смещение частиц регулируется их поведением в прошлом и поведением их соседей (соседей в социальной сети и не обязательно в пространстве). Во время обновления учитываются положение частиц и направление их перемещения (их скорости), лучшее предыдущее положение р, и лучшее положение pg среди соседей. Изменение положения заключается в следующем:

где параметры ср,, ср2 являются переменным из U[0, фтах], которые оценивают относительную роль индивидуального опыта (ср,) и социальной коммуникации (ср2). Случайные величины и г2 принимают значения в интервале [0, 1].

Для предотвращения слишком быстрого движения частиц из одной области пространства поиска в другую скорость ограничена Утах в каждом измерении.

Псевдокод для самой общей версии представлен в алгоритме 4.2. Улучшения были направлены на основной алгоритм, особенно в плане контроля сходимости. В базовой версии параметр Утах запрещает системе слишком много колебаться в пространстве поиска. Использование коэффициентов сходимости помогает лучше управлять этим процессом [CLE 02]. В тех же целях другая версия реализует вес инерции путем умножения скорости на этот коэффициент. В итоге вес инерции уменьшается с течением времени, в результате чего конвергенция контролируется этим параметром. Диапазон движения частиц уменьшается до тех пор, пока совсем не исчезнет.

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

Алгоритм 4.2. Оптимизация методом роя частиц [1] [2]}

152 Системы мультимодальных перевозок Повторить

Для каждой частицы / выполняется

— Обновление позиции Зс,- в соответствии с уравнениями (4.1) и (4.2); Если /(*,) < Да) то

Pi ?= Ч Конец если Если f(pi) < f(pg) то

Pg Pi>

Конец если Конец для

_До тех пор, пока не будет достигнут критерий остановки._

  • [1] Для каждой частицы / выполняется — Случайная инициализация текущего положения х,; — Инициализация лучшего положения для частицы р, по его текущей позиции X/ Pi ?= Xj — Случайная инициализация каждого параметра V,- в пределах максимума Г -V V I
  • [2] max’ maxJ — Обновление наилучшее положение в непосредственной близости от частицы pg := argmin{f(pj)
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >