Artificial Intelligence: 5. Ant Colony Optimisation (ACO) on TSP

Code: GitRepo

Assumptions:

- Termination condition is assumed to be “similarity of path taken by all the ants”

- The count of ants is taken as twice the count of cities, by default

- Other than these, ACO is implement as per the algorithm

- Alpha is the influence on pheromone level

- Beta is the influence of favorability of distance

Methodology:

- We initialize the cities at random coordinates and generate a distance matrix, which basically tells us the distance of a city with each other cities

- Now, we just have nodes on the graph which are waiting to be connected

- Here, connection refers to an ant choosing that edge during its travel

- Now we place the ants in initial city ‘zero’

o We tell the ant to take all the paths that are not visited and return back

o During the travel we store the total distance travelled and the path taken by the ant

o We do this loop for all ants

o During this process the ant will be depositing some amount of phenome in the path which will help the other ants to choose a path when multiple paths are available

o And choosing of a city is done according to a probability which has a calculated amount of pheromone and the distance

- We have a pheromone evaporation level which tells us how much f the pheromone is evaporated during each iteration

- At a certain point all the ants will be taking the same path, this is considered as convergence

- The ants tend to find the shortest path with the probability selection of path on the pheromone

Algorithm:

- Generate cities and ants

- Place ants in the initial city

- Repeat until convergence: (all ants take same path)

o For every ant:

§ Repeat until a unvisited city exits:

· Choose next city with the conditional pheromone probability

· Store the path

§ Go back to the initial city

o Update pheromone level

Observations:

- Though the ants are legally blind, they tend to choose the shortest path after certain iterations with the help of pheromone

- The combined ensemble approach of ants helps in finding the shortest distance

- The parameters alpha, beta, no of ants and the number of cities play a huge role

- Alpha >1 and beta > 0. These conditions are so that the formulation of probability doesn’t get invalid.

- With basic alpha 1 and beta 1, the number of iterations are high

- With alpha 2, and beta 2, the number of iterations gets reduced

- With alpha > beta the ants seem to choose paths that are even longer

- With beta > alpha the ants seem to choose the shorter path helping to converge sooner.

- With increase in number of cities, more computation power is needed, taking more time to converge

- Increasing the number of ants will increase the computational capacity but can give a better result