Ant Colony Optimization (ACO) algorithm is used to find the best way of reaching the final destination and come back. This Algorithm is based on the pattern of Ants. In ACO, a set of software agents called artificial ants search for good solutions to a given optimization problem. To apply ACO, the optimization problem is transformed into the problem of finding the best path on a weighted graph. The artificial ants (hereafter ants) incrementally build solutions by moving on the graph. The solution construction process is stochastic and is biased by a pheromone model, that is, a set of parameters associated with graph components (either nodes or edges) whose values are modified at runtime by the ants.
The ants construct the solutions as follow:
- Each Ant starts from random nodes.
- Then each Ant moves to the next node and keeps a memory of its path.
- The movement of nodes are done in such a way that already visited nodes should not be visited again.
- An Ant will create a solution when it reaches all the nodes.
- Ant uses the probabilistic rule to choose the best path.
- The probabilistic rule is based on the pheromone value. The higher the pheromone the higher the probability an ant will choose that path.
- Once all the ants have completed their tour, the pheromone on the edges is updated.
- Each of the pheromone values is initially decreased by a certain percentage.
- Each path then receives an amount of additional pheromone proportional to the quality of the solutions to which it belongs.
- This procedure is repeatedly applied until a termination criterion is satisfied.
Implementation in Python
#install ACO library !pip install ACO-Pants import pants import math import random nodes= for _ in range(20): x=random.uniform(-10,10) y=random.uniform(-10,10) nodes.append((x,y)) def euclidean(a,b): return math.sqrt(pow(a-b,2)+pow(a-b,2)) world=pants.World(nodes,euclidean) solver=pants.Solver(rho=0.5,q=1,t0=0.01,limit=50,ant_count=10) solution=solver.solve(world) print(solution.distance) print(solution.tour) solutions=solver.solutions(world) best=float("inf") for solution in solutions: assert solution.distance<best best=solution.distance print(best)