Provably Optimal Self-adjusting Step Sizes for Multi-valued Decision Variables

We regard the problem of maximizing a OneMax-like function defined over an alphabet of size gamma. In previous work [GECCO 2016] we have investigated how three different mutation operators influence the performance of Randomized Local Search (RLS) and the (1+ 1) Evolutionary Algorithm. This work revealed that among these natural mutation operators none is superior to the other two for any choice of gamma. We have also given in [ GECCO 2016] some indication that the best achievable run time for large gamma is theta(n log r(log n + logr)), regardless of how the mutation operator is chosen, as long as it is a static choice (i.e., the distribution used for variation of the current individual does not change over time). Here in this work we show that we can achieve a better performance if we allow for adaptive mutation operators. More precisely, we analyze the performance of RLS using a self-adjusting mutation strength. In this algorithm the size of the steps taken in each iteration depends on the success of previous iterations. That is, the mutation strength is increased after a successful iteration and it is decreased otherwise. We show that this idea yields an expected optimization time of theta( n( log n + logr)), which is optimal among all comparison-based search heuristics. This is the first time that self-adjusting parameter choices are shown to outperform static choices on a discrete multi-valued optimization problem.