Limits to learning in reinforcement learning hyper-heuristics

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • University of Nottingham

Abstract

Learning mechanisms in selection hyper-heuristics are used to identify the most appropriate subset of heuristics when solving a given problem. Several experimental studies have used additive reinforcement learning mechanisms, however, these are inconclusive with regard to the performance of selection hyper-heuristics with these learningmechanisms. This paper points out limitations to learning with additive reinforcement learning mechanisms. Our theoretical results show that if the probability of improving the candidate solution in each point of the search process is less than 1/2 which is a mild assumption, then additive reinforcement learning mechanisms perform asymptotically similar to the simple random mechanism which chooses heuristics uniformly at random. In addition, frequently used adaptation schemes can affect the memory of reinforcement learning mechanisms negatively. We also conducted experiments on two well-known combinatorial optimisation problems, bin-packing and flowshop, and the obtained results confirm the theoretical findings. This study suggests that alternatives to the additive updates in reinforcement learning mechanisms should be considered.

Details

Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization - 16th European Conference, EvoCOP 2016, Proceedings
Publication statusPublished - 2016
Event16th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016 - Porto, Portugal
Duration: 30 Mar 20161 Apr 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9595
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference16th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2016
CountryPortugal
CityPorto
Period30/03/161/04/16

Keywords

  • Hyper-heuristics, Reinforcement learning, Runtime analysis