The variants of the Bees Algorithm (BA): a survey

Artificial Intelligence Review - Tập 47 - Trang 67-121 - 2016
Wasim Abdulqawi Hussein1, Shahnorbanun Sahran1, Siti Norul Huda Sheikh Abdullah1
1Pattern Recognition Research Group, Center of Artificial Intelligence Technology, Faculty of Information Systems and Technology, Universiti Kebangsaan Malaysia, Bandar Baru Bangi, Malaysia

Tóm tắt

The Bees Algorithm (BA) is a bee swarm intelligence-based metaheuristic algorithm that is inspired by the natural behavior of honeybees when foraging for food. BA can be divided into four parts: parameter tuning, initialization, local search, and global search. Since its invention, several studies have sought to enhance the performance of BA by improving some of its parts. Thus, more than one version of the algorithm has been proposed. However, upon searching for the basic version of BA in the literature, unclear and contradictory information can be found. By reviewing the literature and conducting some experiments on a set of standard benchmark functions, three main implementations of the algorithm that researchers should be aware of while working on improving the BA are uncovered. These implementations are Basic BA, Shrinking-based BA and Standard BA. Shrinking-based BA employs a shrinking procedure, and Standard BA uses a site abandonment approach in addition to the shrinking procedure. Thus, various implementations of the shrinking and site-abandonment procedures are explored and incorporated into BA to constitute different BA implementations. This paper proposes a framework of the main implementations of BA, including Basic BA and Standard BA, to give a clear picture of these implementations and the relationships among them. Additionally, the experiments show no significant differences among most of the shrinking implementations. Furthermore, this paper reviews the improvements to BA, which are improvements in the parameter tuning, population initialization, local search and global search. It is hoped that this paper will provide researchers who are working on improving the BA with valuable references and guidance.

Tài liệu tham khảo

