A metaheuristic is a high-level search strategy for finding good solutions when exhaustive or deterministic methods become too costly. Ant Colony Optimization (ACO) uses artificial ants to search for good routes, trading a guarantee of the global optimum for faster computation. section 8.4
ACO balances exploration—trying alternative routes—with exploitation of promising ones:
- At each step, an ant probabilistically chooses among unvisited nodes using path pheromone and a distance-based heuristic, typically the inverse of distance. section 8.4
- After each tour, pheromone evaporates across paths and ants deposit more on the edges they traversed; shorter tours receive larger deposits. section 8.4
- The repeated feedback loop favors successful routes while evaporation helps prevent the swarm from settling too early on a mediocre one. section 8.4
Choosing a route
For initial paths of 10, 15, and 20 miles, the inverse-distance heuristics are 0.10, about 0.067, and 0.05. With equal starting pheromone, the 10-mile path has the highest initial selection weight, but alternatives remain possible. section 8.1
Table 8.1 Calculating the initial path probabilities for an artificial ant leaving the Nest (Node A)
|
Available path
|
Distance
|
Heuristic
|
Pheromone
|
Raw Score
|
|
Nest to Crumb B
|
10
|
0.10
|
1
|
0.10
|
|
Nest to Crumb C
|
15
|
0.067
|
1
|
0.067
|
|
Nest to Crumb D
|
20
|
0.05
|
1
|
0.05
|
|
Total Sum
|
|
|
|
0.217
|
Compare the three candidate paths’ distances, heuristics, pheromones, and raw scores. section 8.1



