Skip to main content

Research Repository

Advanced Search

Evolutionary Approaches to Improving the Layouts of Instance-Spaces

Sim, Kevin; Hart, Emma

Authors



Abstract

We propose two new methods for evolving the layout of an instance-space. Specifically we design three different fitness metrics that seek to: (i) reward layouts which place instances won by the same solver close in the space; (ii) reward layouts that place instances won by the same solver and where the solver has similar performance close together; (iii) simultaneously reward proximity in both class and distance by combining these into a single metric. Two optimisation algorithms that utilise these metrics to evolve a model which outputs the coordinates of instances in a 2d space are proposed: (1) a multi-tree version of GP (2) a neural network with the weights evolved using an evolution strategy. Experiments in the TSP domain show that both new methods are capable of generating layouts in which subsequent application of a classifier provides considerably improved accuracy when compared to existing projection techniques from the literature, with improvements of over 10% in some cases. Visualisation of the the evolved layouts demonstrates that they can capture some aspects of the performance gradients across the space and highlight regions of strong performance.

Presentation Conference Type Conference Paper (Published)
Conference Name 17th International Conference, PPSN 2022
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 207-219
Series Title Lecture Notes in Computer Science
Series Number 13398
Series ISSN 1611-3349
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_15
Public URL http://researchrepository.napier.ac.uk/Output/2898209

Files

Evolutionary Approaches To Improving The Layouts Of Instance-Spaces (accepted version) (807 Kb)
PDF




You might also like



Downloadable Citations