The Artificial Bee Colony (ABC) algorithm as a non-standard computational method

Swarm intelligence is defined in the academic literature as the ability to design algorithms inspired by the collective behaviour of decentralized and self-organized social insect colonies. A well-known example of swarm intelligence is a honey bee swarm which has enthused researchers to develop algorithms based on the various activities taking place within a bee colony. An example of one such algorithm is the Artificial Bee Colony (ABC) algorithm proposed by Karaboga in 2005 which simulates the foraging behavior of bees for solving optimization problems and is the one of the most widely studied swarm based algorithms so far.

To begin with, in a real-world bee colony specialised bees are performing different tasks. Being crucial to the survival of their colony, the main aim of these specialised agents is to try to maximize the nectar amount stored in the hive by performing efficient division of labour and self-organization. In the ABC algorithm, the colony of artificial bees contains three main groups of agents:
Employed bees
Onlooker bees
Scout bees

Each group has distinct responsibilities and plays a crucial role in the optimization process. First, an employed bee is responsible for exploiting the available nectar sources and gathering the required information about them. In order to select a food source, an employed bee evaluates several relevant properties such as its direction and distance from the hive and the profitability of the source and then utilizes its own capability to memorize these characteristics. Employed bees would then not only carry the load of nectar extracted back to the hive, but also all their knowledge about the food source. Consequently, this information will be shared with the other bees in the hive.

Therefore, the most important part in the formation of collective knowledge among bees is the exchange of information. In that respect, a crucial area in the hive is the dancing area where information about food sources is communicated by employed bees through the so-called waggle dance. Employed bees share their information with a probability which is proportional to the profitability of the food source. Hence, more profitable food sources would correspond to waggle dances longer in duration and more bees attracted.
In other words, the employed bee stays on a food source, which represents a spot in the solution space, and provides the coordinate for the other bees in the hive for reference. The position of a food source corresponds to a possible solution to the optimization problem while the nectar amount of that food source signifies the quality or fitness of the associated solution.

Second, a bee waiting on the hive’s dance area for making a decision to choose a given food source to exploit is called an onlooker. The onlooker bee receives the information that employed bees share with it about the location and quality of food sources around the hive. Then, the onlooker selects an existing food source to be further explored. The onlooker could watch numerous dances and chooses to employ herself at the most profitable source. There is a higher probability of onlookers choosing more profitable sources since more information is flowing about them on the dance area in the hive. Hence, the dance of employed bees carrying higher nectar recruits the onlookers for the food source areas with higher nectar amount.

Finally, when an employed bee’s given food source has been exhausted, that bee becomes a scout and starts to carry out random search for discovering new food sources in the vicinity of the hive (the solution space). The abandonment of a food source happens when its quality is not improved after performing a maximum allowable number of iterations.

Algorithm description

Abc algorithm in pseudo code

 

Class of computational problems addressed

In Computer Science, optimization problems deal with finding the best solution from the set of all feasible solutions. Optimization is an instance field in which nature models are frequently developed and applied and the ABC algorithm simulating foraging behaviour of honeybees is a typical example of nature inspired optimization algorithm.

Originally, the ABC algorithm has been proposed for solving unconstrained optimization problems and showed that it has good performance on both multimodal and multi-variable problems for a number of reasons presented below.
The survival and progress of the bee colony are dependent upon the fast discovery and competent utilization of the best food resources in the vicinity of the hive. Similarly, the successful solution of a challenging engineering problem is connected to the relatively fast discovery of good solutions especially for problems that need to be solved in real time.

It must be noted that in a robust search process, the processes of exploration and exploitation must be carried out together. Deterministic and probabilistic selection of employed and onlooker bees respectively exploit the sources by local searches in the neighbourhood of solutions. The abandoning of exhausted food sources in the foraging process, signifies the abandoning of solutions not beneficial anymore to the search progress and the new solutions inserted instead of them allow for the exploration of new areas in the search space. That is why in the ABC algorithm while the employed and onlooker bees control exploitation in the search space, the scouts carry out the exploration. Therefore, the local search performance of the ABC algorithm depends on the neighbourhood search and greedy selection mechanisms performed by employed and onlooker bees. On the other hand, the global search performance of the algorithm depends on the random search process performed by scouts.

Comparison to other algorithms

When it comes down to comparison between ABC and other swarm based algorithms, ABC’s main advantages are being relatively simple and flexible, with fast convergence and fewer setting parameters.
Apart from the maximum evaluation number and population size, a basic swarm based Particle Swarm Optimization algorithm (PSO) has three control parameters (cognitive and social factors, inertia weight) while a standard Genetic Algorithm (GA) has three more control parameters (crossover rate, mutation rate, generation gap). On the other hand, apart from the Colony Size (SN) and the Maximum cycle number (MCN) control parameters, the ABC algorithm has only one control parameter (i.e. limit). Hence, ABC is as simple and flexible as PSO, but with less employment of control parameters and many studies have showed that ABC outperformed PSO. For example, Civicioglu and Besdok statistically compared the numerical optimization results of PSO and ABC which indicated that ABC had a very successful decision mechanism that decides which areas within the search space required to be surveyed in more detail.

It should be noted that in PSO and GA the best solution found so far is always kept in the population and it can be used for producing new velocities in the case of PSO and new solutions in the case of GA. However, in ABC, the best solution discovered so far is not always held in the population since it could be replaced with a randomly produced solution by a scout thus it might not contribute to the production of trial solutions. ABC employs a greedy selection process between the candidate and the parent solutions. In ABC, in the onlooker bees phase, the solutions with the higher fitness value are used more often than those with less fitness values to produce trial solutions. It means that the promising regions of the search space are searched in shorter time and in detail. This selection process is similar to the natural selection or to the seeded selection employed in GA.

Furthermore, when the ABC algorithm is compared to other evolutionary algorithms such as GA it has another distinguishing feature – it does not require any external parameters such as crossover and mutation rate. As noted, in order to produce new or candidate solutions from the present ones, GA employ crossover operators, while ABC produces the candidate solution from its parent by a simply taking the difference of randomly determined parts of the parent and a randomly chosen solution from the population. As a consequence, this process increases the convergence speed of search into a local minimum. Moreover, in ABC there are two different types of processes to control the diversity in the given population. In the case of GA, the mechanism used to provide the required diversity in the population is a mutation process which creates a modification on a randomly selected part of the solution. On the other hand, the processes employed by ABC are the following:

Similarly to GA, in ABC a randomly chosen part of a parent could be modified with a randomly determined magnitude to obtain a trail solution which leads to a relatively small modification useful for local search and fine tuning.

What is more, rather than changing a part of a solution, a whole solution in the population could be removed and then a new randomly produced one could be inserted into the population by a scout bee. As a result, this mechanism not only allows the ABC algorithm a global search ability but also prevents the search from premature convergence. Also, the dependency of the algorithms’ performance on the population size is weakened. That is why there is a good balance between the local search process carried out by artificial onlooker and employed bees and the global search process managed by artificial scouts.