A Framework for the experimental evaluation of metaheuristics

PhD thesis abstract

A key issue in promoting the adoption of optimisation methodologies in the real world is the ability to separate, at the implementation level, the problem description from the method used to solve it, while preserving an appropriate matching between problems and solvers. Arguably, much of the optimisation software available today is geared either towards solving a well-defined class of problems, and doing it as efficiently as possible using tried-and-tested solvers, or towards approaching broad classes of problems with “softer” algorithms, such as the various types of meta-heuristics, in which case the myriad of not-so-problem-independent algorithm configurations typically becomes mixed with some aspects of problem specification. In particular, comparing different types of optimisers in order to select the most well-suited to a given practical setting becomes difficult, and the apples-to-oranges argument often applies to the comparison.

In this work, a software model of optimisation problems is proposed. Starting with a very general definition of optimisation, contemplating local and global, discrete and continuous, single-objective and multi-objective optimisation, the relevant entities of an abstract optimisation problem are identified along with the relationships between them. These are then aggregated and structured to arrive at the software components of the model, in an object-oriented way. In order to provide a suitable matching between problems and solvers, the model interface is designed to reflect, not the details of the optimisation problem itself, but the properties which it may possess and on which solvers may depend. For example, a local optimisation problem may not be defined without specifying a neighbourhood structure. Then, to reflect its existence, and to allow, say, a local search algorithm to use it according to its own policy, the model of the problem must supply suitable mechanisms, or methods, such as neighbourhood enumeration.

To illustrate how adopting the proposed model may allow solvers to be implemented in much more problem-independent ways, application examples based on local search meta-heuristics and on some classical combinatorial optimisation problems are presented.

Finally, the model is shown to be able to accommodate constructive optimisation methods as well, through a reformulation of the optimisation problem. The resulting problem formulation is compatible with both local and constructive optimisation methods, establishing an important link between the two search paradigms, both at a theorical and at a pratical level.