Paper Info
Title
A First Step towards the Runtime Analysis of Evolutionary Algorithm Adjusted with Reinforcement Learning
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 T(N logN) 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.
Year
DOI
Venue
2013
10.1109/ICMLA.2013.42
ICMLA (1)
Keywords
Field
DocType
efficient auxiliary fitness function,greedy exploration strategy,fitness function evaluation,n logn,runtime analysis,rl method,inefficient auxiliary fitness function,first step,onemax problem,inefficient fitness function,evolutionary algorithm,reinforcement learning,rl implementation,conventional evolutionary algorithm,theory,learning artificial intelligence,complexity,evolutionary computation
Interactive evolutionary computation,Mathematical optimization,Evolutionary algorithm,Evolutionary robotics,Computer science,Evolutionary computation,Fitness function,Fitness approximation,Artificial intelligence,Machine learning,Learning classifier system,Reinforcement learning
Conference
Citations 
PageRank 
References 
5
0.47
18
Authors
3
Name
Order
Citations
PageRank
Maxim Buzdalov114125.29
Arina Buzdalova2619.42
Anatoly Shalyto39820.06