Improvement And Extension Of Differential Evolution Algorithm

In 1995 R. Storn and K. Price proposed a new real-coded evolutionary algorithm, differential evolution (DE). It is a global optimization algorithm of derivative-free. DE is real-coded and uses multi-parent crossover. A new individual will replace the current individual if and only if it is not-worse than the current individual. There are several variants of DE. The most popular one is DE/rand/1, the updating of an individual can be summarized as follows. For each individual in the current population, three different individuals are chosen at random and an intermediate individual will be generated by disturbing one of them along the direction determined by the other two. Then a trial individual will be generated by crossover between the intermediate individual and the current individual . Finally the natural selection"survival of the fittest"will be carried out between the trial individual and the current individual , and the better one will be survived. Thus the current individuals in the current population will be updated one by one and from generation to generation.First, we aim to improve the performance of DE by presenting some new evolutionary operators such as mutation of chemical adsorption and mutation during the selection. These operators can strengthen the local search ability of DE considerably. Then we will analyze the population sequence generated by DE process with Markov chains. Finally we will propose a bi-level tournament selection for handling multi-objectives and constraints for DE, which makes DE capable of solving multi-objective optimization with mixed variables and many constraints. Mutation of Chemical Adsorption Note that the mutation operator in DE X_r1(t)+Fï¿ (X_r2(t),X_r3(t)) is actually linear. The linearity might bring much difficulty to the efficiency of DE because the mutant individual is always lied in the super-plane determined by the parent individuals , , . In other words, new individuals will never escape from the super-plane determined by their parent individuals. So the algorithm might be trapped into local optimum. The mutation process of DE can be regarded as a process of physical adsorption because there is only a displacement during the mutation. If we consider each component of an individual as a chemical bond, the process of letting some components of an individual is attached to another individual (base point) can be regarded as a mutation of chemical adsorption. Take the base point as an example. The mutation of chemical adsorption can be described as follows component-wisely.where is the strength of adsorption. The chemical adsorption is a kind of non-linear operators. Note that if we set , chemical adsorption will be the same as physical adsorption and the mutation of chemical adsorption will be the same as that of original DE. We need to pay attention to two points while using the mutation operator with chemical adsorption: 1) how to select the base point; 2) how to set the strength of adsorption. We simply choose as the base point and set in this paper, where is the dimension of the considered problem. Further study is needed on this topic.Mutation During the Selection In differential evolution (DE), the selection rule is deterministic, i.e., the trial individual replaces the current individual if and only if it is not worse than the current individual. This means the selection pressure is very high in DE. This may accelerate the convergence process, but may degenerate the variety of the population. Therefore, we provide weak individual another opportunity at some preset probability (10% as an example) to improve. Two questions arise: what is weak individual and which mutation operator will be applied. We define the weak individual as those who are worse than the average of the current population. That is, is said to be weak if . For the mutation, we choose the Cauchy-Lorentz mutation with the best individual as its center, i.e., the mutant individual .For convenience, we call the differential evolution algorithm with the mutation of chemical adsorption and the mutation during selection modified differential evolution (mDE). Numerical results show that mDE is 1.31 times faster than another modification of differential evolution (DERL) proposed by P. Kaelo and M.M. Ali (TABLE 2.1). Markov Analysis of Differential Evolution DE is a kind of population based stochastic algorithm. Its searching process can be described as stochastic process. In fact, each population can be regarded as a state of the evolutionary process and all possible populations can be regarded as the state space of the stochastic process. It is easy to show that the state space is finite in the finite precision and the population sequence generated by DE is a homogeneous finite Markov chain. Note that the population sequence generated by standard genetic algorithm is a homogeneous, irreducible, aperiodic and finite Markov chain. But for DE, the Markov chain is neither irreducible nor aperiodic. In fact, we have the following results. Proposition 1. For the population Markov chain generated by DE, the optimal state set is closed.Proposition 2. For the population Markov chain generated by original DE, the state set corresponding to uniform populations (in which all individuals are same) is closed.The proposition shows that original DE might failed to get the global optimum. For the modified DE we have proposed in this paper, we have Theorem 1. The population Markov chain generated by the modified DE can converge to the global optimal population for any initial population Extension of Differential Evolution The original DE is designed for singleobjective unconstrained optimization with continuous variables. We consider using DE for multi-objective constrained optimization with mixed-variables. In order to handle the multi objectives and the constraints simultaneously, we proposed a new selection rule, called bi-level tournament selection. The individuals are evaluated and selected by two levels of tournament. That is, the PK result between two individuals and is decided by two levels of tournament, the lower level tournament and the top level tournament. The lower level tournament is among the current individual (or the trial individual )and randomly chosen individuals. Three scores are marked as ratio of objectives , ratio of violations , and ratio of individual distributions . The top level tournament is between and , the fitness function is defined as where . The individual will be picked and the individual be killed if and only if . The weak individual is redefined as those individual who satisfies . Real-time relaxation and rounding method is introduced to handle the discrete variables. The usual elite archive technique is also used for improving the quality of solutions. Numerical results show that the extended DE can solve the multi-objective constrained optimization with mixed-variables reliably and effectively.