# Q4(b) ACO components and roles [10]

Subject: Intelligent Systems II

Exam: TEE

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

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

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

**Question. Q4(b)** [10 marks · 2024-04-17]

Describe the key components of an Ant Colony Optimization algorithm and their respective roles in finding optimal solutions.

### Answer

**Ant Colony Optimization (ACO)** is a population-based stochastic optimization method inspired by ants reinforcing useful paths with pheromone. Artificial ants construct feasible solutions, evaluate them and update a shared pheromone model.

| Component | Role | TSP interpretation |
| --- | --- | --- |
| Problem graph / feasible moves | Defines allowable solution components and constraints | Cities are nodes, travel edges have costs |
| Artificial ants | Construct candidate solutions incrementally | Build tours visiting each city once then return |
| Pheromone τᵢⱼ | Learned desirability from prior successful tours | Strong trails favor often-rewarded edges |
| Heuristic ηᵢⱼ | Problem-specific local guidance | Often 1/dᵢⱼ: shorter edges look attractive |
| Tabu/visited set | Prevents invalid repeat decisions | Do not revisit a city before the closing edge |
| Probabilistic transition | Balances learned and local guidance | Normalize desirabilities over unvisited cities |
| Evaporation ρ | Forgets old trails; helps avoid stagnation | Multiply old pheromone by 1−ρ |
| Deposit / reinforcement | Rewards useful solutions | Ant on tour of length L deposits Q/L |
| Best-tour memory | Retains best solution discovered | Shorter tour replaces incumbent |
| Termination | Bounds computation | Iteration/time/no-improvement limit |



$$
p_{ij}^{(k)}=\frac{\tau_{ij}^{\alpha}\eta_{ij}^{\beta}}{\sum_{h\in allowed_k}\tau_{ih}^{\alpha}\eta_{ih}^{\beta}}
$$



α controls pheromone influence; β controls heuristic influence. If two allowed edges have desirabilities 2 and 6, their probabilities are 2/8=0.25 and 6/8=0.75. The less preferred edge can still be explored.



$$
\tau_{ij}^{new}=(1-\rho)\tau_{ij}^{old}+\sum_k Q/L_k\;\text{on edges used by ant }k
$$



**Algorithm flow:** initialize trails → construct all tours → compute lengths → evaporate → deposit → retain best tour → repeat. A population and random choice promote exploration; reinforcement promotes exploitation. High evaporation may forget useful trails too quickly, while too little evaporation can lock the colony into an inferior route. ACO is a heuristic and does not guarantee the global optimum after a fixed iteration count.