Engelbrecht Andries P. Computational Intelligence: An Introduction

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

268 14. Cultural Algorithms

process, assume that an EP is used as the search algorithm in the population space.

The resulting algorithm is referred to as a CAEP.

The belief space is used to determine the mutational step sizes, and the direction

of changes (i.e. whether step sizes are added or subtracted). Reynolds and Chung

[720] proposed four ways in which the knowledge components can be used within the

inﬂuence function:

• Only the normative component is used to determine step sizes during oﬀspring

generation:



(t)=x

(t) + size(I

(t))N

(0, 1) (14.12)

where

size(I

(t)) = x

max,j

(t) − x

min,j

(t) (14.13)

is the size of the belief interval for component j.

• Only the situational component is used for determining change direction:



(t)=







(t)+|σ

(t)N

(0, 1)| if x

(t) < ˆy

(t) ∈S(t)

(t) −|σ

(t)N

(0, 1)| if x

(t) > ˆy

(t) ∈S(t)

(t)+σ

(t)N

(0, 1) otherwise

(14.14)

where σ

is the strategy parameter associated with component j of individual

• The normative component is used to determine change directions, and the situ-

ational component is used to determine step sizes. Equation (14.14) is used, but

with

(t) = size(I(t)) (14.15)

• The normative component is used for both the search directions and step sizes:

(t)=







(t)+|size(I

(t))N

(0, 1)| if x

(t) <x

min,j

(t)

(t) −|size(I

(t))N

(0, 1)| if x

(t) >x

max,j

(t)

(t)+βsize(I

(t))N

(0, 1) otherwise

(14.16)

where β>0 is a scaling coeﬃcient.

14.4 Fuzzy Cultural Algorithm

Section 14.3.2 discussed a fuzzy acceptance function, which initially allows many in-

dividuals to adjust the belief space, and less individuals as the generation number

increases. This section discusses a completely fuzzy CA approach, where an alter-

native fuzzy acceptance function is used and both belief space and population space

adaptations are based on fuzzy logic. This fuzzy CA was shown to improve accuracy

and convergence speed [725].

14.4 Fuzzy Cultural Algorithm 269

14.4.1 Fuzzy Acceptance Function

Reynolds and Zhu [725] proposed an acceptance function that selects few individuals

in the early steps of the search, but more as the generation number increases. The

motivation for this approach stems from the fact that the initial population usually

has only a few ﬁt individuals that can sensibly contribute to the belief space.

As the ﬁrst step, a fuzzy similarity matrix (or fuzzy equivalence relation), R,iscon-

structed for the population space where

=1−

|f(x

) − f(x



l=1

|f(x

(14.17)

for i, j =1,...,n

,withn

the size of the population, and R =[r

]. Before calculation

of R, the individuals are sorted from best to worst according to ﬁtness. The equivalence

relation is then used to calculate the α-cuts matrix (refer to Section 20.4), R

follows:



1ifr

>α(t)

0ifr

≤ α(t)

(14.18)

where α(t) is referred to as the reﬁnement value, and R

=[α

]fori, j =1,...,n

A value of α

= 1 indicates an elite individual that will be used to update the belief

space, while a value of α

= 0 indicates a non-elite individual. Because elements are

sorted according to ﬁtness, the elite elements will occupy the ﬁrst elements of R

The reﬁnement value is initialized to a large value, but bounded by the interval [0, 1],

which will ensure a small number of elite individuals. After each generation, the value

of α is changed according to

α(t +1)=



if t ≥ 

1 − γ

(t − )/n

if t ∈ [0,)

(14.19)

where γ

and γ

are positive constants (suggested to be γ

=0.2andγ

=2.66 [725]),

and  is set such that /t

max

=0.3.

14.4.2 Fuzziﬁed Belief Space

Only two knowledge components are considered. The situational component is crisp

and stores the best individual. The normative component is fuzziﬁed.

The fuzzy interval update rule occurs in the following steps for each x

(t),l =

1,...,n

(t):

1. Initialization: Upper and lower bounds are initialized to the domain, as follows:

min,lj

(0) = x

min,j

(14.20)

max,lj

(0) = x

max,j

(14.21)

where x

minj

and x

max,j

are the domain bounds for component j.

270 14. Cultural Algorithms

2. Calculate the center of the interval for each individual as

(t)=

min,lj

(t)+x

max,lj

(t)) (14.22)

Interval bounds are adjusted until x

min,lj

(t),x

max,lj

(t) ∈ [0.9c

(t), 1.1c

(t)].

3. Compute the fuzzy membership functions, f

)andf

) for each individual

