A Swarm Intelligence approach to Optimization Problems using the Artificial Bee Colony (ABC) Algorithm
A complete step-by-step on implementing the ABC in python
Swarm Intelligence (SI) is a subfield of Computational Intelligence (CI) and is concerned with the development of bio-inspired multi-agent intelligent systems. SI uses the collective behavior of natural agents such as flocks of birds and schools of fish as an inspiration to create those algorithms.
Those algorithms have proven to be very efficient in solving real-world problems. Some of the tasks that can be solved using SI algorithms are clustering, planetary mapping, controlling nano robots and a variety of problems in data mining such as feature selection and classification.
Mathematically speaking, to solve a real world optimization problem using computational intelligence algorithms, we will need a mathematical representation of our problem, this representation is called Objective Function, which is a mathematical rule that describes the problem and all the decision variables within this problem.
For short, an optimization problem is defined by a search space, which is the region where we will look for a solution, a set of decision variables, which includes all the parameters that influence our problem and of course the objective function, which mathematical rules the problem and also give us a goodness measurement of a candidate solution.
The goal of an optimization problem is to find the best solution from all feasible solutions. This normally means that we want to minimize or maximize the objective function. In other words, we want to find the set of input decision variables that minimizes of maximizes the value of our objective function, also called fitness value.
The Artificial Bee Colony Algorithm
The Artificial Bee Colony (ABC) algorithm is an optimization algorithm which simulates the behavior of a bee colony and was first proposed by Karaboga in 2005 for real-parameter optimization.
In this mathematical model, our bee colony is composed of three types of bees: The Employee Bees, which will work on the collection of food to the hive at a specific food source. The Onlooker Bees, which will patrol the employees to verify when a specific food source is not worth it anymore, and the Scout Bees, which will be the ones looking for new food sources locations.
On the ABC algorithm a food source is defined as a position in the search space (a candidate solution for the optimization problem), and initially the number of food sources is equal to the number of bees on the hive. The quality of a food source is defined by the value of the objective function on that position (fitness value).
The emergent intelligent behavior from the bees can be summarized on some few steps:
- The bees start to randomly explore the environment looking for good food sources (fitness value).
- After finding a food source, the bee becomes an employee bee and begins to extract the food at the discovered source.
- The employee bee returns to the hive with the nectar and unloads the nectar. After unloading the nectar, she can go back to her discovered source site directly or she can share information about her source site by performing a dance on the dance area.
- If a food source is exhausted, the employee bee becomes a scout and starts to randomly search for a new food source.
- Onlooker bees waiting in the hive watch the employee bees on their food source collection and choose a source among the more profitable sources.
- The selection of a food source is proportional to the quality of the source (fitness value).
Even though we described three types of bees, at an implementation level we realize that there are only two types, the employees and the onlookers. The scout bee is in fact an exploratory behavior that can be performed by both employees and onlooker bees.
In this article we will be using Python, since it has been increasingly shown efficient in numerical computation, and it makes easier to implement a set of objective benchmarks to reuse on our swarm intelligence algorithms.
you can download the deap package here.
To begin the development of our algorithm we must find a way to represent our Bee agent on the python code. There are three main generic functionalities that any bee needs to have. The first one is when due to the exploratory behavior a bee moves out of our decision boundary it needs to have the ability to return to the hive. The second one is the ability to update the status of the actual food source in which the bee is working on and evaluate if a new neighborhood region its a better food source. And the last one realizes when a food source is exhausted and now the bee has to scout for some new food sources.
With that in mind, we can implement the class ArtificialBee in python as follows:
The main behavior of an employee bee is to extract the food from the food source in which the employee is working on becomes exhausted. At an implementation level, this behavior can be seen as generating a new position close to where the employee bee is, and evaluating if this new position has a better amount of food. The employee bee always will memorize the best food source position achieved so far until it is exhausted.
The EmployeeBee class can be implemented as follows:
The onlooker bees will patrol the work of employee bees. The will fly over the hive and check the progress of their work and evaluate which employees are being more successful in gathering food.
The onlooker bees will always target the best employees, using a probabilistic approach, as a “meeting point”, where the other bees should come to this successful position with the hope to extract more food.
At an implementation level, the onlooker bees will look through the best employees and try to improve that food source. After a specific number of trials, the onlooker bee will tell to the hive that this food source is exhausted and must be discarded.
The OnlookerBee class can be implemented as follows:
The Complete Artificial Bee Colony Algorithm
After implementing the main types of agents that are going to be used, its time to actually implement all the steps described previously with some python code.
Observe that we have implemented each step of our algorithm in separated methods. First we reset the internal parameters of ours ABC algorithm and initialize our employee bees and onlooker bees at random positions. A default strategy that is very well succeeded in real-world problems, is to initialize half of the entire hive as employee bees and the other half as onlooker bees.
After that, we begin by sending our employee bees to collect food at their respective initial food sources, always looking for better spots of food around it. Once the employee bees phase is done, we send the onlooker bees to patrol their work and evaluate how good the food extraction is going on each food source. Finally, its time to check if some food source is exhausted, at this point either employee or onlooker can become a scout bee and began an exploration process in the search for a new food source.
The complete ABC algorithm can be implemented as follows:
Testing on Bechmark Functions
An advantage that SI algorithms have over classical and gradient-based methods is the ability to perform very well on non-differentiable functions and also multi-modal functions.
As far as optimization problems are concerned, there are several well-known benchmark functions to evaluate the performance of an optimization algorithm. Some of those functions were implemented on our objective_function.py, and their formulas are listed below.
To test our framework and check if our ABC algorithm is doing as expected, we can implement the following test code and plot the fitness value over the iterations and evaluate how well the minimization process went for each one of those functions.
We can check the results by analyzing the plot of fitness versus a number of iterations for each one of our benchmark functions, you can also check the output of optimizer.optimal_solution.pos, and check that the ABC got a very good approximate value to the optimal point for our benchmark functions.
- A comparative study of Artificial Bee Colony algorithm —Dervis Karaboga, Bahriye Akay
- Swarm Intelligence in Optimization — Christian Blum, Xiaodong Li
- A modified Artificial Bee Colony algorithm for real-parameter optimization — Bahriye Akay, Dervis Karaboga
What’s next ?
Well, now that we know how the ABC works and how to implement it, we can apply it to solve some interesting problems for us, such as clustering and image segmentation. We only have to make some slight changes on the algorithm and understand how we can turn those problems in an optimization task!
Stay tuned for the next chapter!