Engelbrecht Andries P. Computational Intelligence: An Introduction

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

188 11. Evolutionary Programming

real-valued vector representations, with application to the optimization of continuous

functions.

As summarized in Algorithm 11.1, EP utilizes four main components of EAs:

• Initialization: As with other EC paradigms, a population of individuals is

initialized to uniformly cover the domain of the optimization problem.

• Mutation: The mutation operator’s main objective is to introduce variation in

the population, i.e. to produce new candidate solutions. Each parent produces

one or more oﬀspring through application of the mutation operator. A number

of EP mutation operators have been developed, as discussed in Section 11.2.1.

• Evaluation: A ﬁtness function is used to quantify the “behavioral error” of

individuals. While the ﬁtness function provides an absolute ﬁtness measure to

indicate how well the individual solves the problem being optimized, survival in

EP is usually based on a relative ﬁtness measure (refer to Chapter 15). A score is

computed to quantify how well an individual compares with a randomly selected

group of competing individuals. Individuals that survive to the next generation

are selected based on this relative ﬁtness. The search process in EP is therefore

driven by a relative ﬁtness measure, and not an absolute ﬁtness measure as is

the case with most EAs.

• Selection: The main purpose of the selection operator is to select those indi-

viduals that survive to the next generation. Selection is a competitive process

where parents and their oﬀspring compete to survive, based on their performance

against a group of competitors. Diﬀerent selection strategies are discussed in

Section 11.2.2.

Mutation and selection operators are applied iteratively until a stopping condition is

satisﬁed. Any of the stopping conditions given in Section 8.7 can be used.

Algorithm 11.1 Basic Evolutionary Programming Algorithm

Set the generation counter, t =0;

Initialize the strategy parameters;

Create and initialize the population, C(0), of n

individuals;

for each individual, x

(t) ∈C(t) do

Evaluate the ﬁtness, f(x

(t));

end

while stopping condition(s) not true do

for each individual, x

(t) ∈C(t) do

Create an oﬀspring, x



(t), by applying the mutation operator;

Evaluate the ﬁtness, f(x



(t));

Add x



(t)tothesetofoﬀspring,C



(t);

end

Select the new population, C(t +1),fromC(t) ∪C



(t), by applying a selection

operator;

t = t +1;

end

11.2 Evolutionary Programming Operators 189

In comparison with GAs and GP, there are a few diﬀerences between these EAs and

EP, some of which have already been discussed:

• EP emphasizes phenotypic evolution, instead of genotypic evolution. The focus

is on behaviors.

• Due to the above, EP does not make use of any recombination operator. There

is no exchange of genetic material.

• EP uses a relative ﬁtness function to quantify performance with respect to a

randomly chosen group of individuals.

• Selection is based on competition. Those individuals that perform best against

a group of competitors have a higher probability of being included in the next

generation.

• Parents and oﬀspring compete for survival.

• The behavior of individuals is inﬂuenced by strategy parameters, which de-

termine the amount of variation between parents and oﬀspring. Section 11.3

discusses strategy parameters in more detail.

11.2 Evolutionary Programming Operators

The search process of an EP algorithm is driven by two main evolutionary opera-

tors, namely mutation and selection. Diﬀerent implementations of these operators are

discussed in Sections 11.2.1 and 11.2.2 respectively.

11.2.1 Mutation Operators

As mutation is the only means of introducing variation in an EP population, it is

very important that the design of a mutation operator considers the exploration–

exploitation trade-oﬀ. The variation process should facilitate exploration in the early

stages of the search to ensure that as much of the search space is covered as possible.

After an initial exploration phase, individuals should be allowed to exploit obtained

information about the search space to ﬁne tune solutions. A number of mutation

operators have been developed, which addressses this trade-oﬀ to varying degrees.

For this discussion, assume that the task is to minimize a continuous, unconstrained

function, f : R

→ R.Ifx

(t) denotes a candidate solution (as represented by the

i-th individual) at generation t, then each x

(t) ∈ R,j =1,...,n

In general, mutation is deﬁned as



(t)=x

(t)+∆x

(t) (11.1)

where x



(t) is the oﬀspring created from parent x

(t) by adding a step size ∆x

(t)to

the parent. The step size is noise sampled from some probability distribution, where

