Evolutionary Computation Methods for Instance Generation in Optimisation Domains

Abstract

The generation of instances of optimisation problems is a very common task in computer science. Traditionally, researchers apply statistical or pseudo-random methods to create instances with which to validate their proposals: algorithms or operators. At the same time, some authors have proposed sets known as benchmarks so that new proposals can be evaluated in these instances, and thus avoid the task of generating instances for researchers. However, these sets are often characterised by (1) being designed to be hard to solve by off-the-shelf, state-of-the-art algorithms at the time of their creation and (2) by their low diversity, meaning the instances tend to share many similar characteristics. However, many of the proposals in the field of optimisation do not seek to evaluate state-of-the-art algorithms. Therefore, finding a solution to these benchmarks is not always the final objective in these publications. Hence, there is a need for instances that exhibit some diversity in their characteristics so that the strengths and weaknesses of a wider range of solvers can be evaluated. This factor is essential in problems such as Algorithm Selection; i.e., mapping a portfolio of algorithms to a set of instances. Since, in practice, there is no algorithm that can be expected to outperform others in every instance, collecting diverse instances with known best solvers could facilitate the evaluation of the strengths and weaknesses of the algorithms. Generating instances that are diverse from one another requires a method that (1) is capable of performing a space exploration and (2) has a mechanism for measuring diversity with respect to the rest of the instances encountered earlier in the search. This thesis examines the problem of generating diverse and performance-biased instances from a portfolio of algorithms by proposing two major variants of Novelty Search (NS).The methods apply single- and multi-objective approaches to generate instances that are diverse and discriminatory, meaning they are designed to be diverse among themselves and also easy to solve for one target algorithm and not for others in a portfolio. By doing this, we aim to facilitate the generation of diverse sets of instances that can be used to fill currently existing gaps, perform algorithm selection within a portfolio and determine the regions of space where an algorithm excels/fails. Although the proposals are mainly evaluated using the well-known Knapsack Problem (KP), experiments with the Travelling Salesman Problem (TSP) show that the methods can be generalised to other domains of combinatorial optimisation. The results suggest that both NS methods are able to generate diverse and discriminatory instances in the KP and TSP domains when using a portfolio of deterministic heuristics. Moreover, both methods outperformed previous Evolutionary Algorithm (EA) approaches in the KP domain. Finally, the methods are integrated into DIGNEA, a Diverse Instance Generator with Novelty Search and Evolutionary Algorithms, a C++ framework that was developed during the research for this thesis to facilitate the generation of diverse and discriminatory instances for optimisation domains for the research community.