In computer science and operations research, the bees algorithm is a population-based search algorithm first developed in 2005. It mimics the food foraging behaviour of swarms of honey bees. In its basic version, the algorithm performs a kind of neighbourhood search combined with search and can be used for both combinatorial optimization and functional optimisation.
The foraging process in nature
A colony of honey bees can extend itself over long distances (up to 14 km) and in multiple directions simultaneously to exploit a large number of food sources. A colony prospers by deploying its foragers to good fields. In principle, flower patches with plentiful amounts of nectar or pollen that can be collected with less effort should be visited by more bees, whereas patches with less nectar or pollen should receive fewer bees.
The foraging process begins in a colony by scout bees being sent to search for promising flower patches. Scout bees move randomly from one patch to another. During the harvesting season, a colony continues its exploration, keeping a percentage of the population as scout bees.
When they return to the hive, those scout bees that found a patch which is rated above a certain quality threshold (measured as a combination of some constituents, such as sugar content) deposit their nectar or pollen and go to the “dance floor” to perform a dance known as the waggle dance.
This dance is essential for colony communication, and contains three pieces of information regarding a flower patch: the direction in which it will be found, its distance from the hive and its quality rating (or fitness). This information helps the colony to send its bees to flower patches precisely, without using guides or maps. Each individual’s knowledge of the outside environment is gleaned solely from the waggle dance. This dance enables the colony to evaluate the relative merit of different patches according to both the quality of the food they provide and the amount of energy needed to harvest it. After waggle dancing inside the hive, the dancer (i.e. the scout bee) goes back to the flower patch with follower bees that were waiting inside the hive. More follower bees are sent to more promising patches. This allows the colony to gather food quickly and efficiently.
While harvesting from a patch, the bees monitor its food level. This is necessary to decide upon the next waggle dance when they return to the hive. If the patch is still good enough as a food source, then it will be advertised in the waggle dance and more bees will be recruited to that source.
The Bees Algorithm
The Bees Algorithm is an optimisation algorithm inspired by the natural foraging behaviour of honey bees to find the optimal solution. The algorithm requires a number of parameters to be set, namely: number of scout bees (n), number of sites selected out of n visited sites (m), number of best sites out of m selected sites (e), number of bees recruited for best e sites (nep), number of bees recruited for the other (m-e) selected sites (nsp), initial size of patches (ngh) which includes site and its neighbourhood and stopping criterion.
The pseudo code for the bees algorithm in its simplest form: 1. Initialise population with random solutions. 2. Evaluate fitness of the population. 3. While (stopping criterion not met) //Forming new population. 4. Select sites for neighbourhood search. 5. Recruit bees for selected sites (more bees for best e sites) and evaluate fitnesses. 6. Select the fittest bee from each patch. 7. Assign remaining bees to search randomly and evaluate their fitnesses. 8. End While.
In first step, the bees algorithm starts with the scout bees (n) being placed randomly in the search space. In step 2, the fitnesses of the sites visited by the scout bees are evaluated. In step 4, bees that have the highest fitnesses are chosen as “selected bees” and sites visited by them are chosen for neighbourhood search. Then, in steps 5 and 6, the algorithm conducts searches in the neighbourhood of the selected sites, assigning more bees to search near to the best e sites. The bees can be chosen directly according to the fitnesses associated with the sites they are visiting. Alternatively, the fitness values are used to determine the probability of the bees being selected. Searches in the neighbourhood of the best e sites which represent more promising solutions are made more detailed by recruiting more bees to follow them than the other selected bees. Together with scouting, this differential recruitment is a key operation of the Bees Algorithm. However, in step 6, for each patch only the bee with the highest fitness will be selected to form the next bee population. In nature, there is no such a restriction. This restriction is introduced here to reduce the number of points to be explored. In step 7, the remaining bees in the population are assigned randomly around the search space scouting for new potential solutions. These steps are repeated until a stopping criterion is met. At the end of each iteration, the colony will have two parts to its new population – those that were the fittest representatives from a patch and those that have been sent out randomly.
The Bees Algorithm has found many applications in engineering, such as:
- Training neural networks for pattern recognition.
- Forming manufacturing cells.
- Scheduling jobs for a production machine.
- Solving continuous problems and engineering optimization.
- Finding multiple feasible solutions to a preliminary design problems.
- Data clustering
- Optimising the design of mechanical components.
- Multi-Objective Optimisation.
- Tuning a fuzzy logic controller for a robot gymnast.
- Computer Vision and Image Analysis.
In Job Shop Scheduling
The honey bees' effective foraging strategy can be applied to job shop scheduling problems.
A feasible solution in a job shop scheduling problem is a complete schedule of operations specified in the problem. Each solution can be thought of as a path from the hive to the food source. The figure on the right illustrates such an analogy
The makespan of the solution is analogous to the profitability of the food source in terms of distance and sweetness of the nectar. Hence, the shorter the makespan, the higher the profitability of the solution path.
We can thus maintain a colony of bees, where each bee will traverse a potential solution path. Once a feasible solution is found, each bee will return to the hive to perform a waggle dance. The waggle dance will be represented by a list of "elite solutions", from which other bees can choose to follow another bee's path. Bees with a better makespan will have a higher probability of adding its path to the list of "elite solutions", promoting a convergence to an optimal solution.
Using the above scheme, the natural honey bee's self organizing foraging strategy can be applied to the job shop scheduling problem.
- Artificial bee colony algorithm
- Ant colony optimization algorithms
- Evolutionary computation
- Intelligent Water Drops
- Invasive weed optimization algorithm
- Lévy flight foraging hypothesis
- Manufacturing Engineering Centre
- Particle swarm optimization
- Swarm intelligence
- 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
- Duc Truong Pham, Ashraf Afify, Ebubekir Koc "Manufacturing cell formation using the Bees Algorithm". IPROMS 2007 Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.
- D. T. Pham, E. Koç, J. Y. Lee, and J. Phrueksanant, Using the Bees Algorithm to schedule jobs for a machine, Proc Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, LAMDAMAP, Euspen, UK, Cardiff, p. 430–439, 2007.
- Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S., and M.Zaidi "The Bees Algorithm – A Novel Tool for Complex Optimisation Problems"", Proceedings of IPROMS 2006 Conference, pp.454–461
- Von Frisch K. Bees: Their Vision, Chemical Senses and Language. (Revised edn) Cornell University Press, N.Y., Ithaca, 1976.
- Seeley TD. The Wisdom of the Hive: The Social Physiology of Honey Bee Colonies. Massachusetts: Harvard University Press, Cambridge, 1996.
- Bonabeau E, Dorigo M, and Theraulaz G. Swarm Intelligence: from Natural to Artificial Systems. Oxford University Press, New York, 1999.
- Camazine S, Deneubourg J, Franks NR, Sneyd J, Theraula G and Bonabeau E. Self-Organization in Biological Systems. Princeton: Princeton University Press, 2003.
- D. T. Pham, E. Koç, A. Ghanbarzadeh, and S. Otri, Optimisation of the weights of multi-layered perceptrons using the Bees Algorithm, Proc 5th International Symposium on Intelligent Manufacturing Systems, Turkey, 2006.
- D. T. Pham, A. Ghanbarzadeh, E. Koç, and S. Otri, Application of the Bees Algorithm to the training of radial basis function networks for control chart pattern recognition, Proc 5th CIRP International Seminar on Intelligent Computation in Manufacturing Engineering (CIRP ICME '06), Ischia, Italy, 2006.
- D. T. Pham, S. Otri, A. Ghanbarzadeh, and E. Koç, Application of the Bees Algorithm to the training of learning vector quantisation networks for control chart pattern recognition, Proc Information and Communication Technologies (ICTTA'06), Syria, p. 1624–1629, 2006.
- D. T. Pham, A. J. Soroka, A. Ghanbarzadeh, E. Koç, S. Otri, and M. Packianather, Optimising neural networks for identification of wood defects using the Bees Algorithm, Proc 2006 IEEE International Conference on Industrial Informatics, Singapore, 2006.
- Pham D. T., Zaidi Muhamad, Massudi Mahmuddin, Afshin ghanbarzadeh, Ebubekir Koc, Sameh Otri. Using the bees algorithm to optimise a support vector machine for wood defect classification. IPROMS 2007 Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.""
- Yang X.S., "Engineering Optimizations Via Nature-Inspired Virtual Bee Algorithms". Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, LECTURE NOTES IN COMPUTER SCIENCE 3562:2005, pp. 317-323 , Springer Berlin / Heidelberg.
- D. T. Pham, M. Castellani, and A. Ghanbarzadeh, Preliminary design using the Bees Algorithm, Proc Eighth International Conference on Laser Metrology, CMM and Machine Tool Performance, LAMDAMAP, Euspen, UK, Cardiff, p. 420–429, 2007.
- D. T. Pham, S. Otri, A. A. Afify, M. Mahmuddin, and H. Al-Jabbouli, Data clustering using the Bees Algorithm, Proc 40th CIRP Int. Manufacturing Systems Seminar, Liverpool, 2007.
- D. T. Pham, A. J. Soroka, E. Koç, A. Ghanbarzadeh, and S. Otri, Some applications of the Bees Algorithm in engineering design and manufacture, Proc Int. Conference on Manufacturing Automation (ICMA 2007), Singapore, 2007.
- Pham D.T., Ghanbarzadeh A. "Multi-Objective Optimisation using the Bees Algorithm"", Proceedings of IPROMS 2007 Conference
- D.T Pham, Ahmed Haj Darwish, E.E Eldukhri, Sameh Otri. "Using the Bees Algorithm to tune a fuzzy logic controller for a robot gymnast."", Proceedings of IPROMS 2007 Conference
- Olague, G. and Puente, C. 2006. Parisian evolution with honeybees for three-dimensional reconstruction. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (Seattle, Washington, USA, July 08 – 12, 2006). GECCO '06. ACM, New York, NY, 191–198. doi:10.1145/1143997.1144030
- Olague, G.; Puente, C. Honeybees as an Intelligent based Approach for 3D Reconstruction. ICPR 2006. 18th International Conference on Pattern Recognition. 2006, Volume 1, Issue , 0-0 0 Page(s):1116–1119. doi:10.1109/ICPR.2006.632
- Olague, G. Puente, C.. The Honeybee Search Algorithm for Three-Dimensional Reconstruction. 8 th European Workshop on Evolutionary Computation in Image Analysis and Signal Processing. Lecture Notes in Computer Science 3907. Springer-Verlag. pp. 427–437. EvoIASP2006. Best Paper Award for EvoIASP 2006. doi:10.1007/11732242, ISBN 978-3-540-33237-4
- Chong C, Low MYH, Sivakumar AI and Gay KL (2006) "A Bee Colony Optimization Algorithm to Job Shop Scheduling" Simulation Conference, WSC 06. Monterey, CA.
- Pham D.T., Ashraf Afify, Ebubekir Koc "Manufacturing cell formation using the Bees Algorithm". IPROMS 2007 Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.
- Nakrani S. and Tovey C., "On Honey Bees and Dynamic Server Allocation in Internet Hosting Centers". Adaptive Behaviour, 2004. 12(3-4):pp. 223–240.
- Tovey C., "The Honey Bee Algorithm: A Biological Inspired Approach to Internet Server Optimization". Engineering Enterprise, the Alumni Magazine for ISyE at Georgia Institute of Technology, Spring 2004, pp. 13–15.
- Yang X.S., "Engineering Optimizations Via Nature-Inspired Virtual Bee Algorithms". Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, LECTURE NOTES IN COMPUTER SCIENCE 3562:2005, pp. 317–323, Springer Berlin / Heidelberg.
- Chin Soon Chong, Malcolm Yoke Hean Low, Appa Iyer Sivakumar and Kheng Leng Gay, "A bee colony optimization algorithm to job shop scheduling", In Proceedings of the 2006 Winter Simulation Conference, December 3–6, 2006, Monterey, CA USA, pp. 1954–1961.
- Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S., and M.Zaidi "The Bees Algorithm – A Novel Tool for Complex Optimisation Problems"", Proceedings of IPROMS 2006 Conference, pp.454-461
- Pham D.T., Ghanbarzadeh A. "Multi-Objective Optimisation using the Bees Algorithm"", Proceedings of IPROMS 2007 Conference
- Pham D.T., Koç E.,Ghanbarzadeh A., Otri S. "Optimisation of the Weights of Multi-Layered Perceptrons Using the Bees Algorithm". IMS’06 Intelligent Manufacturing Systems Conference. Sakarya, Turkey.
- Pham D.T., Ghanbarzadeh A., Koc E., and Otri S. "Application of the Bees Algorithm to the Training of Radial Basis Function Networks for Control Chart Pattern Recognition". Proc 5th CIRP International Seminar on Intelligent Computation in Manufacturing Engineering (CIRP ICME '06). 2006. Ischia, Italy, pp. 711–716.
- Pham D.T., Soroka A.J., Koç E.,Ghanbarzadeh A., Otri S., Packianather M. "Optimising Neural Networks for Identification of Wood Defects Using the Bees Algorithm". 4th International IEEE Conference on Industrial Informatics.INDIN’06 16–18 August 2006, Singapore.
- NewScientist: The Honeybee Algorithm award Best Paper for EvoIASP 2006
- The Bees Algorithm – First Prize-winning Poster
- BBC Interview Records
- MEC Bees won ‘best communication’ prize at INTEGR8OR
- Boffins put dancing bees to work – BBC News