Evolutionary Approaches to Improving the Layouts of Instance-Spaces

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.