# Q6(a) ACO tour lengths, evaporation and pheromone deposition [10]

Subject: Intelligent Systems II

Exam: TEE

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

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

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

**Question. Q6(a)** [10 marks · 2025-04-28]

For the four city Travelling salesman problem, the pheromone and cost matrix (A, B, C, D in that order given by row no, and column no) are given by

| Pheromone | A | B | C | D |
| --- | --- | --- | --- | --- |
| A | 0 | 15 | 5 | 4 |
| B | 15 | 0 | 4 | 8 |
| C | 5 | 4 | 0 | 1 |
| D | 4 | 8 | 1 | 0 |

| Cost | A | B | C | D |
| --- | --- | --- | --- | --- |
| A | 0 | 10 | 4 | 3 |
| B | 10 | 0 | 1 | 2 |
| C | 4 | 1 | 0 | 1 |
| D | 3 | 2 | 1 | 0 |

Ant L1 travels from A-B-C-D-A and Ant L1 travels from A-C-B-D-A and Taking vaporization co-efficient as 0.5, calculate the following:1.The length of each path 2.Pheromone level for each path

### Answer

### Given

Initial pheromones and symmetric costs are printed above; evaporationρ=0.5. The two listed tours are treated as ant 1 and ant 2, although the scan repeats the nameL 1. Deposit constantQ is not supplied.

### To find

Tour lengths and updated edge pheromones after evaporation and both deposits.

### Formula and why



$$
L_k=\sum_{(i,j)\in tour_k}d_{ij},\quad\Delta\tau_{ij}^{k}=\begin{cases}Q/L_k&(i,j)\in tour_k\\0&\text{otherwise}\end{cases}
$$





$$
\tau_{ij}^{new}=(1-\rho)\tau_{ij}^{old}+\sum_k\Delta\tau_{ij}^{k}
$$



Declare the standard Ant System update: evaporate once, then add both ants' deposits. Because the matrices are symmetric, treat each city pair as an undirected edge. Give the answer inQ, then illustrateQ=1; noQ value is silently attributed to the paper.

### Step 1. Compute tour 1 from the cost matrix



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



### Step 2. Compute tour 2 from the cost matrix



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



Tour 2 is shorter and deposits more per used edge:Q/10 instead ofQ/15. Use the cost matrix for lengths, not the pheromone matrix.

### Step 3. List which ants use each undirected edge

| Edge | Old τ | After evaporation 0.5τ | Deposits | New τ |
| --- | --- | --- | --- | --- |
| AB | 15 | 7.5 | Q/15 | 7.5+Q/15 |
| AC | 5 | 2.5 | Q/10 | 2.5+Q/10 |
| AD | 4 | 2 | Q/15+Q/10=Q/6 | 2+Q/6 |
| BC | 4 | 2 | Q/15+Q/10=Q/6 | 2+Q/6 |
| BD | 8 | 4 | Q/10 | 4+Q/10 |
| CD | 1 | 0.5 | Q/15 | 0.5+Q/15 |

BC andCB are the same undirected edge here; both tours also useDA. Both deposits must be included on those shared edges.

### Step 4. If Q=1 is assumed, substitute



$$
\tau^{new}\approx\begin{bmatrix}0&7.566667&2.600000&2.166667\\7.566667&0&2.166667&4.100000\\2.600000&2.166667&0&0.566667\\2.166667&4.100000&0.566667&0\end{bmatrix}
$$



For example,τAD=0.5×4+1/15+1/10=2+1/6=2.166667. Pheromone is maintained on edges; a single scalar “pheromone of the whole tour” is not defined by this rule. Each path's edge levels can be read from the matrix. The diagonal stays unused at 0.