Runtime analysis of a population-based evolutionary algorithm with auxiliary objectives selected by reinforcement learning

We propose the method of selection of auxiliary objectives (2 + 2λ)-EA+RL which is the population-based modification of the EA+RL method. We analyse the efficiency of this method on the problem XdivK that is considered to be a hard problem for random search heuristics due to multiple plateaus. We prove that in the case of presence of a helping auxiliary objective this method can find the optimum in 0(n2) fitness evaluations in expectation, while the initial EA+RL, which is not population-based, yields at least Ω (nk−1) fitness evaluations, where k is the plateau size. We also prove that in the case of presence of an obstructive auxiliary objective the expected runtime increases only by a constant factor.