Evaluating Performance of Honey Bee Mating Optimization

A branch of nature-inspired algorithms, known as swarm intelligence, is focused on insect behavior in order to develop some meta-heuristics which can initiate the insect’s problem solution abilities. An ant colony [1, 2] and particle swarm optimization [3] are examples of the well-known algorithms that mimic insect behavior in problem modeling and solution. Honey bee mating algorithms (HBMO) belong to the novel swarm-based algorithms which are inspired by the marriage process in real bee colonies. The aim of this work is to study the performance of HBMO and its ability in finding a global optimum in comparison with other evolutionary algorithms like GA. In the present work, the HMBO algorithm is presented and applied to several test functions. Sensitivity analysis on crossover operators was performed and a performance comparison of HBMO and GA was implemented using a benchmarking study.

There are five main steps in the development of the HBMO algorithm, as described below.

Step 1: Mating flight of queen bees with drones

In nature

In the marriage process, the queens mate during their mating flights far from the nest. A mating flight starts with a waggle dance performed by the queen that then starts a mating flight during which the drones follow the queen and mate with her in the air. In each mating, sperm reaches the spermatheca and accumulates there to form the genetic pool of the colony [4]. The queen is pursued by a large swarm of drones (drone comets) when copulation occurs. Insemination ends with the eventual death of the drone and the queen receiving the mating sign. The queen mates multiple times but the drone, inevitably, only once. These features make bee mating the most spectacular mating among insects [5].

In algorithm

Each member of the bees colony, such as queen, drones and broods, are represented as a real coded string. A chromosome was used to represent a candidate solution to a problem where each gene in the chromosome represents a parameter of the candidate solution. The speed of each queen at the start of each mating flight is initialized at random. A list of drones is then randomly produced. The objective function for them is evaluated and the best one would be selected as the first queen. Next, a number of mating flights would be undertaken. The speed decreases during the mating flight. A drone mates with a queen probabilistically using an annealing function as follows [4]:

where \(\operatorname{prob}(Q,D)\) is the probability of adding the sperm of drone D to the spermatheca of queen Q (that is, the probability of a successful mating), Δ(f) is the absolute difference between the fitness of drone, f(D) and the fitness of queen, f(Q) and S(t) the speed of the queen at time t.

After each transition in space, the speed and energy of the queen decays according to the following equations:

(2)

(3)

(4)

where α∈[0,1], E(t) is the energy of the queen at time t, γ is the amount of speed reduction after each transition and M is the maximum number of mating flight.

If the mating is successful (i.e., the drone passes the probabilistic decision rule), sperm of the drone is stored in the spermatheca of the queen. This part of the algorithm is like simulated annealing, i.e., a random number is produced and then a drone will pass the probabilistic decision rule if his probabilistic function value is greater than the random number. The spermatheca in developing the algorithm is simulated by a list of strings which belong to drones chromosome that have passed the probabilistic rule. The stopping criterion for mating flight of queen is reached when her spermatheca is full (maximum number of mating is reached), when her energy reaches a critical point or when her speed reaches its lower bound.

Step 2: Creation of new broods by the queen

In nature

Each time a queen lays fertilized eggs, she randomly retrieves a mixture of the sperm accumulated in the spermatheca to fertilize the egg [6].

In algorithm

When all queens complete their mating flights, they start breeding and new broods are formed. Crossover operator is used to mix queen’s genotype with drones. For a required number of broods, a queen is selected in proportion to her fitness and is mated with a randomly selected sperm from her spermatheca. This process is similar to that of the GA, with the difference that in the GA each offspring is born from two parents while in the HBMO algorithm a brood may have some genes from one drone and some from another. In other words, a brood does not have a specified father. Four crossover operators (intermediate, single point, two point, scattered) were considered in this work. Sensitivity analysis on the type of crossover was performed to find the most effective one.

Step 3: Improvement of the broods’ fitness by workers

In nature

