Tuning the Performance of the MMAS Heuristic

@incollection{ridge07tuning, abstract = {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. 1}, author = {Ridge, Enda and Kudenko, Daniel}, booktitle = {Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics}, citeulike-article-id = {3170714}, keywords = {ant-colony, experimental-method, tsp}, pages = {46--60}, posted-at = {2008-08-28 22:04:26}, priority = {2}, series = {Lecture Notes in Computer Science}, title = {Tuning the Performance of the MMAS Heuristic}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.63.4349}, volume = {4638}, year = {2007} }

TY - CHAP ID - ridge07tuning L3 - citeulike-article-id:3170714 N2 - 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. 1 SE - Lecture Notes in Computer Science EP - 60 TI - Tuning the Performance of the MMAS Heuristic VL - 4638 T2 - Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics SP - 46 KW - ant-colony KW - experimental-method KW - tsp AU - Ridge, Enda AU - Kudenko, Daniel PY - 2007/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.63.4349 ER -