Engelbrecht Andries P. Computational Intelligence: An Introduction

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

258 13. Differential Evolution

with the worst global best solution is re-initialized. DynDE re-initializes the one sub-

population when

E(C

x(t), C

x(t)) <

1/n

(13.32)

where E(C

x(t), C

x(t)) is the Euclidean distance between the best individuals of

sub-populations C

and C

, X represents the extent of the search space, n

is the

number of peaks, and n

is the search space dimension. It is this condition that

requires assumption 1, which suﬀers from obvious problems. For example, peaks are

not necessarily evenly distributed. It may also be the case that two peaks exist with a

distance less than

1/n

from one another. Also, it is rarely the case that the number

of peaks is known.

After a change is detected, a strategy is followed to increase diversity. This is done by

assigning a diﬀerent behavior to some of the individuals of the aﬀected sub-population.

The following diversity increasing strategies have been proposed [577]:

• Re-initialize the sub-populations: While this strategy does maximize diversity,

it also leads to a severe loss of knowledge obtained about the search space.

• Use quantum individuals: Some of the individuals are re-initialized to random

points inside a ball centered at the global best individual,

x(t), as outlined in

Algorithm 13.11. In this algorithm, R

max

is the maximum radius from

x(t).

• Use Brownian individuals: Some positions are initialized to random positions

around

x(t), where the random step sizes from

x(t) are sampled from a Gaussian

distribution. That is,

(t)=

x(t)+N(0,σ) (13.33)

• Introduce some form of entropy: Some individuals are simply added noise, sam-

pled from a Gaussian distribution. That is,

(t)=x

(t)+N(0,σ) (13.34)

Algorithm 13.11 Initialization of Quantum Individuals

for each individual, x

(t), to be re-initialized do

Generate a random vector, r

∼ N(0, 1);

Compute the distance of r

from the origin, i.e.

E(r

, 0)=









j=1

(13.35)

Find the radius, R ∼ U(0,R

max

);

(t)=

x(t)+Rr

/E(r

, 0);

end

13.6 Applications 259

13.6 Applications

Diﬀerential evolution has mostly been applied to optimize functions deﬁned over

continuous-valued landscapes [695, 811, 813, 876]. Considering an unconstrained op-

timization problem, such as listed in Section A.5.3, each individual, x

, will be repre-

sented by an n

-dimensional vector where each x

∈ R. For the initial population,

each individual is initialized using

∼ U(x

min,j

max,j

) (13.36)

The ﬁtness function is simply the function to be optimized.

DE has also been applied to train neural networks (NN) (refer to Table 13.1 for

references). In this case an individual represents a complete NN. Each element of an

individual is one of the weights or biases of the NN, and the ﬁtness function is, for

example, the sum-squared error (SSE).

Table 13.1 summarizes a number of real-world applications of DE. Please note that

this is not meant to be a complete list.

Table 13.1 Applications of Diﬀerential Evolution

Application Class Reference

Clustering [640, 667]

Controllers [112, 124, 164, 165, 394, 429, 438, 599]

Filter design [113, 810, 812, 883]

Image analysis [441, 521, 522, 640, 926]

Integer-Programming [390, 499, 500, 528, 530, 817]

Model selection [331, 354, 749]

NN training [1, 122, 550, 551, 598]

Scheduling [528, 531, 699, 748]

System design [36, 493, 496, 848, 839, 885]

13.7 Assignments

1. Show how DE can be used to train a FFNN.

2. Discuss the inﬂuence of diﬀerent values for the population diversity tolerance,



, and the gene diversity tolerance, 

, as used in equations (13.11) and (13.12)

for the hybrid DE.

3. Discuss the merits of the following two statements:

(a) If the probability of recombination is very low, then DE exhibits a high

probability of stagnation.

(b) For a small population size, it is sensible to have a high probability of

recombination.

260 13. Differential Evolution

4. For the DE/rand-to-best/y/z strategies, suggest an approach to balance explo-

ration and exploitation.

5. Discuss the consequences of too large and too small values of the standard devi-

ation, σ, used in Algorithm 13.6.

6. Explain in detail why the method for adding noise to trial vectors as given in

equation (13.15) may result in genetic drift.

7. With reference to the DynDE algorithm in Section 13.5.3, explain the eﬀect of

very small and very large values of the standard deviation, σ.

8. Researchers in DE have suggested that the recombination probability should

