Learning Descriptors for Novelty-Search Based Instance Generation via Meta-evolution
-
Marrero, Alejandro
1
-
Segredo, Eduardo
1
-
León, Coromoto
1
-
Hart, Emma
2
-
1
Universidad de La Laguna
info
- 2 Edinburgh Napier University, Edinburgh, United Kingdom
Year of publication: 2024
Pages: 206-213
Type: Conference paper
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.
Funding information
Funders
-
EPSRC
- EP/V026534/1
- Canarian Agency for Research, Innovation and Information Society of the Department of Universities, Science and Innovation
-
Culture and by the European Social Fund Plus (ESF+) Integrated Operational Program of the Canary Islands 2021-2027, Axis 3 Priority Topic 74 (85%)
- TESIS2020010005
Bibliographic References
- 10.1007/978-3-030-58942-4_3
- 10.1145/3321707.3321845
- 10.1145/3377930.3390181
- 10.1109/TEVC.2022.3152384
- 10.1016/j.cor.2021.105692
- Nguyen Dang, Özgür Akgün, Joan Espasa, Ian Miguel, and Peter Nightingale. 2022. A framework for generating informative benchmark instances. arXiv preprint arXiv:2205.14753 (2022).
- Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012. DEAP: Evolutionary Algorithms Made Easy. Journal of Machine Learning Research 13 (jul 2012), 2171--2175.
- Karl Pearson F.R.S. 1901. LIII. On lines and planes of closest fit to systems of points in space. Philosophical Magazine Series 1 2 (1901), 559--572.
- 10.1007/BF00342633
- Aurelien Geron. 2019. Hands-On Machine Learning with Scikit-Learn, Keras, and TensorFlow: Concepts, Tools, and Techniques to Build Intelligent Systems (2nd ed.). O'Reilly Media, Inc.
- 10.1109/TEVC.2022.3159855
- Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. 2003. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary computation 11, 1 (2003), 1--18.
- 10.1016/j.ejor.2021.12.009
- 10.1162/EVCO_a_00025
- 10.1007/978-3-030-16670-0_8
- Andrew Lensen, Bing Xue, and Mengjie Zhang. 2021. Genetic Programming for Manifold Learning: Preserving Local Topology. IEEE Transactions on Evolutionary Computation (2021).
- 10.1016/j.orp.2016.09.002
- 10.1145/3583131.3590504
- 10.1145/3449726.3463160
- 10.1007/978-3-031-14714-2_16
- 10.1016/j.softx.2023.101355
- Leland McInnes, John Healy, and James Melville. 2020. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426 [stat.ML]
- 10.1145/2908812.2908929
- Jean-Baptiste Mouret and Jeff Clune. 2015. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015).
- 10.1016/j.cor.2004.03.002
- 10.1007/s00500-019-03822-w
- 10.1007/s00500-019-03822-w
- 10.3389/frobt.2016.00040
- 10.1109/CEC45853.2021.9504848
- 10.1007/978-3-031-14714-2_15
- 10.1016/j.cor.2020.105184
- 10.5555/1893659.1893693
- 10.1038/s42256-018-0006-z
- 10.1609/aaai.v29i1.9601