7 Ant Colony Optimization Introduction

Individuals of the swarm may lack a certain property, but the swarm as a whole possesses it.
This is called the emergent property of the swarm.
Example: Wetness of water (individual water molecules are not wet).
Example: Solidity of matter (single atoms or molecules are not solid).
Intelligence can be an emergent property (e.g., brain as a collective of neurons).
Each element of the swarm has:
- Simple behavior.
- Rules for interacting with others and the environment.
There is no central controller.
Property x emerges from local interactions.

Ants are blind, reactive, and lack planning capabilities.
However, as a colony, they can perform complex tasks like finding food.
Termites can build complex structures without a central architect.
Swarm intelligence has inspired successful optimization algorithms (ant colony optimization and particle swarm optimization).

Introduced by Danburg in 1989.
Experiment setup: Ants, nest, food, and an obstacle.
Symmetric obstacle: Ants initially choose randomly, but eventually, most choose one way.
Asymmetric obstacle (shorter and longer paths): Ants quickly find the shortest path.

Intelligence resides in the environment, not the ants themselves.
Stigmergy: Indirect communication via interaction with the environment.
Ants release pheromones to mark the environment and are attracted to pheromones.

Triggering action based on intent to solve a problem (not how ants operate).
Sign-based stigmergy: Ants release pheromones and follow them without knowing they are solving a problem.

Ants are behaviorally unsophisticated but can perform complex tasks collectively.
Communicate via pheromones and follow trails.

Individual ants lay pheromone trails while traveling.
Pheromone trails evaporate over time.
Trail strength accumulates with multiple ants using a path.
Ants prefer paths with more pheromone.
Why this leads to the shortest path:
- Longer paths take more time, leading to pheromone evaporation.
- Shorter paths accumulate pheromones faster.
- Positive feedback loop: more pheromone attracts more ants to the shorter path.

Autocatalytic reaction: A reaction that produces the catalyst, speeding up the reaction (positive feedback).
This is analogous to the pheromone accumulation on the shortest path.

Agents move along edges between nodes in a graph.
Choice of path based on pheromone strength (and possibly other factors).
Ant's path represents a solution.
When an ant completes a solution, pheromone is laid on its path, proportional to solution quality.
Overall behavior: stigmergy leads to finding the shortest path.

Goal: Find the shortest path through multiple cities.
Cities: A, B, C, D.
Connections between cities with initial random pheromone amounts.
Ant is placed on a node at random.
Ant chooses the next node based on pheromone levels.
Example: At B, edges to A, C, D have pheromone level 10, 40, and 0
Ant is memory, remembers where it went, so that same city is not visited twice.
Solution evaluation and pheromone update:
- Evaporate pheromone proportionally to existing quantity.
- Increase pheromone on the path based on the quality of the solution.
Subsequent ants are biased towards the best parts of the path.
The process creates a learning algorithm where ant doesn't, the environment does based on existing pheromones.