|
BCO |
|
|
||||
|
In the 1999-2003, the basic concepts of BCO were introduced, under the name Bee System, by Dušan Teodorović (adviser) and Panta Lučić (Ph.D. candidate) while doing research at Virginia Tech. BCO is nature-inspired meta-heuristic developed for efficiently finding solutions of difficult combinatorial optimization problems.
The basic idea behind BCO is to build the multi agent system (colony of artificial bees) that will search for good solutions of various combinatorial optimization problems exploring the principles used by honey bees during nectar collection process. Artificial bee colony usually consists of small number of individuals, but nevertheless, BCO principles are gathered from natural systems. Artificial bees investigate through the search space looking for the feasible solutions. In order to find the best possible 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 ones. 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.
During the evolution of the BCO algorithm authors developed two different approaches. The first approach is based on constructive steps in which bees build solutions step by step. The second and very actual approach of the BCO algorithm is based on the improvement of complete solutions in order to obtain the best possible final solution. In the text to follow we explain both concepts through the general description of the algorithm.
The population of agents consisting of B individuals (artificial bees) is engaged in BCO. The algorithm consists of two alternating phases: forward pass and backward pass (BCO animation). During each forward pass, every artificial bee explores the search space. It applies a predefined number of moves (NC), which construct and/or improve the solution, yielding a new solution. NC is a parameter used to define the frequency of information exchange between bees. Its value depends on each particular problem characteristics. If NC takes small values, then the search process is intensified, since each newly generated part consists of only a few components. The difference between solutions, generated by different bees, is minor. On the other hand, if NC is large, each bee adds more components to its partial solution, thus introducing variety among different solutions.
Suppose we have B bees, namely Bee 1, Bee 2, . . . , Bee B which participate in the decision-making process on n entities. One of the possible situations which may arise after the first forward pass in the case NC = 3 and B = 3 is illustrated in Fig. 1.
Figure 1. An example of partial solutions after the first forward pass, NC = 3, B = 3
Upon obtaining new partial solutions for each bee, the second phase, the so-called backward pass, starts (Fig. 2). During the backward pass, all bees share information about their solutions. In nature, bees would perform a dancing ritual, which would inform other bees about the amount of food they have found, and the proximity of the patch to the hive. In the search algorithm, the quality of each generated solution is determined, i.e. the current value of the objective function is calculated. During the backward pass, every bee decides, with a certain probability, whether it will stay loyal to its solution or not. Contrary to bees in nature, artificial bees that are loyal to their generated solutions are at the same time recruiters, i.e. their solutions are considered by other bees. Once the solution is abandoned the bee becomes uncommitted and has to select one of the advertised solutions. This decision is taken with a probability, such that better advertised solutions have greater opportunities to be chosen for further exploration.
Figure 2. The first backward pass, NC = 3, B = 3
In such a way, within each backward pass all bees are divided into two groups (R recruiters, and the remaining B − R uncommitted bees) as shown in Figure 3.
Figure 3. Dividing bees into two groups (B = 3)
Values for R and B − R change from one backward pass to another. Let us assume that after comparing all generated partial solutions Bee 3 from the previous example decided to abandon its solution, and join Bee 1. The resulting situation is presented in Figure 4.
Bee 1 and Bee 3 “fly together” along the path already generated by Bee 1. In practice, this means that the partial solution generated by Bee 1 is associated (copied) to Bee 3. When they “reach the end of the path”, they are free to make an individual decision about the next constructive step. This actually means that each of them will add different components to the same partial solution. Bee 2 will keep its partial solution without being chosen by any hive-mates and will perform a new constructive step independently.
Figure 4. Recruiting of uncommitted followers and the second forward pass NC = 3, B = 3
The two phases of the search algorithm, namely the forward and backward passes, alternate in order to generate all required complete solutions (one for each bee). At that stage the best solution is determined and an iteration of BCO is completed. The BCO algorithm runs iteration by iteration until a stopping condition is met. A possible stopping condition could be, for example, the maximum number of iterations, the maximum number of iterations without the improvement of the objective function, the maximum allowed CPU time, etc. In the end, the best solution found is reported as the final one. The BCO algorithm parameters whose values need to be set prior the algorithm execution are as follows:
B - The number of bees involved in the search, IT - The number of iteration. NP - The number of forward and backward passes in a single iteration. NC - The number of changes in one forward pass. S - the best known solution
The following is the pseudo code of the BCO algorithm:
procedure BCO(in B, IT, NP, NC, out S) S ← set empty solution for j = 1 to IT do for i = 1 to B do the bee i ← Set empty solution. for k = 1 to NP do for i = 1 to B do for r = 1 to NC do Evaluate all possible constructive moves of the bee i. According to evaluation, choose one move using the roulette wheel. for i = 1 to B do Evaluate solution of the bee i. for i = 1 to B do Make a decision whether the bee i is loyal. for i = 1 to B do if the bee i doesn't loyal then Choice one of the loyal bee which will be followed by the bee i. if the best solution generated by the bees better than the solution S then S ← the best bee's solution.
a) Loyalty Decision
After the completion of forward pass, each bee decides whether it stays loyal to the previously discovered solution or not. This decision depends on the quality of its own solution related to all other existing solutions. The probability that b-th bee (at the beginning of the new forward pass) is loyal to its previously generated partial/complete solution is expressed as follows:
where: Ob- the normalized value for the objective function of partial/complete solution created by the b-th bee; Omax- maximum over all normalized values of partial/complete solutions to be compared; u - the counter (ordinary number) of the forward pass (taking values 1, 2, .., NC).
The normalization is performed in two ways, depending on whether a minimization or maximization of the objective function is required. If Сb (b = 1, 2,..., B) denotes the objective function value of b-th bee partial/complete solution, normalized value of the Cb in the case of minimization is calculated as follows
where Cmn and Cmax are values of partial/complete solutions related to minimal and maximal objective function value, respectively, obtained by all engaged bees. From equation (2) it could be seen that if b-th bee partial/complete solution is closer to maximal value of all obtained solutions, Cmax, than its normalized value, Ob, is smaller and vice versa. In the case of maximization criterion, normalized value of Cb is calculated as follows:
From above equation (3) it is obvious that if the value of the partial/complete solution, Cb, is higher, then its normalized value, Ob, is larger, and vice versa.
Let us discuss equation (1) in some more details. A greater Ob value corresponds to a better generated solution, and a higher probability of bee loyalty to the previously discovered solution. The higher index in the forward pass increases the influence of the already discovered solution. This is expressed by the term u in the denominator of the exponent (equation (1)). In other words, at the beginning of the search process bees are ‘‘braver’’ when searching the solution space. The more forward passes are made, the less courage they have: as we approach the end of the search process, the bees are more focused on already known solutions.
Using equation (1) and a random number generator, every artificial bee decides whether to become uncommitted follower or to continue exploring its own solution. If chosen random number is smaler than the calculated probability, then the bee stays loyal to its own solution. Otherwise, if the random number is greater than the probability, pbu+1, the bee becomes uncommitted.
b) Recruiting Process
For each uncommitted bee it is decided which recruiter it will follow, taking into account the quality of all advertised solutions. The probability that b’s partial/complete solution would be chosen by any uncommitted bee equals:
where Ok represents normalized value for the objective function of the k-th advertised solution and R denotes the number of recruiters. Using equation (4) and a random number generator, each uncommitted follower joins one recruiter through a roulette wheel.
The roulette wheel is a well-known model of choice. The main inspiration for its development came from a game-gambling roulette. Any solution can be chosen, and the probability of its selection (the size of a particular slot on the roulette wheel) depends on the quality of the solution, i.e. the value of the objective function (solutions 1,2, …, 6 from Fig. 5). In the practice, the size of the slot on the roulette wheel associated to each solution is determined by the ratio of the corresponding normalized objective function value and the sum of the normalized objective function values for all advertised solutions. On one hand, a solution with better objective function value has a higher chance to be selected. On the other hand, there is still a possibility that it will be eliminated from further search process.
Figure 5. Roulette wheel model
|
||||||
