Intelligent Systems II · TEE · papers
Q7(c) ACO path length and pheromone update [5]
Re-examination · 25 Jun 2024
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
For the four-city travelling salesman problem, row and column order is A, B, C, D. The pheromone and cost matrices are:
LaTeX: \tau=\begin{bmatrix}0&15&5&4\\15&0&4&8\\5&4&0&1\\4&8&1&0\end{bmatrix}
LaTeX: 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.
LaTeX: 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_kSolution
Step 1. Calculate tour 1 length
LaTeX: L_1=d_{AB}+d_{BC}+d_{CD}+d_{DA}=10+1+1+3=15Step 2. Calculate tour 2 length
LaTeX: L_2=d_{AC}+d_{CB}+d_{BD}+d_{DA}=4+1+2+3=10Step 3. Calculate deposit per used edge
LaTeX: \Delta\tau_1=1/15\approx0.0666667,\qquad\Delta\tau_2=1/10=0.1The 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
LaTeX: \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.