An integrated White+Black box approach for designing and tuning stochastic local search algorithms

Abstract

This thesis addresses two related Stochastic Local Search (SLS) engineering problems: the Design and Tuning Problem (DTP). The SLS DTP can be informally defined as a meta-level problem of finding a good SLS algorithm which has been tuned for a given class of Combinatorial Optimization Problems (COP). The problem, which this thesis addresses, is a systematic methodology for dealing with SLS DTP which is effective for obtaining better performing SLS algorithms.

Current approaches to address SLS DTP can be classified into white-box: analysis of the SLS algorithm and/or the COP being attacked; or black-box: automated tuning algorithms that aim to get the best SLS configuration given an initial configuration set. These existing approaches have their strengths and limitations, yet they do not solve the SLS DTP well enough.

A novel contribution of this thesis is a generic white-box Fitness Landscape Search Trajectory (FLST) visualization. This visualization is designed to allows the algorithm designers to investigate the n-dimensional fitness landscape structure of the COP being analyzed in 2-D. There are obviously visualization errors by using 2-D to show n-dimensional fitness landscape. However, we are able to quantify the errors and provide mechanism for users to identify the errors. We show in this thesis that even with such inherent visualization errors issue with this FLST visualization, the users can still use it to develop insights on what should be a good search strategy for exploring the given fitness landscape, as well as to observe how his current SLS algorithm behaves on that fitness landscape. This enables the algorithm designer to design the SLS algorithm in a more intuitive manner than existing white-box approaches.

The resulting SLS algorithm still needs to be fine-tuned, and we propose an Integrated White+Black Box Approach (IWBBA) in which we first start with the white-box FLST visualization above, improve the SLS algorithm, and then pass the implementation of the SLS algorithm to be fine-tuned using black-box approaches, stepping up its performance more. The insights gained from the previous white-box step will likely have pruned the possible configuration set, easing and indirectly improving the performance of the black-box tuning algorithm.

To implement this integrated approach, we have built an SLS visualization and engineering tool called Viz. We have successfully applied IWBBA using Viz to develop and improve several SLS algorithms from the literature: Iterated Local Search (ILS) for the Traveling Salesman Problem (TSP), Robust Tabu Search (Ro-TS) for the Quadratic Assignment Problem, and most notably: Tabu Search (TS) for the Low Autocorrelation Binary Sequence (LABS) problem where we obtained state-of-the-art results.