Pčelinji algoritam

U informatici i operacionim istraživanjima, pčelinji algoritam (eng. Bees algorithm) je algoritam pretrage na osnovu populacije koji je razvijen 2005. godine.^[1] Algoritam imitira ponašanje kolonija pčela prilikom potrage za hranom. U svojoj osnovnoj verziji izvršava pretraživanje susedstva u kombinaciji sa globalnim pretraživanjem, i može se koristiti i za kombinatornu i za kontinuiranu optimizaciju. Jedini uslov za upotrebu pčelinjeg algoritma je da su neke mere topološke udaljenosti između rešenja definisane. Efikasnost ovog algoritma se pokazala u mnogim istraživanjima.^[2]^[3]

Strategija pčela u potrazi za hranom

Kolonija pčela se može raširiti u nekoliko pravaca istovremeno sa ciljem prikupljanja nektara ili polena i na taj način pokriti veliko prostranstvo (preko 14 km).^[4] Mali deo kolonije konstantno pretražuje oruženje tražeći nove izvore nektara. Ove pčele izviđači se kreću nasumično u okolini košnice, procenjujući vrednost resursa na koje naiđu.^[4] Kada se vrate u košnicu, skladište pokupljenu hranu. Pčele koje su pronašle vredne izvore nektara, odlaze u deo košnice koji se naziva "podijum za igru" i tu izvode ritual plešući.^[5] Pomoću ovog plesa, pčele komuniciraju sa ostalim pčelama koje nisu bile u ekspediciji, objašnjavajući im na taj način gde se željeni ivor hrane nalazi. Pošto je vreme trajanja plesa proporcionalno oceni resursa pčele izviđača, još dodatnih sakupljača se organizuje da ide u potragu za hranom. Nakon plesa, pčela se vraća cvetu kako bi sakupila još hrane. Dokle god se smatraju vrednim, izvori hrane će biti "reklamirani" od strane pčela sakupljača kroz ples u košnici. Novi regruti mogu takođe učestvovati u plesu i na taj način pozivati što više novih pčela da se priključe sakupljanju. Zahvaljujući ovom procesu, kolonija je u stanju da se fokusira samo na najvrednije izvore hrane.^[4]

Algoritam

Pčelinji algoritam^[2]^[6] imitira strategiju pčela u traženju najboljeg rešenja za optimizaciju problema. Svaki kandidat za rešenje se smatra izvorom hrane (cvetom), a populacija (kolonija) $n$ pčela se koristi za pretragu. Svaki put kada pčela poseti cvet, ona procenjuje njegovu vrednost. Algoritam se sastoji od inicijalizacije i glavnog ciklusa pretrage kroz koji se prolazi $T$ puta, ili dok se ne pronađe odgovarajuće rešenje. Svaki ciklus pretrage se sastoji iz pet koraka: regrutovanje, lokalna pretraga, sužavanje komšiluka pretrage, napuštanje teritorije i globalna pretraga.

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])}

