Intelligent Systems II · TEE · mocks

Q6(a) ACO for TSP [10]

Re-examination · 31 Jan 2026

100-mark timed practice using the actual Re-exam 2026 paper. Q1 compulsory; any four of Q2–Q7. Worked solutions are below the questions.

Question. For the four-city travelling salesman problem the distance matrix and pheromone matrix are given (all pheromones 1). Apply Ant Colony Optimization. Calculate the path travelled by 2 ants 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&1&2&3\\B&1&0&4&5\\C&2&4&0&6\\D&3&5&6&0\end{array},\qquad\tau_{ij}=1\;(i\ne j)LaTeX: D=\begin{array}{c|cccc}&A&B&C&D\\\hline A&0&1&2&3\\B&1&0&4&5\\C&2&4&0&6\\D&3&5&6&0\end{array},\qquad\tau_{ij}=1\;(i\ne j)

Assume \alpha=\beta=1,\;\rho=0.5,\;Q=1LaTeX: \alpha=\beta=1,\;\rho=0.5,\;Q=1.

To find

Both tours, their lengths and the pheromone matrix after one iteration.

Formula and why it applies

P_{ij}=\frac{\tau_{ij}^{\alpha}(1/d_{ij})^\beta}{\sum_{k\in allowed}\tau_{ik}^{\alpha}(1/d_{ik})^\beta}LaTeX: P_{ij}=\frac{\tau_{ij}^{\alpha}(1/d_{ij})^\beta}{\sum_{k\in allowed}\tau_{ik}^{\alpha}(1/d_{ik})^\beta}
\tau_{ij}^{new}=(1-\rho)\tau_{ij}+\sum_{k:\,ij\in tour_k}\frac{Q}{L_k}LaTeX: \tau_{ij}^{new}=(1-\rho)\tau_{ij}+\sum_{k:\,ij\in tour_k}\frac{Q}{L_k}

Use unvisited cities in alphabetical order for cumulative selection. Every ant completes its tour using old pheromones; then evaporate and deposit on each undirected edge, including the return edge.

Solution

Step 1. From A
\eta:\;B=1,\;C=0.5,\;D=0.3333;\;\text{sum}=1.8333\Rightarrow P=0.5455,\;0.2727,\;0.1818LaTeX: \eta:\;B=1,\;C=0.5,\;D=0.3333;\;\text{sum}=1.8333\Rightarrow P=0.5455,\;0.2727,\;0.1818

Cumulative: B 0–0.5455, C 0.5455–0.8182, D 0.8182–1. Ant 1 (0.3) → B; Ant 2 (0.5) → B.

Step 2. From B (C and D left)
\eta:\;C=0.25,\;D=0.2;\;\text{sum}=0.45\Rightarrow P_{BC}=0.5556,\;P_{BD}=0.4444LaTeX: \eta:\;C=0.25,\;D=0.2;\;\text{sum}=0.45\Rightarrow P_{BC}=0.5556,\;P_{BD}=0.4444

Cumulative: C 0–0.5556, D 0.5556–1. Ant 1 (0.8) → D; Ant 2 (0.7) → D.

Step 3. Complete the tours
A\to B\to D\to C\to A,\qquad L=1+5+6+2=14\;\text{(both ants)}LaTeX: A\to B\to D\to C\to A,\qquad L=1+5+6+2=14\;\text{(both ants)}
Swipe across the diagram to read its labels ↔
Re-exam 2026 Q6a: both ants A → B → D → C → A, length 14
Diagram: Re-exam 2026 Q6a: both ants A → B → D → C → A, length 14. Labels: Re-exam 2026 Q6a: both ants A → B → D → C → A, length 14 | 1 | 2 | 3 | 4 | 5 | 6 | A | B | C | D
Step 4. Pheromone update

Used edges AB, BD, DC, CA get 0.5(1)+2\times\frac1{14}=0.6429LaTeX: 0.5(1)+2\times\frac1{14}=0.6429; unused edges AD and BC become 0.5LaTeX: 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 → B → D → C → A, length 14. Pheromone 0.6429 on AB, BD, CD, AC; 0.5 on AD, BC.
Official key note. This key applies no evaporation (1+0.1428=1.1428LaTeX: 1+0.1428=1.1428) and its matrix is inconsistent: it increases the unused edge A–D, leaves the used return edge C–A at 1, and gives B–D and D–B different values. If your examiner follows the no-evaporation idea, the consistent version is 1.1429 on AB, BD, CD, AC and 1 on AD, BC. The paper does not specify ρ. State the convention you use; the resulting matrix depends on it. Grading depends on the examiner’s intended convention.