Title :
A First Step towards the Runtime Analysis of Evolutionary Algorithm Adjusted with Reinforcement Learning
Author :
Buzdalov, Maxim ; Buzdalova, Arina ; Shalyto, Anatoly
Author_Institution :
St. Petersburg Nat. Res. Univ. of Inf. Technol., Mech. & Opt., St. Petersburg, Russia
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.
Keywords :
evolutionary computation; learning (artificial intelligence); OneMax problem; Q-learning; auxiliary fitness functions; evolutionary algorithm; greedy exploration strategy; random mutation hill climber; reinforcement learning; runtime analysis; runtime complexity analysis; single objective optimization; Complexity theory; Evolutionary computation; Genetic algorithms; Learning (artificial intelligence); Markov processes; Optimization; Runtime; complexity; helper-objectives; onemax; reinforcement learning; theory;
Conference_Titel :
Machine Learning and Applications (ICMLA), 2013 12th International Conference on
Conference_Location :
Miami, FL
DOI :
10.1109/ICMLA.2013.42