Artificial Bee Colony Algorithm

Artificial Bee Colony (ABC) algorithm is a Swarm Intelligence optimization algorithm inspired by the functioning of honey bees trying to find the best nectar resources surrounding their bee hive. Derviş Kara-Bogaz first proposed this algorithm in 2005. This algorithm has been used in many forms of optimization of complex non-linear functions. As you will see soon, this algorithm is dependent on the randomness of the situation, it is a great domain for applying better strategies to find the optimal point even faster. You will also notice that if the algorithm has a hint that the point is somehow a local minimum, it has a strategy to even discard it. Hence, it also is efficient in finding the global minimum of functions. In this article, we will look at the algorithm in the simplest manner and also see how we can apply this algorithm to feature selection for training any machine learning model.

The algorithm has multiple phases as follows:

1. Initialization Phase (Think of it like the bees are now out of their hives and are at different positions, mathematically these are the initialization of random points around our function distribution.)
2. Employer Bee Phase (Now the bees have to check the surroundings of their positions and find if there is a better food source than they are currently at, mathematically if there is a point in the vicinity of current, where our function is even more optimal.)
3. Onlooker Bee Phase (Out of all the bees that are out there, which bees have higher chances of getting more food, mathematically out of all the points which point is closer to the optimal point.)
4. Scout Bee Phase (If there is a bee that is trying to find a better food but that bee is already in its best source then abandon it and find a new source, mathematically the point where there is no other point in the vicinity which is closer to the optimal point, this means that this is potentially a local optimum.)
5. Memorise the best solution (After the bees have wandered around their areas, whether finding better or not, after a certain amount of time remember the best food source, mathematically after a certain number of iterations of all these processes, the minimum or maximum result will be the solution that is the closest to the global optimum)

Now let’s look at each of these phases more elaborately.

Initialization Phase

We have a couple of parameters to set at first.

Swarm Size: This is the total number of bees that we are going to use in our algorithm, the higher the number the more efficient the algorithm is, but also takes more time to find the optimum. If the swarm size is set to S, then we take (S/2) as the number of food sources, employer bees and onlooker bees.

Error Limit: Now, we need to set the number of times a bee can check for its surroundings and not get better food. In other words, this limit decides how many times finding optimum in the vicinity can fail before it discards the whole food source and searches for another place randomly.

Maximum number of Iterations: This number will decide how many times we want the Bees to perform the phases.

Food Sources: Now, it’s the time for setting up our bees to the food sources, or selecting random points in our objective function. We do it by the formula as follows:

Where i ranges from 1 to N which represents the food sources. And j is the parameters of the solution vector. Max and min are the limits of x that we set.

Now as we have initialized all the parameters, we are ready to get into the iterative phases of our algorithm.

Employer Bee Phase

In this phase, all the bees find the values of the function at that point. And we will call it f. Now, we will change our food source or the point by a factor, which we will select totally at random and set to a specific parameter of our objective solution:

Where, i and j denote the same as before, and temp denotes that it is not yet declared as the final solution. Also, k is a random integer from 1 to N but not equal to i, and Φ is a random real number between -1 to 1.

Once we get the new temporary solution in the vicinity of the current solution, we calculate the objective function f-new and compare it with our previous function f.

• If f-new is a better solution, then we adapt f-new as our new solution. We don’t increment the error variable for this source and proceed with the iterations.
• If f-new is not a better solution, then we stay with our old f and increment the error variable. Then proceed towards the iteration.

We do this procedure for all the bees with their food source.

Now, if that error variable crosses the error limit that we set at the initialization phase, then we sent that bee to the scouting phase and discard the current food source. This tells us that there is a high probability that the food source is actually just a local optimum.

Now that we have all our new or not new solutions, we find the fitness values for each of them by the following formula:

Where i ranges from 1 to N: N denoting the number of bees.

Let’s take a while and observe the fitness function. As we decrease our value in the objective function, the fitness value increases drastically. In general words, the higher the fitness our solution returns, the better it is.

Get Sayan Banerjee’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Once we have the fitness of all the food sources, we will create a new variable called the probability of fitness function that is going to be used by onlooker bees in the next phase, which can be given by:

The intuition of this probability is that it gives the idea of which food sources have higher chances of reaching the final optimum faster than the others. And that is what the onlooker bee phase makes sure of.

Onlooker Bee Phase

Here we have the fitness function and the probabilities of each food source. What we do now is assign new N onlooker bees and set a random number from 0 to 1 as the limiting probability. So,

• For instance, if OB1(Onlooker Bee) has a limiting probability of 0.6 then it will check that FS1(Food Source 1) has a probability greater or equal to 0.6, if that condition is satisfied, then it will go on and exploit that source, and by exploiting we mean to do the same thing that Employer Bees did just in the previous step.
• If FS1 has a probability less than 0.6 then OB1 will move on and check FS2 and so on till one of the sources matches the criteria.
• If none of the sources matches the criteria then OB1 will be randomly initialized again. (That is a very rare case.)
• Every Onlooker Bee is going to be assigned to one food source, it is possible that more than one bee is assigned to the same source and that will totally abandon the left-out food sources.

