26-09-2013, 04:22 PM
Ant Colony Optimization
Colony Optimization.ppt (Size: 241.5 KB / Downloads: 76)
ACO Concept
Ants (blind) navigate from nest to food source
Shortest path is discovered via pheromone trails
each ant moves at random
pheromone is deposited on path
ants detect lead ant’s path, inclined to follow
more pheromone on path increases probability of path being followed
ACO System
Virtual “trail” accumulated on path segments
Starting node selected at random
Path selected at random
based on amount of “trail” present on possible paths from starting node
higher probability for paths with more “trail”
Ant reaches next node, selects next path
Continues until reaches starting node
Finished “tour” is a solution
Background
Discrete optimization problems difficult to solve
“Soft computing techniques” developed in past ten years:
Genetic algorithms (GAs)
based on natural selection and genetics
Ant Colony Optimization (ACO)
modeling ant colony behavior
The Algorithm
Ant Colony Algorithms are typically use to solve minimum cost problems.
We may usually have N nodes and A undirected arcs
There are two working modes for the ants: either forwards or backwards.
Pheromones are only deposited in backward mode.
Steps for Solving a Problem by ACO
Represent the problem in the form of sets of components and transitions, or by a set of weighted graphs, on which ants can build solutions
Define the meaning of the pheromone trails
Define the heuristic preference for the ant while constructing a solution
If possible implement a efficient local search algorithm for the problem to be solved.
Choose a specific ACO algorithm and apply to problem being solved
Tune the parameter of the ACO algorithm.