Пчелињи алгоритам

С Википедије, слободне енциклопедије

У информатици и операционим истраживањима, пчелињи алгоритам (енг. Беес алгоритхм) је алгоритам претраге на основу популације који је развијен 2005. године.[1] Алгоритам имитира понашање колонија пчела приликом потраге за храном. У својој основној верзији извршава претраживање суседства у комбинацији са глобалним претраживањем, и може се користити и за комбинаторну и за континуирану оптимизацију. Једини услов за употребу пчелињег алгоритма је да су неке мере тополошке удаљености између решења дефинисане. Ефикасност овог алгоритма се показала у многим истраживањима.[2][3]


Пчелињи алгоритам инспирисан је понашањем пчела медарица приликом сакупљања нектара.

Стратегија пчела у потрази за храном[уреди | уреди извор]

Колонија пчела се може раширити у неколико праваца истовремено са циљем прикупљања нектара или полена и на тај начин покрити велико пространство (преко 14 км).[4] Мали део колоније константно претражује оружење тражећи нове изворе нектара. Ове пчеле извиђачи се крећу насумично у околини кошнице, процењујући вредност ресурса на које наиђу.[4] Када се врате у кошницу, складиште покупљену храну. Пчеле које су пронашле вредне изворе нектара, одлазе у део кошнице који се назива "подијум за игру" и ту изводе ритуал плешући.[5] Помоћу овог плеса, пчеле комуницирају са осталим пчелама које нису биле у експедицији, објашњавајући им на тај начин где се жељени ивор хране налази. Пошто је време трајања плеса пропорционално оцени ресурса пчеле извиђача, још додатних сакупљача се организује да иде у потрагу за храном. Након плеса, пчела се враћа цвету како би сакупила још хране. Докле год се сматрају вредним, извори хране ће бити "рекламирани" од стране пчела сакупљача кроз плес у кошници. Нови регрути могу такође учествовати у плесу и на тај начин позивати што више нових пчела да се прикључе сакупљању. Захваљујући овом процесу, колонија је у стању да се фокусира само на највредније изворе хране.[4]

Алгоритам[уреди | уреди извор]

Пчелињи алгоритам[2][6] имитира стратегију пчела у тражењу најбољег решења за оптимизацију проблема. Сваки кандидат за решење се сматра извором хране (цветом), а популација (колонија) пчела се користи за претрагу. Сваки пут када пчела посети цвет, она процењује његову вредност. Алгоритам се састоји од иницијализације и главног циклуса претраге кроз који се пролази пута, или док се не пронађе одговарајуће решење. Сваки циклус претраге се састоји из пет корака: регрутовање, локална претрага, сужавање комшилука претраге, напуштање територије и глобална претрага.

Pseudo kod osnovnog pčelinjeg algoritma
   1 for i=1,…,ns				
       i  scout[i]=Initialise_scout()
       ii flower_patch[i]=Initialise_flower_patch(scout[i])
   2 do until stopping_condition=TRUE		
       i   Recruitment() 	
       ii  for i =1,…,nb
             1 flower_patch[i]=Local_search(flower_patch[i])
             2 flower_patch[i]=Site_abandonment(flower_patch[i])
             3 flower_patch[i]=Neighbourhood_shrinking(flower_patch[i])		
       iii for i = nb,…,ns
             1 flower_patch[i]=Global_search(flower_patch[i])}

