Engelbrecht Andries P. Computational Intelligence: An Introduction

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

278 15. Coevolution

to select opponents that beat a large number of individuals from the competing

population.

Relative Fitness Evaluation

The following approaches can be followed to measure the relative ﬁtness of each indi-

vidual in a population. Assume that the two populations C

and C

coevolve, and the

aim is to calculate the relative ﬁtness of each individual C

of population C

• Simple fitness: A sample of individuals is taken from population C

,andthe

number of individuals in population C

for which C

is the winner, is counted.

The relative ﬁtness of C

is simply the sum of successes for C

• Fitness sharing [323]: A sharing function is deﬁned to take into consideration

similarity among the individuals of population C

. The simple ﬁtness of an

individual is divided by the sum of its similarities with all the other individuals

in that population. Similarity can be deﬁned as the number of individuals that

also beats the individuals from the population C

sample. The consequence of

the ﬁtness sharing function is that unusual individuals are rewarded.

• Competitive fitness sharing [738, 739, 740]: In this case the ﬁtness of indi-

vidual C

is deﬁned as

f(C



l=1

(15.1)

where C

, ···, C

form the population C

sample, and C

is the total

number of individuals in population C

that defeat individual C

. The compet-

itive ﬁtness sharing method rewards those population C

individuals that beat

population C

individuals, which few other population C

individuals could beat.

It is therefore not necessarily the case that the best population C

individual

beats the most population C

individuals.

• Tournament fitness [27] holds a number of single elimination, binary tour-

naments to determine a relative ﬁtness ranking. Tournament ﬁtness results in a

tournament tree, with the root element as the best individual. For each level in

the tree, two opponents are randomly selected from that level, and the best of

the two advances to the next level. In the case of an odd number of competitors,

a single individual from the current level moves to the next level. After tourna-

ment ranking, any of the standard selection operators (refer to Section 8.5) can

be used to select parents.

Hall of Fame

Elitism is a mechanism used in standard EAs to ensure that the best parents of a

current generation survive to the next generation. To be able to survive for more

generations, an individual has to be highly ﬁt in almost every population. For coevo-

lution, Rosin and Belew [740] introduced the hall of fame to extend elitism in time. At

15.2 Competitive Coevolution 279

each generation the best individual of a population is stored in that population’s hall

of fame. The hall of fame may have a limited size, in which case a new individual to

be inserted in the hall of fame will replace the worst individual (or the oldest one). In-

dividuals from one population now compete against a sample of the current opponent

population and its hall of fame. The hall of fame prevents overspecialization.

15.2.2 Generic Competitive Coevolutionary Algorithm

The generic CCE algorithm in Algorithm 15.1 assumes that two competing popula-

tions are used. For a single population CCE algorithm, refer to Algorithm 15.2. For

both these algorithms, any standard EA can be used to evolve each population for

one iteration (i.e. perform reproduction and select the new population). Table 15.1

provides a summary of some publications for EAs used, including PSO.

Algorithm 15.1 Competitive Coevolutionary Algorithm with Two Populations

Initialize two populations, C

and C

;

while stopping condition(s) not true do

for each C

,i=1,...,C

Select a sample of opponents from C

;

Evaluate the relative ﬁtness of C

with respect to this sample;

end

for each C

,i=1,...,C

Select a sample of opponents from C

;

Evaluate the relative ﬁtness of C

with respect to this sample;

end

Evolve population C

for one generation;

Evolve population C

for one generation;

end

Select the best individual from the solution population, S

;

Algorithm 15.2 Single Population Competitive Coevolutionary Algorithm

Initialize one population, C;

while stopping condition(s) not true do

for each C.x

,i=1,...,C.n

Select a sample of opponents from C to exclude C.x

;

Evaluate the relative ﬁtness of C.x

with respect to the sample;

end

Evolve population C for one generation;

end

Select the best individual from C as the solution;

Algorithm 15.1 assumes that C

is the solution population and C

is the test population.

280 15. Coevolution

Table 15.1 Algorithms Used to Achieve Adaptation in CCE

Algorithm Reference

GA [37, 132, 657, 750, 855]

EP [119, 120, 268, 532]

ES [60, 914]

GP [343, 357, 358, 480]

PSO [286, 580, 654]

In CCE it is also possible to use two competing solution populations, in which case

the individuals in one population serve as the test cases of individuals in the other

populations. Here the solution returned by the algorithm is the best individual over

both populations.

The performance of a CCE can be greatly improved if the two competing populations

are as diverse as possible. Diversity can be maintained by incorporating mechanisms

to facilitate niche formation. Shared sampling and the ﬁtness sharing methods achieve

this goal. Alternatively, any niching (speciation) algorithm can be implemented.

15.2.3 Applications of Competitive Coevolution

The ﬁrst applications of coevolution were to evolve IPD strategies [33, 594, 595], and

to evolve sorting algorithms [365]. Since these applications, CCE has been applied to

a variety of complex real-world problems, as summarized in Table 15.2 (please note

that this is not a complete list of applications).

The remainder of this section shows how CCE can be used to evolve game players

for two-player, zero-sum, board games. The approach described here is based on the

work of Chellapilla and Fogel [120, 121, 268] for Checkers, and further investigated by

[156, 286, 580, 654] for Chess, Checkers, Tick-Tack-Toe, the IPD, and Bao. However,

the model described here is not game speciﬁc.

The coevolutionary game learning model trains neural networks in a coevolutionary

fashion to approximate the evaluation function of leaf nodes in a game tree. The

learning model consists of three components:

• A game tree, expanded to a given ply-depth using game tree expansion algo-

rithms such as minimax [629]. The root tree represents the current board state,

while the other nodes in the tree represent future board states. The objective

is to ﬁnd the next move to take the player maximally closer to its goal, i.e. to

win the game. To evaluate the desirability of future board states, an evaluation

function is applied to the leaf nodes.

• A neural network evaluation function to estimate the desirability of board states

represented by the leaf nodes. The NN receives a board state as its input, and

15.3 Cooperative Coevolution 281

Table 15.2 Applications of Competitive Coevolution

Application Reference

Game learning [119, 120, 171, 249, 268, 286, 580, 615, 684, 739]

Military tactical planning [455]

Controller design [513]

Robot controllers [20, 60, 132, 293, 424, 541, 631, 658, 859]

Evolving marketing strategies [786]

Rule generation for [415]

fuzzy logic controllers

Constrained optimization [144, 589, 784]

Autonomous vehicles [93]

Scheduling [855]

Neural network training [119, 120, 286, 580, 657]

Drug design [738]

Iterated prisoners dilemma [33, 172, 594, 595]

produces a scalar output as the board state desirability.

• A population of NNs, where each NN is represented by one individual, and

trained in competition with other NNs. Any EA (or PSO) can be used to adapt

the weights.

The objective of the above model, also summarized in Algorithm 15.3, is to evolve

game-playing agents from zero knowledge about playing strategies. As is evident

from Algorithm 15.3, the training process is not supervised. No target evaluation

of board states is provided. The lack of desired outputs for the NN necessitates a

coevolutionary training mechanism, where a NN competes against a sample of NNs

in game tournaments. After each NN has played a number of games against each of

its opponents, it is assigned a score based on the number of wins, losses and draws.

These scores are then used as the relative ﬁtness measure. Note that the population

of NNs is randomly initialized.

15.3 Cooperative Coevolution

Section 15.1 referred to three diﬀerent types of cooperative coevolution. This section

focuses on mutualism, where individuals from diﬀerent species (or subpopulations)

have to cooperate in some way to solve a global task. Here, the ﬁtness of an individual

depends on that individual’s ability to collaborate with individuals from other species.

One of the major problems to resolve in such cooperative coevolution algorithms is

that of credit assignment: How should the ﬁtness achieved by the collective eﬀort of

all species be fairly split among the participating individuals.

De Jong and Potter [194] proposed a general framework for evolving complex solutions

282 15. Coevolution

Algorithm 15.3 Coevolutionary Training of Game Agents

Create and randomly initialize a population of NNs;

while stopping condition(s) not true do

for each individual (or NN) do

Select a sample of competitors from the population;

for each opponent do

for a specified number of times do

Play a game as ﬁrst player using the NNs as board state evaluators in

a game tree;

Record if game was won, lost, or drawn;

Play another game against the same opponent, but as second player;

Record if game was won, lost, or drawn;

end

Determine a score for the individual;

end

Evolve the population for one generation;

end

Return the best individual as the NN evaluation function;

by merging subcomponents, evolved independently from one another. A separate

population is used to evolve each subcomponent using some EA. Representations from

each subcomponent is then combined to form a complete solution, which is evaluated

to determine a global ﬁtness. Based on this global ﬁtness, some credit ﬂows back to

each subcomponent reﬂecting how well that component collaborated with the others.

This local ﬁtness is then used within the subpopulation to evolve a better solution.

Potter and De Jong [687] applied this approach to function optimization. For an

-dimensional problem, n

subpopulations are used – one for each dimension of

the problem. Each subpopulation is therefore responsible for optimizing one of the

parameters of the problem, and no subpopulation can form a complete solution by

itself. Collaboration is achieved by merging a representative from each subpopulation.

The eﬀectiveness of this collaboration is estimated as follows: Considering the j-th

subpopulation, C

, then each individual, C

,ofC

performs a single collaboration

with the best individual from each of the other subpopulations by merging these best

components with C

to form a complete solution. The credit assigned to C

simply the ﬁtness of the complete solution.

Potter and De Jong found that this approach does not perform well when problem

parameters are strongly interdependent, due to the greediness of the credit assignment

approach. To reduce greediness two collaboration vectors can be constructed. The

ﬁrst vector is constructed by considering the best individuals from each subpopulation

as described above. The second vector chooses random individuals from the other

subpopulations, and merges these with C

. The best ﬁtness of the two vectors is

used as the credit for C

In addition to function optimization, Potter and De Jong also applied this approach

15.4 Assignments 283

to evolve cascade neural networks [688] and robot learning [194, 690].

Other applications of cooperative coevolution include the evolution of predator-prey

strategies using GP [358], evolving fuzzy membership functions [671], robot controllers

[631], time series prediction [569], and neural network training [309].

15.4 Assignments

1. Design a CCE algorithm for playing tick-tack-toe.

2. Explain the importance of the relative ﬁtness function in the success of a CCE

algorithm.

3. Discuss the validity of the following statement: CCGA will not be successful if

the genes of a chromosome are highly correlated.

4. Compare the diﬀerent ﬁtness sampling strategies with reference to computational

complexity.

5. What will be the eﬀect if ﬁtness sampling is done only with reference to the hall

of fame?

6. Why is shared sampling a good approach to calculate relative ﬁtness?

7. Why is niche formation so important in CCE?

8. Design a CCE to evolve IPD strategies.

9. Implement a cooperative coevolutionary DE.

Part IV

COMPUTATIONAL

SWARM INTELLIGENCE

Suppose that you and a group of friends are on a treasure ﬁnding mission. You have

knowledge of the approximate area of the treasure, but do not know exactly where it

is located. You want that treasure, or at least some part of it. Among your friends you

have agreed on some sharing mechanism so that all who have taken part in the search

will be rewarded, but with the person who found the treasure getting a higher reward

than all others, and the rest being rewarded based on distance from the treasure at

the time when the ﬁrst one ﬁnds the treasure. Each one in the group has a metal

detector and can communicate the strength of the signal and his current location to

the nearest neighbors. Each person therefore knows whether one of his neighbors is

nearer to the treasure than he is. What actions will you take? You basically have two

choices: (1) Ignore your friends, and search for the treasure without any information

that your friends may provide. In this case, if you ﬁnd the treasure, it is all yours.

However, if you do not ﬁnd it ﬁrst, you get nothing. (2) Make use of the information

that you perceive from your neighboring friends, and move in the direction of your

closest friend with the strongest signal. By making use of local information, and acting

upon it, you increase your chances of ﬁnding the treasure, or at least maximizing your

reward.

This is an extremely simple illustration of the beneﬁts of cooperation in situations

where you do not have global knowledge of an environment. Individuals within the

group interact to solve the global objective by exchanging locally available information,

which in the end propagates through the entire group such that the problem is solved

more eﬃciently than can be done by a single individual.

In loose terms, the group can be referred to as a swarm. Formally, a swarm can be

deﬁned as a group of (generally mobile) agents that communicate with each other

(either directly or indirectly), by acting on their local environment [371]. The in-

teractions between agents result in distributive collective problem-solving strategies.

Swarm intelligence (SI) refers to the problem-solving behavior that emerges from the

interaction of such agents, and computational swarm intelligence (CSI) refers to al-

gorithmic models of such behavior. More formally, swarm intelligence is the property

of a system whereby the collective behaviors of unsophisticated agents interacting lo-

cally with their environment cause coherent functional global patterns to emerge [702].

Swarm intelligence has also been referred to as collective intelligence.

285

286 IV. COMPUTATIONAL SWARM INTELLIGENCE

Studies of social animals and social insects have resulted in a number of computational

models of swarm intelligence. Biological swarm systems that have inspired computa-

tional models include ants, termites, bees, spiders, ﬁsh schools, and bird ﬂocks. Within

these swarms, individuals are relatively simple in structure, but their collective behav-

ior is usually very complex. The complex behavior of a swarm is a result of the pattern

of interactions between the individuals of the swarm over time. This complex behavior

is not a property of any single individual, and is usually not easily predicted or deduced

from the simple behaviors of the individuals. This is referred to as emergence. More

formally deﬁned, emergence is the process of deriving some new and coherent struc-

tures, patterns and properties (or behaviors) in a complex system. These structures,

patterns and behaviors come to existence without any coordinated control system,

but emerge from the interactions of individuals with their local (potentially adaptive)

environment.

The collective behavior of a swarm of social organisms therefore emerges in a non-

linear manner from the behaviors of the individuals of that swarm. There exists a

tight coupling between individual and collective behavior: the collective behavior of

individuals shapes and dictates the behavior of the swarm. On the other hand, swarm

behavior has an inﬂuence on the conditions under which each individual performs its

actions. These actions may change the environment, and thus the behaviors of that

individual and its neighbors may also change – which again may change the collective

swarm behavior. From this, the most important ingredient of swarm intelligence, and

facilitator of emergent behavior, is interaction, or cooperation. Interaction among in-

dividuals aids in reﬁning experiential knowledge about the environment. Interaction

in biological swarm systems happens in a number of ways, of which social interaction

is the most prominent. Here, interaction can be direct (by means of physical contact,

or by means of visual, audio, or chemical perceptual inputs) or indirect (via local

changes of the environment). The term stigmergy is used to refer to the indirect form

of communication between individuals.

Examples of emergent behavior from nature are numerous:

• Termites build large nest structures with a complexity far beyond the compre-

hension and ability of a single termite.

• Tasks are dynamically allocated within an ant colony, without any central man-

ager or task coordinator.

• Recruitment via waggle dances in bee species, which results in optimal foraging

behavior. Foraging behavior also emerges in ant colonies as a result of simple

trail-following behaviors.

• Birds in a ﬂock and ﬁsh in a school self-organize in optimal spatial patterns.

Schools of ﬁsh determine their behavior (such as swimming direction and speed)

based on a small number of neighboring individuals. The spatial patterns of bird

ﬂocks result from communication by sound and visual perception.

• Predators, for example a group of lionesses, exhibit hunting strategies to out-

smart their prey.

• Bacteria communicate using molecules (comparable to pheromones) to collec-

tively keep track of changes in their environment.

IV. COMPUTATIONAL SWARM INTELLIGENCE 287

• Slime moulds consist of very simple cellular organisms with limited abilities.

However, in times of food shortage they aggregate to form a mobile slug with

the ability to transport the assembled individuals to new feeding areas.

The objective of computational swarm intelligence models is to model the simple

behaviors of individuals, and the local interactions with the environment and neigh-

boring individuals, in order to obtain more complex behaviors that can be used to

solve complex problems, mostly optimization problems. For example, particle swarm

optimization (PSO) models two simple behaviors: each individual (1) moves toward

its closest best neighbor, and (2) moves back to the state that the individual has ex-

perienced to be best for itself. As a result, the collective behavior that emerges is that

of all individuals converging on the environment state that is best for all individuals.

On the other hand, ant colony optimization models the very simple pheromone trail-

following behavior of ants, where each ant perceives pheromone concentrations in its

local environment and acts by probabilistically selecting the direction with the highest

pheromone concentration. From this emerges the behavior of ﬁnding the best alterna-

tive (shortest path) from a collection of alternatives. Models of the local behavior of

ants attending to cemeteries result in the complex behavior of grouping similar objects

into clusters.

This part is devoted to the two computational swarm intelligence paradigms, particle

swarm optimization (PSO), presented in Chapter 16, and ant algorithms (AA), pre-

sented in Chapter 17. The former was inspired from models of the ﬂocking behavior

of birds, while the latter was inspired from a number of models of diﬀerent behaviors

observed in ant and termite colonies.