A Novelty-Search Approach to Filling an Instance-Space with Diverse and Discriminatory Instances for the Knapsack Problem

Marrero, Alejandro; Segredo, Eduardo; León, Coromoto; Hart, Emma

Abstract

We propose a new approach to generating synthetic instances in the knapsack domain in order to fill an instance-space. The method uses a novelty-search algorithm to search for instances that are diverse with respect to a feature-space but also elicit discriminatory performance from a set of target solvers. We demonstrate that a single run of the algorithm per target solver provides discriminatory instances and broad coverage of the feature-space. Furthermore, the instances also show diversity within the performance-space, despite the fact this is not explicitly evolved for, i.e. for a given ‘winning solver’, the magnitude of the performance-gap between it and other solvers varies across a wide-range. The method therefore provides a rich instance-space which can be used to analyse algorithm strengths/weaknesses, conduct algorithm-selection or construct a portfolio solver.

Citation

Marrero, A., Segredo, E., León, C., & Hart, E. (2022). A Novelty-Search Approach to Filling an Instance-Space with Diverse and Discriminatory Instances for the Knapsack Problem. In Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022 (223-236). https://doi.org/10.1007/978-3-031-14714-2_16

• Conference Name: Parallel Problem Solving from Nature – PPSN XVII, 17th International Conference
• Conference Location: Dortmund, Germany
• Start Date: Sep 10, 2022
• End Date: Sep 14, 2022
• Acceptance Date: Jun 6, 2022
• Online Publication Date: Aug 14, 2022
• Publication Date: 2022
• Deposit Date: Aug 22, 2022
• Publicly Available Date: Aug 15, 2023
• Publisher: Springer
• Pages: 223-236
• Series Title: Lecture Notes in Computer Science
• Series Number: 13398
• Book Title: Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022
• ISBN: 978-3-031-14713-5
• DOI: https://doi.org/10.1007/978-3-031-14714-2_16
• Keywords: Instance generation, Novelty search, Evolutionary algorithm, Knapsack problem, Optimisation
• Public URL: http://researchrepository.napier.ac.uk/Output/2898439