Engelbrecht Andries P. Computational Intelligence: An Introduction

Подождите немного. Документ загружается.

228 12. Evolution Strategies

subintervals of equal length, where the s-th interval is computed as

min,j

+(s − 1)



max,j

− x

min,j



min,j

+ s



max,j

− x

min,j

(

(12.42)

The ﬁtness of interval I

is deﬁned by

f(I



i=1

(t) ∈ I

)

f(x

(t)) (12.43)

where

(t) ∈ I



1ifx

(t) ∈ I

0ifx

(t) ∈ I

(12.44)

and

f(x

(t)) is the normalized ﬁtness of x

(t),

f(x

(t)) =

f(x

(t)) − f

min

(t)

max

(t) − f

min

(t)

(12.45)

The minimum and maximum ﬁtness of the current population is indicated by f

min

(t)

and f

max

(t) respectively.

Directed variation is applied to each component of each individual as follows. For

component x

(t), the direction of mutation is determined by f(I

),f(I

j,s−1

)and

f(I

j,s+1

), where x

(t) ∈ I

.Iff(I

) >f(I

j,s−1

)andf(I

) >f(I

j,s+1

), no directed

variation will be applied. If f(I

j,s−1

) >f(I

j,s+1

), then x

(t)movestoward

subinterval I

j,s−1

with probability 1−

f(I

)

f(I

j,s−1

)

. The move is implemented by replacing

(t) with a random number uniformly distributed between x

(t) and the middle-

point of the interval I

j,s−1

. A similar approach is followed when f(I

j,s−1

) <f(I

) <

f(I

j,s+1

). If f (I

) <f(I

j,s−1

)andf(I

) <f(I

j,s+1

), then x

(t)movestowardany

of its neighboring intervals with equal probability.

For the above, f(I

)=f(I

j,n

)=0.

Two approaches have been proposed to apply directed variation. For the ﬁrst, directed

variation is applied, after selection, to the µ members of the new population. For the

second strategy, each parent produces one oﬀspring using directed variation. Crossover

is then applied as usual to create the remaining λ−µ oﬀspring. The selection operator

is applied to the µ parents, the µ oﬀspring produced by directed variation, and the

λ − µ oﬀspring produced by crossover.

12.5.3 Incremental Evolution Strategies

Incremental ES search for an optimal solution by dividing the search process into n

phases – one phase for each decision variable [597]. Each phase consists of two steps.

The ﬁrst step applies a single variable evolution on the one decision variable, while the

second step applies a multi-variable evolution after the ﬁrst phase. For phase numbers

less than n

, a context vector is needed to evaluate the ﬁtness of the partially evolved

individual (similar to the CCGA and CPSO discussed in Sections 15.3 and 16.5.4).

12.6 Advanced Topics 229

12.5.4 Surrogate Evolution Strategy

Surrogate methods have been developed speciﬁcally for problems where the ﬁtness

function is computationally expensive to evaluate. The ﬁtness function is approx-

imated by a set of basis functions, called surrogates. Evaluation of the surrogate

model is computationally less expensive than the original function. The reader is

referred to [860] for more detail on surrogate models for ES.

12.6 Advanced Topics

This section shows how ES can be used to solve constrained problems (Section 12.6.1),

multi-objective optimization problems (Section 12.6.2), problems with dynamically

changing optima (Section 12.6.3), and to locate multiple optima (Section 12.6.4).

12.6.1 Constraint Handling Approaches

While a number of ES variations have been developed to cope with constraints, this

section discusses only some of these approaches.

Tahk and Sun [830] converted the constrained problem to an unconstrained problem

using the augmented Lagrangian approach given in Section A.6.2. A coevolutionary

approach is used to ﬁnd the saddle point, (x

∗

,λ

∗

,λ

∗

), of the Lagrangian given in equa-

tion (A.27). Two populations are used, each with diﬀerent objectives, both evolved in

parallel. Assuming a minimization problem, the one population minimizes the ﬁtness

function,

f(x)=max

,λ

L(x,λ

,λ

) (12.46)

where L(x ,λ

,λ

) is deﬁned in equation (A.27). The second population maximizes

the ﬁtness function,

f(λ

,λ

)=min

L(x,λ

,λ

) (12.47)

Both populations use an ES as search algorithm.

Kramer et al. [488] developed a biased mutation operator to lead the search to more

promising, feasible areas. The mean of the Gaussian distribution, from which muta-

tional step sizes are sampled, is biased to shift the center of the mutation distribution

as illustrated in Figure 12.3.

Let ξ

(t)=(ξ

(t),...,ξ

(t)) be the bias coeﬃcient vector, with ξ

(0) ∼ U(−1, 1),

for all j =1,...,n

. The bias vector, β

(t), is then deﬁned as β

(t)=σ

(t)ξ

(t).

Mutational step sizes are calculated as

∆x

(t)=σ

(t)N

(0, 1) + β

(t)=N

(ξ

(t),σ

(t)) (12.48)

Bias coeﬃcients are self-adapted using



(t)=ξ

(t)+αN(0, 1) (12.49)

230 12. Evolution Strategies



Figure 12.3 Biased Mutation for Evolution Strategies

with α =0.1 (suggested in [488]).

A very simple approach to handle constraints is to change the selection operator to

select the next population as follows: Until µ individuals have been selected,

• First select the best feasible individuals.

• If all feasible solutions have been selected, select those that violate the fewest

constraints.

• As last resort, when individuals are infeasible, and they violate the same number

of constraints, select the most ﬁt individuals.

When a selection operator is applied to select one of two individuals, the following

rules can be applied:

• If both are feasible, select the one with the best ﬁtness.

• If one is feasible, and the other infeasible, select the feasible solution.

• If both are infeasible, select the one that violates the fewest constraints. If

constraint violation is the same, select the most ﬁt individual.

12.6.2 Multi-Objective Optimization

One of the ﬁrst, simple ES for solving multi-objective (MOO) problems was devel-

oped by Knowles and Corne [469]. The Pareto archived evolution strategy (PAES)

12.6 Advanced Topics 231

consists of three parts: (1) a candidate solution generator, (2) the candidate solution

acceptance function, and (3) the nondominated-solutions archive.

The candidate solution generator is an (1 + 1)-ES, where the individual that survives

to the next generation is based on dominance. If the parent dominates the oﬀspring,

the latter is rejected, and the parent survives. If the oﬀspring dominates the parent,

the oﬀspring survives to the next generation. If neither the parent nor the oﬀspring is

dominating, the oﬀspring is compared with the nondominated solutions in the archive,

as summarized in Algorithm 12.4.

The archive maintains a set of nondominated solutions to the MOO. The size of the

archive is restricted. When an oﬀspring dominates the current solutions in the archive,

it is included in the archive. When the oﬀspring is dominated by any of the solutions

in the archive, the oﬀspring is not included in the archive. When the oﬀspring and

the solutions in the archive are nondominating, the oﬀspring is accepted and included

in the archive based on the degree of crowding in the corresponding area of objective

space.

To keep track of crowding, a grid is deﬁned over objective space, and for each cell of the

grid a counter is maintained to keep track of the number of nondominated solutions

for that part of the Pareto front. When an oﬀspring is accepted into the archive, and

the archive has reached its capacity, the oﬀspring replaces one of the solutions in the

highest populated grid cell (provided that the grid cell corresponding to the oﬀspring

has a lower frequency count). When the parent and its oﬀspring are nondominating,

the one with the lower frequency count is accepted in the archive.

The PAES is summarized in Algorithm 12.3.

Costa and Oliveira [159] developed a diﬀerent approach to ensure that nondominated

solutions survive to next generations, and to produce diverse solutions with respect to

objective space. Fitnesses of individuals are based on a Pareto ranking, where individ-

uals are grouped into a number of Pareto fronts. An individual’s ﬁtness is determined

based on the Pareto front in which the individual resides. At each generation, the

Pareto ranking process proceeds as follows. All of the nondominated solutions from

the λ oﬀspring, or µ + λ parents and oﬀspring, form the ﬁrst Pareto front. These

individuals are then removed, and the nondominating solutions from the remainder of

the individuals form the second Pareto front. This process of forming Pareto fronts

continues until all λ (or µ + λ) individuals are assigned to a Pareto front. Individuals

of the ﬁrst Pareto front is assigned a ﬁtness of 1/n

,wheren

is the niche count. The

niche count is the number of individuals in this front that lies within a distance of

from the individual (distance is measured with respect to objective space). The

threshold, σ

, is referred to as the niche radius. Individuals of the next Pareto

front is assigned a ﬁtness of (1 + f

worst

)/n

,wheref

worst

is the worst ﬁtness from the

previous front. This process of ﬁtness assignment continues until all individuals have

been assigned a ﬁtness.

The ﬁtness sharing approach described above promotes diversity of nondominated

solutions. The process of creating Pareto fronts ensures that dominated individuals are

excluded from future generations as follows: Depending on the ES used, µ individuals

232 12. Evolution Strategies

Algorithm 12.3 Pareto Archived Evolution Strategy

Set generation counter;

Generate a random parent solution;

Evaluate the parent;

Add the parent to the archive;

while stopping condition(s) not true do

Create oﬀspring through mutation;

Evaluate oﬀspring;

if offspring is not dominated by parent then

Compare oﬀspring with solutions in the archive;

Update the archive using Algorithm 12.4;

if offspring dominated parent then

Oﬀspring survives to new generation to become the parent;

end

else

//nondominating case

Select the individual that maps to the grid cell with lowest frequency

count;

end

Algorithm 12.4 Archive Update Algorithm used by PAES

Input: A candidate solution and an archive of nondominated solutions;

Output: An updated archive;

if candidate is dominated by any member of the archive then

Reject the candidate;

end

else

if candidate dominates any s olutions in the archive then

Remove all dominated members from the archive;

Add candidate to the archive;

end

else

if archive is full then

if candidate will increase diversity in the archive then

Remove the solution with the highest frequency from the archive;

end

Add candidate to the archive;

end

12.6 Advanced Topics 233

are selected from λ or µ + λ individuals to form the new population. Individuals are

sorted according to their ﬁtness values in ascending order. If the number of individuals

in the ﬁrst front is greater than µ, the next population is selected from the ﬁrst front

individuals using tournament selection. Otherwise the best µ individuals are selected.

An archive of ﬁxed size is maintained to contain a set of nondominated solutions, or

elite. A speciﬁed number of these solutions are randomly selected and included in the

next population.

At each generation, each Pareto optimal solution of the current population is tested

for inclusion in the archive. The candidate solution is included if

• all solutions in the archive are diﬀerent from the candidate solution, thereby

further promoting diversity,

• none of the solutions in the archive dominates the candidate solution, and

• the distance between the candidate and any of the solutions in the archive is

larger than a deﬁned threshold.

Other ES approaches to solve MOPs can be found in [395, 464, 613, 637].

12.6.3 Dynamic and Noisy Environments

Beyer [61, 62, 63, 64] provided the ﬁrst theoretical analyses of ES. In [61] Beyer made

one of the ﬁrst statements claiming that ES are robust against disturbances of the

search landscape. B¨ack and Hammel [42] provided some of the ﬁrst empirical results

to show that low levels of noise in the objective function do not have an inﬂuence on

performance. Under higher noise levels, they recommended that the (µ, λ)-ES, with

µ>1 be used, due to its ability to maintain diversity. In a more elaborate study,

B¨ack [40] reconﬁrmed these statements and showed that the (µ, λ)-ES was perfectly

capable to track dynamic optima for a number of diﬀerent dynamic environments.

Markon et al. [562] showed that (µ + λ)-ES with threshold-selection is capable of

optimizing noisy functions. With threshold-selection an oﬀspring is selected only if its

performance is better than its parents by a given margin.

Arnold and Beyer [32] provided a study of the performance of ES on noisy functions,

where noise is generated from a Gaussian, Cauchy, or χ

distribution. Beyer [65] and

Arnold [31] showed that rescaled mutations improve the performance of ES on noisy

functions. Under rescaled mutations, mutational step sizes are multiplied by a scaling

factor (which is greater than one) to allow larger step sizes, while preventing that these

large step sizes are inherited by oﬀspring. Instead, the smaller step sizes are inherited.

12.6.4 Niching

In order to locate multiple solutions, Aichholzer et al. [12] developed a multipopulation

ES, referred to as the τ (µ/ρ, κ, λ)-ES, where τ is the number of subpopulations and κ

speciﬁes the number of generations that each individual is allowed to survive. Given τ

234 12. Evolution Strategies

clusters, recombination proceeds as follows: One of the clusters is randomly selected,

and roulette wheel selection is used to select one of the individuals from this cluster

as one of the parents. The second parent is selected from any cluster, but such that

individuals from remote clusters are selected with a low probability. Over time, clusters

tend to form over local minima.

Shir and B¨ack [785] proposed a dynamic niching algorithm for ES that identiﬁes ﬁtness-

peaks using a peak identiﬁcation algorithm. Each ﬁtness-peak will correspond to one

of the niches. For each generation, the dynamic niche ES applies the following steps:

The mutation operator is applied to each individual. After determination of the ﬁtness

of each individual, the dynamic peak identiﬁcation algorithm is applied to identify n

niches. Individuals are assigned to their closest niche, after which recombination is

applied within niche boundaries. If required, niches are populated with randomly

generated individuals.

If n

niches have to be formed, they are created such that their peaks are a distance

of at least

√

from one another, where

r =









j=1

max,j

− x

min,j

)