for the lower and upper bounds respectively:

1+x

(14.23)

1+x

(14.24)

for α ≥ 0.

4. Update the lower boundary of each component of individual l:

min,lj

(t +1)=











min,lj

(t)+µ(x

(t))(x

(t) − x

min,lj

(t))

if x

min,lj

(t) ≤ x

(t) < 0.9c

(t)

min,lj

(t)

if 0.9c

(t) ≤ x

(t) < 1.1c

(t)

(14.25)

where µ(x

(t)) = f

(t)).

5. Update the upper boundary of each component of individual l:

max,lj

(t +1)=











max,lj

(t)+µ(x

(t))(x

(t) − x

max,lj

(t))

if 1.1c

(t) <x

(t) ≤ x

max,lj

(t)

max,lj

(t)

if 0.9c

(t) ≤ x

(t) ≤ 1.1c

(t)

(14.26)

where µ(x

(t)) = f

(t)).

14.4.3 Fuzzy Inﬂuence Function

The fuzziﬁed normative knowledge is used to determine both the step size and the

direction of change. Mutational step sizes are based on the age, a

(t), of individuals

as deﬁned in equation (11.68). For each generation that a parent performs better than

its oﬀspring, the parent’s age is incremented. When the oﬀpsring replaces the parent,

the corresponding age is set to 1. The inﬂuence function will eﬀect larger mutations to

individuals with a lower age value, as such individuals are still in a strong exploration

phase. Assuming an EP for the population space, oﬀspring are generated as follows

for each parent, x

(t):



(t)=







(t)+σ

(t)|size(I

(t))N

(0, 1)| if x

(t) <x

min,ij

(t)

(t) − σ

(t)|size(I

(t))N

(0, 1)| if x

(t) >x

max,ij

(t)

(t)+σ

(t)size(I

(t))N

(0, 1) otherwise

(14.27)

where σ

(t) is computed as

(t)=µ(a

(t)) =



1 −

(t)

if a

(t) <α

0ifa

(t) ≥ α

(14.28)

14.5 Advanced Topics 271

where α is a positive constant. If a parent performs better than its oﬀspring for more

than α generations, then that individual will not be mutated.

14.5 Advanced Topics

This section discusses speciﬁc CA implementations for solving constrained optimiza-

tion problems (Section 14.5.1), multi-objective optimization problems (Section 14.5.2),

and dynamic environments (Section 14.5.3).

14.5.1 Constraint Handling

Reynolds and Peng [721], and Dos Santos Coelho and Mariani [219] used a penalty

approach (refer to Section A.6.2) to solve constrained problems. The approach fol-

lowed by Reynolds [721] is to simply set the ﬁtness of any individual that violates a

constraint, to an infeasible value. These penalty methods do not make use of the belief

space to guide individuals to move towards feasible space. Chung and Reynolds [128]

represented constraints as interval-constraint networks. These networks are then used

to determine if an individual violates any of the constraints. In the case of constraint

violations, information from the belief space is used to repair that individual.

Jin and Reynolds [419] expanded the interval representation of the normative knowl-

edge component to also represent constraints. The approach ﬁts a grid structure over

the search space, where the cells are referred to as belief cells. Belief cells are then

classiﬁed into one of four categories (as illustrated in Figure 14.2):

• feasible, which represents a part of the search space where no constraint is

violated;

• infeasible, where at least one constraint is violated;

