Publication Type

PhD Dissertation

Version

publishedVersion

Publication Date

1-2014

Abstract

Meta-heuristic algorithms play an important role in solving combinatorial optimization problems (COP) in many practical applications. The caveat is that the performance of these meta-heuristic algorithms is highly dependent on their parameter configuration which controls the algorithm behaviour. Selecting the best parameter configuration is often a difficult, tedious and unsatisfying task. This thesis studies the problem of automating the selection of good parameter configurations. Existing approaches to address the challenges of parameter configuration can be classified into one-size-fits-all and instance-specific approaches. One-size-fits-all approaches focus on finding a single best parameter configuration for a set of problem instances, while instance-specific approaches attempt to find parameter configurations on a per instance-basis, based on identifying specific features of a specific problem. Both approaches have their strengths and limitations, yet neither offers a generic approach for finding instance-specific parameter configurations. In this thesis, we take a middle ground hybrid approach, where our goal is to perform instance-specific tuning via clustering of problem instances using a problemindependent feature. Our approach is similar to ISAC [64], but instead of using problem-specific features, we propose a problem-independent feature from the local search trajectory. We are primarily concerned with the tuning of target algorithms that are localsearch based, where we make use of the local search trajectory as the feature, since they can be obtained from any given local-search based algorithm with a small additional computation budget. We show that there is a strong correlation between search trajectories and good parameter configurations, and hence clustering by search trajectories allow a configurator to find parameter configurations based on clusters rather than the entire set of training instances. We propose two generic frameworks: CluPaTra and CluPaTra-II that cluster a set of instances using search trajectories before configuring the parameters for each cluster. In CluPaTra, we use a simple pair-wise sequence alignment technique, while in CluPaTra-II, we design two pattern mining techniques to extract compact features for clustering purposes. Using our approaches, we run extensive numerical experiments on three classical problems : Traveling Salesman Problem (TSP), Quadratic Assignment Problem (QAP) and Set Covering Problem (SCP) and demonstrate encouraging results in both cluster quality and overall computational performance. A second contribution of this thesis is the implementation of an automated parameter tuning system that comprises CluPaTra, CluPaTra-II, and other components required for automated tuning. More specifically, we develop AutoParTune, a webbased workbench that enables algorithm designers to perform automated parameter tuning with minimal effort. AutoParTune is constructed based on a three-tier architecture that integrates instance-specific parameter configuration with parameter search space reduction and global tuning. We implement two security techniques to prevent Internet attacks and design a communication schema to establish communication between components. We apply this workbench to tune two problems from industry: the Aircraft Spares Inventory Optimization Problem and the Theme Park Personalized Intelligent Route Guidance Problem. AutoParTune shows a better overall performance compared to the default configurations. Finally, as a bridge for futureworks, we consider an extension of the above instancespecific tuning approach to tune population-based algorithms such as Genetic Algorithms. We introduce two preliminary ideas: PeTra and PaRG which are designed based on generic features pertaining to population dynamics in a Genetic Algorithm. Preliminary experiments with the Two-Population Genetic Algorithm have given promising results in terms of the overall computational performance. In summary, we show in this thesis that our approach yields significant improvement in performance compared with the pure one-size-fits-all configurators on both classical and industry problems. We observe that our approach performs significantly better or equal to several existing instance-specific configurators which use problem specific features. Based on these results, we claim that: (1) Methodologically dividing the instances into smaller clusters before tuning provides better parameter configurations; (2) The Search Trajectory is a suitable generic feature to cluster similar instances for tuning process; (3) Our web-based workbench provides an effective tool for tuning complex optimization problems; and (4) There are viable extensions for automated parameter tuning of population-based algorithms.

Keywords

instance-specific, generic, automated parameter tuning, cluster-based, search trajectory, meta-heuristics

Degree Awarded

PhD in Information Systems

Discipline

Computer Sciences | Operations Research, Systems Engineering and Industrial Engineering | Theory and Algorithms

Supervisor(s)

LAU, Chuin Hoong

First Page

1

Last Page

159

Publisher

Singapore Management University

City or Country

Singapore

Copyright Owner and License

Author

Download

Share

COinS