Parameter Adaptive Differential Evolution for Multi-Modal Function Optimization


In academic research and real-world applications, many optimization problems show different challenging characteristics such as nonlinearity, non-convexity, and/or multimodality which impose great difficulty for traditional nonlinear programming techniques. Differential evolution is a recent branch of evolutionary algorithms and is capable of addressing a wide set of such optimization problems in a relatively uniform and conceptually simple manner. The performance of differential evolution, however, is generally sensitive to its control parameters, since they behave differently for various problems or at different evolution stages of a single problem. The fundamental contributions of this thesis include design and evaluation of parameter adaptive differential evolution to address these problems. The major contributions are summarized below. First, a theoretical analysis has been conducted to investigate the evolutionary stochastic properties of a differential evolution algorithm’s convergence behavior for a spherical function model. A Gaussian approximate model of differential evolution is introduced to facilitate mathematical derivation of the stochastic properties of mutation and selection and help the understanding of the effect of mutation factor on the evolutionary dynamics. Theoretical results, as verified by experimental simulations, highlight the necessity to adaptively evolve control parameters as evolutionary search proceeds. Second, a new parameter adaptive differential evolution algorithm, JADE, is introduced to automatically adapt control parameters responding to a range of function characteristics at different stages of evolutionary search. To improve convergence performance, JADE incorporates a greedy mutation strategy that utilizes the direction information provided by both high-quality solutions in the current generation and inferior solutions previously explored in the evolutionary search. Extensive experiments have been conducted to show their mutual benefits for a good balance between the convergence speed and reliability. In addition, the parameter adaptation avoids the need for users’ prior knowledge of the interaction between the control parameters and the convergence behavior, thus making the algorithm easily usable. Third, extensions of the basic JADE algorithm are considered from several perspectives. Some optimization problems have a demanding limitation on the number of original function evaluations that are expensive in terms of time, cost and/or other limited resources. JADE has been extended to address these problems by incorporating computationally inexpensive surrogate models and adaptively controlling the level of incorporation according to the model accuracy. Radial basis function networks are used to create these models for the sake of a good balance between computational complexity and model accuracy. Experimental results have shown the efficiency of adaptive incorporation of surrogate models in avoiding potential false or premature convergence while significantly reducing the number of original expensive function evaluations. Fourth, many real-world applications involve multi-objective optimization, because they are linked to competing or conflicting outcomes such as profit, risk and/or many other performance related criteria. JADE is extended to multi-objective optimization to search for a set of optimal tradeoff solutions. Simulation results show that JADE achieves fast convergence rate by utilizing the direction information provided by previously explored inferior solutions, even when most or all solutions in the current population become non- dominated and thus the high-quality solutions among them do not necessarily indicate the direction of the optimum. Fifth, the performance of JADE has been evaluated for a variety of benchmark functions of different characteristics such as nonlinearity, non-convexity, multi-modality and high- dimensionality. The performance of JADE is compared with both classic and state-of-the-art algorithms such as the classic DE, other adaptive DE algorithms (SaDE, jDE, SaNSDE), the canonical PSO, Adaptive LEP and Best Levy for single-objective optimization, and MODE, SPEA, GDE3 and NSGA-II for multi-objective optimization. Comprehensive experimental studies have shown that JADE achieves better convergence performance than other algorithms and has better scalability for high-dimensional functions. JADE usually leads to the fastest convergence rate while maintaining the probability of successful convergence at a level very close to the most robust competitive algorithm. The proposed adaptive differential evolution algorithm JADE has been applied in different real-world applications where domain knowledge can be utilized to improve optimization performance. First, it is applied to a winner determination problem in combinatorial auctions, which can be generalized to resource allocation problems in sensor management, supply chain management, etc. Second, JADE solves a data-smoothing problem in credit decision making by searching for the transition probability matrix that satisfies different desired properties and optimally matches the empirical data of credit rating transition. Furthermore, JADE is applied to conduct automatic flight planning in air traffic control systems. It is used to assign an appropriate route to each flight to minimize both system level congestion and total flight distance. In these applications, JADE has produced better results than other state-of-the-art evolutionary algorithms and heuristic approaches in terms of the convergence rate and the quality of the final solutions.