Алгоритмы роевого интеллекта. Алгоритм роя частиц.

Стая птиц представляет собой прекрасный пример коллективного пове­дения животных. Летая большими группами, они почти никогда не сталки­ваются в воздухе. Стая двигается плавно и скоординированно, словно ею кто- то управляет. А любой, кто вешал в своем дворе скворечник, знает, что спус­тя несколько часов его найдут все птицы в округе.

Дело тут отнюдь не в вожаке, отдающем приказы, - в стаях многих ви­дов птиц его просто нет. Как и колония Муравьёв или пчёл, стая представляет собой роевой интеллект. Птицы в ней действуют согласно определенным - довольно простым - правилам. Кружа в небе, каждая из птиц следит за свои­ми сородичами и координирует свое движение согласно их положению, а найдя источник пищи, она оповещает их об этом.

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

Классический алгоритм роя частиц. Алгоритм моделирует многоагентную систему, где аген­ты-частицы двигаются к оптимальным решениям, обмениваясь при этом ин­формацией с соседями.

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

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

 

Метод пчелиной колонии

Для описания поведения пчёл в природе используются три основ­ных понятия: источник нектара (цветок), занятые фуражиры, незанятые фуражиры.

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

Занятые фуражиры закреплены за отдельным источником, на кото­ром они добывают нектар, то есть они “заняты” им. Занятые фуражиры владеют такой информацией о данном источнике нектара, как: расстояние и направление от улья, полезность источника.

Незанятые фуражиры продолжают искать источники нектара для их использования. Существует два типа незанятых фуражиров: разведчи­ки, которые ищут новые источники нектара, и наблюдатели, которые ждут в улье и могут выполнять другие действия в улье.

Среднее количество разведчиков в рое составляет 5-10%.

Несмотря на коллективный характер поведения общественных на­секомых и на разные схемы этого поведения, отдельное насекомое также способно выполнять различные сложные действия, примером чего мо­гут служить сбор и обработка нектара пчёлами, выполнение которых хо­рошо организовано.

Одной из часто возникающих задач в процессе моделирования сложных объектов и систем является нахождение глобального оптимума многомерной функции. Для решения это задачи применяется ряд методов (например, метод Коши, Ньютона, Левенберга-Марквардта и т.п.), кото­рые, однако, требуют непрерывности, дифференцируемости и унимодаль­ ности целевых функций. Поэтому предлагается применять метод пчели­ной колонии для решения задачи оптимизации многомерной функции.

Работу алгоритма можно представить в виде следующих шагов:

1. Задаются начальные параметры работы метода. В случае использования локальной оптимизации задаётся один из традиционных методов локальной оптимизации, который будет использоваться, и задаётся класс агентов, для решения которых бу­дет применяться локальная оптимизация - агент с лучшим решением или агенты, выполнившие моделирование виляющего танца.

2. Создаются начальные агенты-разведчики.

a) Для каждого начального агента-разведчика создаётся слу­чайное решение:

b) Для полученных случайных решений рассчитывается по­лезность данного источника нектара как значение оптимизируемой функ­ции.

3. Выбираются рабочие агенты, т.е. такие агенты, на базе ко­торых будут создаваться новые агенты с помощью процедуры скрещива­ния.

a) Определяется агент c наибольшей полезностью.

b) Процедура имитации отжига.

4. Скрещивание. Поскольку реальные пчёлы-разведчики при выборе источника нектара пользуются также генетическим материалом (в биологии ещё не изучено, каким именно образом разведчики выбирают одни цветки и пропускают другие, то есть предполагается, что разведчики основываются на генетическом опыте), то с помощью процедуры скрещи­вания моделируется именно этот момент поведения пчёл. Для скрещива­ния используются ранее отобранные с помощью процедуры имитации отжига рабочие агенты workBee и лучший агент за все итерации best. Но­вые агенты создаются в два этапа. на базе решений рабочих агентов и на базе решения лучшего агента.

a) Создание новых агентов на базе рабочих агентов

b) Создание новых агентов на базе лучшего агента

c) Для всех новых агентов производится корректировка по­лученных решений.

d) Рассчитывается полезность полученных решений:

e) Выбирается новый лучший агент.

5. Моделирование выполнения виляющего танца. К возмож­ному выполнению танца допускаются рабочие агенты workBee, агенты, созданные путём скрещивания, newWorkBee, лучший агент за все итера­ции best. Моделирование выполнения виляющего танца происходит в не­сколько этапов. В результате данного моделирования выбираются те аген­ты, которые за счёт выполнения танца выполнят вербовку других агентов для исследования найденного ими решения.

a) Выполняется нормирование полезностей агентов, допу­щенных к возможности выполнения танца. При этом нормирование учи­тывает направление оптимизации optOrient.

b) Добавление шумов к полученным нормированным полез­ностям и их корректировка.

c) Определение преимущества танца каждого агента.

d) Выбор тех агентов, которые за счёт выполнения танца вы­полняют вербовку других агентов для исследования найденного ими ре­шения.

6. Если требуется проводить локальную оптимизацию для найденных лучших решений, тогда выполняется локальная оптимизация с помощью указанного метода локальной оптимизации (например, метод Нелдера-Мида, Хука-Дживса, Пауэлла и т.п.). В зависимости от уста­новленных параметров локальная оптимизация выполняется либо для ре­шений тех агентов, которые произвели вербовку, либо только для реше­ния лучшего агента.

7. Выбирается агент с лучшим решением best.

8. Перезапуск агентов. Создаются агенты, которые будут рас­сматриваться как агенты-разведчики для следующей итерации.

К новым агентам-разведчикам будут относиться.

· агенты, выполнившие посредством танца вербовку, лучший агент;

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

· агенты, решение которых создаётся случайным образом:

Также для всех созданных агентов рассчитывается полезность вы­бранного решения.

9. Обновление динамических параметров метода:

10. Проверка на останов.

11. Если проверка на останов дала успешный результат, то выполняет­ся переход к шагу 11, в противном случае - к шагу 3.

12. Конец.