Clustering of Search Trajectory and its Application to Parameter Tuning

• المؤلفون الرئيسيون: Lindawati, Linda, LAU, Hoong Chuin, LO, David
• التنسيق: text
• اللغة: English
• منشور في: Institutional Knowledge at Singapore Management University 2013
• الموضوعات: generic feature; search trajectory; instance-based automated parameter tuning; sequence alignment; local search algorithm; Artificial Intelligence and Robotics; Software Engineering
• الوصول للمادة أونلاين: https://ink.library.smu.edu.sg/sis_research/1806; https://ink.library.smu.edu.sg/context/sis_research/article/2805/viewcontent/CluPaTra_preprint.pdf

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.