Abstract: Population initialization is very important to the performance of differential evolution. A good initialization method can help in finding better solutions and improving convergence rate. According to our earlier study, uniform design generation can enhance the quality of initial population. In this study, a Uniform-Quasi-Opposition Differential Evolution (UQODE) algorithm is proposed. It uses a two-population mechanism and incorporates uniform design and quasi-opposition initialization method into differential evolution to accelerate its convergence speed and improve the stability. At the same time, an adaptive parameter control technology is adopted to avoid tuning the parameters of DE. The UQODE is compared with other three algorithms of standard Differential Evolution (DE), Opposition-based Differential Evolution (ODE) and Quasi-Oppositional Differential Evolution (QODE). Experiments have been conducted on 14 benchmark problems of diverse complexities. The results indicate that our approach has the stronger ability to find better solutions than other three algorithms especially for higher dimensional problems, in terms of the quality and stability of the final solutions.
INTRODUCTION
Differential Evolution is a branch of evolutionary algorithms developed by Storn and Price (1997) for global continuous optimization problem. It has won the third place at the 1st International Contest on Evolutionary Computation. The algorithm uses a special mutation operator based on the linear combination of three individuals and a uniform crossover operator. It has several attractive features. Besides being an exceptionally simple evolutionary strategy, it is significantly faster and robust for solving numerical optimization problem and is more likely to find the functions true global optimum.
Despite having several striking features and successful applications to different fields, DE has sometimes been shown slow convergence and low accuracy of solutions when the solution space is hard to explore. Many efforts have been made to improve the performance of DE and many variants of DE have been proposed.
The first direction for improvement is hybridization. Fan and Lampinen (2003) proposed a new version of DE which a new local search operation, called trigonometric mutation. Sun et al. (2005) developed DE/EDA which combines DE with EDA for the global continuous optimization problem. It combines global information extracted by EDA with differential information obtained by DE to create promising solutions. The presented experimental results demonstrated that DE/EDA outperforms DE and EDA in terms of solution quality within a given number of objective function evaluations. Noman and Iba (2006) proposed a DE variant which incorporated a Local Search (LS) technique to solve optimization problem by adaptively adjusting the length of the search, using a hill-climbing heuristic. Experimenting with a wide range of benchmark functions, the results show that the proposed new version of DE performs better, or at least comparably, to classic DE algorithm. Gong et al. (2008) incorporated the orthogonal design method into DE to accelerate its convergence rate and the self-adaptive parameter control is employed to avoid tuning the parameters of DE. The experiment results indicate that ODE is able to find the optimal or close-to-optimal solutions in all cases. Changsheng Zhang et al. (2009) proposed a hybrid of DE with PSO, called DE-PSO which incorporates concepts from DE and PSO, updating particles not only by DE operators but also by mechanisms of PSO. The presented experimental results demonstrate its effectiveness and efficiency.
The second direction for improvement is dynamic adaptation of the control parameters. DE is sensitive to the two crucial parameters, to a certain extent the parameter values determine whether DE is capable of finding a near-optimum solution or not. So, recently, some studies focus on adaptive control parameters. Zaharie (2002) proposed to transform F into a Gaussian random variable. Liu and Lampinen (2005) proposed a Fuzzy Adaptive Differential Evolution (FADE) which uses fuzzy logic controllers to adapt the mutation and crossover control parameters. Das et al. (2005) proposed two schemes which are named DERSF and DETVSF to adapt the scaling factor F. Brest et al. (2006) presented a novel approach to self-adapt parameters F and Cr. In their method, these two control parameters are encoded at the individual level. Nobakhti and Wang (2008) proposed a Randomised Adaptive Differential Evolution (RADE) method, which a simple randomised self-adaptive scheme is proposed for the DE mutation weighting factor F. Qin and Suganthan (2005) proposed self-adaptive DE (SaDE) which the trial vector generation strategies and two control parameters are dynamically adjusted based on their performance. Zhang and Sanderson (2009) proposed a new Differential Evolution (DE) algorithm (JADE) which the optional archive operation utilizes historical data to provide information of progress direction. The most recent successful parameters are used to guide the setting of new ones.
The third direction for improvement is population initialization. Before solving an optimization problem, we usually have no information about the location of the global minimum. It is desirable that an algorithm starts to explore those points that are scattered evenly in the decision space. Population initialization is a crucial task in evolutionary algorithms because it can affect the convergence speed and also the quality of the final solution. Recently, some researchers are working some methods to improve the EAs population initialization. Leung and Wang (2001) designed a GA called the orthogonal GA with quantization (OGA/Q) for global numerical optimization with continuous variables. Gong et al. (2008) used orthogonal design method to improve the initial population of DE (ODE). Rahnamayan et al. (2007a) proposed two novel initialization approaches which employ opposition-based learning and quasi-opposition to generate initial population. Xu et al. (2008) used chaos initialization to get rapid convergence of DE as the region of global minimum. Pant et al. (2009) proposed a novel initialization scheme called quadratic interpolation to DE with suitable mechanisms to improve its generation of initial population. Peng et al. (2010) used uniform design to generate initial population of DE.
In this study, an improvement version of DE, namely Uniform-Quasi-Opposition Differential Evolution (UQODE) is presented to solve unconstrained optimization problem. UQODE uses a two-population mechanism. According to our previous study (Peng et al., 2010), uniform design generation can enhance the quality of initial population. So,in the first step, uniform design in Peng et al. (2010) is used to generate one population UPop. And then, we use the UPop to obtain another population QOPop by utilizing quasi-oppositional learning. Last, Select the Np fittest individuals from {UPop∪QOPop} as the initial population. We prove that the two-population mechanism and two-step generation of UQODE can increase the percentage of success and the speed of convergence. The experimental results show that UQODE outperforms DE,ODE and QODE.
DIFFERENTIAL EVOLUTION
Unlike GA that uses binary coding for representation, DE uses floating point encoding and combines simple arithmetic operators with the classical events of mutation, crossover and selection to evolve from a randomly generated initial population to a satisfactory one.
| Algorithm 1: DE with rand/1/bin |
OUR PROPOSED APPROACH
Quasi-oppositional optimization: Opposition-Based Learning (OBL) was first proposed by Tizhoosh (2005) and was successfully applied to several problems (Rahnamayan et al., 2007b). The basic concept of OBL is the consideration of an estimate and its corresponding opposite estimate simultaneously to approximate the current candidate solution. Rahnamayan et al. (2007b) proposed quasi-oppositional method based on opposition point. Quasi-opposite numbers are defined as follows:
The quasi-opposite number x'q is defined as:
Pr is a given the probability function, x' is the opposite number, x is the solution for an optimization problem. The x'q definition can be extended to higher dimensions.
UNIFORM DESIGN METHOD
Experimental design method is a sophisticated branch of statistics. The uniform design , proposed by Wang and Fang (1981) is one of space filling designs and has been widely used in computer and industrial experiments. The main objective of uniform design is to sample a small set of points from a given set of points, such that the sampled points are uniformly scattered.
We define the uniform array as UMqn, where, n is factors and q is levels. When n and q are given, the population can be constructed by selecting M combinations from qn. The steps of initialization population are as Algorithm 2.
Algorithm 2: Uniform design initialization |
UNIFORM-QUASI-OPPOSITION DIFFERENTIAL EVOLUTION
In the quasi-oppositional differential evolution, there are two population. The population initialization steps are as follows:
| • | Generate the first population randomly |
| • | Calculate the second quasi-opposite population |
| • | Choose the M better individuals from the combination of two population as initial population |
In our earlier study, the uniform design population initialization is a very effective method to obtain fitter initial candidate individual and increase the speed of convergence of algorithm. So, the basic idea of Uniform-Quasi-Opposition Differential Evolution (UQODE) is that the first population PU are constructed by uniform design. And then, the second quasi-opposite population are calculated based on PU.
The performance of DE is sensitive to the choice of control parameters. Storn suggested the better choice of the parameters are F = 0.5 and CR = 0.9. In order to avoid tuning the parameter F and CR, a self-adaptive para- meter control technology is adopted according to the following scheme:
| (7) |
N(τ, ε) is a normal distribution that can generate values in the range of (τ-3xε, τ+3xε). UQODE is introduced in Algorithm 3.
| Algorithm 3. Main procedure of UQODE |
| Table 1: | Comparison of DE, ODE, QODE and UQODE |
D: Dimension, NFC: No. of function calls (average over 50
trials), SR: Success rate, SP: Success performance. The last row of the
table presents the average success rates. The best NFC and the success performance
for each case are highlighted in boldface. DE, ODE, QODE and UQODE are unable
to solve f 10 (D = 60) |
|
EXPERIMENTS
In order to assess the performance of our proposed algorithm UQODE. We choose a set of 14 benchmark problems(14 test problems having two different dimensions) from f1-f14 (Rahnamayan et al., 2008). The UQODE has been compared with three algorithms: DE,ODE and QODE. The performance metrics has four categories using by Rahnamayan et al. (2008): Number of Function Calls (NFC), Success Rate (SR), average Success Rate (SRave) and Success Perfor-mance (SP).A smaller NFC means higher convergence speed. A larger SR, SRave and SP mean higher stability. In order to minimize the effect of the stochastic nature of the algorithms on metric ,we perform 50 independent runs for each algorithm on the benchmark problems.
The parameters of all algorithms are as follows:
| • | Population size: NP=100 |
| • | Maximum number of function calls: MAXNFC = 1x106 |
| • | The scaling factor F and probability of crossover CR using self-adaptive parameter control scheme as Eq. 7 |
| • | Halting precision: ε = 1x10-8 |
The mean results of 50 independent runs are summarized in Table 1. Results for DE, ODE and QODE are taken from (Rahnamayan et al., 2007a, b). From Table 1, it can be seen that UQODE outperforms DE,ODE and QODE on 19 functions. The UQODE can provide better results with smaller NFC than DE,ODE and QODE for 18 functions. The SR of UQODE is larger than other three algorithms for f410,20, f530,60, f760, f860, f910,20.UQODE performs marginally better than DE,ODE and QODE in terms of average Success Rate (SRave) (0.96, 0.89,0.87 and 0.85, respectively). The UQODE has the stronger ability to find better solutions than other three algorithms especially for higher dimensional problems. These results indicate the combination of uniform design initialization and quasi-opposition initialization can effectively accelerate convergence and improve the performance of differential evolution.
CONCLUSION
In this study, we have presented a new variant of basic DE algorithm (UQODE) in which the initial population is selected using the uniform-quasi-opposition initialization method. The UQODE has compared with other three algorithms of DE,ODE and QODE. According to the experiment results, we can conclude that the combination of uniform design initialization and quasi-opposition initialization method can enhance the capability of our algorithm and UQODE is better and more stable than other three algorithms on most benchmark problems.
Future work consists on extending the present version for solving some real life optimization problems such as the Earth-Moon low energy transfer problem and researching uniform-quasi-opposition initialization method to multiobjective optimization algorithm.
ACKNOWLEDGMENTS
The authors would like to acknowledge the anonymous reviewers and the Editors for their useful comments and constructive suggestions. This work was supported by the National Natural Science Foundation of China under Grant No.60873107(20090110), the National High-Tech Research and Development Plan of China under Grant No.2008AA12A201 (20090610), the Fundamental Research Funds for the Central Universities under Grant No. CUGL090238.(20091101), the Research Foundation of Science and Technology China University of Geosciences (Wuhan) under Grant No. CUGXGF0901 (20081120), the Research Foundation for Outstanding Young Teachers China University of Geosciences (Wuhan) under Grant No. CUGQNL0831 (20080120).