The intuition of this phase is to eliminate sources that have very less probability. Though the selection of the limiting probability is random, resulting that there is even a chance that all the sources satisfy the condition, and that is okay, but mostly what happens is one of the Food Sources ends up being left out and maybe 2 Onlooker Bees start to exploit the same Source. That is how the Bees find out which sources are better.

Now once the onlooker bee phase is over, we get a new set of optimal solutions. They may be changed or not, and behave the same as in the Employer Bee Phase. And we again give these solutions to the Employer Bee phase and the iteration continues till the maximum number of iterations. The Onlooker Bees become the new Employer Bees then and the search continues.

Scout Bee Phase

This phase occurs when one of the bees has encountered more errors than the max limit assigned. In this phase, reassignment of the bee takes place randomly, just like the initialization phase. And then again, the iterations continue as it is.

Memorize the best solution

After all the iterations are completed, we have to check the fitness values of all the food sources and find which gives us the maximum fitness value. That solution will be considered closest to the optimal value of the function.

This is how the Artificial Bee Colony Algorithm Works. Some of the advantages are:

• We can simultaneously perform operations on all the bees parallelly which makes it an opportunity for parallel processing utilization.
• It has the ability to detect local optimum.
• Since we saw there was a lot of randomizations in all the phases, there are a lot of opportunities for modification for better results.
• The application is very simple with very less memory usage.
• They don’t plan before prey, so they take action faster than normal. That also leads to more chaos which creates problems sometimes.

This illustration is from the Swarm Repository which shows how the swarm intelligence actually works.

Now let’s work out the way how to implement it in feature selection for machine learning algorithms.

Feature Selection

Feature selection is one of the really big aspects of data modification. Whenever you are training a data, it is very important that you pay attention to all the factors that it affects, the learning curve, validation accuracy, feature size, execution time, memory usage and the list goes on. When we are dealing with a data with lot of features it takes a lot of time for the model to learn and even at times it is observed that the model gives less accuracy compared to when we remove some features that were not needed into the dataset. There are a couple of ways you can solve it. You can manually pick out the features that you think is not paying much importance to the algorithm. Or you can randomly select features and remove them to check if it gives better results. We are going to look at a method that will help to achieve this using artificial bee colony algorithm. So, dive in,

• First, we need to set up a vector that will tell us which feature to select and which to not. We will use a bit vector for that. Suppose we have N features then we will have a bit vector of N length with each bit representing the activation of the feature. Simply if the bit vector of that particular feature position is one then we are considering that feature for testing, and if it is zero then we are not considering that. Now, the trick question goes there is around 2^n-1 possibility of choosing N features. So how do we start? How many food sources do we select?
• Selecting the food sources is pretty much straightforward, if there are N features then we are taking N food resources and initialising the vector as each of the N will contain only one of the bits as one and the rest of them to zero. If you have an idea about matrices then you can think of the start vector as an NxN Identity Matrix. For, as of each row denoting the i-th source’s feature selection.

• Once we are ready with our source, we need a function that we have to minimize. It is going to be our Cost Function. We will calculate the fitness values for each phase’s cost function and proceed according to the ABC algorithm.
• So, how do we change the values during the Employer Bee phase? Well, we need to set a modification rate parameter. And after each iteration, each bit will go through a selection phase that will randomly assign a real number R-i between 0 and 1. If the number is more than the Modification Rate (MR) then we will not do anything and if it is less than the MR then we will set it to 1. Note: When the random number is more than MR, we don’t do anything meaning if the number is already 1 then we keep it 1.
• Once we are done with the modification we can proceed with the algorithm and in the end, we find out the most efficient bit vector that will represent all the features that give us the highest accuracy.

Conclusion

With that, we have come to the end of this article. This algorithm provides a basis to understand how nature works in its most raw form. It’s a pioneer in understanding the mechanisms that make this world beautiful. There are even more other types of swarm intelligence algorithm one can feel free to explore, the algorithm is for sure chaotic and beyond the understanding of the human mind, but the results with some modifications is fascinating. Last but not least let us have a look at a chart that applied the ABC algorithm along with other algorithms and their accuracy fluctuations with increase and decrease of parameters.

Reference:

Data feature selection based on Artificial Bee Colony algorithm | EURASIP Journal on Image and Video Processing | Full Text (springeropen.com)

HaaLeo/swarmlib: This repository implements several swarm optimization algorithms and visualizes them. Implemented algorithms: Particle Swarm Optimization (PSO), Firefly Algorithm (FA), Cuckoo Search (CS), Ant Colony Optimization (ACO), Artificial Bee Colony (ABC), Grey Wolf Optimizer (GWO) and Whale Optimization Algorithm (WOA) (github.com)