Simple ant colony optimization (SACO) is a population-based metaheuristic for constructing graph solutions with simulated pheromone trails. It models how ants collectively favor promising paths: better solutions intensify trails, attracting further exploration. section 10.3.1 section 10.6
A SACO iteration follows this pattern:
- Initialize every edge with a small random pheromone concentration and place multiple ants at the source node. section 10.3.1
- Let each ant incrementally construct a feasible path, initially selecting randomly and later using a transition probability. section 10.3.1
- Weight each possible move using pheromone concentration and heuristic desirability, typically the inverse of edge distance. section 10.3.1
- Evaporate pheromone and deposit new pheromone during construction, after construction, or through both update methods. section 10.6
Choosing the next edge
With five ants, initial pheromone 0.5, and α = β = 1, an ant at node 1 compares neighboring nodes 2 and 3. Using inverse edge length as desirability, it calculates both transition probabilities, generates a random number between 0 and 1, and selects the corresponding edge; the more desirable edge is more likely. section 10.3.1
Figure 10.8 The first ant is at source node 1 with neighbors 2 and 3. There are two numbers on each edge separated by a colon. The first number represents the length of the edge, and the second represents the current pheromone concentration on the edge.
Inspect the graph showing edge lengths alongside current pheromone concentrations before path construction. section 10.3.1
Figure 10.10 Updated pheromone concentrations
Inspect how pheromone concentrations change after ants construct paths. section 10.3.1
