Tuning the performance of the MMAS heuristic

Enda Ridge, Daniel Kudenko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper presents an in-depth Design of Experiments (DOE) methodology for the performance analysis of a stochastic heuristic. The heuristic under investigation is Max-Min Ant System (MMAS) for the Travelling Salesperson Problem (TSP). Specifically, the Response Surface Methodology is used to model and tune MMAS performance with regard to 10 tuning parameters, 2 problem characteristics and 2 performance metrics-solution quality and solution time. The accuracy of these predictions is methodically verified in a separate series of confirmation experiments. The two conflicting responses are simultaneously optimised using desirability functions. Recommendations on optimal parameter settings are made. The optimal parameters are methodically verified. The large number of degrees-of-freedom in the MMAS design are overcome with a Minimum Run Resolution V design. Publicly available algorithm and problem generator implementations are used throughout. The paper should therefore serve as an illustrative case study of the principled engineering of a stochastic heuristic.

Original languageEnglish
Title of host publicationEngineering Stochastic Local Search Algorithms: Designing, Implementing and Analyzing Effective Heuristics
EditorsT Stutzle, M Birattari, HH Hoos
Place of PublicationBERLIN
PublisherSpringer
Pages46-60
Number of pages15
ISBN (Print)978-3-540-74445-0
Publication statusPublished - 2007
EventInternational Workshop on Engineering Stochastic Local Search Algorithms - Brussels
Duration: 6 Sept 20078 Sept 2007

Conference

ConferenceInternational Workshop on Engineering Stochastic Local Search Algorithms
CityBrussels
Period6/09/078/09/07

Cite this