be sampled from a Gaussian distribution, N (0, 1), while others have suggested

that N(0.5, 0.15) should be used. Compare these two suggestions and provide a

recommendation as to which approach is best.

9. Investigate the performance of a DE strategy if the scale factor is sampled from

a Cauchy distribution.

Chapter 14

Cultural Algorithms

Standard evolutionary algorithms (as discussed in previous chapters) have been suc-

cessful in solving diverse and complex problems in search and optimization. The search

process used by standard EAs is unbiased, using little or no domain knowledge to guide

the search process. However, the performance of EAs can be improved considerably if

domain knowledge is used to bias the search process. Domain knowledge then serves

as a mechanism to reduce the search space by pruning undesirable parts of the solution

space, and by promoting desirable parts. Cultural evolution (CE) [717], based on the

principles of human social evolution, was developed by Reynolds [716, 717, 724] in the

early 1990s as an approach to bias the search process with prior knowledge about the

domain as well as knowledge gained during the evolutionary process.

Evolutionary computation mimics biological evolution, which is based on the principle

of genetic inheritance. In natural systems, genetic evolution is a slow process. Cultural

evolution, on the other hand, enables societies to adapt to their changing environments

at rates that exceed that of biological evolution.

The rest of this chapter is organized as follows: A compact deﬁnition of culture and

artiﬁcial culture is given in Section 14.1. A general cultural algorithm (CA) framework

is given in Section 14.2, outlining the diﬀerent components of CA implementations.

Section 14.3 describes the belief space component of CAs. A fuzzy CA approach is

described in Section 14.4. Advanced topics, including constrained environments are

covered in Section 14.5. Applications of CAs are summarized in Section 14.6.

14.1 Culture and Artiﬁcial Culture

A number of deﬁnitions of culture can be found, for example

• Culture is a system of symbolically encoded conceptual phenomena that are

socially and historically transmitted within and between social groups [223].

• Culture refers to the cumulative deposit of knowledge, experience, beliefs, val-

ues, attitudes, meanings, hierarchies, religion, notions of time, roles, spatial re-

lations, concepts of the universe, and material objects and possessions acquired

www.tamu.edu/classes/cosc/choudhury/culture.html

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

2007 John Wiley & Sons, Ltd

261

262 14. Cultural Algorithms

by a group of people in the course of generations through individual and group

striving.

• Culture is the sum total of the learned behavior of a group of people that is

generally considered to be the tradition of that people and is transmitted from

generation to generation.

• Culture is a collective programming of the mind that distinguishes the members

of one group or category of people from another.

In terms of evolutionary computation, culture is modeled as the source of data that

inﬂuences the behavior of all individuals within that population. This diﬀers from EP

and ES where the behavioral characteristics of individuals – for the current generation

only – are modeled using phenotypes. Within cultural algorithms, culture stores the

general behavioral traits of the population. Cultural information is then accessible to

all the individuals of a population, and over many generations.

14.2 Basic Cultural Algorithm

A cultural algorithm (CA) is a dual-inheritance system, which maintains two search

spaces: the population space (to represent a genetic component based on Darwinian

principles), and a belief space (to represent a cultural component). It is the latter that

distinguishes CAs from other EAs.

The belief space models the cultural information about the population, while the

population space represents the individuals on a genotypic and/or phenotypic level.

Both the population and belief spaces evolve in parallel, with both inﬂuencing one

another. A communication protocol therefore forms an integral part of a CA. Such a

protocol deﬁnes two communication channels. One for a select group of individuals to

adapt the set of beliefs, and another deﬁning the way that the beliefs inﬂuence all of

the individuals in the population space.

A pseudocode cultural algorithm is given in Algorithm 14.1, and illustrated in Fig-

ure 14.1.

Algorithm 14.1 Cultural Algorithm

Set the generation counter, t =0;

Create and initialize the population space, C(0);

Create and initialize the belief space, B(0);

while stopping condition(s) not true do

Evaluate the ﬁtness of each x

(t) ∈C(t);

Adjust (B(t), Accept (C(t)));

Variate (C(t), Inﬂuence (B(t)));

t = t +1;

Select the new population;

end

14.3 Belief Space 263

Accept Influence population

Fitness evaluation

Variate population

Selection

Adjust beliefs

Figure 14.1 Illustration of Population and Belief Spaces of Cultural Algorithms

