Week 9: Ant Colony Optimisation

Question 1

Ant Colony Optimisation

Answer 1

This algorithm takes inspiration from the pathfinding methods of ants. Ants leave pheromones when they traverse a path, which increases the likelihood that subsequent ants will follow this path.

Pros:
- Easy to implement parallel methods
- Feedback procedure accounts for good solutions
- Efficient for TSP-like problems due to inherent structure
- Population-based search (as opposed to Simulated Annealing)

Cons
- Easy to fall into local optima region
- The probability distribution changes over time
- Time of convergence is unknown

Question 2

Pheromone Update

Answer 2

The updating of pheromones is usually tied to the total cost of the path the ant takes.

Question 3

Evaporation

Answer 3

There’s usually a mechanism for evaporating pheromones in each iteration.

Question 4

Probability of Selecting Edges

Answer 4

These are proportional to the pheronome level of the edge multiplied by the inverse of the cost of the edge.