Ant Colony Optimization

Ant Colony Optimization Quadratic Assignment Problem Hernan AGUIRRE, Adel BEN HAJ YEDDER, Andre DIAS and Pascalis RAPTIS

Problem Leader: Marco DorigoLeader: Team 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 Location s

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 facilitieslocation assignment

• Pheromone laying • Basic ACO algorithm • Local Search

1st best

improvemen t

Ant Colony Optimization for QAP • Basic ACO algorithm Actions Strategies  Choosing a Facility 



heuristic

P(pheromone Choosing a Location , heuristic) (solution Pheromone Update 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 No Heuristic Converges local minimum 72 % optimum With heuristic

Converges local minimum 70% optimum

With LS Optimum Avg.12 iterations 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 variesProblem Stage of the search

Coevolution

Let the ants

Conclusions

Great Summer School! The ants did find their way to the Beach Pool Beer

Ants Path Location s

Facilities biggest flow: A B

Pat h (1,A)

Pat h (1,C)

|

|

(2,B)

(2,B)

|

|

(3,C)

Higher cost

Lower cost

(3,A)