Computer Intelligence Ant colony by Pro.Chu

Ant colony optimize (ACO)

Inherent features

• Inherent parallelism
• Stochastic nature
• Adaptivity
• use of feedback
• Autocatalytic in nature

Double bridge experiments: different lengths - the majority ant go though the short path

p1 = (m1+k)^h /(m1+k)^h + (m2+k)^h

p2=1-p1

Basic ideal of ACO

• inspired by the food foraging behavior of ants
• Ants are agents that: - move along between nodes in a graph
• They choose where to go based on pheromone strength (and maybe other things)
• An ant's path represents a specific candidate solution.
• When an ant has finished a solution, pheromone is laid on its path, according to quality of solution.
• This pheromone trail affects behavior of other ants, and this is called 'stigmergy' -a communication method amongst ants

How to implement in program

• Ants: Simple computer agents
• Move ant: Pick next component in the construction of solution
• Trace: Pheromone, delta thor ^k where i,j a global  type of infomation
• Memory: mk or tabu k

Genetic ACO algorithm

1. Initialize
2. repeat // called each iteration
3.  each ant is positioned on the initial node
4.  repeat // called each step
5.     Each ant applied a state transition rule
6.     Apply the pheromone local update rule // optional
7.  until all ants have build a complete solution
8.  apply a local search procedure // optional 
9.  Apply a pheromone global update rule
10. until any stopping criterion is met
11. Return the best route

 ACO for the traveling salesman problem

• TSP is a metaphor problem for the ant colony
• Is is one of the most studied NP-hard* problems in the combinatorial optimization
• It is easy to explain. So that the algorithm behavior is not obscured by too many technicalities.

*Np-hard are at least as hard as the hardest problems in NP, which can be solved with Non-deterministic Turing machine in Polynomial time.

Ant Colony Optimization (ACO) for TSP

• Each edge is associated a static value based on the edge-cost n(i,j) = 1/Li,j , heuristic information indicating a chance or likeliness to move from node i to j

Well see you again, @MySimpleDiary my note story teller