# Q7(b) ACO for TSP [10]

Subject: Intelligent Systems II

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/is2/#tee/mocks/paper-final-2025/q7b

Canonical: https://deep-learning-study-room.vercel.app/read/is2/tee/mocks/paper-final-2025--q7b/

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

**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}
$$



Assume 

$$
\alpha=\beta=1
$$

, 

$$
\rho=0.5
$$

, 

$$
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)](https://deep-learning-study-room.vercel.app/is2/fig/aco_final_graph.ac3cd4aeac.svg)

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}}
$$





$$
\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}=1
$$



| Move | P | Cumulative | Range |
| --- | --- | --- | --- |
| A→B | 0.25 | 0.25 | 0–0.25 |
| A→C | 0.50 | 0.75 | 0.25–0.75 |
| A→D | 0.25 | 1.00 | 0.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.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=14
$$



Swipe across the diagram to read its labels ↔

![Both ants: A → C → D → B → A, length 14](https://deep-learning-study-room.vercel.app/is2/fig/aco_final_tour.1dbfdb8b98.svg)

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.0714
$$

 on each edge of its tour; two ants used the same four edges (AC, CD, DB, BA), so each gets 

$$
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.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}
$$



**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).