Conference Proceeding Article
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.
instance-based automated tuning parameter, search trajectory, sequence alignment, instance clustering
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering | Software Engineering
Intelligent Systems and Decision Analytics; Software and Cyber-Physical Systems
Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011: Selected Papers
City or Country
LINDAWATI, Linda; LAU, Hoong Chuin; and LO, David.
Instance-based parameter tuning via search trajectory similarity clustering. (2011). Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011: Selected Papers. 6683, 131-145. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1336
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.