Prilikom inicijalizacije, $ns$ pčela izviđača se nasumice postavlja u području pretrage, procenjujući vrednost rešenja (polje cveća) kod kojeg su se zatekle. Za svako rešenje, polje cveća (u algoritmu flower_patch) se označava. Tokom procesa regrutovanja, izviđači koji su posetili $nb\leq ns$ najboljih rešenja izvode ritual plesa. Naime, regrutuju dodatne pčele sakupljače da istražuju komšiluk rešenja koja najviše obećavaju. Svaki od izviđača koji su locirali najbolja $ne\leq nb$ rešenja regrutuju $nre$ pčela sakupljača, dok svaki od preostaliih $nb-ne$ izviđača regrutuje $nrb\leq nre$ sakupljača. Na taj način broj sakupljača zavisi od vrednosti pronađenog izvora hrane. U toku lokalne pretrage, regrutovani sakupljači su nasumice raštrkani po cveću u okolini rešenja (trenutno najboljih) posećenih od strane izviđača (lokalna eksploatacija). Ako bilo koja od pčela sakupljača u cveću naiđe na rešenje veće vrednosti od onog koje je pronašla pčela istraživač, ta pčela postaje novi istraživač. U koliko nijedan sakupljač ne pronađe rešenje veće vrednosti od tekućeg, veličina polja cveća se sužava (procedura sužavanje komšiluka pretrage). Polja cveća se u procesu inicijalizacije obično definišu tako da pokrivaju veliku površinu, a zatim se postepeno smanjuju tokom procedure sužavanja. Rezultat toga je da se područje lokalne pretrage postepeno fokusira na prostor uz samo cveće najveće lokalne vrednosti. Ako za predoređen broj ciklusa pretrage nije pronađeno veće rešenje u okviru polja cveća, lokalno rešenje najveće vrednosti se smatra pronađenim, polje se napušta i novi izviđač se nasumice generiše.
Kao i kod pčela u realnom svetu, mali broj izviđača nastavlja sa pretragom prostora rešenja, u nadi da će pronaći deo velike vrednosti (globalna pretraga). Procedura globalne pretrage reinicijalizuje poslednjih $ns-nb$ polja cveća sa nasumice generisanim rešenjima. Na kraju svakog ciklusa pretrage, broj izviđača se ponovo sastoji iz $ns$ pčela: $nr$ izviđača proizvedenih tokom lokalne pretrage (od kojih su neki možda reinicijalizovani tokom napuštanja područja), i $ns-nb$ izviđača generisanih tokom globalne pretrage. Ukupna veličina veštačke kolonije pčela je:

 $n=ne\cdot nre (nb-ne)\cdot nrb ns$

(sakupljači sa elitnih polja sakupljači sa preostalih najboljih polja izviđači).

Primene algoritma

Ovaj algoritam našao je mnoge primene u inžinjerstvu:

Optimizacija klaster sistema^[7]^[8]^[9]
Manufaktura^[10]^[11]^[12]^[13]^[14]^[15]
Upravljanje^[16]^[17]^[18]^[19]
Bioinžinjering^[20]^[21]
Ostali problemi optimizacije^[22]^[23]^[24]^[25]
Više-objektivna optimizacija^[26]^[27]^[28]^[29]

Vidi još

Reference

^ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.
^ ^а ^б Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems Архивирано на сајту Wayback Machine (9. новембар 2016). Proc. ImechE, Part C, 223(12), 2919-2938.
^ Pham, D. T.; Castellani, M. (2014). „Benchmarking and comparison of nature-inspired population-based continuous optimisation algorithms”. Soft Computing. 18 (5): 871—903. S2CID 254031481. doi:10.1007/s00500-013-1104-9.
^ ^а ^б ^в Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics Архивирано на сајту Wayback Machine (1. фебруар 2014). Journal of Computing and Information Systems, 9(3), 1-7.
^ Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.
^ Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems, Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier. стр. 454-459, 2006.
^ Pham D.T., Zaidi M., Mahmuddin M., Ghanbarzadeh A., Koç E., Otri S. (2007), Using the bees algorithm to optimise a support vector machine for wood defect classification, IPROMS 2007 Innovative Production Machines and Systems Virtual Conference.
^ Pham D.T., Darwish A.H. (2010), Using the bees algorithm with Kalman filtering to train an artificial neural network for pattern classification Архивирано на сајту Wayback Machine (6. јул 2015), Journal of Systems and Control Engineering 224(7), 885-892.
^ Pham D.T., Suarez-Alvarez M.M., Prostov Y.I. (2011), Random search with k-prototypes algorithm for clustering mixed datasets, Proceedings Royal Society, 467, 2387-2403.
^ Pham D.T., Castellani M., Ghanbarzadeh A. (2007), Preliminary design using the Bees Algorithm, Proceedings Eighth LAMDAMAP International Conference on Laser Metrology, CMM and Machine Tool Performance. Cardiff - UK, 420-429.
^ Pham, D.T., Otri S., Darwish A.H. (2007), Application of the Bees Algorithm to PCB assembly optimisation, Proceedings 3rd International Virtual Conference on Intelligent Production Machines and Systems (IPROMS 2007), Whittles, Dunbeath, Scotland, 511-516.
^ Pham D.T., Koç E., Lee J.Y., Phrueksanant J. (2007), Using the Bees Algorithm to Schedule Jobs for a Machine, Proceedings 8th international Conference on Laser Metrology, CMM and Machine Tool Performance (LAMDAMAP). Cardiff, UK, Euspen, 430-439.
^ Baykasoğlu A., Özbakır L., Tapkan P. (2009), The bees algorithm for workload balancing in examination job assignment^{[мртва веза]}, European Journal Industrial Engineering 3(4) 424-435.
^ Özbakır L., Tapkan P. (2011), Bee colony intelligence in zone constrained two-sided assembly line balancing problem, Expert Systems with Applications 38, 11947-11957.
^ Xu, Wenjun; Zhou, Zude; Pham, D. T.; Liu, Quan; Ji, C.; Meng, Wei (2012). „Quality of service in manufacturing networks: A service framework and its implementation”. The International Journal of Advanced Manufacturing Technology. 63 (9–12): 1227—1237. S2CID 253681068. doi:10.1007/s00170-012-3965-y.
^ Pham D.T., Darwish A.H., Eldukhri E.E. (2009), Optimisation of a fuzzy logic controller using the Bees Algorithm^{[мртва веза]}, International Journal of Computer Aided Engineering and Technology, 1, 250-264.
^ Alfi A., Khosravi A., Razavi S.E. (2011), Bee Algoritm–Based Nolinear Optimal Control Applied To A Continuous Stirred-Tank Chemical Reactor, Global Journal of Pure & Applied Science and Technology - GJPAST 1(2), 73-79.
^ Fahmy A.A., Kalyoncu M., Castellani M. (2012), Automatic Design of Control Systems for Robot Manipulators Using the Bees Algorithm^{[мртва веза]}, Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(4), 497-508.
^ Castellani M., Pham Q.T., Pham D.T. (2012), Dynamic Optimisation by a Modified Bees Algorithm^{[мртва веза]}, Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(7), 956–971.
^ Bahamish H.A.A., Abdullah R., Salam R.A. (2008), Protein Conformational Search Using Bees Algorithm, Second Asia International Conference on Modeling & Simulation (AICMS 08), Kuala Lumpur, Malaysia, IEEE Press, 911-916.
^ Ruz, Gonzalo A.; Goles, Eric (2013). „Learning gene regulatory networks using the bees algorithm”. Neural Computing and Applications. 22: 63—70. S2CID 254037353. doi:10.1007/s00521-011-0750-z.
^ Guney K., Onay M. (2010), Bees algorithm for interference suppression of linear antenna arrays by controlling the phase-only and both the amplitude and phase, Expert Systems with Applications 37, 3129–3135.
^ Xu S., Yu F., Luo Z., Ji Z., Pham D.T., Qiu R. (2011), Adaptive Bees Algorithm - Bioinspiration from Honeybee Foraging to Optimize Fuel Economy of a Semi-Track Air-Cushion Vehicle, The Computer Journal 54(9), 1416-1426.
^ Pham, D. T.; Koç, Ebubekir (2010). „Design of a two-dimensional recursive filter using the bees algorithm”. International Journal of Automation and Computing. 7 (3): 399—402. S2CID 124240746. doi:10.1007/s11633-010-0520-x.
^ Jevtic A., Gutierrez-Martin A., Andina D.A., Jamshidi M. (2012), Distributed Bees Algorithm for Task Allocation in Swarm of Robots, IEEE Systems Journal 6(2) 296-304.
^ Morsali, Roozbeh; Mohammadi, Mohsen; Maleksaeedi, Iman; Ghadimi, Noradin (2014). „A new multiobjective procedure for solving nonconvex environmental/economic power dispatch”. Complexity. 20 (2): 47—62. Bibcode:2014Cmplx..20b..47M. doi:10.1002/cplx.21505.
^ Lee, Ji Young; Darwish, Ahmed Haj (2008). „Multi-objective Environmental/Economic Dispatch Using the Bees Algorithm with Weighted Sum”. EKC2008 Proceedings of the EU-Korea Conference on Science and Technology. Springer Proceedings in Physics. 124. стр. 267—274. ISBN 978-3-540-85189-9. doi:10.1007/978-3-540-85190-5_28.
^ Sayadi F., Ismail M., Misran N., Jumari K. (2009), Multi-Objective Optimization Using the Bees Algorithm in Time-Varying Channel for MIMO MC-CDMA Systems, European Journal of Scientific Research 33(3), 411-428.
^ Mansouri Poor M., Shisheh Saz M. (2012), Multi-Objective Optimization of Laminates with Straight Free Edges and Curved Free Edges by Using Bees Algorithm, American Journal of Advanced Scientific Research 1(4), 130-136.

