A constrained optimization problem is usually written in the following form:
minf(x), x=(x1,x2, ···,xn) ∈Rn (8)
gj(x) ≥0, j=1,2,3, ···,J (9)
hj(x) = 0 , j=J=1, ···,P, (10)
xi,lo ≤ xi ≤ xi,up, 1≤i≤n (11)
Where Ω= {x = (x1,x2, ,···,xn) ∈ Rn | gj(x) > 0, 1≤j≤J; hj(x) = 0, J+1≤j≤p; xi,lo≤xi≤xi,up, 1≤i≤n} is the feasible region; x∈Ωis the decision vector; J is the number greater-than-or-equal-to type inequality constraints; (p-J) is the number of equality constraints; f(x) is the objective function; gj(x) is the jth inequality constraint; hj(x) is the jth equality constraint; xi,lo,xi,up are the lower and upper bounds, respectively, of the ith variable xi.
In general, equality constraints in Eq. (9) are handled by converting them into the following inequality constraints:
i-|h(x)| > 0, (12)
where t≥0 is the tolerance value of the equality constraints—usually a small positive number. After converting the equality constraints into inequality constraints, there will be p inequality constraints in the constrained optimization problem, Eqs. (7)-(10).
There are many constraint handling methods used in GAs, compared with other methods, but the penalty function method is the most widely adopted. Its main idea is to penalize infeasible solutions, i.e., to solve an unconstrained optimization problem using the following modified objective function, called the penalty fitness function:
F(x) = f (x)+penalty(x),
where penalty(x) is zero when x∈Ω; otherwise, it is positive. Since the degree to which the individual x violates the jth constraint can be measured by
[Homaifar et al., 1994] devised the following penalty fitness function:
where
is the penalty term and Rj(j=1,2,···,p) is the penalty coefficient. Since none of Rj changes with the iteration number (i.e., the generation number), this method is called the static penalty function method. [Joines and Houck, 1994] proposed the following dynamic penalty method:
where v is the iteration number; and C, α, βare constants requiring adjustment. More detail about penalty functions can be found in [Michalewicz and Schoenauer, 1996], and references therein. Although penalty function methods have received wide attention because of their simplicity and ease of implementation, they still have some disadvantages. The biggest drawback is that extensive experimentation is required for setting up appropriate parameters needed to define the penalty function. To deal with this issue, [Deb, 2000] developed a constraint handling method. This method uses the tournament selection mechanism and niching strategy in the selection operation of the GA. The comparison criteria of the tournament selection are: (1) feasible solutions are always superior to infeasible solutions; (2) when two feasible solutions are compared, the one having the better objective function will be chosen; and (2) when two infeasible solutions are compared, the one having the smaller constraint violation will be selected. Maintaining diversity among feasible solutions is an important task for GAs, which was achieved by [Deb, 2000] through use of the niching strategy in the tournament selection operator.
However, each method has its own applicability and there is still no general method that can deal with all kinds of constraints, as stated by Gregory (1995):
“It is unrealistic to expect to find one general nonlinear programming code that is going to work for every kind of nonlinear model. Instead, you should try to select a code that fits the problem you are solving.”
When carrying out the genetic operation on parents to generate offspring, we need to implement selection, crossover, mutation operators and/or the elitist reservation strategy. Proper genetic operators will make GAs more effective. In trying to search the global CNOP in a non-smooth and strongly nonlinear case, an effective constrained optimization algorithm, the VCGA, was developed in the present reported work and its genetic operations are as follows.
3.2.1 Selection operation
The selection operation in the VCGA uses a tournament selection operator. Specifically, two individuals are picked at random from the current population and are compared based on the following comparison criteria:
(1) When both comparative individuals are feasible solutions, the one with the better objective function is preferred.
(2) When there is any infeasible solution among two comparative individuals, firstly pull the infeasible solution to the edge of the spherical constraints — that is, substitute individual x with y=δx/PxP if it is an infeasible solution, where δ>0 is the radius of the ball constraining the initial perturbations—and then perform comparison criterion (1).
3.2.2 Crossover operation
[Herrera et al., 2005] analyzed the performance of BLX-αand indicated that, since it randomly generates offspring genes in the neighborhood of parent genes, the operator has a good global searching ability. Thus, offspring individuals can retain good diversity. [Deb and Agrawal, 1995] discussed the particularities of the simulation binary crossover (SBX) operator and pointed out that, since the range of offspring generated from SBX is in proportion to that of the parents, and the offspring solution near the parent solutions can be generated with higher probability, SBX not only has the ability to be adaptable, but can also attain the optimal solutions of a multimodal objective function. Motivated by these results, we chose BLX-αor SBX randomly to each crossover operation in VCGA.
3.2.3 Mutation operation
A GA is an algorithm that simulates biological evolution. During evolution, the genes of an organism may be subject to several different kinds of mutation leading up to the final state. This inspired us to devise a new mutation operator, which we named — and is referred to as hereafter — the multi-ply mutation operator. The way that the multiply mutation operator performs is as follows.
For each gene xi(1≤I≤n) of an individual x=(x1,x2,···,xn), the multi-ply mutation operator carries out the non-uniform mutation, parameter-based mutation, boundary mutation and uniform mutation in turn according to mutation probabilities Pm,1,Pm,2,Pm,3 and Pm,4 respectively. The procedure for operating the multi-ply mutation operator is shown in Fig. 2, in which ri,i=1,2,3,4 are uniformly distributed random numbers in [0,1], and Pm,i = 1,2,3,4 is the mutation probability.
3.2.3.1 The non-uniform mutation
The non-uniform mutation operation used in our multi-ply mutation operator was proposed by [Michalewicz, 1996]. Its execution procedure is as follows.
For each parent solution x=(x1,x2,···,xn) in a population of the Xth generation, create a new individual y=(y1,y2,···,yn) in the following way:
yi=xi + Δ(X,xi,up - xi)or yi = xi - Δ(X,xi - xi,lo), 1≤i≤n (16)
where Δ(X,y)=yr(1 - X/Tmax) b; r is a uniform random number from [0,1]; Tmax is the maximal evolution generation number; b is a parameter used to determine the degree of non-uniformity; and b=2 (in this study).
The non-uniform mutation operator, which carries out a uniform search in the early part of the evolutionary process and a local search in the later part, has slight adjustment ability. It is one of the most effective mutation operators [Herrera et al., 1998].
3.2.3.2 Parameter-based mutation
The following parameter-based mutation operation was presented by [Deb, 2000] and is used in the multi-ply mutation operator.
Let x=(x1,x2,···,xn) be an individual, and for each gene xi(i=1,2,···,n), both lower and upper boundaries xi,lo and xi,up are specified.
Step (1): Generate a uniformly distributed random number μ in [0,1];
Step (2): Calculate the parameter
as follows:
where ηm is the distribution index for mutation with an arbitrary non-negative value, and δ=min((xi-xi,lo),(xi,up-xi)/(xi,up-xi,lo));
Step (2): Calculate the mutated individual as follows:
where Δmax=xi,up-xi,lo is the maximum perturbation allowed in x=(x1,x2,···,xn).
3.2.3.3 Boundary mutation
The boundary mutation operation is as follows:
Step (1): Obtain an integer k from the integer set {1,2,···n} with the same probability;
Step (2): Generate a uniformly distributed random number u in [0,1];
Step (2): Generate a new individual y=(y1,y2,···yn) from the individual x=(x1,x2,···xn):
3.2.3.4 Uniform mutation
The uniform mutation operation is as follows.
Step (1): Obtain an integer k from the integer set {1,2,···n} with the same probability.
Step (2): Generate a new individual y=(y1,y2,···yn) from the individual x=(x1,x2,···,xn)
where r is a uniformly distributed random number in [xi,lo,xi,up].
3.2.3.4 Elitist reservation strategy
Since the fittest may be lost in crossover and mutation operations, the elitist reservation strategy is employed in the VCGA to avoid this possibility. The detailed steps involved in the operation of the elitist reservation strategy are shown in Fig. 3, in which M is the population size; xi(1),xi(2),···xi(M) is the parent generation; xx+1(1),xx+1(2),···xx+1(M) is the current generation; Ji(m) is the objective function value of the individual xi(m)(m=1,2,··M·); and J(x+1),avg is the average of individual objective function values of the current generation. To operate the elitist reservation strategy shown in Fig. 3 for a generation, its individuals must first be arrayed in their decreasing objective function values.