Q1(b) Applications of ACO [5]

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 LaTeX: \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 LaTeX: 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