In ant colony optimization (ACO), a pheromone concentration is a number assigned to a path or edge. It acts like a shared trail: ants that find promising routes strengthen the trail, making later ants more likely to try those routes. The trail guides a search; it does not make a choice certain. section 10.0 section 10.2
At each node, an artificial ant chooses among feasible next nodes. Its choice combines the edge’s pheromone concentration, τ, with a heuristic desirability, η, such as inverse distance. The parameters α and β control their respective influence. A high α can give too much weight to early, randomly established trails and lead to rapid convergence on a suboptimal path. section 10.3.1
A small shortest-path search
Give every edge an initial pheromone concentration of 0.5 and place five ants at the source node. With α = β = 1, each ant weighs pheromone and inverse edge length when choosing between neighboring nodes. A higher-probability edge is more likely to be selected, but another edge can still be explored. Once the ants construct paths, their trails can be updated for the next iteration. section 10.3.1
A pheromone update has two parts:
- Evaporation reduces existing concentrations so old trails do not retain their influence indefinitely. With no evaporation, ants may repeatedly follow the same path and become trapped in a local optimum. section 10.2
- Deposit strengthens edges used by ants. In a route implementation, each traversed edge receives an amount proportional to Q divided by that ant’s path cost, rewarding shorter paths more strongly. section 10.3.5
def update_pheromones(paths, pheromones):
delta_pheromones = np.zeros_like(pheromones) #1
for i in range(ants): #2
for j in range(city_count - 1):
city1_idx, city2_idx = paths[i, j], paths[i, j + 1] #3
delta_pheromones[city1_idx, city2_idx] += Q / cost_ #4
function(paths[i])
return (1 - evaporation_rate) * pheromones + delta_pheromones #5
The update function shows cost-based deposits accumulated on traversed edges, followed by evaporation of the existing pheromone matrix. section 10.3.5
Pheromone can be deposited while a solution is being built or after its completed path is revisited. For a practical routing experiment, vary the evaporation rate and the relative influence of pheromone and distance: stronger trails exploit discoveries, while continued exploration helps avoid premature stagnation. ACO remains a stochastic search rather than a guarantee of the best route. section 10.6 section 10.3.1