(12.50)

Peaks are formed from the current individuals of the population, by sequentially con-

sidering each as a ﬁtness peak. If an individual is

√

from already deﬁned ﬁtness

peaks, then that individual is considered as the next peak. This process continues

until n

peaks have been found or until all individuals have been considered.

Recombination considers a uniform distribution of resources. Each peak is allowed

˜µ =

parents, and produces

λ =

oﬀspring in every generation. For each

peak,

λ oﬀspring are created as follows: One of the parents is selected from the

individuals of that niche using tournament selection. The other parent, which should

diﬀer from the ﬁrst parent, is selected as the best individual of that niche. If a niche

contains only one individual, the second parent will be the best individual from another

niche. Intermediate recombination is used for the strategy parameters, and discrete

recombination for the genotypes.

The selection operator selects ˜µ individuals for the next generation by selecting n

the best

λ oﬀspring, along with the best ˜µ − n

parents from that niche. If there are

not enough parents to make up a total of ˜µ individuals, the remainder is ﬁlled up by

generating random individuals.

New niches are generated at each generation. Repeated application of the above

process results in niches, where each niche represents a diﬀerent solution.

Shir and B¨ack [785] expanded the approach above to a (1,λ)-ES with corrrelated

mutations.

12.7 Applications of Evolution Strategies 235

