INTRODUCTION
Constrained Optimization Problems (COPs) (Yong et al.,
2009) is a basic research problem in the field of engineering and operations
research. When solving COPs with the traditional mathematical method, it often
falls into local optimum. Therefore, the usage of evolutionary algorithms for
solving COPs becomes a research hotspot. In order to validate the algorithm,
we usually use 13 Benchmark function (hereinafter “13 functions”)
which was summarized by Runarsson and Yao (2000). However,
it doesn’t work well when we solve the second function, Bump, with most
of algorithms.
Differential Evolution (DE) algorithm (Storn and Price,
1997) is a new evolutionary algorithm which has comprehensive ability for
optimization and rapid convergence properties. As a global optimization algorithm
because of lack of constraint handling mechanism, it can not be directly applied
to COPs. Scholars use different ways to improve it in order to make it apply
to COPs, (MezuraMontes et al., 2005) and (Lampinen,
2002) has tried to introduce constraint handling mechanism in DE algorithm,
to solve COPs’s standard 13 functions but the result shows that the solving
quality of Bump problem is poor. Yichao and Xizhao (2008)
and Bingyu et al. (2004) use modified DE algorithm
only to solve the Bump problem get the better effect. However, it still has
the problem that the standard deviation is larger and the robustness of solving
quality is not strong.
In order to successfully solve optimization problem of Bump function, present study improve DE algorithm based on the following two basic ideas: Firstly, the initial population of DE algorithm is initialized by using chaos sequence, population distribution can be made more uniform, hence it is more likely to find the global optimum solution; secondly, chaotic local search approach can improve DE’s search performance. Based on the above ideas, chaotic differential evolution algorithm is proposed for solving bump problem. This algorithm makes improvement in four areas in the framework of basic DE algorithm: first, the initial population of DE algorithm is initialized by using chaos vector sequence; Secondly, the introduction of DEB comparison criteria enables the algorithm to have constraint handling capacity; Thirdly, When the optimal solution of DE algorithm is not updated after several generations, using chaotic local search algorithm helps DE algorithm to jump out the local optimal solution; Finally, at regular intervals of DE algorithm generation, using chaos initialization vector sequence to replace half worse solutions of the original population. The experimental results show that chaotic differential evolution algorithm can successfully solve optimization problem of bump function and its robustness is stronger.
DEFINITION OF THE QUESION
The general form of the COPs problems are as follows:
where,
Dim is scale of problem; S = {XX∈D∧g_{i}(X)≤0∧h_{k}(X)
= 0} is the feasible region; f : D→R is called objective function, inequality
g_{i}(X) is inequality constraint conditions; h_{k}(X) is equality
constraint conditions.
Bump problem is a specific COPs in this study, it is 2nd function in the 13 Benchmark what Runarsson (2) summarized, the concrete form as the following:
where, X expresses a feasible solution X = (x_{1}, x_{2}, ..., x_{n}), x_{i} is a component of feasible solution.
CHAOTIC DIFFERENTIAL EVOLUTION OF SOLVING CONSTRAINT OPTIMIZATION PROBLEM
The basic thought of chaotic differential evolution algorithm is to use the
three major features of chaos sequencesthe randomness, ergodicity and regularity
(Gong and Shaoqian, 2000), to improve differential evolution
algorithm and to enhance its search capabilities; at the same time, introducing
DEB comparison criteria to the modified algorithm can make it have constraint
handling capacity (Fig. 1).