Abbass HA (2001) MBO: marriage in honey bees optimization–a haplometrosis polygynous swarming approach. Proceedings of the 2001 congress on evolutionary computation. IEEE, Seoul, pp 207–214 Abdullah S, Alzaqebah M (2013) A hybrid self-adaptive Bees Algorithm for examination timetabling problems. Appl Soft Comput 13:3608–3620 Abul Hasan MJ, Ramakrishnan S (2011) A survey: hybrid evolutionary algorithms for cluster analysis. Artif Intell Rev 36:179–204 Ahmad SA (2012) A study of search neighbourhood in the Bees Algorithm. Cardiff University, Cardiff Ahmad SA, Pham DT, Ng KW, Ang MC (2012) TRIZ-inspired asymmetrical search neighborhood in the Bees Algorithm. Sixth Asia modelling symposium (AMS). IEEE, Bali, pp 29–33 Ang M, Pham D, Ng K (2009) Minimum-time motion planning for a robot arm using the Bees Algorithm. Proceedings of the 7th IEEE international conference on industrial informatics (INDIN 2009). IEEE, Cardiff, Wales, pp 487–492 Ang MC, Pham DT, Soroka AJ, Ng KW, (2010) PCB assembly optimisation using the Bees Algorithm enhanced with TRIZ operators. 36th annual conference on IEEE industrial electronics society (IECON, (2010) IEEE. Glendale, AZ, pp 2708–2713 Antoniou A, Lu W-S (2007) The optimization problem, practical optimization: algorithms and engineering applications, 1st edn. Springer, New York Auger A, Hansen N (2005) Performance evaluation of an advanced local search evolutionary algorithm. In: The 2005 IEEE congress on evolutionary computation IEEE, pp 1777–1784 Azarbad M, Ebrahimzade A, Izadian V (2011) Segmentation of infrared images and objectives detection using maximum entropy method based on the bee algorithm. Int J Comput Inf Syst Ind Manag Appl 3:26–33 Bahamish HAA, Abdullah R, Salam RA (2008) Protein conformational search using Bees Algorithm. Second Asia international conference on modeling and simulation (AICMS 08). IEEE, Kuala Lumpur, pp 911–916 Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv (CSUR) 35:268–308 Bonabeau E, Dorigo M, Theraulaz G (1999) Swarm intelligence: from natural to artificial systems. Oxford University Press, Oxford Brownlee J (2011) Clever algorithms: nature-inspired programming recipes, 1st edn. Lulu, Raleigh, NC Burke EK, Bykov Y (2008) A late acceptance strategy in hill-climbing for exam timetabling problems. In: PATAT, 2008 Conference. Montreal Castellani M, Pham QT, Pham DT (2012) Dynamic optimisation by a modified bees algorithm. Proc Inst Mech Eng I J Syst Control Eng 226:956–971 Chen S, Wang X (2013) A derivative-free optimization algorithm using sparse grid integration. Am J Comput Math 3:16 Davidovic T, Teodorovic D, Selmic M (2014) Bee colony optimization Part I: the algorithm overview. Yugosl J Oper Res 25:33–56 Dereli T, Das GS (2011) A hybrid ‘bee (s) algorithm’for solving container loading problems. Appl Soft Comput 11:2854–2862 Derrac J, García S, Molina D, Herrera F (2011) A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms. Swarm Evol Comput 1:3–18 Diwold K, Beekman M, Middendorf M (2011) Honeybee optimisation: an overview and a new bee inspired optimisation scheme. In: Panigrahi BK, Shi Y, Lim M-H (eds) Handbook of swarm intelligence. Springer, Berlin, Heidelberg, pp 295–327 Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344:243–278 Engelbrecht AP (2016) Particle swarm optimization with crossover: a review and empirical analysis. Artif Intell Rev 45:131–165 Garnier S, Gautrais J, Theraulaz G (2007) The biological principles of swarm intelligence. Swarm Intell 1:3–31 Ghanbarzadeh A (2007) Bees Algorithm: a novel optimisation tool. Cardiff University, Cardiff Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13:533–549 Glover F, Kochenberger GA (2003) Handbook of metaheuristics. Springer, New York Goldberg DE (1989) Genetic algorithms in search, optimization, and machine learning. Addison-wesley, Menlo Park, CA Hansen P, Mladenović N (2001) Variable neighborhood search: principles and applications. Eur J Oper Res 130:449–467 Hussein WA, Sahran S, Sheikh Abdullah SNH (2014) Patch-Levy-based initialization algorithm for Bees Algorithm. Appl Soft Comput 23:104–121 Hussein WA, Sahran S, Sheikh Abdullah SNH (2015) An improved Bees Algorithm for real parameter optimization. Int J Adv Comput Sci Appl 6:23–39 Hussein WA, Sahran S, Sheikh Abdullah SNH (2016) A fast scheme for multilevel thresholding based on a modified Bees Algorithm. Knowl Based Syst. doi:10.1016/j.knosys.2016.03.010 Idris RM, Kharuddin A, Mustafa M, (2009a) Optimal choice of FACTSdevices for ATC enhancement using Bees Algorithm. Australasian Universities power engineering conference (AUPEC, (2009) IEEE. Adelaide, SA, pp 1–6 Idris RM, Khairuddin A, Mustafa M (2009b) A multi-objective Bees Algorithm for optimum allocation of FACTS devices for restructuredpower system. TENCON 2009–2009 IEEE region 10 conference. IEEE, Singapore, pp 1–6 Imanguliyev A (2013) Enhancements for the Bees Algorithm. Cardiff University, Cardiff Jamil M, Yang X-S (2013) A literature survey of benchmark functions for global optimisation problems. Int J Math Model Numer Optim 4:150–194 Karaboga D, Akay B (2009a) A survey: algorithms simulating bee swarm intelligence. Artif Intell Rev 31:61–85 Karaboga D, Akay B (2009b) A comparative study of artificial bee colony algorithm. Appl Math Comput 214:108–132 Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim 39:459–471 Kennedy J, Eberhart R (1995) Particle swarm optimization. Proceedings of IEEE international conference on neural networks. IEEE, Perth, WA, pp 1942–1948 Kirkpatrick S (1984) Optimization by simulated annealing: quantitative studies. J Stat Phys 34:975–986 Kockanat S, Karaboga N (2015) The design approaches of two-dimensional digital filters based on metaheuristic optimization algorithms: a review of the literature. Artif Intell Rev 44:265–287 Laguna M (1994) A guide to implementing tabu search. Investigación Operativa 4:5–25 Lara C, Flores JJ, Calderón F (2008) Solving a school timetabling problem using a bee algorithm. In: Gelbukh A, Morales EF (eds) MICAI 2008: advances in artificial intelligence. Springer, Berlin, Heidelberg, pp 664–674 Liang J, Qu B, Suganthan P, Chen Q (2014) Problem definitions and evaluation criteria for the CEC 2015 competition on learning-based real-parameter single objective optimization. Zhengzhou University and Nanyang Technological University, Zhengzhou, Singapore Lien L-C, Cheng M-Y (2012) A hybrid swarm intelligence based particle-bee algorithm for construction site layout optimization. Expert Syst Appl 39:9642–9650 Marie-Sainte SL (2015) A survey of particle swarm optimization techniques for solving university examination timetabling problem. Artif Intell Rev 44:537–546 Mastrocinque E, Yuce B, Lambiase A, Packianather MS (2013) A multi-objective optimisation for supply chain network using the Bees Algorithm. Int J Eng Bus Manag 5:1–11 Mathur M, Karale SB, Priye S, Jayaraman V, Kulkarni B (2000) Ant colony approach to continuous function optimization. Ind Eng Chem Res 39:3814–3822 Molga M, Smutnicki C (2005) Test functions for optimization needs, p. 43 Moradi S, Fatahi L, Razi P (2010) Finite element model updating using bees algorithm. Struct Multidiscipl Optim 42:283–291 Muhamad AS, Deris S (2013) An artificial immune system for solving production scheduling problems: a review. Artif Intell Rev 39:97–108 Muhamad Z, Mahmuddin M, Nasrudin MF, Sahran S (2011) Local search manoeuvres recruitment in the Bees Algorithm. In: Proceedings of the 3rd international conference on computing and informatics, Bandung, Indonesia, pp 43–48 Nebti S, Boukerram A (2010) Handwritten digits recognition based on swarm optimization methods. In: Zavoral F, Yaghob J, Pichappan P, El-Qawasmeh E (eds) Networked digital technologies. Springer, Berlin, Heidelberg, pp 45–54 Nguyen K, Nguyen P, Tran N (2012) A hybrid algorithm of harmony search and bees algorithm for a university course timetabling problem. Int J Comput Sci Issues 9:12–17 Otri S (2011) Improving the bees algorithm for complex optimisation problems. Cardiff University, Cardiff Packianather M, Landy M, Pham D (2009) Enhancing the speed of the Bees Algorithm using pheromone-based recruitment. 7th IEEE international conference on industrial informatics (INDIN (2009) IEEE. Cardiff, Wales, pp 789–794 Packianather MS, Kapoor B (2015) A wrapper-based feature selection approach using Bees Algorithm for a wood defect classification system. In: System of systems engineering conference (SoSE), 2015 10th IEEE, pp 498–503 Packianather MS, Yuce B, Mastrocinque E, Fruggiero F, Pham DT, Lambiase A (2014) Novel genetic Bees Algorithm applied to single machine scheduling problem. In: World Automation Congress (WAC), 2014. IEEE, pp 906–911 Passino KM (2002) Biomimicry of bacterial foraging for distributed optimization and control. In: IEEE control systems, pp 52–67 Pham D, Castellani M, Fahmy A (2008a) Learning the inverse kinematics of a robot manipulator using the bees algorithm. Proceedings of the 6th IEEE international conference on industrial informatics (INDIN 2008). IEEE, Daejeon, pp 493–498 Pham D, Darwish AH (2008) Fuzzy selection of local search sites in the Bees Algorithm. Proceedings of the 4th virtual international conference on intelligent production machines and systems (IPROMS 2008). Cardiff, Wales, pp 1–14 Pham D, Darwish AH (2010) Using the bees algorithm with Kalman filtering to train an artificial neural network for pattern classification. Proc Inst Mech Eng I J Syst Control Eng 224:885–892 Pham D, Ghanbarzadeh A (2007) Multi-objective optimisation using the bees algorithm. Proceedings of the 3rd international virtual conference on intelligent production machines and systems (IPROMS 2007). Whittles, Dunbeath, Scotland, pp 111–116 Pham D, Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M (2006a) The bees algorithm-a novel tool for complex optimisation problems. Proceedings of the 2nd virtual international conference on intelligent production machines and systems (IPROMS 2006). Elsevier Science Ltd, Cardiff, pp 454–459 Pham D, Otri S, Ghanbarzadeh A, Koc E (2006b) Application of the bees algorithm to the training of learning vector quantisation networks for control chart pattern recognition. In: Proceedings of information and communication technologies (ICTTA’06) IEEE, Damascus, pp 1624–1629 Pham D, Ghanbarzadeh A, Koc E, Otri S (2006c) Application of the bees algorithm to the training of radial basis function networks for control chart pattern recognition. In: Proceedings of 5th CIRP international seminar on intelligent computation in manufacturing engineering (CIRP ICME’06) Ischia, Italy, pp 711–716 Pham D, Koç E (2010) Design of a two-dimensional recursive filter using the bees algorithm. Int J Autom Comput 7:399–402 Pham D, Koc E, Lee J, Phrueksanant J (2007a) Using the bees algorithm to schedule jobs for a machine. Proceedings of the 8th international conference on laser metrology, CMM and machine tool performance (LAMDAMAP). Euspen, Cardiff, UK, pp 430–439 Pham D, Otri S, Darwish AH (2007b) Application of the Bees Algorithm to PCB assembly optimisation. Proceedings of the 3rd virtual international conference on intelligent production machines and systems (IPROMS 2007). Whittles, Dunbeath, Scotland, pp 511–516 Pham D, Pham Q, Ghanbarzadeh A, Castellani M (2008b) Dynamic optimisation of chemical engineering processes using the bees algorithm. Proceedings of the 17th international federation of automatic control (IFAC) World Congress. Seoul, Korea, pp 6100–6105 Pham DT, Castellani M (2009) The bees algorithm: modelling foraging behaviour to solve continuous optimization problems. Proc Inst Mech Eng C J Mech Eng Sci 223:2919–2938 Pham Q, Pham D, Castellani M (2012) A modified bees algorithm and a statistics-based method for tuning its parameters. Proc Inst Mech Eng I J Syst Control Eng 226:287–301 Prakasam A, Savarimuthu N (2016) Metaheuristic algorithms and probabilistic behaviour: a comprehensive analysis of Ant Colony Optimization and its variants. Artif Intell Rev 45:97–130 Reynolds AM, Smith AD, Reynolds DR, Carreck NL, Osborne JL (2007) Honeybees perform optimal scale-free searching flights when attempting to locate a food source. J Exp Biol 210:3763–3770 Rios LM, Sahinidis NV (2013) Derivative-free optimization: a review of algorithms and comparison of software implementations. J Glob Optim 56:1247–1293 Sadiq AT, Hamad AG (2010) BSA: a hybrid bees’ simulated annealing algorithm to solve optimization & NP-complete problems. Eng Technol J 28:271–281 Seeley TD (2002) When is self-organization used in biological systems? Biol Bull 202:314–318 Shatnawi N (2013) Memory based Bees Algorithm with Levy-flights for multilevel image thresholding. Universiti Kebangsaan Malaysia, Bangi Shatnawi N, Sahran S, Faidzul M (2013) A memory-based Bees Algorithm: an enhancement. J Appl Sci 13:497–502 Srinivasan S, Ramakrishnan S (2011) Evolutionary multi objective optimization for rule mining: a review. Artif Intell Rev 36:205–248 Stützle TG (1999) Local search algorithms for combinatorial problems: analysis, improvements, and new applications. Infix Sankt Augustin, Germany Suganthan PN, Hansen N, Liang JJ, Deb K, Chen Y-P, Auger A, Tiwari S (2005) Problem definitions and evaluation criteria for the CEC 2005 special session on real-parameter optimization. Nanyang Technological University, Singapore and KanGAL Talbi E-G (2009) Metaheuristics: from design to implementation. Wiley, Hoboken, NJ Teodorović D, Šelmić M, Davidović T (2015) Bee colony optimization part II: the application survey. Yugosl J, Oper Res 25:185–219 Weise T (2009) Global optimization algorithms-theory and application, 2nd edn. Thomas Weise Yang X-S (2009) Firefly algorithms for multimodal optimization. In: Watanabe O, Zeugmann T (eds) Stochastic algorithms: foundations and applications. Springer, Berlin, Heidelberg, pp 169–178 Yang X-S (2011) Review of meta-heuristics and generalised evolutionary walk algorithm. Int J Bio Inspired Comput 3:77–84 Yao X, Liu Y, Lin G (1999) Evolutionary programming made faster. IEEE Trans Evol Comput 3:82–102 Yuce B, Mastrocinque E, Lambiase A, Packianather MS, Pham DT (2014) A multi-objective supply chain optimisation using enhanced Bees Algorithm with adaptive neighbourhood search and site abandonment strategy. Swarm Evol Comput 18:71–82 Yuce B, Pham D, Packianather M, Mastrocinque E (2015a) An enhancement to the Bees Algorithm with slope angle computation and Hill Climbing Algorithm and its applications on scheduling and continuous-type optimisation problem. Prod Manuf Res 3:3–19 Yuce B, Mastrocinque E, Packianather MS, Lambiase A, Pham DT (2015b) The Bees Algorithm and its applications. In: Vasant P (ed) Handbook of research on artificial intelligence techniques and algorithms. Information Science Reference, Hershey, PA, pp 122–151. doi:10.4018/978-1-4666-7258-1.ch004 Yuce B, Packianather MS, Mastrocinque E, Pham DT, Lambiase A (2013) Honey bees inspired optimization method: the Bees Algorithm. Insects 4:646–662 Zhang N, Wunsch DC (2003) An extended Kalman filter (EKF) approach on fuzzy system optimization problem. In: The 12th IEEE international conference on fuzzy systems (FUZZ’03) IEEE, pp 1465–1470