Katedra za operaciona istraživanja u saobraćaju
Vesti
>
Bee Colony Optimization (BCO)
The Bee Colony Optimization (BCO) meta-heuristic belongs to the class of Nature-Inspired Algorithms. These algorithms are inspired by various biological and natural processes. Natural systems have become important sources of ideas and models for development of various artificial systems. The popularity of the Nature-Inspired Algorithms is mainly caused by the capability of biological systems to successfully adjust to continually varying environment. Neural networks, evolutionary computation, ant colony optimization, particle swarm optimization, artificial immune systems, and bacteria foraging algorithm are some of the algorithms and concepts that were inspired by nature.
Individuals in various biological systems are engaged in cooperation, collaboration, information exchange, and/or conflicts. In many cases, individuals, that are autonomous in their decision-making, work together with other individuals in order to achieve specific objective. Natural phenomena lecture us that simple individual organisms can create systems able to perform highly complex tasks by interacting with each other.
Few algorithms inspired by bees’ behavior appeared during the last decade (Bee System, BCO algorithm, ABC algorithm, MBO, Bees Algorithm, HBMO algorithm, BeeHive, VBA algorithm). Yonezava and Kikuchi analyzed collective intelligence based on bees’ behavior. Sato and Hagiwara proposed modified genetic algorithm named Bee System. In essence, this algorithm belongs to the class of genetic algorithms. Abbas developed MBO model that is based on the marriage process in honeybees. BeeHive , Artificial Bee Colony (ABC) algorithm and Bees Algorithm are based on foraging behavior in honeybees but all of them use different concepts for algorithm development. An excellent survey of the Bees’ behavior inspired algorithms could be found in Baykasoglu et al.
The BCO meta-heuristic has been proposed quite recently by Lučić and Teodorović. The BCO is inspired by foraging behavior in honeybees. (Lučić and Teodorović used the term “Bee System” in their first paper). The basic plan behind the BCO is to build the multi agent system (colony of artificial bees) able to efficiently solve hard combinatorial optimization problems. The artificial bee colony behaves partially similar, and partially in a different way from bee colonies in nature.
The BCO meta-heuristic has been recently used as a toll for solving large and complex real-world problems. It has been shown that the BCO poses an ability to find high quality solutions of difficult combinatorial problems within a reasonable amount of computer time. The BCO is a stochastic, random-search technique. This technique uses an analogy between the way in which bees in nature search for a food, and the way in which optimization algorithms search for a optimum of (given) combinatorial optimization problems. The basic idea behind the BCO is to build the multi agent system (colony of artificial bees) able to effectively solve difficult combinatorial optimization problems. Artificial bees investigate through the search space looking for the feasible solutions. In order to find better and better solutions, autonomous artificial bees collaborate and exchange information. Using collective knowledge and sharing information among themselves, artificial bees concentrate on more promising areas, and slowly abandon solutions from the less promising areas. Step by step, artificial bees collectively generate and/or improve their solutions. The BCO search is running in iterations until some predefined stopping criteria is satisfied.
The BCO works in a self-organized and decentralized way and therefore represents a good basis for parallelization. It also poses an ability to keep away from becoming trapped in local minima.
Biological Background
Swarm behavior (fish schools, flocks of birds, and herds of land animals) is based on the biological needs of individuals to stay together. When staying together, individuals have a higher probability to stay alive, since predator usually attacks only one individual. Flocks of birds, herds of animals, and fish schools are characterized by collective movement. Herds of animals react at once to changes in the course and speed of their neighbors. Colonies of various social insects (bees, wasps, ants, termites) are also characterized by swarm behavior. Swarm behavior is primarily characterized by autonomy, distributed functioning and self-organizing. The communication systems between individual insects contribute to the pattern called the ‘‘collective intelligence” of the social insect colonies.Swarm Intelligence is the branch of Artificial Intelligence. Swarm Intelligence is based on investigation of actions of individuals in different decentralized systems. These decentralized systems (Multi Agent Systems) are composed of physical individuals (robots, for example) or “virtual” (artificial) ones that communicate among themselves, cooperate, collaborate, exchange information and knowledge and perform some tasks in their environment. When designing Swarm Intelligence models, researchers use some principles of the natural swarm intelligence. The development of artificial systems usually does not involve the entire imitation of natural systems, but explores them while searching for ideas and models.
As we already mentioned, the BCO is inspired by foraging behavior of honeybees. Bees in nature look for a food by exploring the fields in the neighborhood of their hive. They collect and accumulate food for later use by other bees. Typically, in the initial step, some scouts search the region. Completing the search, scout bees will return to the hive and inform their hive-mates about the locations, quantity and quality of available food sources in the areas they have examined. In case they have discovered nectar in the previously investigated locations, scout bees will dance in the so-called “dance floor area” of the hive, in an attempt to “advertise” food locations and encourage the remaining members of the colony to follow their lead. The information about the food quantity is presented using a ritual called a “waggle dance”. If a bee decides to leave the hive to collect nectar, it will follow one of the dancing scout bees to the previously discovered patch of flowers. Upon arrival, the foraging bee takes a load of nectar and returns to the hive relinquishing the nectar to a food storer bee. Several scenarios are then possible for a foraging bee: (1) it can abandon the food location and return to its role of an uncommitted follower; (2) it can continue with the foraging behavior at the discovered nectar source, without recruiting the rest of the colony; (3) it can recruit its hive-mates with the dance ritual before the return to the food location. The bee opts for one of the above alternatives with a certain probability. The described process continues repeatedly, while the bees at a hive accumulate nectar and explore new areas with potential food sources. As several bees may be attempting to recruit their hive-mates at the dance floor area at the same time, it is unclear how a bee resting at a hive decides which dancing bee to follow, although it has been considered that “the recruitment among bees is always a function of the quality of the food source” .
Bee Colony Optimization (BCO) Algorithm
Population of agents (artificial bees) consisting of B bees collaboratively searches for the optimal solution. Every artificial bee generates one solution to the problem. There are two alternating phases (forward pass and backward pass) constituting single step in the BCO algorithm. In each forward pass, every artificial bee explores the search space. It applies a predefined number of moves, which construct and/or improve the solution, yielding to a new solution. For example, let bees Bee 1, Bee 2, …, Bee B participate in the decision-making process on n entities. At each forward pass bees are supposed to select one entity. The possible situation after third forward pass is illustrated on Fig.1.
Fig. 1. An illustration of the third forward pass
Having obtained new partial solutions, the bees go again to the hive and start the second phase, the so-called backward pass. In the backward pass, all artificial bees share information about the quality of their solutions. In nature, bees would return to the hive, perform a dancing ritual, which would inform other bees about the amount of food they have discovered, and the proximity of the patch to the hive. In the search algorithm, the bees announce the quality of the solution, i.e. the value of objective function is computed. Having all solutions evaluated, every bee decides with a certain probability whether it will stay loyal to its solution or not. The bees with better solutions have more chances to keep and advertise their solutions. On the contrary to the bees in nature, artificial bees that are loyal to their partial solutions are at the same time recruiters, i.e. their solutions would be considered by other bees. Once the solution is abandoned by a bee it becomes uncommitted and has to select one of the advertised solutions. This decision is taken with a probability too, so that better advertised solutions have bigger opportunity to be chosen for further exploration. In such a way, within each backward pass all bees are divided into two groups (R recruiters, and remaining B-R uncommitted bees) as it is shown on Fig. 2. Values for R and B-R are changing from one backward pass to another one.
Fig. 2. Recruiting of uncommitted followers
After comparing all generated partial solutions, Bee 2, from the previous example decided to abandon already generated solution and to join Bee B (see Fig.3).
Fig. 3. The possible result of a recruiting process within third backward pass
Bee 2 and Bee B "fly together" along the path already generated by the Bee B. In practice, this means that partial solution generated by Bee B is associated (copied) to Bee 2 also. When they reach the end of that common path, they are free to make an individual decision about the next constructive step to be made. The Bee 1 will keep already generated partial solution without being chosen by any of the uncommitted hive-mates, and therefore, it will perform new constructive step independently. The described situation is illustrated on Fig.4.
Fig. 4. An example of partial solutions after fourth forward
-
The two phases of the search algorithm, forward and backward pass, are alternating in order to generate all required feasible solutions (one for each bee). When all solutions are completed the best one is determined, it is used to update global best solution and an iteration of the BCO is accomplished. At this point all B solutions are deleted, and the new iteration could start. The BCO runs iteration by iteration until a stopping condition is met. The possible stopping conditions could be, for example, the maximum total number of forward/backward passes, the maximum total number of forward/backward passes without the improvement of the objective function, maximum allowed CPU time, etc. At the end, the best found solution (the so called global best) is reported as the final one.
The algorithm parameters whose values need to be set prior the algorithm execution are as follows:
B - The number of bees in the hive;
NC - The number of constructive moves during one forward pass.
At the beginning of the search, all the bees are in the hive. According to the main idea in the current version of the BCO algorithm, the hive is an artificial object, without precise location and does not influence the algorithm execution. It is used only to denote the synchronization points at which bees are exchanging information about the current state of the search.
The pseudocode of the BCO algorithm could be described in the following way:1. Initialization: an empty solution is assigned to every bee;
2. For every bee: // the forward passi. Set k = 1; //counter for constructive moves in the forward pass;
ii. Evaluate all possible constructive moves;
iii. According to evaluation, choose one move using the roulette wheel;
iv. k = k + 1; If k ≤ NC Goto step ii.
3. All bees are back to the hive; // backward pass starts;
4. Evaluate (partial) objective function value for each bee;
5. Every bee decides randomly whether to continue its own exploration and become a recruiter, or to become a follower;
6. For every follower, choose a new solution from recruiters by the roulette wheel;
7. If solutions are not completed Goto step 2;
8. Evaluate all solutions and find the best one;
9. If the stopping condition is not met Goto step 2;
10. Output the best solution found.
Relevant BCO References
- Teodorović, D., “Bee Colony Optimization (BCO)”, in Swarm Intelligence for Knowledge-Based Systems, (Editors: L.C. Jain, S. Dehuri, C.P. Lim), Springer-Verlag, Berlin Heidelberg, 248, 39-60, (2009).
- Teodorović D., Davidović T., Šelmić M., Bee Colony Optimization Overview, (2010) (submitted for publication)
- Lučić, P., Teodorović, D., “Computing with Bees: Attacking Complex Transportation Engineering Problems”, International Journal on Artificial Intelligence Tools, 12, 375-394, (2003).
- Marković, G., Teodorović, D., Aćimović-Raspopović, V., "Routing and wavelength assignment in all-optical networks based on the bee colony optimization", AI Communications-European Journal of Artificial Intelligence, 20, 273 - 285,(2007).
- Teodorović, D., Dell’Orco, M., “Mitigatingtraffic congestion: Solving the Ride-Matching Problem by Bee Colony Optimization “, Transportation Planning and Technology, 31, 135-152, (2008).
- Davidović T., Šelmić M., Teodorović D., “Scheduling Independent Tasks: Bee Colony Optimization Approach” , Proceedings of the the 17th Mediterranean Conference on Control and Automation, MED'09, 1020-1025, Thessaloniki, Greece, (2009).