• semi-feasible, in which case the cell contains both feasible parts of the search

space; and

• unknown

The intervals as given in the normative knowledge component are used to divide the

search space as represented by these intervals into hypercubes or belief cells. The type

of belief cell is determined based on the number of individuals that fall in that cell.

For each cell,

• if there are no feasible or infeasible individuals, the cell is classiﬁed as unknown;

• if there are no infeasible individuals, but at least one feasible individual, the cell

is classiﬁed as feasible;

• if there are no feasible individuals, but at least one infeasible individual, the cell

is classiﬁed as infeasible; or

• if there are both feasible and infeasible individuals, the cell is classiﬁed as semi-

feasible.

272 14. Cultural Algorithms

Search cells

Feasible cells

Semi-feasible cell

Infeasible cells

Figure 14.2 Illustration of Belief Cells

Initially, all cells are classiﬁed as unknown.

The update of the belief space requires the counters of feasible and infeasible individ-

uals per belief cell to be updated. At regular intervals, the normative component is

updated by redeﬁning the hypercubes based on the most recent intervals as contained

in this knowledge component. After recalculation of hypercubes, all the feasible and

infeasible counters have to be updated. Coello and Becerra [145] proposed that the

acceptance function be adapted to use ﬁtness as a secondary criterion in selecting in-

dividuals. Instead, feasible individuals should be given preference to update the belief

space.

The inﬂuence function is changed to promote creation of feasible oﬀspring. If x

(t)is

within a feasible, semi-feasible, or unknown hypercube, mutation is applied such that

the individual remains in the same hypercube, or stays very close to it. If x

(t)isin

an infeasible cell, the direction of mutation is such that the individual moves closer

to a semi-infeasible cell. If there is no semi-feasible cell in the vicinity of x

(t), the

move is made towards an unknown cell. Failing this, x

(t) is initialized to a random

position within the interval deﬁned by the normative component.

14.5.2 Multi-Objective Optimization

Coello and Becerra [146] developed the ﬁrst CA for solving multi-objective optimiza-

tion problems (MOP). The belief space is constructed to consist of a normative compo-

nent (representing intervals) and a grid. The grid is constructed over objective space,

14.5 Advanced Topics 273

and for each cell the number of nondominated solutions that lie within that cell is

recorded. This information is then used to ensure that nondominated solutions are

uniformly distributed along the Pareto front.

The normative knowledge component is updated at regular intervals, while the grid

is updated at each generation. Updating the grid simply involves recalculating the

number of nondominated solutions per cell. An update to the normative component

triggers a recalculation of the grid over objective space.

Within the population space, selection of the new population is adapted to make use

of the grid information contained in the belief space. Tournament selection is used,

and applied to the parents and oﬀspring. The rules of tournament selection is updated

as follows:

• If an individual dominates its competitor, then the dominating individual wins.

• If none of the two competing individuals are dominating, or if their objective

values are the same, then

– if one of the individuals lies outside of the grid, then that individual is

selected.

– if both lie in the grid, the one in the less populated cell is selected.

• If none of the cases above are satisﬁed, the more ﬁt individual is selected.

This MOO approach using CAs maintains an archive of nondominated solutions [146].

14.5.3 Dynamic Environments

Saleem and Reynolds [752] showed that the self-adaptability of CAs, due to the dynam-

ically changing belief space, makes CAs suitable for tracking optima in dynamically

changing environments. The belief space is extended to store information from pre-

vious and current environmental states. Environmental history is stored in a table,

containing the following information for each environment: the location of the best

solution (i.e. the current item stored in the situational knowledge component), the

ﬁtness value of that solution, the change magnitude in each dimension, and the con-

sequent change in ﬁtness value. This information is then used in a dynamic inﬂuence

function to introduce diversity into the population, proportional to the magnitude of

change.

The step size is calculated as

∆x

(t)=

2|f(x

(t)) −

f(x

(t))|

f(t)

(0, 1) (14.29)

where f represents the landscape before change, and

f represents the changed land-

scape;

