Intelligent Systems II · TEE · read

ACO formulas: transition probability, city choice and pheromone update

Unit 3 · Ant colony optimization (ACO)

Unit 3 · Ant colony optimization for TSP · asked as a 10-mark numerical in both 2025–26 papers

From city A an ant may choose B or C. Distances are AB=2 and AC=4. Pheromones are both 1 and α=β=1. Find the next-city probabilities. [2 marks · Worked example]

Given

Current city A; allowed next cities B and C. Distances dAB=2 and dAC=4. Pheromones τAB=τAC=1, and exponents α=β=1. Visited cities are excluded.

To find

P(A→B) and P(A→C).

Formula and why it applies

\eta_{ij}=1/d_{ij}\qquad P_{ij}=\tau_{ij}\eta_{ij}/\sum_{l\in allowed}\tau_{il}\eta_{il}

Shorter distance gives a larger reciprocal. Normalise the desirability weights to probabilities.

Solution

Step 1. Take reciprocal distances

\eta_{AB}=1/2=0.5\qquad\eta_{AC}=1/4=0.25

Step 2. Multiply by pheromone

w_B=1\times0.5=0.5\qquad w_C=1\times0.25=0.25

Step 3. Add allowed weights

0.5+0.25=0.75

Step 4. Divide each weight by their total

P_{AB}=0.5/0.75=2/3

P_{AC}=0.25/0.75=1/3

Final answer. B has probability 2/3; C has probability 1/3. These are probabilities, not a rule forcing the nearest city every time.

Evaporation ρ=.5 means retain 1−.5=.5 of the old pheromone. A completed tour of length 20 deposits Q/20 on each edge it used; with Q=1 this is .05. An unused edge receives no deposit from that ant. Use complete tour length, not the length of the individual edge, in this denominator.

In one line: an ant picks the next city with probability ∝ pheromone × (1/distance); after all ants finish, pheromone evaporates and each ant adds Q/(its tour length) to every edge it used.

1. Transition probability

An ant $k$ at city $i$ moves to an unvisited city $j$ with probability

P^{k}_{ij}=\frac{\tau_{ij}^{\,\alpha}\,\eta_{ij}^{\,\beta}}{\displaystyle\sum_{l\in\text{allowed}}\tau_{il}^{\,\alpha}\,\eta_{il}^{\,\beta}},\qquad \eta_{ij}=\frac1{d_{ij}}

$\tau_{ij}$ : pheromone on edge $i$ – $j$ ; $\eta_{ij}$ : visibility (heuristic), the inverse of distance.
$\alpha$ : weight of pheromone; $\beta$ : weight of distance. In every class example $\alpha=\beta=1$ .
“allowed” = cities this ant has not visited yet.

With all $\tau=1$ and $\alpha=\beta=1$ , the probabilities are simply proportional to $1/d$ .

2. Choosing the city with a random number (cumulative rule)

List the allowed cities in alphabetical (city) order, not sorted by probability.
Write their cumulative probabilities.
Pick the first city whose cumulative value is ≥ the random number $r$ .
When only one city is left, the ant goes there without using a random number, then returns to the start.

Exam trap. In Final 2025 Q7b, from city C the candidates are B (0.4) and D (0.6). In city order the ranges are B: 0–0.4, D: 0.4–1, so r = 0.8 selects D. If you sort by probability (D first) you would pick B and get the wrong tour. The official key uses city order.

3. Pheromone update (after all ants finish)

\tau_{ij}\leftarrow(1-\rho)\,\tau_{ij}+\sum_{k=1}^{m}\Delta\tau^{k}_{ij},\qquad \Delta\tau^{k}_{ij}=\begin{cases}Q/L_k&\text{if ant }k\text{ used edge }(i,j)\\0&\text{otherwise}\end{cases}

$\rho$ : evaporation rate (fraction lost). Class examples use $\rho=0.5$ . $Q$ : deposit constant, usually 1.
$L_k$ : length of ant $k$ 's complete tour including the return edge. Shorter tours deposit more.
Edges are undirected: update $\tau_{ij}$ and $\tau_{ji}$ together (the matrix stays symmetric).
The update happens once per iteration, after every ant has finished; within an iteration all ants use the same pheromone values.

When the question gives no ρ or Q (both 2025–26 papers): write “Assume ρ = 0.5 and Q = 1, as in the class example” and proceed. That is exactly what the Final 2025 key does.

4. Algorithm (Ant System)

Initialise parameters: number of ants, α, β, ρ, Q, initial pheromone $\tau_0$ , maximum iterations.
Place each ant on its start city.
Each ant repeatedly chooses the next city with the transition probability until it has visited all cities, then returns to the start.
Compute each tour length $L_k$ and record the best tour.
Update pheromone: evaporation, then deposit $Q/L_k$ .
Repeat steps 2–5 until the iteration limit; output the best tour.

Parameter	Meaning	Typical value
m	Number of ants	number of cities (or 20)
α	Pheromone importance	1
β	Distance (visibility) importance	1 (often 2–5 in practice)
ρ	Evaporation rate	0.5 in class numericals (0.05–0.5 in practice)
Q	Deposit constant	1 (100 in one slide example)
$\tau_0$	Initial pheromone	1 in exam questions

Yaad rakho: Probability = τ × (1/d), phir normalize. City order mein cumulative, pehla ≥ r. Update = ½ purana + Q/L har us edge par jo use hua (wapas wala edge bhi).