Fig. 1: 
Three comparison criterions of DEB 
Chaos optimization improve the performance of differential evolution in three
aspects: Firstly, according to ergodicity and randomness of chaos sequences,
the initial population of DE algorithm which replaces the initial population
of the random generation is generated to make distribution of initial population
more uniform; Secondly when the optimal solution of populations in DE algorithm
is not updated after several generations’ continuous evolution, the chaotic
local search is used around the optimal solution to enhance the optimal solution’s
quality of population according to the ergodicity of chaos sequence; Thirdly,
assuming population size of DE algorithm is NP, at regular intervals algebra
in DE algorithm, the chaos sequence generate NP/2 new individual; Then the half
individuals of current population which the fitness function is poor can be
replaced by those new generation. In this case, we can maintain the diversity
of population.
DEB comparison criterion: The goal of DE algorithm is to solve global
optimization problems, because of lack of constraint handling capability; it
can not be directly used to solve COPs. In order to make genetic algorithm have
constraint capability, Deb (2000) invented DEB comparison
criterion, it is a method that the two individuals compare advantages and disadvantages
in the constraint condition. This criteria is used to improve the chaotic DE
algorithm and is applied to algorithm with the two individuals’ comparison
all related operation which make the algorithm have constraint handling capability.
The basic implementation ideas of DEB comparison criterion are as follows: first, all of constraints violation degree is added which is defined as the sum of constraint violation degree; second when designing two individuals comparison, a feasible solution priority strategies is used. This specific strategy can be expressed as the following three comparison criterions:
According to COPs, functional forms of the sum of constraint violation degree and DEB comparison criteria are as follows.
Definition 1 (sum of constraint violation degree): G(X) is the sum of constraint violation degree for an individual X in the population, the form is:
where,
where, δ is relaxation degree of equality constraint. We don’t discuss
the settings of δ here because that the problem about g 02 doesn’t
have equality constraints.
Definition 2 (function form of DEB comparison criteria): Prior(X1, X2) express the results that the two solutions X1 and X2 are compared using DEB comparison criteria, the form is:
Differential evolution algorithm of solving COPs problem: Differential
evolution algorithm is a global optimization algorithm proposed by Storn
and Price (1997). Because of his outstanding performance in the first session
of IEEE evolutionary programming contest, DE algorithm has become a new research
focus in the field of evolutionary computing. As same as the genetic algorithm,
DE algorithm is based on population evolutionary and also contains three operators
of mutation, intersect and selection. However, DE algorithm is based on real
valued coding different from genetic algorithm based on binary coding. Compared
with global optimization problem, mutation and intersection operator remain
unchanged to solve COPs in the modified DE algorithm. The algorithm only improves
the selection operator by using DEB comparison criteria to make it have the
constraints handling capacity.
Assuming the form of COPs is same to, population size of DE algorithm is NP. The following is the definition of the three operators in the improved algorithm.
Definition 3 (mutation operator of DE algorithm): Select three variables from the current population randomly {X_{i}X_{i}=(x_{i,1 }, x_{i,2 }, ..., x_{i, Dim}), i=1,2,...,NP}, one is as disturbance variables, the other two subtractions are as difference vector. Variance vector is getted by the following formula.
where, X_{i} denotes arbitrary solution vector of the population, Dim denotes problem scale, r1,r2,r3∈{1,2,...,NP} and r1≠r2≠r3≠, NP is the population
size, F is the scaling factor, G is the algebra of current evolution.
Definition 4 (intersection operator of DE algorithm): The ith vectors
generated by mutation and the ith vectors
of original population are executed intersection operator according to the following
formula (5), to get the candidate vector .
where, j∈{1,2,...,Dim}, Dim said problem scale, CR is the crossover probability, rnd is the random number on [0,1] uniform distribution, j_{rand} is an integer selected randomly on the {1,2, ..., Dim}.
Definition 5 (selection operator of DE Algorithm): The ith candidate
vector
and the ith vectors
of original population are executed selection operator according to the following
formula (6), to get the individual
of next generation with better fitness.
where,
indicates the (G+1) th generation and ith individual of populations. We should
pay attention that the comparison of two individuals use DEB comparison criteria.
Chaotic Optimization of solving COPs problem: Chao is a general phenomenon in nature and is a powerful tool to express nonlinear systems. Its main feature is that it traverses all the states without repetition according to its own “law” within a certain range. It can also be expressed as the randomness, ergodicity and regularity of chaotic motion. Present study just tries to improve DE evolutionary algorithm to enhance its global search capability based on these features.
The common chaos model mainly has the following two forms:
where, k said iterations, k∈{1,2,...,K}, K is Maximum number of iterations.
Equation 7 is called the Logistic mapping, μ = 4, y_{1}∈
(0,1) and y_{1}≠0.25, 0.5, 0.75 in formula (7). y_{1}∈
(0,1), α∈ (0,1), β = 2 in Eq. 8.

Fig. 2: 
Pseudo code of chaotic initialization 
The Eq. (7) and (8) is the variable form
of chaos equation; however, vector representation which is used in the DE algorithm
is as follows after the transformation.
where, Y_{k} = (y_{1,k }, y_{2,k },_{ ...},
y_{Dim ,k}) said kth generation chaos vector, corresponding to the solution
vectors of DE algorithm. Dim said the problem dimension. k said iterations;
y_{i,1}∈ (0,1) and y_{i,1}≠0.25, 0.5, 0.75 in formula
(9), y_{i,1}∈ (0,1), i∈{1,2,...,Dim} in formula (10); the
parameter μ in formula (9) is same as in formula (7), μ = 4, α
and β in Eq. 10 is the same as in Eq.
(8), α ∈ (0,1), β≠2.
Chaotic initialization population: Storn pointed out that if the initialization
population can be the uniform distribution as far as possible, then the DE algorithm
is more possible to find the global optimal solution (Storn
and Price, 1997). Torresponding to it, the chaos variable has randomness
and ergodicity. Therefore this study attempts to get the chaos sequence by using
Eq. 9 and maps it into the initial population which satisfies
the definition domain of DE algorithm.
The basic realization idea of chaotic initialization population is as follows: first, randomly initialize a vector Y_{0} that dimension is Dim; second, by using Logistic mapping (Eq. 9), iterate the vector to arrive Kiter generation to get vector Y_{KIter}; third, because each element of vector Y_{KIter} which is in the range (0, 1) and not within the definition domains, is not a real solution, vector Y_{KIter} is mapped to solution vector Z of definition domain; last, repeat the above three steps N times, to get the population containing N solution vectors.
Suppose to solve COPs described in 1st part. Giving the lowerbound of solution
vector A=(a_{1}, a_{2},..., a_{Dim}), the upperbound
is B = (b_{1}, b_{2},..., b_{Dim}). Chaotic vector Y
which is generated by the formula (9), transforms into the vector Z in the definition
domain by using the e Eq. 11.
Based on the above ideas, the pseudocode of chaos_init function which defines population containing N elements generated by chaotic initialization is shown in Fig. 2.
Chaotic local search: Chaotic local search execute chaos variation around
the optimal solution by using traversal characteristics of chaos sequences and
expect to find the better solution to guide the evolution to move forward. Yue
and Guanzheng (2009) pointed out that Eq. 8 is better
than Eq. 7 when the chaotic mutation are executed, so Eq.
10 which is corresponding to Eq. 8 is selected as a generation
formula for chaos vector.
Based on the above discussion, the implementation idea of chaotic local search
algorithm is first to initialize random vector Y_{0} that dimension
is Dim; then to produce iteratively a sequence {Y_{i} i=1,2,...,M}
containing M chaos vectors by using formula (10); then to add these M vectors
to the optimal solution vectors X_{best} of population to get variation
vector sequence {Z_{i} i=1,2,...,M}; Finally, to find the optimal vector
Z_{best} amoung of {Z_{i}} according to DEB comparison criteria
and return it.

