# Q7(c) ACO path length and pheromone update [5]

Subject: Intelligent Systems II

Exam: TEE

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

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

Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.

**Question. Q7(c)** [5 marks · 2024-06-25]

For the four-city travelling salesman problem, row and column order is A, B, C, D. The pheromone and cost matrices are:



$$
\tau=\begin{bmatrix}0&15&5&4\\15&0&4&8\\5&4&0&1\\4&8&1&0\end{bmatrix}
$$





$$
D=\begin{bmatrix}0&10&4&3\\10&0&1&2\\4&1&0&1\\3&2&1&0\end{bmatrix}
$$



Ant L₁ travels A–B–C–D–A and ant L₂ travels A–C–B–D–A. Taking the vaporization coefficient as 0.5, calculate (1) the length of each path and (2) pheromone level for each path.

### Answer

#### Given

Two tours: A–B–C–D–A and A–C–B–D–A; evaporation ρ=0.5; printed matrices above.

#### To find

Both tour lengths and updated pheromone on every edge.

#### Formula and why it applies

Distance is read from the COST matrix, not the pheromone matrix. Sum all edges including the return home. Under the standard Ant System update, evaporate the old trail once, then add deposits from every ant that traversed the edge.



$$
L_k=\sum_{(i,j)\in tour_k}d_{ij},\qquad \tau_{ij}^{new}=(1-\rho)\tau_{ij}^{old}+\sum_k\Delta\tau_{ij}^{k},\quad \Delta\tau_{ij}^{k}=Q/L_k
$$



#### Solution

**Source / assumption note.** The deposit constant Q is not supplied. The numerical answer below explicitly assumes Q=1 and undirected, symmetric edges. If your examiner specifies another Q, multiply each deposit by that Q. Pheromone is an edge quantity, not one scalar for a whole path.

##### Step 1. Calculate tour 1 length



$$
L_1=d_{AB}+d_{BC}+d_{CD}+d_{DA}=10+1+1+3=15
$$



##### Step 2. Calculate tour 2 length



$$
L_2=d_{AC}+d_{CB}+d_{BD}+d_{DA}=4+1+2+3=10
$$



##### Step 3. Calculate deposit per used edge



$$
\Delta\tau_1=1/15\approx0.0666667,\qquad\Delta\tau_2=1/10=0.1
$$



The shorter tour receives the larger deposit. Shared edges BC and AD receive both deposits; unused-by-an-ant edges receive zero from that ant.

##### Step 4. Update each distinct undirected edge

| Edge | Old pheromone | After evaporation | Deposit from tour 1 | Deposit from tour 2 | New pheromone |
| --- | --- | --- | --- | --- | --- |
| AB | 15 | 7.5 | 1/15 | 0 | 7.566667 |
| AC | 5 | 2.5 | 0 | 1/10 | 2.600000 |
| AD | 4 | 2 | 1/15 | 1/10 | 2.166667 |
| BC | 4 | 2 | 1/15 | 1/10 | 2.166667 |
| BD | 8 | 4 | 0 | 1/10 | 4.100000 |
| CD | 1 | 0.5 | 1/15 | 0 | 0.566667 |

##### Step 5. Assemble the symmetric matrix



$$
\begin{bmatrix}0&7.566667&2.6&2.166667\\7.566667&0&2.166667&4.1\\2.6&2.166667&0&0.566667\\2.166667&4.1&0.566667&0\end{bmatrix}
$$



The diagonal remains zero because an ant does not travel from a city to itself.

**Final answer.** Tour lengths are 15 and 10. The table and matrix give all updated edge pheromones under Q=1.