Report

Ant Colony Optimization Quadratic Assignment Problem Hernan AGUIRRE, Adel BEN HAJ YEDDER, Andre DIAS and Pascalis RAPTIS Problem Leader: Marco Dorigo Team Leader: Marc Schoenauer Quadratic Assignment Problem • Assign n facilities to n locations – Distances between locations – Flows between facilities • Goal known Minimize sum flow x distance • TSP is a particular case of QAP – Models many real world problems • “NP-hard” problem QAP Example Locations Facilities biggest flow: A - B How to assign facilities to locations ? Higher cost Lower cost Ant Colony Optimization (ACO) • Ant Algorithms – Inspired by observation of real ants • Ant Colony Optimization (ACO) – Inspiration from ant colonies’ foraging behavior (actions of the colony finding food) – Colony of cooperating individuals – Pheromone trail for stigmergic communication – Sequence of moves to find shortest paths – Stochastic decision using local information Ant Colony Optimization for QAP facilities-location assignment • Pheromone laying • Basic ACO algorithm • Local Search 1st best improvement Ant Colony Optimization for QAP • Basic ACO algorithm Actions Choosing a Facility Choosing a Location Pheromone Update Strategies heuristic P(pheromone , heuristic) (solution quality) Ant Colony Optimization for QAP • How important search guidance is? Test problems Type of problem Size tai12a tai50a kra30a random random Real-life 12 50 30 • 12 facilities/positions should be easy to solve! • What behavior with real life problems? • QAP solved to optimality up to 30 Parameters for ACO: 500 ants, evaporation =0.9 Results: tai12a • Without local search convergence to local minimum NOT ALWAYS the optimum Heuristic gets better minimun • With local search: always converges to optimum Very quickly Results: Real Life - Kra30a No LS With LS No Heuristic Converges local minimum 72 % optimum Optimum Avg.12 iterations With heuristic Converges local minimum 70% optimum Optimum Avg.10 iterations Future Work • Different strategies Choosing a Facility Choosing a Location Pheromone Update • Remain fixed, all ants use the same! • Performance of strategies varies Problem Stage of the search Co-evolution Let the ants find it! Conclusions Great Summer School! The ants did find their way to the Beach Pool Beer Ants Path Locations Facilities biggest flow: A - B Path Path (1,A) (1,C) | | (2,B) (2,B) | | (3,C) Higher cost Lower cost (3,A)