Table 12.1 Applications of Evolution Strategies

Application Class References

Parameter optimization [256, 443, 548, 679]

Controller design [59, 456, 646]

Induction motor design [464]

Neural network training [59, 550]

Transformer design [952]

Computer security [52]

Power systems [204]

12.7 Applications of Evolution Strategies

The ﬁrst application of ES was in experimental optimization as applied to hydrody-

namical problems [708]. Since then most new ES implementations were tested on

functional optimization problems. ES have, however, been applied to a number of

real-world problems, as summarized in Table 12.1 (note that this is not an exhaustive

list of applications).

12.8 Assignments

1. Discuss the diﬀerences and similarities between ES and EP.

2. Can an ES that utilizes strategy parameters be considered a cultural algorithm?

Motivate your answer.

3. Determine if the reward scheme as given in equation (12.20) is applicable to

minimization or maximization tasks. If it is for minimization (maximization)

show how it can be changed for maximization (minimization).

4. Identify problems with the reinforcement learning approach where the reward

is proportional to changes in phenotypic space. Do the same for the approach

where reward is proportional to step sizes in decision (genetic) space.

5. Implement an (1 + λ)-ES to train a FFNN on any problem of your choice, and

compare its performance with an (µ +1)-ES,(µ + λ)-ES, and (µ, λ)-ES.

