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
Loading...
Date
2010
DOI
Open Access Location
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Massey University
Rights
The Author
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.
Description
Keywords
Decision-making, Data processing, Combinatorial optimisation, Mathematical optimisation, Computer algorithms, Modular local search, Self-adaptive metaheuristics, Decision science