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

Алгоритм в информатике

В области компьютерных наук и исследования операций алгоритм искусственной колонии пчел ( 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}\times (x_{i,k}-x_{j,k})}$

где — случайно выбранное решение-кандидат ( ), — случайный индекс измерения, выбранный из набора , и — случайное число в пределах . После генерации нового решения-кандидата используется жадный выбор. Если значение приспособленности лучше, чем у его родителя , то обновить с помощью ; в противном случае оставить без изменений. После того, как все занятые пчелы завершат процесс поиска; они делятся информацией о своих источниках пищи с пчелами-наблюдателями с помощью виляющих танцев. Пчела-наблюдатель оценивает информацию о нектаре, полученную от всех занятых пчел, и выбирает источник пищи с вероятностью, связанной с количеством ее нектара. Этот вероятностный выбор на самом деле является механизмом выбора колеса рулетки, который описывается уравнением ниже: ${\displaystyle X_{j}}$ ${\displaystyle i\neq 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}\times (ub_{k}-lb_{k})}$

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

Смотрите также

• Эволюционные вычисления
• Эволюционная мультимодальная оптимизация
• Оптимизация роя частиц
• Роевой интеллект
• Алгоритм пчел
• Поиск косяка рыб
• Список метаэвристик, основанных на метафорах

Ссылки

1. Karaboğa, Derviş (2005). «Идея, основанная на рое медоносных пчел для численной оптимизации». S2CID  8215393. {{cite journal}}: Цитировать журнал требует |journal=( помощь )

Внешние ссылки

• Домашняя страница алгоритма искусственной пчелиной колонии (ABC), Турция: Исследовательская группа интеллектуальных систем, кафедра компьютерной инженерии, Университет Эрджиес