Intelligent Systems II · TEE · papers
Q4(b) ACO components and roles [10]
Final examination · 17 Apr 2024
Actual historical paper ·100 marks attempted /140 offered · Q1 compulsory + any four of Q2–Q7. Source defects and solution assumptions are explicitly identified.
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 |
LaTeX: 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.
LaTeX: \tau_{ij}^{new}=(1-\rho)\tau_{ij}^{old}+\sum_k Q/L_k\;\text{on edges used by ant }kAlgorithm 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.