Designing a portfolio of parameter configurations for online algorithm selection

• Main Authors: GUNAWAN, Aldy, LAU, Hoong Chuin, MISIR, Mustafa
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2015
• Subjects: Artificial intelligence; Combinatorial optimization; Design of experiments; OptimizationParameter estimation; Problem solving; Simulated annealing; Tabu search; Traveling salesman problem; Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering; Theory and Algorithms
• Online Access: https://ink.library.smu.edu.sg/sis_research/2851; https://ink.library.smu.edu.sg/context/sis_research/article/3851/viewcontent/DesignPortfolioParameterConfigOnlineAlgor_2015_AAAI.pdf
• Institution: Singapore Management University

Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We apply our approach on a Simulated Annealing-Tabu Search (SA-TS) hybrid algorithm for solving the Quadratic Assignment Problem (QAP) as well as an Iterated Local Search (ILS) on the Travelling Salesman Problem (TSP). We also generate a portfolio of parameter configurations using best-of-breed parameter tuning approaches directly for the comparison purpose. Experimental results show that our approach lead to improvements over best-of-breed parameter tuning approaches.