On the impact of the mutation-selection balance on the runtime of evolutionary algorithms

The interplay between the mutation operator and the selection mechanism plays a fundamental role in the behaviour of evolutionary algorithms. However, this interplay is still not completely understood. This paper presents a rigorous runtime analysis of a non-elitistic population based evolutionary algorithm that uses the linear ranking selection mechanism. The analysis focuses on how the balance between parameter η controlling the selection pressure in linear ranking selection, and parameter Χ controlling the bit-wise mutation rate impacts the expected runtime. The results point out situations where a correct balance between selection pressure and mutation rate is essential for finding the optimal solution in polynomial time. In particular, it is shown that there exist fitness functions which under a certain assumption can be solved in polynomial time if the ratio between parameters η and Χ is appropriately tuned to the problem instance class, but where a small change in this ratio can increase the runtime exponentially. Furthermore, it is shown that the appropriate parameter choice depends on the characteristics of the fitness function. Hence there does in general not exists a problem-independent optimal balance between mutation rate and selection pressure. The results are obtained using new techniques based on branching processes. Copyright 2009 ACM.