Приликом иницијализације, пчела извиђача се насумице поставља у подручју претраге, процењујући вредност решења (поље цвећа) код којег су се затекле. За свако решење, поље цвећа (у алгоритму флоwер_патцх) се означава. Током процеса регрутовања, извиђачи који су посетили најбољих решења изводе ритуал плеса. Наиме, регрутују додатне пчеле сакупљаче да истражују комшилук решења која највише обећавају. Сваки од извиђача који су лоцирали најбоља решења регрутују пчела сакупљача, док сваки од преосталиих извиђача регрутује сакупљача. На тај начин број сакупљача зависи од вредности пронађеног извора хране. У току локалне претраге, регрутовани сакупљачи су насумице раштркани по цвећу у околини решења (тренутно најбољих) посећених од стране извиђача (локална експлоатација). Ако било која од пчела сакупљача у цвећу наиђе на решење веће вредности од оног које је пронашла пчела истраживач, та пчела постаје нови истраживач. У колико ниједан сакупљач не пронађе решење веће вредности од текућег, величина поља цвећа се сужава (процедура сужавање комшилука претраге). Поља цвећа се у процесу иницијализације обично дефинишу тако да покривају велику површину, а затим се постепено смањују током процедуре сужавања. Резултат тога је да се подручје локалне претраге постепено фокусира на простор уз само цвеће највеће локалне вредности. Ако за предоређен број циклуса претраге није пронађено веће решење у оквиру поља цвећа, локално решење највеће вредности се сматра пронађеним, поље се напушта и нови извиђач се насумице генерише.
Као и код пчела у реалном свету, мали број извиђача наставља са претрагом простора решења, у нади да ће пронаћи део велике вредности (глобална претрага). Процедура глобалне претраге реиницијализује последњих поља цвећа са насумице генерисаним решењима. На крају сваког циклуса претраге, број извиђача се поново састоји из пчела: извиђача произведених током локалне претраге (од којих су неки можда реиницијализовани током напуштања подручја), и извиђача генерисаних током глобалне претраге. Укупна величина вештачке колоније пчела је:


(сакупљачи са елитних поља + сакупљачи са преосталих најбољих поља + извиђачи).

Примене алгоритма[уреди | уреди извор]

Овај алгоритам нашао је многе примене у инжињерству:


Погледати још[уреди | уреди извор]

