Not guaranteeing convergence of differential evolution on a class of multimodal functions

• We constructed a Linear Deceptive function as the representative of a class of multimodal functions.
• DE cannot guarantee convergence in probability on the above class of multimodal functions.
• A random drift model was firstly used to analyze the convergence of a real-coded evolutionary algorithm.
• DE's mutation operators prefer to search in the aggregating region of the target individuals.

The theoretical studies of differential evolution algorithm (DE) have gradually attracted the attention of more and more researchers. According to recent researches, the classical DE cannot guarantee global convergence in probability except for some special functions. Along this perspective, a problem aroused is that on which functions DE cannot guarantee global convergence. This paper firstly addresses that DE variants are difficult on solving a class of multimodal functions (such as the Shifted Rotated Ackley's function) identified by two characteristics. One is that the global optimum of the function is near a boundary of the search space. The other is that the function has a larger deceptive optima set in the search space. By simplifying the class of multimodal functions, this paper then constructs a Linear Deceptive function. Finally, this paper develops a random drift model of the classical DE algorithm to prove that the algorithm cannot guarantee global convergence on the class of functions identified by the two above characteristics.

Figure optionsDownload as PowerPoint slide