# Q1(b) Applications of ACO [5]

Subject: Intelligent Systems II

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/is2/#tee/mocks/paper-final-2025/q1b

Canonical: https://deep-learning-study-room.vercel.app/read/is2/tee/mocks/paper-final-2025--q1b/

100-mark timed practice using the actual Final 2025 paper. Q1 compulsory; any four of Q2–Q7. Worked solutions are below the questions.

**List the applications of Ant Colony Optimization and explain any one application in detail.** [5 marks]

### Answer

### Definition (1 line)

Ant Colony Optimization is a probabilistic, population-based metaheuristic (Dorigo, 1992) in which artificial ants build solutions on a graph and communicate through pheromone trails. In the update rule used here, evaporation reduces all stored trails; deposits then reinforce edges of selected tours according to solution quality. Evaporation does not occur only on poor paths.

### Applications

1. **Travelling salesman problem**: shortest tour visiting every city once.
2. **Vehicle routing**: delivery routes for a fleet with capacity and time windows (minimising distance, time, fuel).
3. **Network routing**: adaptive routing of data packets in communication and sensor networks (AntNet).
4. **Job-shop and project scheduling**: assigning jobs to machines to minimise completion time.
5. **Image processing**: edge detection, with ants moving over pixel-intensity graphs.
6. **Assignment problems**: quadratic assignment, timetabling, graph colouring.
7. **Feature selection and data mining**: Ant-Miner for classification rules.
8. **Load balancing** in distributed systems and cloud task allocation.

### One application in detail: vehicle routing (or TSP)

1. **Graph.** Depot and customers are nodes; travel times or distances are edge weights.
2. **Ants.** Each ant builds a complete set of routes. From its current customer it chooses the next with probability 

$$
\propto\tau_{ij}\,(1/d_{ij})
$$

, skipping customers already served or that would exceed the vehicle capacity; when the vehicle is full it returns to the depot.
3. **Evaluation.** Total distance (plus penalties for late deliveries).
4. **Learning.** Pheromone evaporates everywhere and is added in proportion to 

$$
Q/L
$$

 on the routes of good solutions, so short connections are reinforced.
5. **Result.** Repeated iterations search for low-cost routes; finite-run convergence to the optimum is not guaranteed. Companies use this for parcel delivery, waste collection and school-bus routing.

### Advantages and limitations

| Advantages | Limitations |
| --- | --- |
| Naturally suited to graph and routing problems | Several parameters to tune (α, β, ρ, number of ants) |
| Can share useful route information and adapt search to changing graphs | Convergence time is uncertain; may stagnate on a sub-optimal path |
| Positive feedback + parallel ants | Theoretical analysis is difficult |

**Yaad rakho:** ACO = “raaste wale problems” (TSP, routing, scheduling). PSO = “numbers wale problems” (continuous function, weights).