tailieunhanh - Bee colony optimization part I: The algorithm overview

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. | Yugoslav Journal of Operations Research 25 (2015), Number 1, 33–56 DOI: Invited survey BEE COLONY OPTIMIZATION PART I: THE ALGORITHM OVERVIEW ´ Tatjana DAVIDOVIC Mathematical Institute, Serbian Academy of Sciences and Arts tanjad@ ´ Duˇsan TEODOROVIC Faculty of Transport and Traffic Engineering, University of Belgrade dusan@ ˇ ´ Milica SELMI C Faculty of Transport and Traffic Engineering, University of Belgrade Received: October 2013 / Accepted: May 2014 Abstract: 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 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 give the preliminary results regarding its convergence. The application survey is elaborated in Part II of our paper. Keywords: Meta–heuristics, Swarm Intelligence, Foraging of Honey Bees. MSC: 68T20, 90C59, 92D50. 34 ˇ T. Davidovi´c, D. Teodorovi´c, M. Selmi´ c / BCO Part I: The Algorithm Overview 1. INTRODUCTION The nature-inspired algorithms are motivated by a variety of biological and natural processes. Their popularity is based primarily on the ability of biological systems to efficiently adapt to frequently changeable environments. Evolutionary computation, neural networks, ant colony optimization, particle swarm optimization, artificial immune