Anton Antonov

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

Computer Science, Uncategorized
tony
September 22, 2014

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.

ABCalgorithmartificialbeebeesbio-inspiredcolonycomputationnon-standard

Join the ConversationLeave a reply

Your email address will not be published. Required fields are marked *

Comment*

Name*

Website

Save my name, email, and website in this browser for the next time I comment

Comments

  168. Чеки на гостиницу в Казане

    I don’t even understand how I ended up here, however I assumed this put up used to be great.
    I do not realize who you are however definitely you’re going to a well-known blogger in case you aren’t already.
    Cheers!

    Reply
  171. breast tape

    Hey there! Do you know if they make any plugins
    to help with Search Engine Optimization? I’m trying to get my blog
    to rank for some targeted keywords but I’m not
    seeing very good success. If you know of any please share. Many thanks!

    Reply
  178. Гостиничные чеки в Казани

    Hello there! I know this is kinda off topic but I was wondering if you knew where I could
    get a captcha plugin for my comment form? I’m using the same blog platform
    as yours and I’m having difficulty finding one? Thanks a lot!

    Reply
  180. body tape for stomach

    It is in point of fact a great and useful piece of info.
    I am satisfied that you shared this useful information with us.
    Please keep us up to date like this. Thanks for
    sharing.

    Reply
  182. newsmax live tv

    I wanted to thank you for this fantastic read I definitely loved every little bit of it. I have you book marked to check out new stuff you post� newsmax anchors

    Reply