A First Step towards the Runtime Analysis of Evolutionary Algorithm Adjusted with Reinforcement Learning.

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

Abstract

A first step towards analyzing runtime complexity of an evolutionary algorithm adaptively adjusted using reinforcement learning is made. We analyze the previously proposed EA + RL method that enhances single-objective optimization by selecting efficient auxiliary fitness functions. Precisely, Random Mutation Hill Climber adjusted with Q-learning using greedy exploration strategy is considered. We obtain both lower and upper bound for the number of fitness function evaluations needed for this EA + RL implementation to solve a modified OneMax problem. It turns out that EA + RL with an inefficient auxiliary fitness function performs on par with a conventional evolutionary algorithm, namely in Θ(N log N) fitness function evaluations, where N is the size of the OneMax problem. In other words, we show that reinforcement learning successfully ignores inefficient fitness function. A lower bound for the ε-greedy exploration strategy for ε > 0 is analyzed as well.
Original languageEnglish
Title of host publicationICMLA '13
Subtitle of host publicationProceedings of the 2013 12th International Conference on Machine Learning and Applications
PublisherIEEE Press
Pages203-208
Number of pages6
Volume1
ISBN (Electronic)978-0-7695-5144-9
DOIs
Publication statusPublished - 04 Dec 2013
Externally publishedYes
Event2013 12th International Conference on Machine Learning and Applications - Miami, United States of America
Duration: 04 Dec 201307 Dec 2013

Conference

Conference2013 12th International Conference on Machine Learning and Applications
Country/TerritoryUnited States of America
CityMiami
Period04 Dec 201307 Dec 2013

Keywords

  • reinforcement learning
  • onemax
  • helper-objectives
  • theory
  • complexity

Fingerprint

Dive into the research topics of 'A First Step towards the Runtime Analysis of Evolutionary Algorithm Adjusted with Reinforcement Learning.'. Together they form a unique fingerprint.

Cite this