6. Evaluate the following approaches to initialize deviation strategy parameters:

(a) For all individuals, the same initial value is used for all components of the

genotype, i.e.

(0) = σ(0), ∀i =1,...,n

, ∀j =1,...,n

where σ(0) = α min

j=1,...,n

{|x

max,j

− x

min,j

|} with α =0.9.

(b) The same as above, but α =0.1.

236 12. Evolution Strategies

component of the genotype, i.e.

(0) = σ

(0), ∀j =1,...,n

where σ

(0) ∼ U (0,αmin

j=1,...,n

{|x

max,j

− x

min,j

|})forα =0.9andα =

0.1.

(d) The same as above, but with σ

(0) ∼|N(0,αmin

j=1,...,n

{|x

max,j

−

min,j

|})| for α =0.9andα =0.1.

(e) Each component of each genotype uses a diﬀerent initial value, i.e.

(0) ∼|N(0,α min

j=1,...,n

{|x

max,j

−x

min,j

|})|, ∀i =1,...,n

, ∀j =1,...,n

for α ∼ U(0, 1).

7. Discuss the advantages of using a lifespan within (µ, κ, λ)-ES compared to (µ, λ)-

ES.

8. True or false: (µ + λ)-ES implements a hill-climbing search. Motivate your

answer.

