in

Ant Colony Optimization using Python

Ant colony optimization in python
Reading time: 2 min

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)

Written by Sumit Paul

Self-motivated Blogger. Very much fascinated by tech stuffs especially softwares.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Loading…

Loading…

0
Particle swarm intelligence python code

Particle Swarm Optimization| Machine Learning Algorithm inspired by Birds

decryption program,infoclusters.com

Part 2 – Decryption Using Combination Of Caesar And Transposition Algorithm