An ant is a simulated search agent that incrementally constructs a candidate path while communicating indirectly through pheromone trails. A group of ants explores alternatives, and repeated pheromone updates can favor promising routes. section 10.2
A simple ant-colony search proceeds through these actions:
- Start each ant at the source or nest with an initially random or equal pheromone concentration on available paths. section 10.2 section 10.3.1
- Construct a path incrementally, selecting the next feasible edge using pheromone strength and an edge-desirability heuristic. section 10.3.1
- Update trails through evaporation and deposit, allowing useful routes to gain influence while retaining some exploration. section 10.2
- Tune pheromone influence carefully: excessive emphasis on pheromone can produce rapid convergence to a suboptimal path. section 10.3.1
Choosing the next edge
In a shortest-path graph, place five ants at source node 1 and initialize each edge with pheromone 0.5. If the ant can move to nodes 2 or 3, it combines pheromone with inverse edge length, then draws a random number to select the next node. Each ant repeats this process until it constructs a path; updated pheromone concentrations then influence later choices. 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.
Use the graph view to inspect neighboring nodes, edge lengths, and current pheromone concentrations involved in the first decision. section 10.3.1
