Self-Adaptive Mutations May Lead to Premature Convergence

Self-adaptive mutations are known to endow evolutionary algorithms (EAs) with the ability of locating local optima quickly and accurately, whereas it was unknown whether these local optima are finally global ones provided that the EA runs long enough. In order to answer this question it is assumed that the (1 + 1)-EA with self-adaptation is located in the vicinity P of a local solution with objective function value ". In order to exhibit convergence to the global optimum with probability 1 the EA must generate an offspring that is an element of the lower level set S containing all solutions (including a global one) with objective function value less than ". In case of multimodal objective functions these sets P and S are generally not adjacent, i.e., minfkx yk: x 2 P; y 2 Sg> 0, so that the EA has to surmount the barrier of solutions with objective function values larger than " by a lucky mutation. It will be proven that the probability of this event is less than 1 even under an infinite time horizon. This result implies that the EA can get stuck at a non-global optimum with positive probability. Some ideas of how to avoid this problem are discussed as well