Spoljašnje veze

Pčelinji algoritam (sajt)
Upotreba pčelinjeg plesa - BBC Njuz
Optimizacija algoritma zasnovanog na ponašanju pčela medarica pri potrazi za hranom Архивирано на сајту Wayback Machine (1. фебруар 2014)

[Pham_&_al,_2005-1] Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.

[Pham_&_Castellani,_2009-2] а ^б Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems Архивирано на сајту Wayback Machine (9. новембар 2016). Proc. ImechE, Part C, 223(12), 2919-2938.

[3] Pham, D. T.; Castellani, M. (2014). „Benchmarking and comparison of nature-inspired population-based continuous optimisation algorithms”. Soft Computing. 18 (5): 871—903. S2CID 254031481. doi:10.1007/s00500-013-1104-9.

[Tereshko_&_Loengarov,_2005-4] а ^б ^в Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics Архивирано на сајту Wayback Machine (1. фебруар 2014). Journal of Computing and Information Systems, 9(3), 1-7.

[5] Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.

[6] Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems, Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier. стр. 454-459, 2006.

[7] Pham D.T., Zaidi M., Mahmuddin M., Ghanbarzadeh A., Koç E., Otri S. (2007), Using the bees algorithm to optimise a support vector machine for wood defect classification, IPROMS 2007 Innovative Production Machines and Systems Virtual Conference.

[8] Pham D.T., Darwish A.H. (2010), Using the bees algorithm with Kalman filtering to train an artificial neural network for pattern classification Архивирано на сајту Wayback Machine (6. јул 2015), Journal of Systems and Control Engineering 224(7), 885-892.

[9] Pham D.T., Suarez-Alvarez M.M., Prostov Y.I. (2011), Random search with k-prototypes algorithm for clustering mixed datasets, Proceedings Royal Society, 467, 2387-2403.

[10] Pham D.T., Castellani M., Ghanbarzadeh A. (2007), Preliminary design using the Bees Algorithm, Proceedings Eighth LAMDAMAP International Conference on Laser Metrology, CMM and Machine Tool Performance. Cardiff - UK, 420-429.

[11] Pham, D.T., Otri S., Darwish A.H. (2007), Application of the Bees Algorithm to PCB assembly optimisation, Proceedings 3rd International Virtual Conference on Intelligent Production Machines and Systems (IPROMS 2007), Whittles, Dunbeath, Scotland, 511-516.

[12] Pham D.T., Koç E., Lee J.Y., Phrueksanant J. (2007), Using the Bees Algorithm to Schedule Jobs for a Machine, Proceedings 8th international Conference on Laser Metrology, CMM and Machine Tool Performance (LAMDAMAP). Cardiff, UK, Euspen, 430-439.

[13] Baykasoğlu A., Özbakır L., Tapkan P. (2009), The bees algorithm for workload balancing in examination job assignment^{[мртва веза]}, European Journal Industrial Engineering 3(4) 424-435.

[14] Özbakır L., Tapkan P. (2011), Bee colony intelligence in zone constrained two-sided assembly line balancing problem, Expert Systems with Applications 38, 11947-11957.

