Ant

‫‪ant colony‬‬ ‫محمد امین راستگو جهرمی‬ ‫مهدی دهقان نژاد‬ ‫و فی الرض آیات للموقنین و فی انفسکم افل تبصرون‬

ant colony • Communication through the use of pheromone trails. • Self-organisation: high-level function is the result of the combination of the ants’ low-level tasks.

Effect: optimised cost of the ants’ searching process though global information is not available.

Foraging behavior of Ants

• 2 ants start with equal probability of going on either path.

Foraging behavior of Ants

• The ant on shorter path has a shorter to-and-fro time from it’s nest to the food.

Foraging behavior of Ants

• The density of pheromone on the shorter path is higher because of 2 passes by the ant (as compared to 1 by the other).

Foraging behavior of Ants

• The next ant takes the shorter route.

Foraging behavior of Ants

• Over many iterations, more ants begin using the path with higher pheromone, thereby further reinforcing it.

Foraging behavior of Ants

• After some time, the shorter path is almost exclusively used.

Defining Ant Systems • Problem Representation The problem has to be represented as a graph, the solution being a minimum cost path.

• Evaluation function Problem-specific function that evaluates the solutions.

• Local heuristic The information that guides the ants’ search process e.g. the gain in the value of the evaluation function.

• Pheromone update rule(s) Define the amount and timing of the pheromone disposal.

• Probabilistic transition rule Utilises both the heuristic value and the pheromone amounts so that the ants decide their transitions from one node of the graph to the next.

General Ant Colony Heuristic

For discrete optimization problem with: • Set of nodes S={1,…,N} • Edges for nodes with time-dependent costs • States = lists of nodes • Neighbourhood of states given by the edges • Constraints for feasible states, solutions • Costs for solutions given by the edgecosts

Ant Colony Meta-heuristic • Procedure AntMetaHeuristic – Set parameters, initial pheromone levels – While (termination condition not met) do • Construct Ants’ Solutions • Evaluate Solutions • Update Pheromones (according to soln goodness)

– End

• End

General Ant Colony Heuristic (II)

Pheromone evaporation

Ants generation and activity

Daemon activities

05/31/08

Seminar Learning Algorithms

12

General Ant Colony Heuristic (III) Ants generation and activity: compute  make decision while resources transition and move available: create ant probabilities  for each ant: 4. initialize 5. let ant run until a solutionevaluate update the is found the current state state 6. possibly: update pheromone and routing possibly table update pheromone 05/31/08

Seminar Learning Algorithms

13