liveBook · Manning

State transition rule

As explained in Algorithms Every Programmer Should Know

A procedure for choosing among available next states, often by assigning probabilities to alternatives.

A state transition rule chooses an ant’s next unvisited node by assigning a probability to each available path. The probability reflects both the path’s pheromone level and its heuristic desirability, typically the inverse of its distance. section 8.1

Pxy = 𝜏xy . ηxy / sum(𝜏.η)

The rule multiplies pheromone by heuristic desirability, then divides by the sum of those scores across available paths. section 8.1

Choosing from the Nest

With pheromone levels initially equal to 1, distances of 10, 15, and 20 give the paths from the Nest probabilities of 46%, 31%, and 23%. After moving to B, the ant recalculates its choice: C has 55% probability and D 45%. section 8.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through normalized path scores numerically, then implements next-node selection in a function.
Examples
Calculates choices from the Nest and from B using distances and initially equal pheromone levels.
What you can do after
Apply it to choose an ant’s next unvisited node using weighted probabilities based on pheromone and heuristic desirability.
How it connects
Connects ant colony optimization with pheromone, heuristic desirability, distance, and exploration and exploitation.

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.