Evolutionary Approaches to Improving the Layouts of Instance-Spaces

Sim, Kevin; Hart, Emma

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.

Citation

Sim, K., & Hart, E. (2022). Evolutionary Approaches to Improving the Layouts of Instance-Spaces. In Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022 (207-219). https://doi.org/10.1007/978-3-031-14714-2_15

• Conference Name: 17th International Conference, PPSN 2022
• 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: 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