Alejandro Marrero
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 |
Files
Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution
(1.1 Mb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
You might also like
Analysing the performance of migrating birds optimisation approaches for large scale continuous problems
(2016)
Presentation / Conference Contribution
Hybridisation of Evolutionary Algorithms through hyper-heuristics for global continuous optimisation
(2016)
Presentation / Conference Contribution
Hybrid parameter control approach applied to a diversity-based multi-objective Memetic Algorithm for frequency assignment problems
(2016)
Presentation / Conference Contribution
The importance of the individual encoding in memetic algorithms with diversity control applied to large Sudoku puzzles
(2017)
Presentation / Conference Contribution
Downloadable Citations
About Edinburgh Napier Research Repository
Administrator e-mail: repository@napier.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search