Референце[уреди | уреди извор]

  1. ^ Пхам ДТ, Гханбарзадех А, Коц Е, Отри С, Рахим С анд Заиди M. Тхе Беес Алгоритхм. Тецхницал Ноте, Мануфацтуринг Енгинееринг Центре, Цардифф Университy, УК, 2005.
  2. ^ а б Пхам, D.Т., Цастеллани, M. (2009), Тхе Беес Алгоритхм – Моделлинг Форагинг Бехавиоур то Солве Цонтинуоус Оптимисатион Проблемс Архивирано на сајту Wayback Machine (9. новембар 2016). Проц. ИмецхЕ, Парт C, 223(12), 2919-2938.
  3. ^ Пхам, D. Т.; Цастеллани, M. (2014). „Бенцхмаркинг анд цомпарисон оф натуре-инспиред популатион-басед цонтинуоус оптимисатион алгоритхмс”. Софт Цомпутинг. 18 (5): 871—903. С2ЦИД 254031481. дои:10.1007/с00500-013-1104-9. 
  4. ^ а б в Тересхко V., Лоенгаров А., (2005) Цоллецтиве Децисион-Макинг ин Хонеy Бее Форагинг Дyнамицс Архивирано на сајту Wayback Machine (1. фебруар 2014). Јоурнал оф Цомпутинг анд Информатион Сyстемс, 9(3), 1-7.
  5. ^ Вон Фрисцх, К. (1967) Тхе Данце Лангуаге анд Ориентатион оф Беес. Харвард Университy Пресс, Цамбридге, МА.
  6. ^ Пхам D.Т., Гханбарзадех А., Коц Е., Отри С., Рахим С., Заиди M., Тхе Беес Алгоритхм, А Новел Тоол фор Цомплеx Оптимисатион Проблемс, Проц 2нд Инт Виртуал Цонф он Интеллигент Продуцтион Мацхинес анд Сyстемс (ИПРОМС 2006), Оxфорд: Елсевиер. стр. 454-459, 2006.
  7. ^ Пхам D.Т., Заиди M., Махмуддин M., Гханбарзадех А., Коç Е., Отри С. (2007), Усинг тхе беес алгоритхм то оптимисе а суппорт вецтор мацхине фор wоод дефецт цлассифицатион, ИПРОМС 2007 Инновативе Продуцтион Мацхинес анд Сyстемс Виртуал Цонференце.
  8. ^ Пхам D.Т., Дарwисх А.Х. (2010), Усинг тхе беес алгоритхм wитх Калман филтеринг то траин ан артифициал неурал нетwорк фор паттерн цлассифицатион Архивирано на сајту Wayback Machine (6. јул 2015), Јоурнал оф Сyстемс анд Цонтрол Енгинееринг 224(7), 885-892.
  9. ^ Пхам D.Т., Суарез-Алварез M.M., Простов Y.I. (2011), Рандом сеарцх wитх к-прототyпес алгоритхм фор цлустеринг миxед датасетс, Процеедингс Роyал Социетy, 467, 2387-2403.
  10. ^ Пхам D.Т., Цастеллани M., Гханбарзадех А. (2007), Прелиминарy десигн усинг тхе Беес Алгоритхм, Процеедингс Еигхтх ЛАМДАМАП Интернатионал Цонференце он Ласер Метрологy, ЦММ анд Мацхине Тоол Перформанце. Цардифф - УК, 420-429.
  11. ^ Пхам, D.Т., Отри С., Дарwисх А.Х. (2007), Апплицатион оф тхе Беес Алгоритхм то ПЦБ ассемблy оптимисатион, Процеедингс 3рд Интернатионал Виртуал Цонференце он Интеллигент Продуцтион Мацхинес анд Сyстемс (ИПРОМС 2007), Wхиттлес, Дунбеатх, Сцотланд, 511-516.
  12. ^ Пхам D.Т., Коç Е., Лее Ј.Y., Пхруексанант Ј. (2007), Усинг тхе Беес Алгоритхм то Сцхедуле Јобс фор а Мацхине, Процеедингс 8тх интернатионал Цонференце он Ласер Метрологy, ЦММ анд Мацхине Тоол Перформанце (ЛАМДАМАП). Цардифф, УК, Еуспен, 430-439.
  13. ^ Баyкасоğлу А., Öзбакıр L., Тапкан П. (2009), Тхе беес алгоритхм фор wорклоад баланцинг ин еxаминатион јоб ассигнмент[мртва веза], Еуропеан Јоурнал Индустриал Енгинееринг 3(4) 424-435.
  14. ^ Öзбакıр L., Тапкан П. (2011), Бее цолонy интеллигенце ин зоне цонстраинед тwо-сидед ассемблy лине баланцинг проблем, Еxперт Сyстемс wитх Апплицатионс 38, 11947-11957.
  15. ^ Xу, Wењун; Зхоу, Зуде; Пхам, D. Т.; Лиу, Qуан; Ји, C.; Менг, Wеи (2012). „Qуалитy оф сервице ин мануфацтуринг нетwоркс: А сервице фрамеwорк анд итс имплементатион”. Тхе Интернатионал Јоурнал оф Адванцед Мануфацтуринг Тецхнологy. 63 (9–12): 1227—1237. С2ЦИД 253681068. дои:10.1007/с00170-012-3965-y. 
  16. ^ Пхам D.Т., Дарwисх А.Х., Елдукхри Е.Е. (2009), Оптимисатион оф а фуззy логиц цонтроллер усинг тхе Беес Алгоритхм[мртва веза], Интернатионал Јоурнал оф Цомпутер Аидед Енгинееринг анд Тецхнологy, 1, 250-264.
  17. ^ Алфи А., Кхосрави А., Разави С.Е. (2011), Бее Алгоритм–Басед Нолинеар Оптимал Цонтрол Апплиед То А Цонтинуоус Стирред-Танк Цхемицал Реацтор, Глобал Јоурнал оф Пуре & Апплиед Сциенце анд Тецхнологy - ГЈПАСТ 1(2), 73-79.
  18. ^ Фахмy А.А., Калyонцу M., Цастеллани M. (2012), Аутоматиц Десигн оф Цонтрол Сyстемс фор Робот Манипулаторс Усинг тхе Беес Алгоритхм[мртва веза], Процеедингс оф тхе Институтион оф Мецханицал Енгинеерс, Парт I: Јоурнал оф Сyстемс анд Цонтрол Енгинееринг, 226(4), 497-508.
  19. ^ Цастеллани M., Пхам Q.Т., Пхам D.Т. (2012), Дyнамиц Оптимисатион бy а Модифиед Беес Алгоритхм[мртва веза], Процеедингс оф тхе Институтион оф Мецханицал Енгинеерс, Парт I: Јоурнал оф Сyстемс анд Цонтрол Енгинееринг, 226(7), 956–971.
  20. ^ Бахамисх Х.А.А., Абдуллах Р., Салам Р.А. (2008), Протеин Цонформатионал Сеарцх Усинг Беес Алгоритхм, Сецонд Асиа Интернатионал Цонференце он Моделинг & Симулатион (АИЦМС 08), Куала Лумпур, Малаyсиа, ИЕЕЕ Пресс, 911-916.
  21. ^ Руз, Гонзало А.; Голес, Ериц (2013). „Леарнинг гене регулаторy нетwоркс усинг тхе беес алгоритхм”. Неурал Цомпутинг анд Апплицатионс. 22: 63—70. С2ЦИД 254037353. дои:10.1007/с00521-011-0750-з. 
  22. ^ Гунеy К., Онаy M. (2010), Беес алгоритхм фор интерференце суппрессион оф линеар антенна арраyс бy цонтроллинг тхе пхасе-онлy анд ботх тхе амплитуде анд пхасе, Еxперт Сyстемс wитх Апплицатионс 37, 3129–3135.
  23. ^ Xу С., Yу Ф., Луо З., Ји З., Пхам D.Т., Qиу Р. (2011), Адаптиве Беес Алгоритхм - Биоинспиратион фром Хонеyбее Форагинг то Оптимизе Фуел Ецономy оф а Семи-Трацк Аир-Цусхион Вехицле, Тхе Цомпутер Јоурнал 54(9), 1416-1426.
  24. ^ Пхам, D. Т.; Коç, Ебубекир (2010). „Десигн оф а тwо-дименсионал рецурсиве филтер усинг тхе беес алгоритхм”. Интернатионал Јоурнал оф Аутоматион анд Цомпутинг. 7 (3): 399—402. С2ЦИД 124240746. дои:10.1007/с11633-010-0520-x. 
  25. ^ Јевтиц А., Гутиеррез-Мартин А., Андина D.А., Јамсхиди M. (2012), Дистрибутед Беес Алгоритхм фор Таск Аллоцатион ин Сwарм оф Роботс, ИЕЕЕ Сyстемс Јоурнал 6(2) 296-304.
  26. ^ Морсали, Роозбех; Мохаммади, Мохсен; Малексаееди, Иман; Гхадими, Норадин (2014). „А неw мултиобјецтиве процедуре фор солвинг нонцонвеx енвиронментал/ецономиц поwер диспатцх”. Цомплеxитy. 20 (2): 47—62. Бибцоде:2014Цмплx..20б..47М. дои:10.1002/цплx.21505. 
  27. ^ Лее Ј.Y., Дарwисх А.Х. (2008), . дои:10.1007/978-3-540-85190-5_28.  Недостаје или је празан параметар |титле= (помоћ) Мулти-објецтиве Енвиронментал/Ецономиц Диспатцх Усинг тхе Беес Алгоритхм wитх Wеигхтед Сум, Процеедингс оф тхе ЕУ-Кореа Цонференце он Сциенце анд Тецхнологy (ЕКЦ2008), Ед. С.D. Yоо, Хеиделберг, D, Спрингер Берлин Хеиделберг, 267-274.
  28. ^ Саyади Ф., Исмаил M., Мисран Н., Јумари К. (2009), Мулти-Објецтиве Оптимизатион Усинг тхе Беес Алгоритхм ин Тиме-Варyинг Цханнел фор МИМО MC-ЦДМА Сyстемс, Еуропеан Јоурнал оф Сциентифиц Ресеарцх 33(3), 411-428.
  29. ^ Мансоури Поор M., Схисхех Саз M. (2012), Мулти-Објецтиве Оптимизатион оф Ламинатес wитх Страигхт Фрее Едгес анд Цурвед Фрее Едгес бy Усинг Беес Алгоритхм, Америцан Јоурнал оф Адванцед Сциентифиц Ресеарцх 1(4), 130-136.

Спољашње везе[уреди | уреди извор]