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

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

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.

Citation

Marrero, A., Segredo, E., León, C., & Hart, E. (in press). Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution. In Genetic and Evolutionary Computation Conference (GECCO ’24), July 14–18, 2024, Melbourne, VIC, Australia. https://doi.org/10.1145/3638529.3654028

• Conference Name: ACM GECCO 2024
• Conference Location: Melbourne, Australia
• 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