f(t) is the ﬁtness value of the best solution as stored in the history table. This

results in large step sizes for large environmental changes; thereby increasing diversity.

274 14. Cultural Algorithms

14.6 Applications

Cultural algorithms have been applied to solve a number of problems, with one of

the ﬁrst applications modeling the evolution of agriculture in the Valley of Oaxaca

(Mexico) [715, 721]. Other applications of CAs include concept learning [826], induc-

ing decision trees [718], real-valued function optimization [720], optimizing semantic

networks [747], software testing [647], assessing the quality of GP [163], data mining

[420], image segmentation [723], and robotics [287].

14.7 Assignments

1. Discuss how a CA can be used to train a FFNN.

2. What are the similarities and diﬀerences between CAs and ES?

3. Discuss the validity of the following statement: The belief space can be likened

to a blackboard system used in multi-agent systems.

4. With reference to [24], show how CAs address the three levels of adaptation:

population, individual, and component.

5. Investigate the performance of diﬀerent selection operators, as discussed in Sec-

tion 8.5, as acceptance function.

6. Propose membership functions for the fuzzy sets used to implement the rules

as given in Algorithm 14.2 for the fuzzy acceptance function discussed in Sec-

tion 14.3.2.

7. Discuss the merits of the fuzzy acceptance function of Section 14.3.2 with refer-

ence to the fuzzy rules summarized in Algorithm 14.2.

8. Implement a DE for the population space of a CA, and compare its performance

with CAEP.

Chapter 15

Coevolution

Coevolution is the complementary evolution of closely associated species. Coevolution

between two species is nicely illustrated using Holland’s example of the competitive

interaction between a plant and insects [377]. Consider a certain species of plant living

in an environment containing insects that eat the plant. The survival “game” consists

of two parts: (1) to survive, the plant needs to evolve mechanisms to defend itself from

the insects, and (2) the insects need the plant as food source to survive. Both the

plant and the insects evolve in complexity to obtain characteristics that will enable

them to survive. For example, the plant may evolve a tough exterior, but then the

insects evolve stronger jaws. Next the plant may evolve a poison to kill the insects.

Next generations of the insect evolve an enzyme to digest the poison. The eﬀect

of this coevolutionary process is that, with each generation, both the plant and the

insects become better at their defensive and oﬀensive roles. In the next generation,

each species change in response to the actions of the other species during the previous

generation.

The biological example described above is an example of predator-prey competitive

coevolution, ‘where there is an inverse ﬁtness interaction between the two species. A

win for the one species means a failure for the other. To survive, the “losing” species

adapts to counter the “winning” species in order to become the new winner. During

this process the complexity of both the predator and the prey increases.

An alternative coevolutionary process is symbiosis, where the diﬀerent species coop-

erate instead of compete. In this case a success in one species improves the survival

strength of the other species. Symbiotic coevolution is thus achieved through a positive

ﬁtness feedback among the species that take part in this cooperating process.

In standard EAs, evolution is usually viewed as if the population attempts to adapt in

a ﬁxed physical environment. In contrast, coevolutionary (CoE) algorithms (CoEA)

realize that in natural evolution the physical environment is inﬂuenced by other

independently-acting biological populations. Evolution is therefore not just locally

within each population, but also in response to environmental changes as caused by

other populations. Another diﬀerence between standard EAs and CoEAs is that EAs

deﬁne the meaning of optimality through an absolute ﬁtness function. This ﬁtness

function then drives the evolutionary process. On the other hand, CoEAs do not

deﬁne optimality using a ﬁtness function, but attempt to evolve an optimal species

where optimality is deﬁned as defeating opponents (in the case of predator-prey CoE).

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

2007 John Wiley & Sons, Ltd

275

276 15. Coevolution

Section 15.1 provides a summary of diﬀerent types of coevolution. Competitive coevo-

lution is discussed in Section 15.2, while some cooperative coevolution approaches are

summarized in Section 15.3.

15.1 Coevolution Types

As indicated in the introduction of this chapter, two main classes of coevolutionary

