Bees algorithm

In computer science and operations research, the Bees Algorithm is a population-based search algorithm which was developed in 2005.[1] It mimics the food foraging behaviour of honey bee colonies. In its basic version the algorithm performs a kind of neighbourhood search combined with global search, and can be used for both combinatorial optimization and continuous optimization. The only condition for the application of the Bees Algorithm is that some measure of topological distance between the solutions is defined. The effectiveness and specific abilities of the Bees Algorithm have been proven in a number of studies.[2][3]

The Bees Algorithm is inspired by the foraging behaviour of honey bees.

Honey bees foraging strategy in nature

A colony of honey bees can extend itself over long distances (over 14 km) [4] and in multiple directions simultaneously to harvest nectar or pollen from multiple food sources (flower patches). A small fraction of the colony constantly searches the environment looking for new flower patches. These scout bees move randomly in the area surrounding the hive, evaluating the profitability (net energy yield) of the food sources encountered.[4] When they return to the hive, the scouts deposit the food harvested. Those individuals that found a highly profitable food source go to an area in the hive called the “dance floor”, and perform a ritual known as the waggle dance.[5] Through the waggle dance a scout bee communicates the location of its discovery to idle onlookers, which join in the exploitation of the flower patch. Since the length of the dance is proportional to the scout’s rating of the food source, more foragers get recruited to harvest the best rated flower patches. After dancing, the scout returns to the food source it discovered to collect more food. As long as they are evaluated as profitable, rich food sources will be advertised by the scouts when they return to the hive. Recruited foragers may waggle dance as well, increasing the recruitment for highly rewarding flower patches. Thanks to this autocatalytic process, the bee colony is able to quickly switch the focus of the foraging effort on the most profitable flower patches.[4]

The Bees Algorithm

The Bees Algorithm [2][6] mimics the foraging strategy of honey bees to look for the best solution to an optimisation problem. Each candidate solution is thought of as a food source (flower), and a population (colony) of n agents (bees) is used to search the solution space. Each time an artificial bee visits a flower (lands on a solution), it evaluates its profitability (fitness).
The Bees Algorithm consists of an initialisation procedure and a main search cycle which is iterated for a given number T of times, or until a solution of acceptable fitness is found. Each search cycle is composed of five procedures: recruitment, local search, neighbourhood shrinking, site abandonment, and global search.

The pseudocode for the standard Bees Algorithm[2]
   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])}

In the initialisation routine ns scout bees are randomly placed in the search space, and evaluate the fitness of the solutions where they land. For each solution, a neighbourhood (called flower patch) is delimited.
In the recruitment procedure, the scouts that visited the nb≤ns fittest solutions (best sites) perform the waggle dance. That is, they recruit foragers to search further the neighbourhoods of the most promising solutions. The scouts that located the very best ne≤nb solutions (elite sites) recruit nre foragers each, whilst the remaining nb-ne scouts recruit nrb≤nre foragers each. Thus, the number of foragers recruited depends on the profitability of the food source.
In the local search procedure, the recruited foragers are randomly scattered within the flower patches enclosing the solutions visited by the scouts (local exploitation). If any of the foragers in a flower patch lands on a solution of higher fitness than the solution visited by the scout, that forager becomes the new scout. If no forager finds a solution of higher fitness, the size of the flower patch is shrunk (neighbourhood shrinking procedure). Usually, flower patches are initially defined over a large area, and their size is gradually shrunk by the neighbourhood shrinking procedure. As a result, the scope of the local exploration is progressively focused on the area immediately close to the local fitness best. If no improvement in fitness is recorded in a given flower patch for a pre-set number of search cycles, the local maximum of fitness is considered found, the patch is abandoned (site abandonment), and a new scout is randomly generated.
As in biological bee colonies,[4] a small number of scouts keeps exploring the solution space looking for new regions of high fitness (global search). The global search procedure re-initialises the last ns-nb flower patches with randomly generated solutions.
At the end of one search cycle, the scout population is again composed of ns scouts: nr scouts produced by the local search procedure (some of which may have been re-initialised by the site abandonment procedure), and ns-nb scouts generated by the global search procedure. The total artificial bee colony size is n=ne•nre+(nb-ne)•nrb+ns (elite sites foragers + remaining best sites foragers + scouts) bees.

Applications

This is a dynamic list and may never be able to satisfy particular standards for completeness. You can help by expanding it with reliably sourced entries.

The Bees Algorithm has found many applications in engineering, such as:

Optimisation of classifiers / clustering systems [7][8][9]

Manufacturing[10][11][12][13][14][15]

Control[16][17][18][19]

Bioengineering[20][21]

Other optimisation problems[22][23][24][25][26]

Multi-objective optimisation[27][28][29][30]

See also

References

  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.
  2. 1 2 3 Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems. Proc. ImechE, Part C, 223(12), 2919-2938.
  3. ↑ Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms, Soft Computing, 1-33.
  4. 1 2 3 4 Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics. 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, pp. 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, 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 W., Zhou Z., Pham D.T., Liu Q., Ji C., Meng W. (2012), Quality of service in manufacturing networks: a service framework and its implementation, International Journal Advanced Manufacturing Technology, 63(9-12), 1227-1237.
  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 G.A., Goles E. (2013), Learning gene regulatory networks using the bees algorithm, Neural Computing and Applications, 22(1), 63-70.
  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ç E. (2011), Design of a two-dimensional recursive filter using the bees algorithm, International Journal Automation and Computing 7(3) 399-402.
  25. ↑ Kavousi A., Vahidi B., Salehi R., Bakhshizadeh M.K., Farokhnia N., Fathi S.H. (2012), Application of the Bee Algorithm for Selective Harmonic Elimination Strategy in Multilevel Inverters, IEEE Transactions on Power Electronics 27(4) 1689-1696.
  26. ↑ 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.
  27. ↑ Morsali, Roozbeh; Mohammadi, Mohsen; Maleksaeedi, Iman; Ghadimi, Noradin. "A new multiobjective procedure for solving nonconvex environmental/economic power dispatch". Complexity 20 (2): 47–62. doi:10.1002/cplx.21505.
  28. ↑ Lee J.Y., Darwish A.H. (2008), Multi-objective Environmental/Economic Dispatch Using the Bees Algorithm with Weighted Sum, Proceedings of the EU-Korea Conference on Science and Technology (EKC2008), Ed. S.D. Yoo, Heidelberg, D, Springer Berlin Heidelberg, 267-274.
  29. ↑ 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.
  30. ↑ 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.

External links

This article is issued from Wikipedia - version of the Friday, April 29, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.