Ant colony is an artificial algorithm that imitate behaviour of the ants
when passing through the obstacle in order to search the food. The ants will
always through the shortest path to reach the food. This can be done because
the ant releases the chemical subtances called “pheromone” and affects the behaviour
of the other ants. But this pheromone can decay over time, and will disppear. Because
there are many ants, so this pheromone will always be added by other ants
before it is gone. So the longer the path that passed through by the ant, the
less the pheromone on the starting point of the path. With this natural
behaviour, the ants will always find the shortest path between their nest and
food.
But how do the ants find the shortest path from their nest to the food ?
The first thing that is done by the ants is go to the food sources randomly
while spreading the pheromone to the path that is passed through. The other ant
will feel this pheromone, and the ant will follow the stronger pheromone rather
than the weaker pheromone. The longer the path, the weaker the pheromone on the
starting point. So, based on this natural behaviour, the ants can always find
the shortest path while searching the food from their nest.
This biological phenomenom is the beginning of Ant Colony Algorithm (ACO)
creation. That is used in optimization technique. We will learn ACO using
Python programming language. For this good opportunity, we will learn how to
use Ant Colony Algorithm to find the shortest path from city to city. To do
this job we should follow these steps :
1. Initialize a square array which are contain the route with each distance
that must be travelled by the ants (route array / distances).
2. Initialize a square array for pheromone and must be same size with route
array.
For this purpose we initialize all pheromone values to be 0.1.
3. Set the number of ants that must be travelled the path.
4. Set the number of the best ants that can be through the path with the
shortest distance.
5. Set the number of iterations of the optimization in order to find the
shortest route.
6. Set the decay rate of the pheromone.
7. Set the value of alpha and beta.
8. Set the formula for the decision. This decision will be used by ants to
decide where to go to the next city. For this purpose the formula of decision
is :
city_to_city_score = pheromone ** alpha * (1.0 / distance) ** beta
9. Set the probability of going to the next city. The probability is :
prob_of_going_to_city(i) = city_to_city_score(i) / sum_of_all_available_city_to_city_scores
10. Set the formula of spreaded pheromone of every ant that has travelled between two cities. For this purpose we use formula below:1 / (distance between two cities)
Let’s create the Python program for ACO. In this Python of ACO, there are 6
functions such as :
1. aco(distances_, n_ants_, n_best_, n_iterations_, decay_, alpha_=1,
beta_=1), is a main function in ACO algorithm. In this function we can
initialize some variables for ACO such as distances, the number of ants (n_ants),
the number of the best ants that pass through the shortest path (n_best),
number of iterations (n_iterations), decay rate, alpha, and beta value.
2. gen_all_paths(), in this function we will receive 2 values such as all
path (path from start to end) that has been passed by the ant and value of its
total distance (distance from start to end).
3. gen_path(start), in this function we will receive just all path (path
from start to end), so this function is part of gen_all_paths() function.
4. gen_path_dist(path), in this function we will receive the total distance
of all path (from start to end), so this function is part of gen_all_paths().
5. spread_pheronome(all_paths, n_best, shortest_path), the ant will spread
the pheromone in this function. The spread formula is
1 /
(distance between two cities).
6. pick_move(pheromone, dist, visited), the ant will make a decision of
where to go to the next city by using the formula of probability.
Okay, that is the education about ACO. In this post, we are not discussing
the detail about Python program. But you can see the detail by yourself about
the Python program of ACO from the Python file below. I hope you are enjoying
this little knowledge, see you soon.
Please Fill The Comment Wisely.