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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

Алгоритъмът на изкуствените пчелни семейства (ИПС) (на английски: Artificial Bee Colony algorithm (ABC), да не се греши с Алгоритъм на пчелите), предложен от Дервиш Карабога (Dervis Karaboga) през 2005 г.,[1] е вдъхновена от природата оптимизационна техника, която симулира интелигентно поведение на търсене на храна на рояк от медоносни пчели. Група от медоносни пчели се нарича рояк, който чрез социално сътрудничество може успешно да изпълнява задачи.

Описание на алгоритъма[редактиране | редактиране на кода]

В модела на ИПС има три групи пчели: „заети пчели“ (employed bees), „пчели-зяпачи“ (onlookers) и „пчели-разузнавачи“ (scouts). Позицията на източник на храна представлява възможно решение на оптимизационния проблем, а количество нектар в източника на храна е аналог на качеството (фитнеса) на съответното решение. Броят на заетите пчелите или пчелите-зяпачи е равен на броя на решенията в популацията. В първата стъпка, ИПС генерира случайно разпределена начална популация P (C = 0) на SN решения (позиции на източниците на храна), където SN обозначава размера на заетите пчели или пчелите зяпачи (случайни минувачи, зрители). Всяко решение xi (i = 1, 2, ..., SN) е D-мерен вектор, където, D е броят на параметрите за оптимизация.[2]

След инициализацията, популацията от позициите (решенията) е обект на повтарящи се цикли, C = 1, 2, ..., MCN, процеси на търсене от заетите пчели, пчелите-зяпачи и пчелите-разузнавачи. Една заета пчела променя позицията на източника на храна в паметта си и открива нова позиция на източник на храна. При условие, че количеството нектар в новата позиция е по-голямо от това в предишния източник, пчелата запаметява новата позиция на източника на храна и забравя старата. В противен случай тя запазва предишната позиция в паметта си. След приключване на процеса на търсене на всички заети пчели, те споделят информация за позициите на източниците на храна с пчелите-зяпачи. Всеки зяпач оценява информацията за нектара, предоставена от всички заети пчели и след това избира източник на храна в зависимост от количеството нектар в източниците. Както и в случая на заетите пчели, и тази пчела променя позицията на източника в паметта си и проверява неговото количество нектар. При условие, че неговото количество нектар е по-голямо от това на предишния източник, пчелата запаметява новата позиция и забравя старата. Определят се изоставените източници, след което на случаен принцип се генерират нови източници на храна, за да бъдат заменени с изоставените източници от изкуствени разузнавачи.

Основните етапи на алгоритъма са както следва:[2][3]

1: Инициализиране на популацията
2: ПОВТОРИ
3: Постави всяка заета пчела в източника на храна
4: Постави всяка пчела зяпач (случаен минувач, зрител) в източници на храна в зависимост от количество нектар.
5: Изпрати пчелите разузнавачи в областта на търсене за да открият нови източници на храна.
6: Запомни най-добрият източник на храна открит до този момент.
7: ДОКАТО (изискванията са изпълнени)

В алгоритъма на ИПС, всеки цикъл на търсене се състои от три етапа:[2]

  1. Изпращане на заетите пчелите върху техните хранителни източници и оценяването на количеството нектар.
  2. След споделянето на информацията за количеството нектар в хранителни източници, пчелите-зяпачи избират регионите на източниците на храна и оценяват количеството нектар в източниците на храна.
  3. Определяне на пчелите-разузнавачи и след това изпращането им на случаен принцип върху възможни нови източници на храна.

Тези три стъпки се повтарят за предварително определен брой цикли, наречен максимален брой цикли (Maximum Cycle Number (MCN)) или докато не бъде удовлетворен даден критерий за прекратяване на алгоритъма.[4]

Източници[редактиране | редактиране на кода]

  1. Karaboga D., An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.
  2. а б в Karaboga D., B. Akay, A comparative study of Artificial Bee Colony algorithm, Applied Mathematics and Computation 214 (2009) 108–132
  3. Karaboga D., B. Basturk, A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm, J Glob Optim (2007) 39:459–471, DOI 10.1007/s10898-007-9149-x
  4. Karaboga D., B. Basturk, On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing 8 (2008) 687–697