Modular local search : a framework for self-adaptive metaheuristics : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Decision Science at Massey University

Abstract

This research develops Modular Local Search (MLS), a framework such that trajectory-based metaheuristics can be expressed as subsets of “modules” from a common library, with a common structure. The standardized modules and structure allow the easy formulation of common metaheuristic paradigms, as well as the easy creation of relatively complex hybrids by simply listing the modules that should be included. A new markup language called Modular Local Search Markup Language (MLSML) is developed so that new metaheuristics can be implemented declaratively, rather than programmatically. Some advanced ideas are introduced and explored, whereby metaheuristics are able to modify themselves during their execution, by varying parameters and swapping modules into and out of activation. This ability introduces the potential for semi-intelligent algorithms that are capable of a type of learning. Several demonstration methods are developed and these show promise on a small test set of problem instances. A new combinatorial optimization problem is developed to serve as the testing ground for the new heuristic ideas. The Arc Subset Routing Problem (ASRP) involves routing a vehicle on a graph, choosing a subset of the arcs, such that the reward collected by traversing these arcs is maximised subject to a constraint on the total distance travelled. This problem is first formulated and explored as a traditional Operations Research investigation; construction heuristics are developed, as well as some improvement routines for local search, and computational tournaments are performed to compare the methods. Some attention is given to developing methods to predict which of two heuristics is most suited to a given problem instance, based on an analysis of the characteristics of that problem. Initial results demonstrate the potential of such an approach. The MLS framework offers a powerful and flexible structure both for the easy and consistent implementation of existing metaheuristics, and also as a platform for the development of new, advanced metaheuristic ideas. Early results are encouraging, and a number of directions for future research are discussed, including some complex real-world problems for which the self-adaptive capabilities of MLS would be especially useful.