Bee Colony Optimization - part I: The algorithm overview
DOI:
https://doi.org/10.2298/YJOR131011017DKeywords:
Meta-heuristics, Swarm Intelligence, Foraging of Honey BeesAbstract
This paper is an extensive survey of the Bee Colony Optimization (BCO) algorithm, proposed for the first time in 2001. BCO and its numerous variants belong to a class of nature-inspired meta-heuristic methods, based on the foraging habits of honeybees. Our main goal is to promote it among the wide operations research community. BCO is a simple, but efficient meta-heuristic technique that has been successfully applied to many optimization problems, mostly in transport, location and scheduling fields. Firstly, we shall give a brief overview of the other meta-heuristics inspired by bees’ foraging principles pointing out the differences between them. Then, we shall provide the detailed description of the BCO algorithm and its modifications, including the strategies for BCO parallelization, and giving the preliminary results regarding its convergence. The application survey is elaborated in Part II of our paper.References
Abbass, H.A., “MBO: Marriage in honeybees optimization - a haplometrosis polygynous swarming approach”, Proceedings of the Congress on Evolutionary Computation, Seoul, South Korea, 1 (2001) 207–214.
Afshar, A., Bozorg Haddad, O., Mariño, M.A., and Adams, B.J., “Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operation”, J. Franklin Institute, 344(5) (2007) 452–462.
Anantasate, S., Chokpanyasuwan, C., Pattaraprakorn, W., and Bhasaputra, P., “Multi-objective optimal placement of distributed generation using bee colony optimization”, GMSARN International Journal, 3 (2009) 55–64.
Banharnsakun, A., Achalakul, T., and Sirinaovakul, B., “Artificial bee colony algorithm on distributed environments”, Proc. Second World Congress on Nature and Biologically Inspired Computing (NaBIC’10), Fukuoka, 1 (2010) 13–18.
Beni, G., and Wang, J., “Swarm intelligence”, Proc. Seventh Annual Meeting of the Robotics Society of Japan, RSJ Press, Tokyo, 1 (1989) 425–428.
Bonabeau, E., Dorigo, M., and Theraulaz, G., Swarm Intelligence, Oxford University Press, Oxford, 1997.
Camazine, S., and Sneyd, J., “A model of collective nectar source by honeybees: self-organization through simple rules”, Journal of Theoretical Biology, 149 (1991) 547–571.
Chong, C. S., Low, M. Y. H., Sivakumar, A. I., and Gay, K. L., “A bee colony optimization algorithm to job shop scheduling”, In Proceedings of the Winter Simulation Conference, Washington, DC, 1 (2006) 1954–1961.
Crainic, T. G., Davidović, T., and Ramljak, D., “Designing parallel meta-heuristic methods”, In M. Despotović-Zrakić, V. Milutinović, and A. Belić, editors, High Performance and Cloud Computing in Science and Education, IGI-Global, (2014) 260–280.
Davidović, T., Jakšić, T., Ramljak, D., Šelmić, M., and Teodorović, D., “MPI parallelization strategies for bee colony optimization”, Optimization, Special Issue entitled “Advances in Discrete Optimization” dedicated to BALCOR 2011, 62(8) (2013) 1113–1142.
Davidović, T., Ramljak, D., Šelmić, M., and Teodorović, D., “MPI parallelization of bee colony optimization”, Proc. 1st International Symposium & 10th Balkan Conference on Operational Research, Thessaloniki, Greece, 2 (2011) 193–200.
Davidović, T., Ramljak, D., Šelmić, M., and Teodorović, D., “Bee colony optimization for the p-center problem”, Computers and Operations Research, 38(10) (2011) 1367–1376.
Davidović, T., Šelmić, M., and Teodorović, D., “Scheduling independent tasks: Bee colony optimization approach”, Proc. 17th Mediterranean Conference on Control and Automation, Makedonia Palace, Thessaloniki, Greece, 1 (2009) 1020–1025.
Davidović, T., Šelmić, M., Teodorović, D., and Ramljak, D., “Bee colony optimization for scheduling independent tasks to identical processors”, J. Heur., 18(4) (2012) 549–569.
Dimitrijević, B., Teodorović, D., Simić, V., and Šelmić, M., “Bee colony optimization approach to solving the anticovering location problem”, Journal of Computing in Civil Engineering, 26(6) (2011) 759–768.
Drias, H., Sadeg, S., and Yahi, S., “Cooperative bees swarm for solving the maximum weighted satisfiability problem”, LNCS: Computational Intelligence and Bioinspired Systems, 3512 (2005) 318–325.
Edara, P., Šelmić, M., and Teodorović, D., “Heuristic solution algorithms for a traffic sensor optimization problem”, INFORMS 2008, Washington D.C., Oct. 12–15, (2008).
Fonseca, R., Paluszewski, M., and Winter, P., “Protein structure prediction using bee colony optimization metaheuristic”, J. Math. Model. Alg., 9(2) (2010) 181–194.
Gutjahr, W.J., “Convergence analysis of metaheuristics”, In V. Maniezzo, T. Stützle, and S. Voss, editors, Matheuristics: hybridizing metaheuristics and mathematical programming, Springer, 10 (2009) 159–187.
Jakšić Krüger, T., “On the convergence of the bee colony optimization meta-heuristic”, Proc. Fourth Symposium “Mathematics and Applications”, Faculty of Mathematics, University of Belgrade, May, 24–25, Serbia (in Serbian), IV(1) (2013) 176–187.
Jakšić Krüger, T., Davidović, T., Teodorović, D., and Šelmić, M., “The bee colony optimization algorithm and its convergence”, International Journal of Bio-Inspired Computation, (accepted), (2014).
Karaboga, D., “An idea based on honeybee swarm for numerical optimization”, Technical report, Erciyes University, Engineering Faculty Computer Engineering Department Kayseri/Turkiye, (2005).
Karaboga, D., and Akay, B., “A survey: Algorithms simulating bee swarm intelligence”, Artificial Intelligence Review, 31 (2009) 61–85.
Karaboga, D., Gorkemli, B., Ozturk, C., and Karaboga, N., “A comprehensive survey: Artificial bee colony (ABC) algorithm and applications”, Artificial Intelligence Review, 42(1) (2014) 21–57.
Kaufmann, A., and Gupta, M., Introduction to Fuzzy Arithmetic, New York: Van Nostrand Reinhold Company, (1988).
Kovač, N., “Bee colony optimization algorithm for the minimum cost berth allocation problem”, Proc. XIBalkan Conference on Operational Research (BALCOR, 2013), Sept. 07–11, Beograd–Zlatibor, Serbia, 1 (2013) 245-254.
Lučić, P., and Teodorović, D., “Bee system: Modeling combinatorial optimization transportation engineering problems by swarm intelligence”, Preprints of the TRISTAN IV Triennial Symposium on Transportation Analysis, Sao Miguel, Azores Islands, (2001) 441–445.
Lučić, P., and Teodorović, D., “Transportation modeling: An artificial life approach”, Proc. 14th IEEE International Conference on Tools with Artificial Intelligence, Washington, DC, (2002) 216–223.
Lučić, P., and Teodorović, D., “Computing with bees: Attacking complex transportation engineering problems”, International Journal on Artificial Intelligence Tools, 12(3) (2003) 375–394.
Lučić, P., and Teodorović, D., “Vehicle routing problem with uncertain demand at nodes: The bee system and fuzzy logic approach”, In J. L. Verdegay, editor, Fuzzy Sets based Heuristics for Optimization, Physica Verlag: Berlin Heidelberg, (2003) 67–82.
Maksimović, P., and Davidović, T., “Parameter calibration in the bee colony optimization algorithm”, Proc. XI Balkan Conference on Operational Research (BALCOR 2013), Sept. 07–11, Beograd–Zlatibor, Serbia, 1 (2013) 263–272.
Marković, G., Teodorović, D., and Aćimović-Raspopović, V., “Routing and wavelength assignment in all-optical networks based on the bee colony optimization”, AI Commun., 20(4) (2007) 273–285.
McFadden, D., “Conditional logit analysis of quantitative choice behavior”, In P. Zaremmbka, editor, Frontier of Econometrics, Academic Press, New York, (1973).
Nakrani, S., and Tovey, C., “On honey bees and dynamic server allocation in internet hosting centers”, Adapt. Syst., 12(3–4) (2004) 223–240.
Narasimhan, H., “Parallel artificial bee colony (PABC) algorithm”, Proc. VIII International Conference on Computer Information Systems and Industrial Management (CISIM, 2009), World Congress on Nature and Biologically Inspired Computing (NaBIC’09), Coimbatore, (2009).
Nikolić, M., and Teodorović, D., “Empirical study of the bee colony optimization (BCO) algorithm”, Expert Systems with Applications, 40(11) (2013) 4609–4620.
Nikolić, M., and Teodorović, D., “Transit network design by bee colony optimization”, Expert Systems with Applications, 40(15) (2013) 5945–5955.
Parpinelli, R. S., Benitez, C. M. V., and Lopes, H. S., “Parallel approaches for the artificial bee colony algorithm”, In B. K. Panigrahi, Y. Shi, and M-H. Lim, editors, Handbook of Swarm Intelligence: Concepts, Principles and Applications, volume Series: Adaptation, Learning, and Optimization, Springer, Berlin, Germany, 8 (2011), 329–346.
Pham, D. T., Ghanbarzadeh, A., Koc, E., Otri, S., and Zaidi, M., “The bees algorithm - a novel tool for complex optimisation problems”, Proc. 2nd Virtual International Conference on Intelligent Production Machines and Systems (IPROMS 2006), Elsevier, Cardiff, Wales, UK, (2006) 454–459.
Pham, D. T., Soroka, A. J., Ghanbarzadeh, A., and Koc, E., “Optimising neural networks for identification of wood defects using the bees algorithm”, Proc. IEEE International Conference on Industrial Informatics, Singapore, (2006) 1346–1351.
Sato, T., and Hagiwara, M., “Bee system: Finding solution by a concentrated search”, Proc. IEEE International Conference on Systems, Man, and Cybernetics: Computational Cybernetics and Simulation, Orlando, FL, USA, (1997) 3954–3959.
Seeley, T., Honeybee Ecology: A Study of Adaptation in Social Life. Princeton Univ. Press, (1995).
Srichandum, S., and Rujirayanyong, T., “Production scheduling for dispatching ready mixed concrete trucks using bee colony optimization”, Amer. J. Engineer. App. Sci., 3(1) (2010) 7–14.
Stojanović, T., Davidović, T., and Ognjanović, Z., “Bee-colony optimization for the satisfiability problem in probabilistic logic”, (submitted for publication), (2013).
Subotić, M., Tuba, M., and Stanarević, N., “Different approaches in parallelization of the artificial bee colony algorithm”, International Journal of Mathematical Models and Methods in Applied Sciences, 5(4) (2011) 755–762.
Suguna, N., and Thanushkodi, K., “A novel rough set reduct algorithm for medical domain based on bee colony optimization”, J. Comput., 2(6) (2010) 49–54.
Šelmić, M., Teodorović, D., and Vukadinović, K., “Locating inspection facilities in traffic networks: An artificial intelligence approach”, Transport. Plan. Techn., 33(6) (2010) 481–493.
Teodorović, D., “Swarm intelligence systems for transportation engineering: Principles and applications”, Transp. Res. Pt. C-Emerg. Technol., 16 (2008) 651–782.
Teodorović, D., “Bee colony optimization (BCO)”, In C. P. Lim, L. C. Jain, and S. Dehuri, editors, Innovations in Swarm Intelligence, Springer-Verlag, Berlin Heidelberg, (2009) 39–60.
Teodorović, D., and Dell’Orco, M., “Bee colony optimization - a cooperative learning approach to complex transportation problems”, In Advanced OR and AI Methods in Transportation. Proceedings of the 10th Meeting of the EURO Working Group on Transportation, Poznan, Poland, (2005) 51–60.
Teodorović, D., and Dell’Orco, M., “Mitigating traffic congestion: Solving the ride-matching problem by bee colony optimization”, Transport. Plan. Techn., 31(2) (2008) 135–152.
Teodorović, D., Šelmić, M., and Mijatović-Teodorović, Lj., “Combining case–based reasoning with bee colony optimization for dose planning in well differentiated thyroid cancer treatment”, Expert Systems with Applications, 40(6) (2013) 2147–2155.
Teodorović, D., and Šelmić, M., “The BCO algorithm for the p-median problem”, Proc. XXXIV Serbian Operations Research Conference, Zlatibor, Serbia (in Serbian), (2007).
Vassiliadis, V., and Dounias, G., “Nature inspired intelligence for the constrained portfolio optimization problem”, In Artificial Intelligence: Theories, Models and Applications, LNCS, vol. 5138, Springer-Verlag, Berlin–Heidelberg, (2008) 431–436.
Wedde, H. F., Farooq, M., and Zhang, Y., “BeeHive: An efficient fault-tolerant routing algorithm inspired by honey bee behavior”, LNCS: Ant Colony Optimization and Swarm Intelligence, 3172 (2004) 83–94.
Wong, L.-P., Hean Low, M. Y., and Chong, C. S., “A bee colony optimization algorithm for traveling salesman problem”, Proc. 2-nd Asia International Conference on Modelling & Simulation, Kuala Lumpur, Malaysia, (2008) 818–823.
Wong, L.-P., Hean Low, M.Y., and Chong, C.S., “An efficient bee colony optimization algorithm for traveling salesman problem using frequency-based pruning”, Proc. 7-th IEEE International Conference on Industrial Informatics, Cardiff, Wales, UK, June 24–26, (2009) 775–782.
Yang, C., Chen, J., and Tu, X., “Algorithm of fast marriage in honey bees optimization and convergence analysis”, Proc. IEEE International Conference on Automation and Logistics, Jinan, China, (2007) 1794–1799.
Yang, X-S., “Engineering optimizations via nature-inspired virtual bee algorithms”, In J. Mira and J. R. Alvarez, editors, Proc. IWINAC International Work-conference on the Interplay between Natural and Artificial Computation, IWINAC 2005, LNCS 3562, Las Palmas de Gran Canaria, Canary Islands, Spain, June 15–18, (2005) 317–323.
Zadeh, L., “Fuzzy sets”, Information and Control, 8 (1965) 338-353.
Downloads
Published
Issue
Section
License
Copyright (c) 2015 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
