Alejandro Marrero
Synthesising Diverse and Discriminatory Sets of Instances using Novelty Search in Combinatorial Domains
Marrero, Alejandro; Segredo, Eduardo; Leon, Coromoto; Hart, Emma
Abstract
Gathering sufficient instance data to either train algorithm-selection models or understand algorithm footprints within an instance space can be challenging. We propose an approach to generating synthetic instances that are tailored to perform well with respect to a target algorithm belonging to a predefined portfolio but are also diverse with respect to their features. Our approach uses a novelty search algorithm with a linearly weighted fitness function that balances novelty and performance to generate a large set of diverse and discriminatory instances in a single run of the algorithm. We consider two definitions of novelty: (1) with respect to discriminatory performance within a portfolio of solvers; (2) with respect to the features of the evolved instances. We evaluate the proposed method with respect to its ability to generate diverse and discriminatory instances in two domains (knapsack and bin-packing), comparing to another well-known quality diversity method, Multi-dimensional Archive of Phenotypic Elites (MAP-Elites) and an evolutionary algorithm that only evolves for discriminatory behaviour. The results demonstrate that the novelty search method outperforms its competitors in terms of coverage of the space and its ability to generate instances that are diverse regarding the relative size of the "performance gap" between the target solver and the remaining solvers in the portfolio. Moreover, for the Knapsack domain, we also show that we are able to generate novel instances in regions of an instance space not covered by existing benchmarks using a portfolio of state-of-the-art solvers. Finally, we demonstrate that the method is robust to different portfolios of solvers (stochastic approaches, deterministic heuristics and state-of-the-art methods), thereby providing further evidence of its generality.
Citation
Marrero, A., Segredo, E., Leon, C., & Hart, E. (online). Synthesising Diverse and Discriminatory Sets of Instances using Novelty Search in Combinatorial Domains. Evolutionary Computation, https://doi.org/10.1162/evco_a_00350
Journal Article Type | Article |
---|---|
Acceptance Date | Mar 15, 2024 |
Online Publication Date | May 6, 2024 |
Deposit Date | Apr 16, 2024 |
Publicly Available Date | Aug 7, 2024 |
Print ISSN | 1063-6560 |
Electronic ISSN | 1530-9304 |
Publisher | MIT Press |
Peer Reviewed | Peer Reviewed |
DOI | https://doi.org/10.1162/evco_a_00350 |
Keywords | Instance Generation; Quality Diversity; Novelty Search; MAP-Elites; Knapsack Prob- lem; Bin Packing Problem |
Public URL | http://researchrepository.napier.ac.uk/Output/3594407 |
Publisher URL | https://direct.mit.edu/evco/issue/32/1 |
Files
This file is under embargo until Aug 7, 2024 due to copyright reasons.
Contact repository@napier.ac.uk to request a copy for personal use.
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
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