FloTra: Flower-shape trajectory mining for instance-specific parameter tuning

• Main Authors: LINDAWATI, Lindawati, ZHU, Feida, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2013
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/1838; https://ink.library.smu.edu.sg/context/sis_research/article/2837/viewcontent/MIC_13.pdf
• Institution: Singapore Management University

The performance of a heuristic algorithm is highly dependent on its parameter configuration, yet finding a good parameter configuration is often a time-consuming task. In this paper we propose FloTra, a Flower graph mining for graph search Trajectory pattern extraction for generic instance-specific automated parameter tuning. This algorithm provides efficient extraction of compact and discriminative features of the search trajectory, upon which problem instances are clustered and the corresponding optimal parameter configurations are computed. Experimental evaluations of our approach on the Quadratic Assignment Problem (QAP) show that our approach offers promising improvement over existing parameter tuning algorithms. In this work, we introduce FloTra, a technique to uncover important patterns from search trajectory graph for generic instance-specific automated parameter tuning. FloTra is an extension of CluPaTra and SufTra that overcomes their limitation on descriptiveness. FloTra constructs a graph representation of search trajectory and conducts a graph pattern mining to discover specific and important patterns in search trajectory. Using these patterns, FloTra then clusters the Instances and computes a corresponding optimal parameter configuration for each cluster. We have applied our approach on QAP and SCP and show that FloTra gives an encouraging improvement for the overall performance.