approaches can be identiﬁed, namely competitive coevolution and cooperative coevo-

lution. For each of these classes, Fukuda and Kubota [293] identiﬁed a number of

subclasses. For competitive coevolution, the following subclasses can be found:

• Competition, where both species are inhibited. Due to the inverse ﬁtness

interaction between the two species, success in one of the species is felt as failure

by the other species.

• Amensalism, where one species is inhibited, and the other is not aﬀected.

In the case of cooperative (or symbiotic) coevolution, the following subclasses can be

identiﬁed:

• Mutualism, where both species beneﬁt. The positive ﬁtness interaction leads

to an improvement in one species whenever the other species improves.

• Commensalism, where only one of the species beneﬁts, while the other is not

aﬀected.

• Parasitism, where one of the species (the parasite) beneﬁts, while the other

species (the host) is harmed.

The focus of this chapter will be on competitive (predator-prey) coevolution and mu-

tualism.

15.2 Competitive Coevolution

Competitive coevolution (CCE) works to produce optimal competing species through

a pure bootstrapping process. Solutions to problems are found without any prior

knowledge from human experts, or any other information on how to solve the problem.

A CCE algorithm usually evolves two populations simultaneously. Individuals in one

population represent solutions to a problem, while individuals in the other population

represent test cases. Individuals in the solution population evolve to solve as many

test cases as possible, while individuals in the test population evolve to present an

incrementally increasing level of diﬃculty to the solution individuals. The ﬁtness

of individuals in the solution population is proportional to the number of test cases

solved by the solution. The ﬁtness of individuals in the test population is inversely

proportional to the number of strategies that solve it.

This is the CCE approach popularized by Hillis [365]. However, Hillis was not the ﬁrst

15.2 Competitive Coevolution 277

to consider CCE. Miller [594, 595] and Axelrod [33] used CCE to evolve strategies

for the iterated prisoner’s dilemma (IPD). Holland [377] incorporated coevolution in

a single population GA, where individuals compete against other individuals of the

same population.

Section 15.2.1 discusses competitive ﬁtness. The hall of fame concept is discussed in

Section 15.2.1. A generic CCE algorithm is given in Section 15.2.2. Some applications

of CCE are given in Section 15.2.3.

15.2.1 Competitive Fitness

Standard EAs use a user-deﬁned, absolute ﬁtness function to quantify the quality of

solutions. This absolute ﬁtness function directly represents the optimization problem.

The ﬁtness of each individual is evaluated independently from any other population,

or individual, using this ﬁtness function. In CCE, the driving force of the evolution-

ary process is via a relative ﬁtness function that only expresses the performance of

individuals in one population in comparison with individuals in another population.

Usually, the relative ﬁtness computes a score of how many opponents are beaten by

an individual. It should be clear that the only quantiﬁcation of optimality is which

population’s individuals perform better. No ﬁtness function that describes the optimal

point is used.

In order to calculate the relative ﬁtness of an individual, two aspects are of importance:

(1) Which individuals from the competing population are used, and (2) exactly how

these competing individuals are used to compute the relative ﬁtness. The ﬁrst aspect

refers to ﬁtness sampling, and is discussed in Section 15.2.1. Relative ﬁtness evaluation

approaches are summarized in Section 15.2.1.

Fitness Sampling

The relative ﬁtness of individuals is evaluated against a sample of individuals from the

competing population. The following sampling schemes have been developed:

• All versus all sampling [33], where each individual is tested against all the

individuals of the other population.

• Random sampling [711], where the ﬁtness of each individual is tested against

a randomly selected group (consisting of one or more) individuals from the other

population. The random sampling approach is computationally less complex

than all versus all sampling.

• Tournament sampling [27], which uses relative ﬁtness measures to select the

best opponent individual.

• All versus best sampling [793], where all the individuals are tested against

the ﬁttest individual of the other population.

• Shared sampling [738, 739, 740], where the sample is selected as those opponent

individuals with maximum competitive shared ﬁtness. Shared sampling tends