**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**

#### Note:

**rho: percent evaporation of pheromone**

**q: total pheromone deposited by each ant**

**t0: initial pheromone level along each edge**

**limit: number of iterations to perform**

**ant_count: total number of ants**

**Code:**

#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[1]-b[1],2)+pow(a[0]-b[0],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)

## Comments

Loading…