Limits to learning in reinforcement learning hyper-heuristics

Fawaz Alanazi*, Kristian Per Lehre

*Corresponding author for this work

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

12 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization - 16th European Conference, EvoCOP 2016, Proceedings
PublisherSpringer Verlag
Pages170-185
Number of pages16
Volume9595
ISBN (Print)9783319306971
DOIs
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
Country/TerritoryPortugal
CityPorto
Period30/03/161/04/16

Keywords

  • Hyper-heuristics
  • Reinforcement learning
  • Runtime analysis

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Limits to learning in reinforcement learning hyper-heuristics'. Together they form a unique fingerprint.

Cite this