RT info:eu-repo/semantics/doctoralThesis
T1 Evolutionary Computation Methods for Instance Generation in Optimisation Domains
A1 Marrero Díaz, Alejandro
AB The generation of instances of optimisation problems is a very common task in computerscience. Traditionally, researchers apply statistical or pseudo-random methods to createinstances with which to validate their proposals: algorithms or operators. At the sametime, some authors have proposed sets known as benchmarks so that new proposalscan be evaluated in these instances, and thus avoid the task of generating instancesfor researchers. However, these sets are often characterised by (1) being designedto be hard to solve by off-the-shelf, state-of-the-art algorithms at the time of theircreation and (2) by their low diversity, meaning the instances tend to share manysimilar characteristics.However, many of the proposals in the field of optimisation do not seek to evaluatestate-of-the-art algorithms. Therefore, finding a solution to these benchmarks is notalways the final objective in these publications. Hence, there is a need for instancesthat exhibit some diversity in their characteristics so that the strengths and weaknessesof a wider range of solvers can be evaluated. This factor is essential in problems suchas 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 inevery instance, collecting diverse instances with known best solvers could facilitate theevaluation of the strengths and weaknesses of the algorithms. Generating instancesthat are diverse from one another requires a method that (1) is capable of performinga space exploration and (2) has a mechanism for measuring diversity with respect tothe rest of the instances encountered earlier in the search.This thesis examines the problem of generating diverse and performance-biasedinstances from a portfolio of algorithms by proposing two major variants of NoveltySearch (NS).The methods apply single- and multi-objective approaches to generateinstances that are diverse and discriminatory, meaning they are designed to be diverseamong themselves and also easy to solve for one target algorithm and not for othersin a portfolio. By doing this, we aim to facilitate the generation of diverse sets ofinstances that can be used to fill currently existing gaps, perform algorithm selectionwithin 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 methodscan be generalised to other domains of combinatorial optimisation. The results suggestthat both NS methods are able to generate diverse and discriminatory instances in theKP and TSP domains when using a portfolio of deterministic heuristics. Moreover,both methods outperformed previous Evolutionary Algorithm (EA) approaches in theKP domain.Finally, the methods are integrated into DIGNEA, a Diverse Instance Generatorwith Novelty Search and Evolutionary Algorithms, a C++ framework that was developedduring the research for this thesis to facilitate the generation of diverse anddiscriminatory instances for optimisation domains for the research community.
YR 2024
FD 2024
LK http://riull.ull.es/xmlui/handle/915/37726
UL http://riull.ull.es/xmlui/handle/915/37726
LA en
NO The present thesis has been partially supported by Agencia Canaria de Investigación Innovación y Sociedad de la Información de la Consejería de Economía, Conocimiento y Empleo y por el Fondo Social Europeo (FSE) Programa Operativo Integrado de Canarias 2014-2020, Eje 3 Tema Prioritario 74 (85%) - under grant TESIS2020010005.
DS Repositorio institucional de la Universidad de La Laguna
RD 08-ene-2025