Fig. 3: 
Pseudo code of chaotic local search 
Assumed to solve COPs problem of part 1, according to above idea, pseudocode of chaotic local search function is as Fig. 3.
Chaotic differential evolution algorithm of solving COPs problem: The implementation method solving chaotic differential evolution algorithm of COPs is, first, to generate the initial population of DE algorithm by using chaotic initialization function chaos_init; second, to execute mutation, crossover and selection operations of DE evolutionary algorithm; in the implementation process of DE algorithm, if the optimal solution of population is not updated when it evolute the certain generations, then the population is optimized by using local search function chaos_search; at the same time, at evolutionary intervals generation, the new initial solution set which is generated by using chaotic initialization function chaos_init replace the half worse solution of population.
Pseudocode is shown in Fig. 4.
EXPERIMENTS
Benchmark function is 20 dimensions Bump problem which is introduced earlier.
Present study carries out independently 20 times improved chaotic DE algorithm
to solve Bump problem (Table 1).
Where Dim expresses the dimension of Bump function; NP expresses population's
scale; F expresses scaling factor; CR expresses the crossover probability; MAX_GEN
expresses the maximum times of iterations for DE algorithm; CIter expresses
the algebra which the population optimal solution is not updated continuously
in the condition of triggering chaotic local search criteria; FIter expresses
the operation frequency that the population is replaced through carrying on
chaotic initialization; μ is a parameter of chaos vector equation formula
(9); α and β is parameters of chaos vector equation formula (10);
KIter expresses iteration times of chaos equation which generate finally chaos
vector in chaotic initialization function chaos_init; M expresses number of
the chaotic variation vector which is generated around optimal solution in chaotic
local search function chaos_search.
The detailed information of optimal solution after carrying out 20 times experiments is shown by histogram in Fig. 5. We can clearly see from the Fig. 5 that all 20 times tests obtain known optimal solution 0.803619.
In order to verify validity of the chaotic DE algorithm, Table 2 compares it to solve the quality of bump functions with other algorithms. Other algorithms include:

Fig. 4: 
Pseudo code of chaotic differential evolution 

Fig. 5: 
Column chart of the results in 20 independent experiments
for Chaotic DE 
In the four algorithm participating comparison, IRY algorithm (Runarsson
and Yao, 2005) makes the improvement to classics RY algorithm (Runarsson
and Yao, 2000), it is the most competitive to solve COPs at present; In
order to have the comparability, the other three are all DE algorithm, DiversityDE
are the most effective DE algorithm to solve COPs, MDE and PSODE are DE algorithm
which are designed only for bump function.
Table 1: 
Parameter settings of Chaotic DE 

Table 2: 
The comparison results with other papers 

As can be seen from Table 2, chaotic difference evolution algorithm is the best in five algorithms to solve Bump function. Compared with IRY algorithm and DiversityDE algorithm which solve the standard 13 problem of COPs, the algorithm in this study is that not only the mean of optimal solution and the worst solution is prior but also the variance of optimal solution is smaller. It indicates that this algorithm to solve Bump problems has high quality and stability. MDE algorithm and PSODE algorithm which are designed only for Bump function optimization problem is higher quality but the method adopted in the article also has advantages in comparison with them, especially in terms of standard deviation, it indicates that stability of this algorithm is stronger.
CONCLUSION
An novel difference evolution algorithm based on the chaotic optimization is proposed in this study. The new algorithm which solves successfully Bump function, uses the DEB comparison criterion to process constraint. The simulation results show that: according to the Bump function, the new algorithm is very competitive and robustness.
Two chaotic optimization operators do not depend on the specific form of DE algorithm. Therefore, we will focus on combine the two operators with other forms of DE algorithm to solve the constrained problem in the future.