Basic ABC Algorithm Explaining and Coding from Scratch
Hello friends. I am Ali İhsan TAŞDELEN. I am studying Computer Engineering in Erciyes University. I proud of being student of Derviş Karaboğa & Bahriye Akay and work with them. I am going to explain ABC-Basic and we will code it together. Let’s go :)
What is ABC?
The Artificial Bee Colony (ABC) algorithm is a swarm based meta-heuristic algorithm that was introduced by Karaboga in 2005 (Karaboga, 2005) for optimizing numerical problems. It was inspired by the intelligent foraging behavior of honey bees. The algorithm is specifically based on the model proposed by Tereshko and Loengarov (2005) for the foraging behaviour of honey bee colonies.
The model consists of three essential components: employed and unemployed foraging bees, and food sources. The first two components, employed and unemployed foraging bees, search for rich food sources, which is the third component, close to their hive. The model also defines two leading modes of behaviour which are necessary for self-organizing and collective intelligence: recruitment of foragers to rich food sources resulting in positive feedback and abandonment of poor sources by foragers causing negative feedback.
In ABC, a colony of artificial forager bees (agents) search for rich artificial food sources (good solutions for a given problem). To apply ABC, the considered optimization problem is first converted to the problem of finding the best parameter vector which minimizes an objective function. Then, the artificial bees randomly discover a population of initial solution vectors and then iteratively improve them by employing the strategies: moving towards better solutions by means of a neighbour search mechanism while abandoning poor solutions. [Scholarpedia]
We can easily understand the idea and inspiration from Scholarpedia’s simple article. ABC is a really simple algorithm and it is the ABC’s success mystery. The advantages of ABC are easy to understand and implement, it has very few control parameters, and yet it performs mostly better than other similar Population-Based Algorithms. It has an easy-to-use algorithm and a really great problem solving range. Let’s dive in.
What is purpose of our bees?
Firstly, What is the three phase of our algorithm? What do the Employee Bee, On-Looker Bee and Scout bee mean?
In the ABC algorithm, each cycle of the search consists of three steps: sending the employed bees onto the food sources and then measuring their nectar amounts; selecting of the food sources by the onlookers after sharing the information of employed bees and determining the nectar amount of the foods; determining the scout bees and then sending them onto possible food sources.
Let’s Start to Algorithm
At the initialization stage, a set of food source positions are randomly selected by the bees and their nectar amounts are determined.
Let’s snap hands and start. During to initialization stage we will generate random food source positions. Just imagine that they are real-world nutriant zones. Like flower field, fruit tree, etc.
Producing initial food source sites If the search space is considered to be the environment of the hive that contains the food source sites, the algorithm starts with randomly producing food source sites that correspond to the solutions in the search space. Initial food sources are produced randomly within the range of the boundaries of the parameters.
1. Producing initial food source sites
(EQ 1)
x[i,j] = x[min,j] + rand(0,1) * (x[max,j] — x[min,j])
SN = The number of food sources,
D = The number of optimisation parameters,
i = Integer in 0…SN,
j = Integer in 0…D,
x = Food Source Site (Solution)
x[min] = Lower Bound of our Function,
x[max] = Upper Bound of our Function,
rand(0,1) = Uniformly distributed random float number between 0 and 1.
And code in Python. We will take help from NumPy.
import numpy as np
self.solution = self.conf.LOWER_BOUND + np.random.rand(self.conf.FOOD_NUMBER, self.conf.DIMENSION) * (self.conf.UPPER_BOUND - self.conf.LOWER_BOUND)Congrats. We generated food source. Our bees can work now. Chap Chap….
In addition, counters which store the numbers of trials of solutions are reset to 0 in this phase
We should generate trial (failure) vector either. Trial means to resistance to change. It shows to exhaustment of source. It is crucial part of scout bee phase.
trial[i] = 0
i = 0..SN
trial = The amount of exhaustment
In Python :
import numpy as np
self.failure = np.zeros(self.conf.FOOD_NUMBER)Our these food sources will be used in cycles. During every three phase we manuplate our food sources for more optimise value.
Before send employee bees, we must compute fitness values.
if F(i) ≥ 0 ;
fitness[i] = 1 / (1 + F(i))
if F(i) < 0;
fitness[i] = 1 + abs(F(i))
F(i) = The result of objective function
fitness[i] = Fitness value of i.th solution
abs(x) = The absolute of x
In Python :
def fitness_calculator(self, fun):
return 1 / (1 + fun) if fun >= 0 else 1 + np.abs(fun)So our initialization section are done. In Python :
def initilaze(self):
self.solution = self.conf.LOWER_BOUND + np.random.rand(self.conf.FOOD_NUMBER, self.conf.DIMENSION) * (self.conf.UPPER_BOUND - self.conf.LOWER_BOUND)
self.fitness = np.array([self.fitness_calculator(self.function_calculator(i)) for i in self.solution])
self.globalOpt = self.function_calculator(self.globalParams)
#globalOpt : Our Global Optimum Result2 . Sending employed bees to the food source sites
Each employed bee is associated with only one food source site. Hence, the number of food source sites is equal to the number of employed bees. An employed bee produces a modification on the position of the food source (solution) in her memory depending on local information (visual information) and finds a neighboring food source, and then evaluates its quality [Karaboga & Akay 2012]
We will modificate to food source and we will control to new food source is better than old food source. If it is, our employee bee goes there and forage in there. It means we change to old food source with new food source.
(EQ 2)
v[i,j] = x[i,j] + rand(-1,1) * (x[i,j] — x[k,j])
i != k
SN = The number of food sources,
D = The number of optimisation parameters,
i = Integer in 0…SN,
j = Random integer in 0…D,
k = Random integer in 0..SN and not equal with i
x = Food Source Site (Solution)
v[i,j] = j.th dimension of new solution candidate for i.th solution
x[i,j] = j.th dimension of i.th old solution
Get Ali İhsan TAŞDELEN’s stories in your inbox
Join Medium for free to get updates from this writer.
rand(-1,1) = Uniformly distributed random float number between -1 and 1.
Within the neigbourhood of every food source site represented by x[i], a food source v[i] is determined by changing one parameter of x [Karaboga & Akay 2012]
As can be seen from Eq. (2) [It is our last equation], as the difference between the parameters of the x[i,j] and x[k,j] decreases, the perturbation on the position x[i,j] decreases. Thus, as the search approaches to the optimal solution in the search space, the step length is adaptively reduced. If a parameter value produced by this operation exceeds its predetermined boundaries, the parameter can be set to an acceptable value. In this work, the value of the parameter exceeding its boundary is set to its boundaries. [Karaboga & Akay 2012]
Now we will make clip process. It means our new solution candidate (v) must be in range of our search space.
if v[i] < x[min]:
v[i] = x[min]
if v[i] > x[max]:
v[i] = x[max]
after that process, we will calculate our fitness value.
After producing v[i] within the boundaries, a fitness value for a minimization problem can be assigned to the solution v[i] by (3) [It’s our fitness function witch I show you] [Karaboga & Akay 2012]
We know how to compute fitness. After that we will greedy select.
#Important Note
For maximization problems, the cost function can be directly used as a fitness function. [Karaboga & Akay 2012]
A greedy selection is applied between x[i] and v[i]; then the better one is selected depending on fitness values representing the nectar amount of the food sources at x[i] and v[i]. If the source at v[i] is superior to that of x[i] in terms of profitability, the employed bee memorizes the new position and forgets the old one. Otherwise the previous position is kept in memory. If x[i] cannot be improved, its counter holding the number of trials is incremented by 1, otherwise, the counter is reset to 0. [Karaboga & Akay 2012]
Okay we will do greedy selection. In article my proffessors explained really awesome. I will show what is meaning of it.
(EQ 3)
if fit(v[i]) > fit(x[i]);
Change x[i] with v[i] and make trial (failure) value zero.
else;
Increase failure of x[i]
In Python Employee Bee Phase :
def generate_new_solution(self, index):
random_dimension = (int)(self.conf.DIMENSION * random.random())
random_neighbour = (int)(self.conf.FOOD_NUMBER * random.random())
while random_neighbour == index:
random_neighbour = (int)(self.conf.FOOD_NUMBER * random.random())
new_solution = np.copy(self.solution[index])
old_solve = new_solution[random_dimension]
new_solution[random_dimension] = max(min(old_solve + (old_solve - self.solution[random_neighbour, random_dimension]) * ((random.random() - 0.5) * 2), self.conf.UPPER_BOUND), self.conf.LOWER_BOUND)
new_fitness = self.fitness_calculator(self.function_calculator(new_solution))
if new_fitness > self.fitness[index]:
self.solution[index] = new_solution
self.fitness[index] = new_fitness
self.failure[index] = 0
else:
self.failure[index] += 1
def send_employed_bees(self):
i = 0
while i < self.conf.FOOD_NUMBER and not self.stopping_condition():
self.generate_new_solution(i)
i += 13. Calculating probability values involved in probabilistic selection
After all employed bees complete their searches, they share their information related to the nectar amounts and the positions of their sources with the onlooker bees on the dance area. This is the multiple interaction feature of the artificial bees of ABC. An onlooker bee evaluates the nectar information taken from all employed bees and chooses a food source site with a probability related to its nectar amount. This probabilistic selection depends on the fitness values of the solutions in the population. A fitness-based selection scheme might be a roulette wheel, ranking based, stochastic universal sampling, tournament selection or another selection scheme. In basic ABC, roulette wheel selection scheme in which each slice is proportional in size to the fitness value is employed
(EQ 4)
p[i] = 0.9 * fitness[i] / fitness[max] + 0.1
p = Probabilty vector.
fitness[i] = Fitness value of i.th solution
fitness[max] = Maximum fitness value in current solutions
In this probabilistic selection scheme, as the nectar amount of food sources (the fitness of solutions) increases, the number of onlookers visiting them increases, too. This is the positive feedback feature of ABC [Karaboga & Akay 2012]
In Python :
def probabilty_calculator(self):
maxFit = np.max(self.fitness)
self.probabilties = 0.9 * self.fitness / maxFit + 0.14. Food source site selection by onlookers based on the information provided by employed bees
In the ABC algorithm, a random real number within the range [0,1] is generated for each source. If the probability value (p[i] in Eq. (4)) associated with that source is greater than this random number then the onlooker bee produces a modification on the position of this food source site by using Eq. (2) as in the case of the employed bee. After the source is evaluated, greedy selection is applied and the onlooker bee either memorizes the new position by forgetting the old one or keeps the old one. If solution xi cannot be improved, its counter holding trials is incremented by 1, otherwise, the counter is reset to 0. This process is repeated until all onlookers are distributed onto food source sites. [Karaboga & Akay 2012]
i = 1, j= 1
while j< SN:
r = random(0,1)
if r < p[i]:
j = j + 1 and generate v[i] (eq 2) and use greedy selection. If we changed our new solution change trial to zero. If we couldn’t increase to trial
i = i + 1 and i = i mod SN
SN = The number of food sources,
rand(0,1) = Uniformly distributed random float number between 0 and 1.
p[i]= i.th value of probabilty vector.
v[i] = The new solution candidate for i.th solution
Now we have done to onlooker bee phase. Let’s send them from swarm.
In Python :
def generate_new_solution(self, index):
random_dimension = (int)(self.conf.DIMENSION * random.random())
random_neighbour = (int)(self.conf.FOOD_NUMBER * random.random())
while random_neighbour == index:
random_neighbour = (int)(self.conf.FOOD_NUMBER * random.random())
new_solution = np.copy(self.solution[index])
old_solve = new_solution[random_dimension]
new_solution[random_dimension] = max(min(old_solve + (old_solve - self.solution[random_neighbour, random_dimension]) * ((random.random() - 0.5) * 2), self.conf.UPPER_BOUND), self.conf.LOWER_BOUND)
new_fitness = self.fitness_calculator(self.function_calculator(new_solution))
if new_fitness > self.fitness[index]:
self.solution[index] = new_solution
self.fitness[index] = new_fitness
self.failure[index] = 0
else:
self.failure[index] += 1
def send_onlooker_bees(self):
i = 0
j = 0
while j < self.conf.FOOD_NUMBER and not self.stopping_condition():
r = random.random()
if r < self.probabilties[i]:
j += 1
self.generate_new_solution(i)
i += 1
i = i % self.conf.FOOD_NUMBER5. Abandonment criteria: Limit and scout production
In a cycle, after all employed bees and onlooker bees complete their searches, the algorithm checks to see if there is any exhausted source to be abandoned. In order to decide if a source is to be abandoned, the counters which have been updated during search are used. If the value of the counter is greater than the control parameter of the ABC algorithm, known as the ‘‘limit”, then the source associated with this counter is assumed to be exhausted and is abandoned. The food source abandoned by its bee is replaced with a new food source discovered by the scout, which represents the negative feedback mechanism and fluctuation property in the self-organization of ABC. This is simulated by producing a site position randomly and replacing it with the abandoned one. Assume that the abandoned source is x[i], then the scout randomly discovers a new food source to be replaced with x[i]. This operation can be defined as in (eq 1). In basic ABC, it is assumed that only one source can be exhausted in each cycle, and only one employed bee can be a scout. If more than one counter exceeds the ‘‘limit” value, one of the maximum ones might be chosen programmatically
After that our article is done. Our algorithm is almost done either :) Okay let’s see equations of scout bee phase.
if trial[max] > LIMIT:
Produce to the new food source using (Eq 1), and the newly created solution replaces the old solution, calculates the fitness value, and resets the trial of the old solution.
trial[max] = Maximum value of trial (failure) vector.
In Python :
def send_scout_bees(self):
if np.amax(self.failure) >= self.conf.LIMIT:
i = self.failure.argmax(axis = 0)
self.solution[i] = self.conf.LOWER_BOUND + np.random(self.conf.DIMENSION) * (self.conf.UPPER_BOUND - self.conf.LOWER_BOUND)
self.fitness[i] = self.fitness_calculator(self.function_calculator(self.solution[i]))
self.failure[i] = 0Pseudo-Code of ABC
Microsoft Word — Doc1.docx (erciyes.edu.tr)
Official Site of ABC
Artificial Bee Colony (ABC) Algorithm Homepage (erciyes.edu.tr)
# In site, there is python code. Don’t forget to review to code either.
Python Code ABC
def increase_eval(self):
self.eval_count += 1Eval is meaning of evaluation. Our stopping condition will be maximum evaluation.
def stopping_condition(self):
status = self.eval_count >= self.conf.MAXIMUM_EVALUATION
return statusLastly, we must memorize to best solve in every cycle. After our loop finished, best solve will be our answer.
def memorize_best_solve(self):
var = self.function_calculator(self.solution[np.argmax(self.fitness)])
if var < self.globalOpt:
self.globalParams = np.copy(self.solution[np.argmax(self.fitness)])
self.globalOpt = varAnd we can count cycles.
def increase_cycle(self):
self.cycle += 1Okay, now we can complete our algorithms code.
from ABC_Algorithm import ABC_Algorithm
from Config import Config
def main(argv):
conf = Config(argv)
abc = ABC_Algorithm(conf)
abc.initilaze()
abc.memorize_best_solve()
while not abc.stopping_condition():
abc.send_employed_bees()
abc.probabilty_calculator()
abc.send_onlooker_bees()
abc.memorize_best_solve()
abc.send_scout_bees()
abc.increase_cycle()
if __name__ == '__main__':
main(sys.argv[1:])❤ Thank You ❤
I express my great gratitude to Derviş Karaboğa, Bahriye Akay for their efforts to me. Thank you Özlem Erdaş Çiçek for her effort and care to me. She everytime support me in academy and life. I hope you enjoyed and learned as well.
