Previous: AIDA-96-10 Next: AIDA-96-15 Index 1996

Intellectics Group: Technical Report 96-10

Improvements on Ant System: Introducing MAX-MIN Ant System

Thomas Stützle and Holger Hoos

Ant System is general purpose heuristic algorithm inspired by an analogy to the behavior of real ant colonies. It is applicable to a wide variety of hard combinatorial optimization problems. In this technical report we introduce an improved version of Ant System, MAX--MIN Ant System. We describe the new features included in MAX--MIN Ant System and present computational results for the application to symmetric and asymmetric Traveling Salesman Problems. Additionally we perform a detailed experimental investigation of parameters and design choices of MAX--MIN Ant System. The performance of MAX--MIN can be further improved by adding a local search phase in which some ants are allowed to improve their solution.

Full Paper: Compressed postscript BibTeX entry