Chapter 13

Diﬀerential Evolution

Diﬀerential evolution (DE) is a stochastic, population-based search strategy developed

by Storn and Price [696, 813] in 1995. While DE shares similarities with other evolu-

tionary algorithms (EA), it diﬀers signiﬁcantly in the sense that distance and direction

information from the current population is used to guide the search process. Further-

more, the original DE strategies were developed to be applied to continuous-valued

landscapes.

This chapter provides an overview of DE, organized as follows: Section 13.1 discusses

the most basic DE strategy and illustrates the method of adaptation. Alternative DE

strategies are described in Sections 13.2 and 13.3. Section 13.4 shows how the original

DE can be applied to discrete-valued and binary-valued landscapes. A number of

advanced topics are covered in Section 13.5, including multi-objective optimization

(MOO), constraint handling, and dynamic environments. Some applications of DE

are summarized in Section 13.6.

13.1 Basic Diﬀerential Evolution

For the EAs covered in the previous chapters, variation from one generation to the next

is achieved by applying crossover and/or mutation operators. If both these operators

are used, crossover is usually applied ﬁrst, after which the generated oﬀspring are

mutated. For these algorithms, mutation step sizes are sampled from some probability

distribution function. DE diﬀers from these evolutionary algorithms in that

• mutation is applied ﬁrst to generate a trial vector, which is then used within the

crossover operator to produce one oﬀspring, and

• mutation step sizes are not sampled from a prior known probability distribution

function.

In DE, mutation step sizes are inﬂuenced by diﬀerences between individuals of the

current population.

Section 13.1.1 discusses the concept of diﬀerence vectors, used to determine muta-

tion step sizes. The mutation, crossover, and selection operators are described in

Sections 13.1.2 to 13.1.4. Section 13.1.5 summarizes the DE algorithm, and control

Computational Intelligence: An Introduction, Second Edition A.P. Engelbrecht

2007 John Wiley & Sons, Ltd

237