190 11. Evolutionary Programming

the deviation of the noise is determined by a strategy parameter, σ

. Generally, the

step size is calculated as

∆x

(t)=Φ(σ

(t))η

(t) (11.2)

where Φ : R → R is a function that scales the contribution of the noise, η

(t).

Based on the characteristics of the scaling function, Φ, EP algorithms can be grouped

into three main categories of algorithms:

• non-adaptive EP, in which case Φ(σ)=σ. In other words, the deviations in

step sizes remain static.

• dynamic EP, where the deviations in step sizes change over time using some

deterministic function, Φ, usually a function of the ﬁtness of individuals.

• self-adaptive EP, in which case deviations in step sizes change dynamically.

The best values for σ

are learned in parallel with the decision variables, x

Since the deviations, σ

, have an inﬂuence on the behavior of individuals in the case

of dynamic and self-adaptive EP, these deviations are referred to as strategy parame-

ters. Each individual has its own strategy parameters, in which case an individual is

represented as the tuple,

(t)=(x

(t),σ

(t)) (11.3)

While deviations are the most popular choice for strategy parameters, Fogel [265, 266],

extended EP to use correlation coeﬃcients between components of the individual as

strategy parameters, similar to their use in evolution strategies (refer to Chapter 12).

Strategy parameters are discussed in more detail in Section 11.3.

As is the case with all EAs, EP follows a stochastic search process. Stochasticity is

introduced by computing step sizes as a function of noise, η

, sampled from some

probability distribution. The following distributions have been used for EP:

• Uniform: Noise is sampled from a uniform distribution [580]

(t) ∼ U(x

min,j

max,j

) (11.4)

where x

min

and x

max

provide lower and upper bounds for the values of η

.It

is important to note that

E[η

] = 0 (11.5)

to prevent any bias induced by the noise. Here E[•] denotes the expectation

operator.

Wong and Yuryevich [916] proposed a uniform mutation operator where

∆x

(t)=U(0, 1)(ˆy

(t) − x

(t)) (11.6)

with

y(t) the best individual from the current population, C(t). This mutation

operator directs all individuals to make random movements towards the best

individual (very similar to the social component used in particle swarm opti-

mization; refer to Chapter 16). Note that the best individual does not change.

11.2 Evolutionary Programming Operators 191

• Gaussian: For the Gaussian mutation operators, noise is sampled from a

zero-mean, normal distribution [266, 265]:

(t) ∼ N (0,σ

(t)) (11.7)

For completeness sake, and comparison with other distributions, the Gaussian

density function is given as (assuming a zero mean)

(x)=

√

2π

−x

/(2σ

)

(11.8)

where σ is the deviation of the distribution.

• Cauchy: For the Cauchy mutation operators [934, 932, 936],

(t) ∼ C(0,ν) (11.9)

where ν is the scale parameter.

The Cauchy density function centered at the origin is deﬁned by

(x)=

ν + x

(11.10)

for ν>0. The corresponding distribution function is

(x)=

arctan(

) (11.11)

The Cauchy distribution has wider tails than the Gaussian distribution, and

therefore produces more, larger mutations than the Gaussian distribution.

• L

evy: For the L´evy distribution [505],

(t) ∼ L(ν) (11.12)

The L´evy probability function, centered around the origin, is given as

L,ν,γ

(x)=



∞

−γq

cos(qx)dq (11.13)

where γ>0 is the scaling factor, and 0 <ν<2 controls the shape of the

distribution. If ν = 1, the Cauchy distribution is obtained, and if ν =2,the

Gaussian distribution is obtained.

For |x| >> 1, the L´evy density function can be approximated by

(x) ∝ x

−(ν+1)

(11.14)

An algorithm for generating L´evy random numbers is given in [505].

• Exponential: In this case [621],

(t) ∼ E(0,ξ) (11.15)

192 11. Evolutionary Programming

The density function of the double exponential probability distribution is given

E,ξ

(x)=

−ξ|x|

(11.16)

where ξ>0 controls the variance (which is equal to

). Random numbers can

be calculated as follows:

x =



ln(2y)ify ≤ 0.5

−

ln(2(1 − y)) if y>0.5

(11.17)

where y ∼ U(0, 1). It can be noted that E(0,ξ)=

E(0, 1).