The function of workers is taking care of the brood and feeding them with the royal jelly. The royal jelly is a special food which belongs to the queen and makes the queen become bigger than other members in the hive. Feeding broods with royal jelly makes them become better and lets them have a potential of being the next queen.

In algorithm

In the algorithm, this functionality of workers is modeled by representing them with a heuristic which acts to improve and/or take care of a set of broods. A set of different heuristics is represented by workers to improve the genotype of the broods. In this work, four types of mutation operator were used as the heuristic function.

Step 4: Adaptation of the workers’ fitness

In nature

This step does not exist in nature.

In algorithm

The rate of improvement in the brood’s genotype, as a result of a heuristic application to that brood, is the definition of the fitness function for each worker. In this way, the fitness function of each worker becomes updated in every iteration to give more chance to the worker which has more positive effect on the broods’ gene. In the next iteration, the workers will be used in proportion to their fitness function. In the present study, the roulette wheel selection method was applied for this purpose.

Step 5: Replacement of the least fit queen(s) with the fittest brood(s)

In nature

Broods arise either from fertilized or unfertilized eggs. The former represent potential queens or workers, whereas the latter represent prospective drones [7].

In algorithm

In the algorithm, broods cannot replace the worker but the best brood replaces the worst queen until there is no brood that is better than any of the queens. The remaining broods would not be killed but a predefined number of best broods (elites) would be selected and replaced with the worst ones. In this way, the list of drones will be updated in each mating flight and with this replacement the exploitation will be powered. A new mating flight begins until all assigned mating flights are completed or convergence criteria are met.

The principal ideas of the genetic algorithm (GA) were originally developed by Holland [8] and later refined and described in detail by Goldberg [9]. The GA is an adaptive method that imitates the genetic process in nature and can be applied to optimization problems. The main steps in the GA are as follows:

1. 1.

   Encoding decision variables and placing them in chromosomes.

2. 2.

   Creating an initial population.

3. 3.

   Determining the fitness of every chromosome in the current population.

4. 4.

   Selecting better chromosomes for mating.

5. 5.

   Running crossover operators to generate new strings from the available chromosomes.

6. 6.

   Performing mutation to randomly alter one or more genes.

7. 7.

   Repeating steps 3–6 in order to find the best solutions.

Seven test functions, listed in Table 1, were used to evaluate the performance of the HBMO algorithm and compare it with that of the GA. Parameters of the HBMO and GA given in Tables 2 and 3, respectively, were selected after thorough testing. A number of different alternative values were tested in each test function and the ones selected are those that provided the best computational results. For some of the parameters, a range of values is given, which means that the used value is different for each test function.

Four crossover operators, mentioned above, were tested and the operator with the best result of HBMO and GA was used for each algorithm. Tables 4 and 5 represent the objective functions in the sensitivity analysis on crossover operators in HBMO and GA, respectively. The best results corresponding to each test function for GA and HBMO are shown by bold numbers. It can be concluded from Table 4 that the intermediate crossover operator provides the best results for all test functions in the HBMO. However, Table 4 demonstrates that for the GA there are a variety of crossover types which can provide the best results. In the following, the best crossover was used for comparison.

Table 6 summarizes the comparison of results from GA and HBMO for the same number of function evaluations for the benchmark functions. Table 6 reveals that at the same number of function evaluations, the HBMO reaches a better minimum than the GA and is more likely not to be trapped in local minima. In the case of functions 6 and 7 the GA cannot reach the global optimum point after 2000 and 700 function evaluations, respectively, and it becomes trapped in a local optimum.

Performance of the HBMO algorithm was investigated using seven benchmark functions. Results of the HBMO were compared with the results of the GA. We briefly recall the features of the HBMO:

• It was shown that the HBMO performs better than the GA in terms of speed of convergence and finding the global minimum.

• The optimization results demonstrated that the HBMO algorithm is convergent to the global minimum for all the test functions, although these test functions are complex and have many local optima.

• The results are promising and encourage further research for applying the HBMO algorithm to complex and real-time optimization problems.