Skip to main content

Research Repository

Advanced Search

Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution

Marrero, Alejandro; Segredo, Eduardo; León, Coromoto; Hart, Emma

Authors

Alejandro Marrero

Eduardo Segredo

Coromoto León



Abstract

The ability to generate example instances from a domain is important in order to benchmark algorithms and to generate data that covers an instance-space in order to train machine-learning models for algorithm selection. Quality-Diversity (QD) algorithms have recently been shown to be effective in generating diverse and discriminatory instances with respect to a portfolio of solvers in various combinatorial optimisation domains. However these methods all rely on defining a descriptor which defines the space in which the algorithm searches for diversity: this is usually done manually defining a vector of features relevant to the domain. As this is a limiting factor in the use of QD methods, we propose a meta-QD algorithm which uses an evolutionary algorithm to search for a nonlinear 2D projection of an original feature-space such that applying novelty-search method in this space to generate instances improves the coverage of the instance-space. We demonstrate the effectiveness of the approach by generating instances from the Knapsack domain, showing the meta-QD approach both generates instances in regions of an instance-space not covered by other methods, and also produces significantly more instances.

Presentation Conference Type Conference Paper (Published)
Conference Name ACM GECCO 2024
Start Date Jul 14, 2024
End Date Jul 18, 2024
Acceptance Date Mar 21, 2024
Deposit Date Apr 17, 2024
Publisher Association for Computing Machinery (ACM)
Book Title Genetic and Evolutionary Computation Conference (GECCO ’24), July 14–18, 2024, Melbourne, VIC, Australia
ISBN 9798400704949
DOI https://doi.org/10.1145/3638529.3654028
Keywords Instance generation, instance-space analysis, knapsack problem, novelty search, evolutionary computation, neural-network
Public URL http://researchrepository.napier.ac.uk/Output/3594757