Improving performance of a hyper-heuristic using a multilayer perceptron for vehicle routing

Tyasnurita, Raras; �zcan, Ender; Shahriar, Asta; John, Robert

Abstract

A hyper-heuristic is a heuristic optimisation method which generates or selects heuristics (move operators) based on a set of components while solving a computationally difficult problem. Apprenticeship learning arises while observing the behavior of an expert in action. In this study, we use a multilayer perceptron (MLP) as an apprenticeship learning algorithm to improve upon the performance of a state-of-the-art selection hyper-heuristic used as an expert, which was the winner of a cross-domain heuristic search challenge (CHeSC 2011). We collect data based on the relevant actions of the expert while solving selected vehicle routing problem instances from CHeSC 2011. Then an MLP is trained using this data to build a selection hyper-heuristic consisting of a number classifiers for heuristic selection, parameter control, and move-acceptance. The generated selection hyper-heuristic is tested on the unseen vehicle routing problem instances. The empirical results indicate the success of MLP-based hyper-heuristic achieving a better performance than the expert and some previously proposed algorithms.

Citation

Tyasnurita, R., Özcan, E., Shahriar, A., & John, R. (2015). Improving performance of a hyper-heuristic using a multilayer perceptron for vehicle routing.

• Conference Name: 15th UK Workshop on Computational Intelligence (UKCI 2015)
• End Date: Sep 9, 2015
• Acceptance Date: Jul 6, 2015
• Publication Date: Sep 7, 2015
• Deposit Date: Sep 12, 2017
• Publicly Available Date: Sep 12, 2017
• Peer Reviewed: Peer Reviewed
• Keywords: Multilayer Perceptron, Hyper-heuristic, Vehicle Routing,; Apprenticeship Learning
• Public URL: https://nottingham-repository.worktribe.com/output/761994
• Related Public URLs: http://www.ukci2015.ex.ac.uk
• Contract Date: Sep 12, 2017