• Chaos: A chaotic distribution is used to sample noise [417]:

(t) ∼ R(0, 1) (11.18)

where R(0, 1) represents a chaotic sequence within the space (−1, 1). The chaotic

sequence can be generated using

t+1

=sin(2/x

,t=0, 1 ... (11.19)

• Combined distributions: Chellapilla [118] proposed the mean mutation op-

erator (MMO), which uses a linear combination of Gaussian and Cauchy distri-

butions. In this case,

(t)=η

N,ij

(t)+η

C,ij

(t) (11.20)

where

N,ij

∼ N(0, 1) (11.21)

C,ij

∼ C(0, 1) (11.22)

The resulting distribution generates more very small and large mutations com-

pared to the Gaussian distribution. It generates more very small and small

mutations compared to the Cauchy distribution. Generally, this convoluted dis-

tribution produces larger mutations than the Gaussian distribution, and smaller

mutations than the Cauchy distribution.

Chellapilla also proposed an adaptive MMO, where

∆x

(t)=γ

(t)(C

(0, 1) + ν

(t)N

(0, 1)) (11.23)

where γ

(t)=σ

2,ij

(t) is an overall scaling parameter, and ν

= σ

1,ij

/σ

2,ij

determines the shape of the probability distribution function; σ

1,ij

and σ

2,ij

are

deviation strategy parameters. For low values of ν

, the Cauchy distribution is

approximated, while large values of ν

resemble the Gaussian distribution.

The question now is how these distributions address the exploration–exploitation

trade-oﬀ. Recall that a balance of small and large mutations is needed. The Cauchy

distribution, due to its wider tail, creates more, and larger mutations than the Gaus-

sian distribution. The Cauchy distribution therefore facilitates better exploration

than the Gaussian distribution. The L´evy distribution have tails in-between that of

11.2 Evolutionary Programming Operators 193

the Gaussian and Cauchy distributions, and therefore also provides better exploration

than for the Gaussian distribution. While the Cauchy distribution does result in larger

mutations, care should be taken in applying Cauchy mutations. As pointed out by

Yao et al. [936], the smaller peak of the Cauchy distribution implies less time for

exploitation. The Cauchy mutation operators therefore are weaker than the Gaussian

operators in ﬁne-tuning solutions. Yao et al. [932, 936] also show that the large mu-

tations caused by Cauchy operators are beneﬁcial only when candidate solutions are

far from the optimum. It is due to these advantages and disadvantages that the L´evy

distribution and convolutions such as those given in equations (11.20) and (11.23) oﬀer

good alternatives for balancing exploration and exploitation.

Another factor that plays an important role in balancing exploration and exploita-

tion is the way in which strategy parameters are calculated and managed, since step

sizes are directly inﬂuenced by these parameters. The next section discusses strategy

parameters in more detail.

11.2.2 Selection Operators

Selection operators are applied in EP to select those individuals that will survive to

the next generation. In the original EP, and most variations of it, the new population

is selected from all the parents and their oﬀspring. That is, parents and oﬀspring

compete to survive. Diﬀering from other EAs, competition is based on a relative

ﬁtness measure and not an absolute ﬁtness measure. An absolute ﬁtness measure

refers to the actual ﬁtness function that quantiﬁes how optimal a candidate solution

is. On the other hand, the relative ﬁtness measure expresses how well an individual

performs compared to a group of randomly selected competitors (selected from the

parents and oﬀspring).

As suggested by Fogel [275], this is possibly the ﬁrst hint towards coevolutionary

optimization. For more detail on coevolution and relative ﬁtness measures, refer to

Chapter 15. This section only points out those methods that have been applied to EP.

For the purposes of this section, notation is changed to correspond with that of EP

literature. In this light, µ is used to indicate the number of parent individuals (i.e.

population size, n

), and λ is used to indicate the number of oﬀspring.

The ﬁrst step in the selection process is to calculate a score, or relative ﬁtness, for each

parent, x

(t), and oﬀspring, x



(t). Deﬁne P(t)=C(t) ∪C



(t) to be the competition

pool, and let u

(t) ∈P(t),i =1,...,µ+ λ denote an individual in the competition

pool. Then, for each u

(t) ∈P(t) a group of n

competitors is randomly selected from

the remainder of individuals (i.e. from P(t)\{u

(t)}). A score is calculated for each

(t) as follows

(t)=



l=1

(t) (11.24)

194 11. Evolutionary Programming

where (assuming minimization)

(t)=



1iff(u

(t)) <f(u

(t))

0otherwise

(11.25)

Wong and Yuryevich [916], and Ma and Lai [542] proposed an alternative scoring

strategy where

(t)=

1ifr

f(u

(t))

f(u

(t))+f(u

(t))

0otherwise

(11.26)

where the n

opponents are selected as l = 2µr

+1,withr

∼ U(0, 1).

In this case, if f(u

(t)) << f(u

(t)), in which case the ﬁtness of u

is signiﬁcantly

better than that of u

,thenu

will have a high probability of being assigned a winning

score of 1. This approach is less strict than the requirement that f(u

(t)) <f(u

(t)),

somewhat reducing the eﬀects of selection pressure.

Based on the score assigned to each individual, u

(t), any of a number of selection

methods can be used (as summarized in Section 8.5):

• Elitism: the best µ individuals from P(t) are selected to form the new popu-

lation, C(t +1).

• Tournament selection: The best µ individuals are stochastically selected using

tournament selection.

• Proportional selection: Each individual is assigned a probability of being

selected:

(t)) =

