Skip to main content

Research Repository

Advanced Search

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

Authors

Alejandro Marrero

Eduardo Segredo

Coromoto León



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.

Presentation Conference Type Conference Paper (Published)
Conference Name Parallel Problem Solving from Nature – PPSN XVII, 17th International Conference
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

Files

A Novelty-Search Approach To Filling An Instance-Space With Diverse And Discriminatory Instances For the Knapsack Problem (accepted version) (691 Kb)
PDF




You might also like



Downloadable Citations