[15] Xu, Wenjun; Zhou, Zude; Pham, D. T.; Liu, Quan; Ji, C.; Meng, Wei (2012). „Quality of service in manufacturing networks: A service framework and its implementation”. The International Journal of Advanced Manufacturing Technology. 63 (9–12): 1227—1237. S2CID 253681068. doi:10.1007/s00170-012-3965-y.

[16] Pham D.T., Darwish A.H., Eldukhri E.E. (2009), Optimisation of a fuzzy logic controller using the Bees Algorithm^{[мртва веза]}, International Journal of Computer Aided Engineering and Technology, 1, 250-264.

[17] Alfi A., Khosravi A., Razavi S.E. (2011), Bee Algoritm–Based Nolinear Optimal Control Applied To A Continuous Stirred-Tank Chemical Reactor, Global Journal of Pure & Applied Science and Technology - GJPAST 1(2), 73-79.

[18] Fahmy A.A., Kalyoncu M., Castellani M. (2012), Automatic Design of Control Systems for Robot Manipulators Using the Bees Algorithm^{[мртва веза]}, Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(4), 497-508.

[19] Castellani M., Pham Q.T., Pham D.T. (2012), Dynamic Optimisation by a Modified Bees Algorithm^{[мртва веза]}, Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering, 226(7), 956–971.

[20] Bahamish H.A.A., Abdullah R., Salam R.A. (2008), Protein Conformational Search Using Bees Algorithm, Second Asia International Conference on Modeling & Simulation (AICMS 08), Kuala Lumpur, Malaysia, IEEE Press, 911-916.

[21] Ruz, Gonzalo A.; Goles, Eric (2013). „Learning gene regulatory networks using the bees algorithm”. Neural Computing and Applications. 22: 63—70. S2CID 254037353. doi:10.1007/s00521-011-0750-z.

[22] Guney K., Onay M. (2010), Bees algorithm for interference suppression of linear antenna arrays by controlling the phase-only and both the amplitude and phase, Expert Systems with Applications 37, 3129–3135.

[23] Xu S., Yu F., Luo Z., Ji Z., Pham D.T., Qiu R. (2011), Adaptive Bees Algorithm - Bioinspiration from Honeybee Foraging to Optimize Fuel Economy of a Semi-Track Air-Cushion Vehicle, The Computer Journal 54(9), 1416-1426.

[24] Pham, D. T.; Koç, Ebubekir (2010). „Design of a two-dimensional recursive filter using the bees algorithm”. International Journal of Automation and Computing. 7 (3): 399—402. S2CID 124240746. doi:10.1007/s11633-010-0520-x.

[25] Jevtic A., Gutierrez-Martin A., Andina D.A., Jamshidi M. (2012), Distributed Bees Algorithm for Task Allocation in Swarm of Robots, IEEE Systems Journal 6(2) 296-304.

[26] Morsali, Roozbeh; Mohammadi, Mohsen; Maleksaeedi, Iman; Ghadimi, Noradin (2014). „A new multiobjective procedure for solving nonconvex environmental/economic power dispatch”. Complexity. 20 (2): 47—62. Bibcode:2014Cmplx..20b..47M. doi:10.1002/cplx.21505.

[27] Lee, Ji Young; Darwish, Ahmed Haj (2008). „Multi-objective Environmental/Economic Dispatch Using the Bees Algorithm with Weighted Sum”. EKC2008 Proceedings of the EU-Korea Conference on Science and Technology. Springer Proceedings in Physics. 124. стр. 267—274. ISBN 978-3-540-85189-9. doi:10.1007/978-3-540-85190-5_28.

[28] Sayadi F., Ismail M., Misran N., Jumari K. (2009), Multi-Objective Optimization Using the Bees Algorithm in Time-Varying Channel for MIMO MC-CDMA Systems, European Journal of Scientific Research 33(3), 411-428.

[29] Mansouri Poor M., Shisheh Saz M. (2012), Multi-Objective Optimization of Laminates with Straight Free Edges and Curved Free Edges by Using Bees Algorithm, American Journal of Advanced Scientific Research 1(4), 130-136.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]