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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Similar trends are observed in the plots obtained in the full feature space but not shown due to space limitations.
References
Deap: Distributed evolutionary algorithms in Python. https://deap.readthedocs.io/en/master/
Matilda: Melbourne algorithm test instance library with data analytics. https://matilda.unimelb.edu.au/matilda/
Umap: Uniform manifold approximation and projection for dimension reduction. https://umap-learn.readthedocs.io/en/latest/index.html
Hansen, N., Müller, S.D., Koumoutsakos, P.: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evol. Comput. 11(1), 1–18 (2003)
Hasselmann, K., Ligot, A., Ruddick, J., Birattari, M.: Empirical assessment and comparison of neuro-evolutionary methods for the automatic off-line design of robot swarms. Nat. Commun. 12(1), 1–11 (2021)
Le Goff, L.K., et al.: Sample and time efficient policy learning with CMA-ES and Bayesian optimisation. In: Artificial Life Conference Proceedings, pp. 432–440. MIT Press (2020)
Lensen, A., Xue, B., Zhang, M.: Can genetic programming do manifold learning too? In: Sekanina, L., Hu, T., Lourenço, N., Richter, H., García-Sánchez, P. (eds.) EuroGP 2019. LNCS, vol. 11451, pp. 114–130. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-16670-0_8
Lensen, A., Xue, B., Zhang, M.: Genetic programming for manifold learning: preserving local topology. IEEE Trans. Evol. Comput. (2021)
Loshchilov, I., Hutter, F.: CMA-ES for hyperparameter optimization of deep neural networks. arXiv preprint arXiv:1604.07269 (2016)
Van der Maaten, L., Hinton, G.: Visualizing data using t-SNE. J. Mach. Learn. Res. 9(11) (2008)
Muñoz, M.A., Villanova, L., Baatar, D., Smith-Miles, K.: Instance spaces for machine learning classification. Mach. Learn. 107(1), 109–147 (2017). https://doi.org/10.1007/s10994-017-5629-5
Partridge, M., Calvo, R.A.: Fast dimensionality reduction and simple PCA. Intell. Data Anal. 2(3), 203–214 (1998)
Schofield, F., Lensen, A.: Using genetic programming to find functional mappings for UMAP embeddings. In: 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 704–711. IEEE (2021)
Smith-Miles, K., Baatar, D., Wreford, B., Lewis, R.: Towards objective measures of algorithm performance across instance space. Comput. Oper. Res. 45, 12–24 (2014)
Smith-Miles, K., Bowly, S.: Generating new test instances by evolving in instance space. Comput. Oper. Res. 63, 102–113 (2015)
Smith-Miles, K., van Hemert, J., Lim, X.Y.: Understanding TSP difficulty by learning from evolved instances. In: Blum, C., Battiti, R. (eds.) LION 2010. LNCS, vol. 6073, pp. 266–280. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13800-3_29
Smith-Miles, K., Lopes, L.: Generalising algorithm performance in instance space: a timetabling case study. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 524–538. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_41
Smith-Miles, K., Lopes, L.: Measuring instance difficulty for combinatorial optimization problems. Comput. Oper. Res. 39(5), 875–889 (2012)
Wang, Y., Huang, H., Rudin, C., Shaposhnik, Y.: Understanding how dimension reduction tools work: an empirical approach to deciphering t-SNE, UMAP, TriMap, and PaCMAP for data visualization. J. Mach. Learn. Res. 22(201), 1–73 (2021)
Acknowledgments
Hart gratefully acknowledges the support EPSRC EP/V026534/1.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Sim, K., Hart, E. (2022). Evolutionary Approaches to Improving the Layouts of Instance-Spaces. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tušar, T. (eds) Parallel Problem Solving from Nature – PPSN XVII. PPSN 2022. Lecture Notes in Computer Science, vol 13398. Springer, Cham. https://doi.org/10.1007/978-3-031-14714-2_15
Download citation
DOI: https://doi.org/10.1007/978-3-031-14714-2_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-14713-5
Online ISBN: 978-3-031-14714-2
eBook Packages: Computer ScienceComputer Science (R0)