(t)



2µ

l=1

(t)

(11.27)

Roulette-wheel selection can then be used to select the µ individuals for the next

generation.

• Nonlinear ranking selection [933]: Individuals are sorted in ascending order

of score and then ranked. Then,

(2µ−i)

(t)



2µ

l=1

(11.28)

Instead of using a stochastic selection, ranking can be used to ﬁnd the µ elite

individuals to form the new population.

Diﬀerent methods have also been proposed to decide which of the parent or its oﬀspring

will survive to the next generation. Wei et al. [894] proposed that each parent pro-

duces more than one oﬀspring, where the number of oﬀspring produced is determined

by the ﬁtness of the individual. The more ﬁt the parent is, the more oﬀspring are

generated. The best oﬀspring generated from a parent is selected (based on absolute

ﬁtness measure), and competes with the parent for survival. Competition between

the parent and oﬀspring is based on simulated annealing [894]. The oﬀspring, x



(t),

survives to the next generation if f(x



(t)) <f(x

(t)) or if

(−(f(x



(t))−f(x

(t)))/τ(t))

>U(0, 1) (11.29)

11.3 Strategy Parameters 195

where τ is the temperature coeﬃcient, with τ(t)=γτ(t −1), 0 <γ<1; otherwise the

parent survives.

The above metropolis selection has the advantage that the oﬀspring has a chance of

surviving even if it has a worse ﬁtness than the parent, which reduces selection pressure

and improves exploration.

11.3 Strategy Parameters

As hinted in equation (11.2), step sizes are dependent on strategy parameters, which

form an integral part of EP mutation operators. Although Section 11.2.1 indicated

that a strategy parameter is associated with each component of an individual, it is

totally possible to use one strategy parameter per individual. However, the latter

approach limits the degrees of freedom in addressing the exploration – exploitation

trade-oﬀ. For the purposes of this section, it is assumed that each component has

its own strategy parameter, and that individuals are represented as given in equation

(11.3).

11.3.1 Static Strategy Parameters

The simplest approach to handling strategy parameters is to ﬁx the values of devia-

tions. In this case, the strategy parameter function is linear, i.e.

Φ(σ

(t)) = σ

(t)=σ

(11.30)

where σ

is a small value. Oﬀspring are then calculated as (assuming a Gaussian

distribution)



(t)=x

(t)+N

(0,σ

) (11.31)

with ∆x

(t)=N

(0,σ

). The notation N

(•, •) indicates that a new random value

is sampled for each component of each individual.

A disadvantage of this approach is that a too small value for σ

limits exploration

and slows down convergence. On the other hand, a too large value for σ

limits

exploitation and the ability to ﬁne-tune a solution.

11.3.2 Dynamic Strategies

One of the ﬁrst approaches to change the values of strategy parameters over time, was

to set them to the ﬁtness of the individual [271, 265]:

(t)=σ

(t)=γf(x

(t)) (11.32)

in which case oﬀspring is generated using



(t)=x

