# Q6(a) ACO for TSP [10]

Subject: Intelligent Systems II

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/is2/#tee/papers/paper-reexam-2026/q6a

Canonical: https://deep-learning-study-room.vercel.app/read/is2/tee/papers/paper-reexam-2026--q6a/

Actual TEE re-exam · 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 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)
$$



Assume 

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





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



Swipe across the diagram to read its labels ↔

![Re-exam 2026 Q6a: both ants A → B → D → C → A, length 14](https://deep-learning-study-room.vercel.app/is2/fig/aco_reexam_graph.02195c6ee9.svg)

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

; unused edges AD and BC become 

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