WikiDer > Алгоритм искусственной пчелиной семьи

Artificial bee colony algorithm

В Информатика и исследование операций, то алгоритм искусственной пчелиной семьи (ABC) - это алгоритм оптимизации, основанный на интеллектуальном кормлении роя медоносных пчел, предложенный Дервишем Карабогой (Университет Эрджиес) в 2005 году.^[1]

Алгоритм

В модели ABC колония состоит из трех групп пчел: нанятых пчел, зевак и разведчиков. Предполагается, что для каждого источника пищи используется только одна искусственная пчела. Другими словами, количество работающих пчел в колонии равно количеству источников пищи вокруг улья. Нанятые пчелы идут к источнику пищи и возвращаются в улей и танцуют на этой территории. Наемная пчела, чей источник пищи был оставлен, становится разведчиком и начинает искать новый источник пищи. Зрители наблюдают за танцами работающих пчел и выбирают источники пищи в зависимости от танцев. Ниже приведены основные этапы алгоритма:^[1]

Первоначальные источники пищи производятся для всех используемых пчел.
ПОВТОРЕНИЕ
- Каждая используемая пчела идет к источнику пищи в ее памяти и определяет ближайший источник, затем оценивает количество своего нектара и танцует в улье.
- Каждый наблюдатель наблюдает за танцем работающих пчел и выбирает один из их источников в зависимости от танцев, а затем идет к этому источнику. Выбрав вокруг этого соседа, она оценивает количество нектара в нем.
- Определяются заброшенные источники пищи, которые заменяются новыми источниками пищи, обнаруженными разведчиками.
- Зарегистрирован лучший из найденных до сих пор источников пищи.
ДО ПОКА (требования выполнены)

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

Алгоритм искусственной пчелиной семьи

Алгоритм искусственной пчелиной колонии (ABC) - это метод оптимизации, который моделирует поведение медоносных пчел при кормлении, и успешно применяется для решения различных практических задач.^{[нужна цитата]}. ABC принадлежит к группе алгоритмов разведки роя и был предложен Карабогой в 2005 году.

Набор медоносных пчел, называемый рой, может успешно решать задачи посредством социального сотрудничества. В алгоритме ABC есть три типа пчел: рабочие пчелы, пчелы-наблюдатели и пчелы-разведчики. Работающие пчелы ищут пищу вокруг источника пищи в своей памяти; тем временем они делятся информацией об этих источниках пищи с пчелами-наблюдателями. Пчелы-наблюдатели, как правило, выбирают хорошие источники пищи из тех, что находят пчелы-работники. У источника пищи более высокого качества (пригодности) будет больше шансов быть выбранным наблюдателями, чем у источника более низкого качества. Пчелы-разведчики переводятся из нескольких работающих пчел, которые оставляют свои источники пищи и ищут новые.

В алгоритме ABC первая половина роя состоит из занятых пчел, а вторая половина - из пчел-наблюдателей.

Количество используемых пчел или пчел-наблюдателей равно количеству растворов в рое. ABC генерирует случайно распределенную начальную популяцию растворов SN (источников пищи), где SN обозначает размер роя.

Позволять ${displaystyle X_ {i} = {x_ {i, 1}, x_ {i, 2}, ldots, x_ {i, n}}}$ представляют ${displaystyle i ^ {th}}$ раствор в рое, где ${displaystyle n}$ это размерный размер.

Каждая нанятая пчела ${displaystyle X_ {i}}$ генерирует новый вариант решения ${displaystyle V_ {i}}$ рядом с его нынешним положением, как показано ниже:

{displaystyle v_ {i, k} = x_ {i, k} + Phi _ {i, k} imes (x_ {i, k} -x_ {j, k})}

куда ${displaystyle X_ {j}}$ - случайно выбранный вариант решения ( ${displaystyle ieq j}$ ), ${displaystyle k}$ случайный индекс измерения, выбранный из набора ${displaystyle {1,2, ldots, n}}$ , и ${displaystyle Phi _ {i, k}}$ случайное число в пределах ${displaystyle [-1,1]}$ . Как только новый вариант решения ${displaystyle V_ {i}}$ генерируется, используется жадный выбор. Если значение пригодности ${displaystyle V_ {i}}$ лучше, чем у его родителя ${displaystyle X_ {i}}$ , затем обновите ${displaystyle X_ {i}}$ с ${displaystyle V_ {i}}$ ; в противном случае держите ${displaystyle X_ {i}}$ без изменений. После того, как все занятые пчелы завершат процесс поиска; они делятся информацией о своих источниках пищи с пчелами-наблюдателями посредством танцев виляния. Пчела-наблюдатель оценивает информацию о нектаре, полученную от всех используемых пчел, и выбирает источник пищи с вероятностью, связанной с количеством нектара. Этот вероятностный выбор на самом деле является механизмом выбора колеса рулетки, который описывается следующим уравнением:

{displaystyle P_ {i} = {frac {mathrm {fit} _ {i}} {sum _ {j} {mathrm {fit} _ {j}}}}}

куда ${displaystyle mathrm {fit} _ {i}}$ значение пригодности ${displaystyle i ^ {th}}$ раствор в рое. Как видно, чем лучше решение ${displaystyle i}$ , тем выше вероятность ${displaystyle i ^ {th}}$ выбран источник питания. Если положение не может быть улучшено за заранее определенное количество циклов (называемое пределом), то источник пищи прекращается. Предположим, что заброшенный источник ${displaystyle X_ {i}}$ , а затем пчела-разведчик обнаруживает новый источник пищи, который нужно заменить ${displaystyle i ^ {th}}$ как уравнение ниже:

{displaystyle x_ {i, k} = lb_ {k} + Phi _ {i, k} imes (ub_ {k} -lb_ {k})}

куда ${displaystyle Phi _ {i, k} = mathrm {rand} (0,1)}$ случайное число в пределах ${displaystyle [0,1]}$ на основе нормального^{[ненадежный источник?]} распространение и ${displaystyle lb_ {k}, ub_ {k}}$ нижняя и верхняя границы ${displaystyle k ^ {th}}$ размер соответственно.