At each iteration (each generation), individuals are ﬁrst evaluated using the ﬁtness

function speciﬁed for the EA on the population level. An acceptance function is then

used to determine which individuals from the current population have an inﬂuence

on the current beliefs. The experience of the accepted individuals is then used to

adjust the beliefs (to simulate evolution of culture). The adjusted beliefs are then

used to influence the evolution of the population. The variation operators (crossover

and mutation) use the beliefs to control the changes in individuals. This is usually

achieved through self-adapting control parameters, as functions of the beliefs.

The population space is searched using any of the standard EAs, for example an EP

[720] or GA [716]. Recently, particle swarm optimization (PSO) has been used on

the population space level [219]. The next section discusses the belief space in more

detail.

14.3 Belief Space

The belief space serves as a knowledge repository, where the collective behaviors (or

beliefs) of the individuals in the population space are stored. The belief space is also

referred to as the meme pool,whereameme is a unit of information transmitted by

behavioral means. The belief space serves as a global knowledge repository of behav-

ioral traits. The memes within the belief space are generalizations of the experience

of individuals within the population space. These experiential generalizations are ac-

cumulated and shaped over several generations, and not just one generation. These

generalizations express the beliefs as to what the optimal behavior of individuals con-

stitutes.

264 14. Cultural Algorithms

The belief space can eﬀectively be used to prune the population space. Each individual

represents a point in the population search space: the knowledge within the belief

space is used to move individuals away from undesirable areas in the population space

towards more promising areas.

Some form of communication protocol is implemented to transfer information between

the two search spaces. The communication protocol speciﬁes operations that control

the inﬂuence individuals have on the structure of the belief space, as well as the

inﬂuence that the belief space has on the evolution process in the population level.

This allows individuals to dictate their culture, causing culture to also evolve. On

the other hand, the cultural information is used to direct the evolution on population

level towards promising areas in the search space. It has been shown that the use of

a belief space reduces computational eﬀort substantially [717, 725].

Various CAs have been developed, which diﬀer in the data structures used to model

the belief space, the EA used on the population level, and the implementation of the

communication protocol. Section 14.3.1 provides an overview of diﬀerent knowledge

components within the belief space. Acceptance and inﬂuence functions are discussed

in Sections 14.3.2 and 14.3.4 respectively.

14.3.1 Knowledge Components

The belief space contains a number of knowledge components to represent the be-

havioral patterns of individuals from the population space. The types of knowledge

components and data structures used to represent the knowledge depends on the prob-

lem being solved. The ﬁrst application of CAs used version spaces represented as a

lattice to store schemata [716]. For function optimization, vector representations are

used (discussed below) [720]. Other representations that have been used include fuzzy

systems [719, 725], ensemble structures [722], and hierarchical belief spaces [420].

In general, the belief space contains at least two knowledge components [720]:

• A situational knowledge component, which keeps track of the best solutions

found at each generation.

• A normative knowledge component, which provides standards for individual

behaviors, used as guidelines for mutational adjustments to individuals. In the

case of function optimization, the normative knowledge component maintains

a set of intervals, one for each dimension of the problem being solved. These

intervals characterize the range of what is believed to be good areas to search in

each dimension.

If only these two components are used, the belief space is represented as the tuple,

B(t)=(S(t), N(t)) (14.1)

where S(t) represents the situational knowledge component, and N(t)representsthe

normative knowledge component. The situational component is the set of best solu-

tions,

S(t)={

(t):l =1,...,n

} (14.2)

14.3 Belief Space 265

and the normative component is represented as

N(t)=(X

(t), X

(t),...,X

(t)) (14.3)

where, for each dimension, the following information is stored:

(t)=(I

(t),L

(t),U

(t)) (14.4)

denotes the closed interval, I

(t)=[x

min,j

(t),x

max,j

(t)] = {x : x

min,j

≤ x ≤

max,j

}, L

(t) is the score for the lower bound, and U

(t) is the score for the upper

bound.

In addition to the above knowledge components, the following knowledge components

can be added [672, 752]:

• A domain knowledge component, which is similar to the situational knowledge

component in that it stores the best positions found. The domain knowledge

component diﬀers from the situational knowledge component in that knowledge

is not re-initialized at each generation, but contains an archive of best solutions

since evolution started – very similar to the hall-of-fame used in coevolution.