(t)+N(0,σ

(t))

= x

(t)+σ

(t)N(0, 1) (11.33)

196 11. Evolutionary Programming

In the above, γ ∈ (0, 1].

If knowledge of the global optimum exists, the error of an individual can be used

instead of absolute ﬁtness. However, such information is usually not available. Alter-

natively, the phenotypic distance from the best individual can be used as follows:

(t)=σ

(t)=|f(

y) − f(x

)| (11.34)

where

y is the most ﬁt individual. Distance in decision space can also be used [827]:

(t)=σ

(t)=E(

y, x

) (11.35)

where E(•, •) gives the Euclidean distance between the two vectors.

The advantage of this approach is that the weaker an individual is, the more that

individual will be mutated. The oﬀspring then moves far from its weak parent. On

the other hand, the stronger an individual is, the less the oﬀspring will be removed

from its parent, allowing the current good solution to be reﬁned. This approach does

have some disadvantages:

• If ﬁtness values are very large, step sizes may be too large, causing individuals

to overshoot a good minimum.

• The problem is even worse if the function value of the optimum is a large, non-

zero value. If the ﬁtness values of good individuals are large, large step sizes

result, causing individuals to move away from good solutions. In such cases,

if knowledge of the optimum is available, using an error measure will be more

appropriate.

A number of proposals have been made to control step sizes as a function of ﬁtness.

A non-extensive list of these methods is given below (unless otherwise stated, these

methods assume a minimization problem):

• Fogel [266] proposed an additive approach, where



(t)=x

(t)+



(t)f(x

)+γ

+ N

(0, 1) (11.36)

where β

and γ

are respectively the proportionality constant and oﬀset pa-

rameter.

• For the function f(x

)=x

+ x

,B¨ack and Schwefel [45] proposed that

(t)=σ

(t)=

1.224

f(x

(t))

(11.37)

where n

is the dimension of the problem (in this case, n

=2).

• For training recurrent neural networks, Angeline et al. [28] proposed that



(t)=x

(t)+βσ

(t)N

(0, 1) (11.38)

where β is the proportionality constant, and

(t)=U(0, 1)

1 −

f(x

(t))

max

(t)

(

(11.39)

11.3 Strategy Parameters 197

with f

max

(t) the maximum ﬁtness of the current population. Take note that the

objective here is to maximize f,andthatf(x

(t)) returns a positive value. If

f(x

(t)) is a small value, then σ

(t) will be large (bounded above by 1), which

results in large mutations. Deviations are scaled by a uniform number in the

range [0, 1] to ensure a mix of small and large step sizes.

• Ma and Lai [542] proposed that deviations be proportional to normalized ﬁtness

values:



(t)=x

(t)+β

(t)N

(0, 1) (11.40)

where β

is the proportionality constant, and deviations are calculated as

(t)=

f(x

(t))



l=1

f(x

(t))

(11.41)

with n

the size of the population. This approach assumes f is minimized.

• Yuryevich and Wong [943] proposed that

(t)=(x

max,j

− x

min,j

)



max

(t) − f(x

(t))

max

(t)

+ γ



(11.42)

to combine both boundary information and ﬁtness information. In the above

min

and x

max

specify the bounds in decision space, and γ>0isanoﬀset

parameter to ensure non-zero deviations. Usually, γ is a small value.

This approach assumes that f is maximized. The inclusion of boundary con-

straints forces large mutations for components with a large domain, and small

mutations if the domain is small.

• Swain and Morris [827] set deviations proportional to the distance from the best

individual, i.e.

(t)=β

|ˆy

(t) − x

(t)| + γ (11.43)

where γ>0, and the proportionality constant is calculated as

= β

E(x

min

, x

max

)

(11.44)

with β ∈ [0, 2], and E(x

min

, x

max

) gives the width of the search space as the

Euclidean distance between the vectors x

min

and x

max

. The parameter, γ,

deﬁnes a search neighborhood. Larger values of γ promote exploration, while

smaller values promote exploitation. A good idea is to adapt γ over time, starting

with large values that are decreased over time.

Oﬀspring are generated using



(t)=x

(t) − dir(x

)σ

(t)N

(0, 1) (11.45)

where the direction of the update is

dir(x

)=sign(ˆy

− x

) (11.46)