Exploiting diverse distance metrics for surrogate-based optimisation of ordering problems

Smith, Jim; Stone, Christopher; Serpell, Martin

Abstract

Surrogate-assisted optimisation has proven success in the continuous domain, but only recently begun to be explored for other representations, in particular permutations. The use of Gaussian kernel-based models has been proposed, but only tested on small problems.
This case study considers much larger instances, in the experimental setting of a real-world ordering problem. We also investigate whether creating models using different distance metrics generates a diverse ensemble. Results demonstrate the following effects of use to other researchers: (i) Numerical instability in matrix inversion is a factor across all metrics, regardless of algorithm used. The likelihoood increases significantly once the models are parameterised using evolved solutions as well as the initial random pop- ulation; (ii) This phase transition is also observed in different indicators of model quality. For example, predictive accuracy typically decreases once models start to include data from evolved samples. We explain this transition in terms of the distribution of samples and Gaussian kernel basis of the models; (iii) Measures of how well models predict rank-orderings are less affected; (iv) Benchmark compar- isons show that using surrogate models decreases the number of evaluations required to find good solutions, without affecting quality.

• Presentation Conference Type: Conference Paper (unpublished)
• Conference Name: ACM-SIGEVO Genetic and Evolutionary Computation Conference, GECCO ’16
• Start Date: Jul 20, 2016
• End Date: Jul 24, 2016
• Acceptance Date: Mar 20, 2016
• Publication Date: Jan 1, 2016
• Deposit Date: May 19, 2016
• Publicly Available Date: May 19, 2016
• Peer Reviewed: Peer Reviewed
• Pages: 701-708
• ISBN: 9781450342063
• Keywords: evolutionary computation, surrogate modelling, statistical disclosure control, artificial intelligence
• Public URL: https://uwe-repository.worktribe.com/output/923494
• Publisher URL: http://dx.doi.org/10.1145/2908812.2908854
• Additional Information: Title of Conference or Conference Proceedings : ACM-SIGEVO Genetic and Evolutionary Computation Conference, GECCO ’16
• Contract Date: May 19, 2016