• A history knowledge component, used in problems where search landscapes

may change. This component maintains information about sequences of envi-

ronmental changes. For each environmental change, the following information is

stored: the current best solution, the directional change for each dimension and

the current change distance.

• A topographical knowledge component, which maintains a multi-dimensional

grid representation of the search space. Information is kept about each cell of

the grid, e.g. frequency of individuals that occupy the cell. Such frequency

information can be used to improve exploration by forcing mutation direction

towards unexplored areas.

The type of knowledge components and the way that knowledge is represented have

an inﬂuence on the acceptance and inﬂuence functions, as discussed in the following

sections.

14.3.2 Acceptance Functions

The acceptance function determines which individuals from the current population will

be used to shape the beliefs for the entire population. Static methods use absolute

ranking, based on ﬁtness values, to select the top n% individuals. Any of the selection

methods for EAs (refer to Section 8.5) can be used, for example elitism, tournament

selection, or roulette-wheel selection, provided that the number of individuals remains

the same.

Dynamic methods do not have a ﬁxed number of individuals that adjust the belief

space. Instead, the number of individuals may change from generation to generation.

Relative ranking, for example, selects individuals with above average (or median)

266 14. Cultural Algorithms

performance [128]. Alternatively, the number of individuals is determined as

(t)=

 (14.5)

with γ ∈ [0, 1]. Using this approach, the number of individuals used to adjust the

belief space is initially large, with the number decreasing exponentially over time.

Other simulated-annealing based schedules can be used instead.

Adaptive methods use information about the search space and process to self-adjust

the number of individuals to be selected. Reynolds and Chung [719] proposed a fuzzy

acceptance function to determine the number of individuals based on generation num-

ber and individual success ratio. Membership functions are deﬁned to implement the

rules given in Algorithm 14.2.

14.3.3 Adjusting the Belief Space

For the purpose of this section, it is assumed that the belief space maintains a situ-

ational and normative knowledge component, and that a continuous, unconstrained

function is minimized.

With the number of accepted individuals, n

(t), known, the two knowledge compo-

nents can be updated as follows [720]:

• Situational knowledge: Assuming that only one element is kept in the situa-

tional knowledge component,

S(t +1)={

y(t +1)} (14.6)

where

y(t +1)=



min

l=1,...,n

(t)

(t)} if f (min

l=1,...,n

(t)

(t)}) <f(

y(t))

y(t)otherwise

(14.7)

• Normative knowledge: In adjusting the normative knowledge component, a

conservative approach is followed when narrowing intervals, thereby delaying

too early exploration. Widening of intervals is applied more progressively. The

interval update rule is as follows:

min,j

(t +1)=



(t)ifx

(t) ≤ x

min,j

(t)orf(x

(t)) <L

(t)

min,j

(t)otherwise

(14.8)

max,j

(t +1)=



(t)ifx

(t) ≥ x

max,j

(t)orf(x

(t)) <U

(t)

max,j

(t)otherwise

(14.9)

(t +1)=



f(x

(t)) if x

(t) ≤ x

min,j

(t)orf (x

(t)) <L

(t)

(t)otherwise

(14.10)

14.3 Belief Space 267

Algorithm 14.2 Fuzzy Rule-base for Cultural Algorithm Acceptance Function

if the current generation is early in the search then

if the success ratio is low then

Accept a medium number of individuals (30%);

end

if the success ratio is medium then

Accept a medium number of individuals;

end

if the success ratio is high then

Accept a larger number of individuals (40%);

end

if the current generation is in the middle stages of the search then

if the success ratio is low then

Accept a smaller number of individuals (20%);

end

if the success ratio is medium then

Accept a medium number of individuals;

end

if the success ratio is high then

Accept a medium number of individuals;

end

if the current generation is near the end of the search then

if the success ratio is low then

Accept a smaller number of individuals;

end

if the success ratio is medium then

Accept a smaller number of individuals;

end

if the success ratio is high then

Accept a medium number of individuals;

end

(t +1)=



f(x

(t)) if x

(t) ≥ x

max,j

(t)orf (x

(t)) <U

(t)

(t)otherwise

(14.11)

for each x

(t),l=1,...,n

(t).

14.3.4 Inﬂuence Functions

Beliefs are used to adjust individuals in the population space to conform closer to the

global beliefs. The adjustments are realized via inﬂuence functions. To illustrate this