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

  1. Marrero, Alejandro 1
  2. Segredo, Eduardo 1
  3. León, Coromoto 1
  4. Hart, Emma 2
  1. 1 Universidad de La Laguna
    info

    Universidad de La Laguna

    San Cristobal de La Laguna, España

    ROR https://ror.org/01r9z8p25

  2. 2 Edinburgh Napier University, Edinburgh, United Kingdom
Actas:
GECCO 24: Proceedings of the Genetic and Evolutionary Computation Conference

Ano de publicación: 2024

Páxinas: 206-213

Tipo: Achega congreso

DOI: 10.1145/3638529.3654028 GOOGLE SCHOLAR lock_openAcceso aberto editor

Resumo

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.

€ Ver financiamento

Información de financiamento

Financiadores

  • 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

Referencias bibliográficas

  • 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