Intelligent Systems II · TEE · papers
Q6(a) ACO tour lengths, evaporation and pheromone deposition [10]
Final / re-examination · 28 Apr 2025
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, 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
LaTeX: 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}
LaTeX: \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
LaTeX: L_1=d_{AB}+d_{BC}+d_{CD}+d_{DA}=10+1+1+3=15Step 2. Compute tour 2 from the cost matrix
LaTeX: L_2=d_{AC}+d_{CB}+d_{BD}+d_{DA}=4+1+2+3=10Tour 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
LaTeX: \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.