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. (2024, July). Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution. Presented at GECCO '24: Genetic and Evolutionary Computation Conference, Melbourne, Australia

• Presentation Conference Type: Conference Paper (published)
• Conference Name: GECCO '24: Genetic and Evolutionary Computation Conference
• Start Date: Jul 14, 2024
• End Date: Jul 18, 2024
• Acceptance Date: Mar 21, 2024
• Online Publication Date: Jul 14, 2024
• Publication Date: 2024
• Deposit Date: Apr 17, 2024
• Publicly Available Date: Jul 14, 2024
• Publisher: Association for Computing Machinery (ACM)
• Peer Reviewed: Peer Reviewed
• Book Title: GECCO '24: Proceedings of the Genetic and Evolutionary Computation Conference
• 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