Intelligent Systems II · TEE · papers

Q7(b) ACO for TSP [10]

Final examination · 24 Nov 2025

Actual TEE paper · 100 marks · 3 hours · Q1 compulsory + any 4 of Q2–Q7 · every answer verified (key errors flagged)

Question. For the four-city travelling salesman problem, the distance and pheromone matrices (A, B, C, D) are given. Apply Ant Colony Optimization. Calculate the path travelled by 2 ants to cover all cities starting from city A. Random numbers for Ant 1 are 0.3, 0.8 and for Ant 2 are 0.5, 0.7. Also update the pheromone matrix after 1 iteration. [10 marks]

Answer

Given

D=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&4&2&4\\B&4&0&3&6\\C&2&3&0&2\\D&4&6&2&0\end{array}\qquad \tau=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&1&1&1\\B&1&0&1&1\\C&1&1&0&1\\D&1&1&1&0\end{array}LaTeX: D=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&4&2&4\\B&4&0&3&6\\C&2&3&0&2\\D&4&6&2&0\end{array}\qquad \tau=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&1&1&1\\B&1&0&1&1\\C&1&1&0&1\\D&1&1&1&0\end{array}

Assume \alpha=\beta=1LaTeX: \alpha=\beta=1, \rho=0.5LaTeX: \rho=0.5, Q=1LaTeX: Q=1 (class convention; not stated in the question).

To find

Tour of each ant, tour lengths, updated pheromone matrix.

Swipe across the diagram to read its labels ↔
Final 2025 Q7b: distances (all pheromones start at 1)
Diagram: Final 2025 Q7b: distances (all pheromones start at 1). Labels: Final 2025 Q7b: distances (all pheromones start at 1) | 4 | 2 | 4 | 3 | 6 | 2 | A | B | C | D

Formula and why it applies

P_{ij}=\frac{\tau_{ij}\,\eta_{ij}}{\sum_{l\in\text{allowed}}\tau_{il}\,\eta_{il}},\qquad\eta_{ij}=\frac1{d_{ij}}LaTeX: P_{ij}=\frac{\tau_{ij}\,\eta_{ij}}{\sum_{l\in\text{allowed}}\tau_{il}\,\eta_{il}},\qquad\eta_{ij}=\frac1{d_{ij}}
\tau_{ij}^{new}=(1-\rho)\tau_{ij}+\sum_{k:\,ij\in\mathrm{tour}_k}\frac{Q}{L_k}LaTeX: \tau_{ij}^{new}=(1-\rho)\tau_{ij}+\sum_{k:\,ij\in\mathrm{tour}_k}\frac{Q}{L_k}

The sum includes only ants whose completed tour contains edge ij. An unused edge receives no deposit but still evaporates. Here distances are symmetric, so a traversed edge updates both symmetric matrix cells. Both ants construct their tours using the old pheromones; update after both finish, including their return to A.

Solution

Step 1. Probabilities from A (both ants start at A)
\tau\eta:\;A\to B=1\times\tfrac14=0.25,\quad A\to C=1\times\tfrac12=0.5,\quad A\to D=1\times\tfrac14=0.25;\quad\text{sum}=1LaTeX: \tau\eta:\;A\to B=1\times\tfrac14=0.25,\quad A\to C=1\times\tfrac12=0.5,\quad A\to D=1\times\tfrac14=0.25;\quad\text{sum}=1
MovePCumulativeRange
A→B0.250.250–0.25
A→C0.500.750.25–0.75
A→D0.251.000.75–1

Ant 1: r = 0.3 → C. Ant 2: r = 0.5 → C.

Step 2. Probabilities from C (B and D left)
C\to B=\tfrac13=0.3333,\quad C\to D=\tfrac12=0.5;\quad\text{sum}=0.8333\Rightarrow P_{CB}=0.4,\;P_{CD}=0.6LaTeX: C\to B=\tfrac13=0.3333,\quad C\to D=\tfrac12=0.5;\quad\text{sum}=0.8333\Rightarrow P_{CB}=0.4,\;P_{CD}=0.6

Cumulative in city order: B 0–0.4, D 0.4–1. Ant 1: r = 0.8 → D. Ant 2: r = 0.7 → D.

Step 3. Complete the tours

Only B is left, then return to A.

\text{Ant 1}=\text{Ant 2}:\;A\to C\to D\to B\to A,\qquad L=2+2+6+4=14LaTeX: \text{Ant 1}=\text{Ant 2}:\;A\to C\to D\to B\to A,\qquad L=2+2+6+4=14
Swipe across the diagram to read its labels ↔
Both ants: A → C → D → B → A, length 14
Diagram: Both ants: A → C → D → B → A, length 14. Labels: Both ants: A → C → D → B → A, length 14 | 4 | 2 | 4 | 3 | 6 | 2 | A | B | C | D
Step 4. Pheromone update

Each ant deposits Q/L=1/14=0.0714LaTeX: Q/L=1/14=0.0714 on each edge of its tour; two ants used the same four edges (AC, CD, DB, BA), so each gets 2/14=0.1429LaTeX: 2/14=0.1429.

\text{used edge: }(1-0.5)(1)+0.1429=0.6429\qquad\text{unused edge (AD, BC): }(1-0.5)(1)+0=0.5LaTeX: \text{used edge: }(1-0.5)(1)+0.1429=0.6429\qquad\text{unused edge (AD, BC): }(1-0.5)(1)+0=0.5
\tau_{\text{new}}=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&0.6429&0.6429&0.5\\B&0.6429&0&0.5&0.6429\\C&0.6429&0.5&0&0.6429\\D&0.5&0.6429&0.6429&0\end{array}LaTeX: \tau_{\text{new}}=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&0.6429&0.6429&0.5\\B&0.6429&0&0.5&0.6429\\C&0.6429&0.5&0&0.6429\\D&0.5&0.6429&0.6429&0\end{array}
Final answer. Both ants: A → C → D → B → A, length 14. Updated pheromone: 0.6429 on AB, AC, CD, BD; 0.5 on AD and BC. In the next iteration the ants will prefer the edges of this tour.
Official key note. The key's matrix shows 0.643 on AC, CD and BD but leaves AB at 0.5, i.e. it forgot to deposit on the return edge B → A even though it counted its length (4) in L = 14. Your slides deposit on the return edge, so AB = 0.6429 is correct. If you wish, write one line: “the return edge B–A is part of the tour, so it also receives Q/L.”

Official marking: path of Ant 1 (3) + path of Ant 2 (3) + pheromone matrix (4).