Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

1-2011

Abstract

This paper is concerned with automated tuning of parameters in local-search based meta-heuristics. Several generic approaches have been introduced in the literature that returns a ”one-size-fits-all” parameter configuration for all instances. This is unsatisfactory since different instances may require the algorithm to use very different parameter configurations in order to find good solutions. There have been approaches that perform instance-based automated tuning, but they are usually problem-specific. In this paper, we propose CluPaTra, a generic (problem-independent) approach to perform parameter tuning, based on CLUstering instances with similar PAtterns according to their search TRAjectories. We propose representing a search trajectory as a directed sequence and apply a well-studied sequence alignment technique to cluster instances based on the similarity of their respective search trajectories. We verify our work on the Traveling Salesman Problem (TSP) and Quadratic Assignment Problem (QAP). Experimental results show that CluPaTra offers significant improvement compared to ParamILS (a one-size-fits-all approach). CluPaTra is statistically significantly better compared with clustering using simple problem-specific features; and in comparison with the tuning of QAP instances based on a well-known distance and flow metric classification, we show that they are statistically comparable.

Keywords

instance-based automated tuning parameter, search trajectory, sequence alignment, instance clustering

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Software Engineering

Publication

Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011: Selected Papers

Volume

6683

First Page

131

Last Page

145

ISBN

9783642255656

Identifier

10.1007/978-3-642-25566-3_10

Publisher

Springer Verlag

City or Country

Berlin

Additional URL

http://doi.org/10.1007/978-3-642-25566-3_10

Download

Share

COinS