Publication Type
Journal Article
Version
publishedVersion
Publication Date
2013
Abstract
This paper is concerned with automated classification of Combinatorial Optimization Problem instances for instance-specific parameter tuning purpose. We propose the CluPaTra Framework, a generic approach to CLUster instances based on similar PAtterns according to search TRAjectories and apply it on parameter tuning. The key idea is to use the search trajectory as a generic feature for clustering problem instances. The advantage of using search trajectory is that it can be obtained from any local-search based algorithm with small additional computation time. We explore and compare two different search trajectory representations, two sequence alignment techniques (to calculate similarities) as well as two well-known clustering methods. We report experiment results on two classical problems: Travelling Salesman Problem and Quadratic Assignment Problem and industrial case study.
Keywords
generic feature, search trajectory, instance-based automated parameter tuning, sequence alignment, local search algorithm
Discipline
Artificial Intelligence and Robotics | Software Engineering
Publication
Journal of the Operational Research Society
Volume
64
Issue
12
First Page
1742
Last Page
1752
ISSN
0160-5682
Identifier
10.1057/jors.2012.167
Publisher
Palgrave Macmillan
Citation
Lindawati, Linda; LAU, Hoong Chuin; and LO, David.
Clustering of Search Trajectory and its Application to Parameter Tuning. (2013). Journal of the Operational Research Society. 64, (12), 1742-1752.
Available at: https://ink.library.smu.edu.sg/sis_research/1806
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://dx.doi.org/10.1057/jors.2012.167
