Fill - Free fillable Del 08.3 DBE Report On Population Dynamics In EvE Del_08.3_DBE_Report_on_Population_dynamics_in

Contract number

507953

Workpackage 8

Population dynamics in the Evolutionary En-

vironment

Deliverable 8.3

Report on Population dynamics in EvE

Project funded by the European

Community under the “Information

Society Technology” Programme

1 / 66

Contract number: 507953

Pr oject acronym: DBE

Title: Digital Business Ecosystem

Deliverable N

: D8.3

Due date: 05/2006

Delivery date: 07/2006

Short description: The ﬁnal report on population dynamics. Note

that this task has been brought forward by ﬁve months.

Author: UBHAM

Partners contributed: STU, LSE, HWU

Made available to: Public

Versioning

Version Date Author, Organisation

1.0 30/06/2006 J. E. Rowe, B. Mitavskiy, J. Woodward (UBHAM)

2.0 24/07/2006 J. E. Rowe, B. Mitavskiy, J. Woodward (UBHAM)

Quality check

internal reviewer: Gerard Briscoe (HWU)

internal reviewer: Thomas Kurz (STU)

This work is licensed under the Creative Commons

Attribution-NonCom mercial-ShareAlike 2.5 License. To view a copy of this license,

visit : http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative

Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

2 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

3 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Contents

1 Introduction and relationship to the project 6

2 An evolutionary approach to the dynamic set cover problem 8

2.1 The dynamic set cover problem . .................... 8

2.2 TheUMDAalgorithm ......................... 9

2.3 Javacode ................................ 10

3 Theoretical analysis of variable-length evolutionary systems 12

4 Some Results about the Markov Chains Associated to GPs and General

EAs. 14

4.1 Introduction ............................... 14

4.2 Notation................................. 15

4.3 HowDoesaHeuristicSearchAlgorithmWork?............ 19

4.4 TheMarkovChainAssociatedtoanEvolutionaryAlgorithm..... 19

4.5 A Special Kind of Reproduction Steps and the Extended Geiringer

Theorem................................. 20

4.6 Nonlinear Genetic Programming (GP) with Homologous Crossover. . 24

4.7 The Statement of the Schema-Based Version of Geiringer’s Theorem

for Non-linear GP under Homologous Crossover. . . ......... 29

4.8 HowDoWeObtainTheorem4.7.1fromTheorem4.5.2? ....... 33

4.9 What Does Theorem 4.5.2 Tell Us in the Presence of Mutation for Non-

linearGP?................................ 39

4.10 What Can Be Said in the Presence of Selection in the General Case? . 49

4.11 What are the relations  and  for the case of ﬁtness-proportional

selection? ................................ 53

4.12 What Can Be Said when the Last Elementary Step is Mutation? . . . . 61

4.13Conclusions............................... 64

4 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Executive Summary

This report is the ﬁnal report from UBHAM on WP8 (sub-task S4, Population dynam-

ics in the evolutionary environment) brought forward from month 36. It is a summary

of work done at UBHAM during the period January–April 2006.

The report is in four main parts. The ﬁrst part introduces the work and describes

its relationship to the rest of the project. The second par t outlines our work on ex-

tending evolutionary algorithms to cope with changing requirements (the dynamic set

cover problem). The third part gives an overview of our continuing theoretical analy-

sis of evolutionary systems with variable-length structures (including trees). Th e main

theoretical results are presented in the fourth part, which is a technical paper, to be

published in the journal Theoretical Computer Science.

The main “customers” within the DBE project of this work have been STU and,

indirectly, Intel and Sun. The applications of our research have been of some assistance

in the creation of the EvE architecture and algorithms. Most of the work, however, will

be of long-term interest with an impact beyond the lifetime of the project.

5 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Chapter 1

Introduction and relationship to

the project

This deliverable is the ﬁnal report for sub-task S4 (Population dynamics in the evolu-

tionary environment), which is scheduled to run from month 19 to month 36, and builds

on the work of S3, already reported [21] and the preliminary report from S4 [20]. The

objectives of this sub-task are:

1. To investigate the effects of a changing environment on evolution. Such changes

may come from external forces (e.g. changes in users’ requirements) or inter-

nally (e.g. from the migration of information).

2. To inform the development of DBE Evolutionary Environment, by liaising with

STU, Intel and Sun with regard to representations, operators and ﬁtness deﬁni-

tions.

3. To study population dynamics of variable-sized structures. This will involve

both empirical studies, as well as a theoretical extension of existing work on

limit theorems for variable-sized strin gs.

In our previous reports [21, 20] we described a formalisation of the problem faced

by the EvE as a (weighted) set covering problem, and showed than an evolutionary

approach could be effective on such a problem. We then planned to build on this work

in the following ways:

1. Working with STU to help with their initial implementation of the EvE.

2. Extending the evolutionary approach to deal with changing requirements.

3. Empirical and theoretical studies of the extended algorithm.

4. Continuing collaboration with STU (see [18]) and HWU (see [1]) in the design

of a more sophisticated EvE (including visits to STU).

6 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Unfortunately, due to personnel problems, UBHAM has had to withdraw from the

project early. We have made some contribution to STU’s development of the EvE, in-

cluding collaborative visits. We have also begun work on designing the extension to

deal with dynamic requests. This work is presented in chapter 2. However, the empir-

ical and theoretical studies have not been completed, although the java code has been

handed over to STU. We are also unable to assist STU with their further development.

We have made more progress, however, in our theoretical studies on variable-length

evolution. Since it is envisioned that the extended algorithm may have to deal with

such structures to represent SBVR statements (e.g. in tr ee form) this is a potentially

rich area of research [19]. We summarise our results in chapter 3. Chapter 4 contains a

copy of our most recent publication on this subject (to appear in Theoretical Computer

Science). It is highly technical, and is included for completeness, since this is our ﬁnal

deliverable.

7 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Chapter 2

An evolutionary approach to the

dynamic set cover problem

2.1 The dynamic set cover problem

We b rieﬂy recall the set cover problem as a model f or the DBE EvE. We begin b y

assuming a large collection of features. These are individual things that a consumer

might want. We assume they are atomic. A request from a user is (in the simplest

form) a list of desired features. Service providers make available services to users. A

service comprises, amongst other things, a descirption of all the features which it can

provide. So, from an abstract perspective, we think of a service as being a subset of

features. The problem faced by the EvE is to ﬁnd a collection of services so that, when

taken as a whole, they provide all the features requested. We also want this to be done

as cheaply as possible. We assume each service has an associated cost, and the user

would like the cheapest collection o f services that meets their request.

This problem can be solved effectively u sing an evolutionary approach, as we have

seen in our previous reports. What we now consider is the dynamic set cover problem.

Over time, a user may produce a sequence o f different requests. Similarly, a set of users

with a common (or similar) local service pool, may make different, but related requests.

If the different requests were all unrelated to each other, then the most efﬁcient thing to

do would be to re-run the evolutionary algorithm from scratch on a random population.

However, it is assumed that requests from related users will be somehow similar to

each other. For example, there may be some features, or feature combinations, which

frequently occur in requests from users of a certain type. We want to be able to exploit

this commonality to make the evolutionary algorithm more efﬁcient.

One way to approach this problem is to make sure the initial population used is

biased towards services which occur frequently in response to user requests. We pro-

pose a pro bability vector v which a ssigns a certain probability to each service in the

genepool. When a new request arrives, we generate the new initial population as fol-

lows. We suppose N is the population size, and there are S services in the genepool).

Then to create a new member of the population, we create a binary string of length S,

8 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

where the probability of setting the k

bitto1isv

. We repeat this N times to ﬁll up

the population. Each string is interpreted as a subset of services, where a 1 in position

k indicates that service k is included.

When a new habitat is ﬁrst created, it is given a genepool. It must also then get a

vector v to help it construct populations. It could take this vector from a neighbouring

habitat that corresponds to a similar user type. Or, if there is no suitable neighbour, it

could start off b y setting v

to be a small p robability such as 1/N .

After a request comes from the user, the population is initialised using v. The evo-

lutionary algorithm (see next section) is then run to produce a solution. That solution

will be a collection of services that meets the request as cheaply as possible. We now

want to update v so that the services that appeared in the solution become more likely

to appear in the future. One scheme is to set



(1 − α)v

+ α if k is in the solution

αv

if k is not in the solution

where 0 <α<1 is a learning rate. When the next request comes in, the new version

of v is used to create the initial population, which is now biased towards the more

frequently used services. This form of selection is related to the population “thinning”

algorithm proposed in [18], which acts as a pre-selection phase in the EvE. We propose

that such a method be included in future versions.

2.2 The UMDA algorithm

The scheme d escribed in the previous section incrementally modiﬁes the frequencies

of services in the initial population. We thought it might be appropriate, then, to in-

vestigate the use of an evolutionary algorithm which also operates on the frequencies

of the services. The UMDA (‘Univariate Marginal Distribution Algorithm’) is such an

evolutionary algorithm. It was invented by Heinz Muhlenbein [7] and has been well-

analysed from a theoretical perspective [6, 23]. The algorithm follows three phases:

selection, generation, mutation.

Selection A subset of individuals from the current population are selected depending

on their ﬁtness.

Generation For each service k, denote by p

the frequency with which it appears in

the selected population. Generate a new population using the probability vector

Mutation Mutate each bit of each string in the population with probability μ.

There are several ways in which to perform selection. One may use the standard pro-

portional or tournament selection schemes to select a number of individuals. Or one

may selected a certain fraction of the best individuals (e.g. take the best half of the

population). The generation stage proceeds exactly as with the initial population, only

now we use the vector p. The mutation rate is typically set to 1/S, so that, on average,

one service is included or deleted from a solution.

As a simple example, suppose that our population is as follows:

9 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

0 0 1 1 0 0 1 fitness = 100

1 0 1 1 0 0 0 fitness = 90

1 0 1 0 0 0 1 fitness = 75

0 1 0 1 0 0 1 fitness = 50

1 0 0 0 0 1 0 fitness = 30

0 1 1 1 0 0 1 fitness = 25

That is, the ﬁrst string indicates a subset containing the third, fourth and seventh ser-

vice, and so on. The population has been ranked in order o f ﬁtness. We now select the

best half of the population, namely the ﬁrst three strings. For each service (bit posi-

tion) we consider the frequency with which it appears in these top three strings. For

example, the ﬁrst service occurs in the second and third string, but not the ﬁrst string.

Its frequency is therefore 2/3. The frequencies for each service are:

service

1234567

frequency 2/3012/3002/3

We now generate a new population by sampling the services according to these prob-

abilities. That is, every time we generate a new string, the ﬁrst bit is set to a one with

probability 2/3 and so on. So we might get:

1011001

1010001

1011000

0011001

1010000

We then apply mutation. That is, each bit has a probability μ of changing. The value

of μ is usually set to be 1/S, which in this case is 1/7 so that, on average, one bit is

changed p er string. The resulting population might be:

1001001

1110001

1011000

0011101

0011011

1010110

The ﬁtnesses are then calculated, and the population ranked accordingly, and the next

generation begins.

2.3 Java code

Java code implemented the UMDA algorithm can be found at

http://www.cs.bham.ac.uk/ jer/scp.tar.

10 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

After unpackin g the tar ﬁle, the program must be compiled using

javac pop.java

which can then be run. Various parameters can be adjusted in the ﬁle

parameters.java.

This code is preliminary and for experimental purposes only.

11 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Chapter 3

Theoretical analysis of

variable-length evolutionary

systems

We have p reviously reported several theoretical results in the analysis of evolutionary

algorithms. These were generally in two areas:

• Results relating to variable-length structures (in the inﬁnite population limit)

• Results relating to ﬁnite populations for strings.

As an example, we proposed and proved a generalisation of the classic Geiringer’s the-

orem for ﬁnite populations. Simply put, this states that the repeated action of crossover

is to destroy the correlations between elements of solutions, so that a population tends

to s state of ”linka ge equilibrium”. I t is worth pointing out that th e generation stag e of

the UMDA algorithm takes the population in a single step to this state, as it explicitly

de-couples the linkage between services in a solution. UMDA can therefore be seen

(at least theoretically) as applying repeated strong crossover at each generation.

In our current work, we have continued to look at these themes. In the following

chapter, we present a technical paper containing our results, which we summarise here.

Firstly, we return again to Geiringer’s theorem [4], but now considering the evo-

lution of variable size and shape individuals, namely trees. This, therefore, applies to

standard Genetic Programming (in which we evolve programs in the form of trees). It

also potentially applies to the DBE EvE if, as is envisaged, the types of requests and

service combinations allowed become more sophisticated than simple lists and subsets.

For example, a hierarchical workﬂow pattern could be represented as a tree structure.

We establish, for tree structures, the kinds of shapes (or schemata as they are tech-

nically known) which play a fundamental role in the analogue of Geiringer’s theorem,

and show how crossover again has the effect of de-coupling the correlations that exist

in the population.

On the issue of bloat (that is, uncontrolled growth of structures during evolution),

there are a number of possible counter-measures that can be employed. The simplest

12 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

and strictest is to disallow items larger than a certain threshold. Less severe, but still ef-

fective, is to have a certain probability that items larger than the threshold will be killed

off. Such a method (called the Tarpeian method) has been proposed and theoretically

motivated by Riccardo Poli [10]. An even less strict method is to have a penalty func-

tion that penalises large structures, but this can be difﬁcult to design correctly. See [8]

for a survey of methods.

Secondly, we continue to look at general evolutionary algorithms from the Markov

chain perspective, and begin to build a framework in which bounds on the stationary

distribution can be proved. This distribution gives the probability that a given popu-

lation (or a population with any desired property) will be found by the evolutionary

algorithm in the long-run. The framework relies on the construction of a kind of order

relation (technically a pre-order ) between populations. Once such an order has been

appropriately constructed, then one can use it to determine if one population is more

likely than another to appear in the stationary distribution.

A simple application of this framework establishe s, f or example, that if we have an

evolutionary algorithm which goes through the phases: mutation, selection, crossover

(in that order), then it is impossible that the stationary distribution can be uniform.

There are always some populations which are preferred to other. This is even true even

if all individuals actually have the same ﬁtness! We ascribe this to the implicit biases

induced by crossover, which tends to “prefer” some types of population over others.

One of the practical consequences of this observation is that one has to be rather

careful when designing crossover operators that one is aware that such biases are being

introduced. For example, it is kn own that certain crossovers for variable-length string

structures have biases towards strings of a certain length. That is, such strings will tend

to be “over sampled” in the long run.

Although we have produced a considerable amount of theoretical work in this pe-

riod, it is true to say that at the moment it is still largely of only theoretical interest. We

include our paper in the next chapter for completeness, rather than expecting it to be

of direct value to the project. We had hoped to use the remaining time of the project to

use such results to help design appropriate crossover operators for structured services

within the EvE but, with our withdrawal from the project, this must be left to others, or

to some future work.

13 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Chapter 4

Some Results about the Markov

Chains Associated to GPs and

General EAs.

This chapter is a paper accepted for publication in Theoretical Computer Science.

4.1 Introduction

Geiringer’s classical theorem (see [4]) is an important part of GA theory. It has been

cited in a number of papers: see, for instance, [12], [13], [17] and [22]. It deals with

the limit of the sequence of population vectors obtained by repeatedly applying the

crossover operator C(p)



i,j

(i, j→k)

where r

(i, j→k)

denotes th e proba bility

of obtaining the individual k from the parents i and j after crossover. In other words,

it speaks to the limit of repeated crossover in the case o f an inﬁnite population. In [5],

a new version of this result was proved for ﬁnite populations, addressing the limiting

distribution of the associated Markov chain, as follows. Let Ω=



i=1

denote the

search space of a given genetic algorithm (intuitively A

is the set of alleles correspond-

ingtothei

gene and n is the chromosome length). Fix a population P consisting of

m individuals with m being an even number. P can be thought of as an m by n matrix

whose rows are the individuals of the population P . Write

P =

⎛

⎜

⎝

... a

⎞

⎟

⎠

Notice that the elements of the i

column of P are members of A

. Continuing with

the notation used in [12], denote by Φ(h, P, i) where h ∈ A

the proportion of rows,

say j,ofP for which a

= h. In other words, let R

= {j | 1 ≤ j ≤ m and a

= h}.

14 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Now simply let Φ(h, P, i)=

. The classical Geiringer theorem (see [4] or, [12]

for modern notation) says that if one starts with a population P of individuals and runs

a genetic algorithm (GA) in the absence of selection and mutation (cro ssover being

the only operator involved) then, in the “long run”, the frequency of occurrence o f

the individual (h

,...,h

) before time t, call it Φ(h

,...,h

,t), approaches

independence:

lim

t→∞

Φ(h

,...,h

,t)=



i=1

Φ(h, P, i).

Thereby, Geiringer’s theorem tells us something about the limiting frequency with

which certain elements of the search space are sampled in the long run, provided one

uses crossover alone. In [12] this theorem has been generalized to cover the cases

of variable-length GA’s and homologous linear genetic programming (GP) crossover.

The limiting distributions of the frequency of occurrence of individuals belonging to a

certain schema under these algorithms have been computed. The special conditions un-

der which such a limiting distribution exists for linear GP under homologous crossover

have been established (see theorem 9 and section 4.2.1 of [12]). In [5] a rather powerful

extension of the ﬁnite population version of Geiringer’s theorem has been established.

In the current paper we shall use the recipe described in [5] to derive a version of

Geiringer’s theorem for nonlinear GP with homologous crossover (see section 4.6 or

[9] for a detailed description of how nonlinear GP with homologous crossover works)

which is based on Poli hyperschemata (see section 4.6 or [9]). The ﬁrst step in this

procedure is to describe the search space and the appropriate family of reproduction

transformations so that the resulting GP algorithm is bijective and self-transient in the

sense of deﬁn ition 5.2 of [5]. Then the generalized Geiring e r theorem (theorem 5.2

of [5]) as well as corollaries 6.1 and 6.2 of [5] apply. The necessary details are sum-

marized in the next few sections. A schema based version of Geirnger’s theorem for

nonlinear GP applies even in the presence of “node-mutation” (see section 4.9).

The ﬁnite population Geiringer theorem established in [5] may completely describe

the stationary distribution of the Markov chain associated to an evolutionary algorithm

only in the absence of selection. In section 4.10 we introduce a pre-order relation on

the states of a Markov chain associated to an evolutionary algorithm which is deﬁned

in terms of selection alone, and establish some general inequalities about the station-

ary distribution of this Markov chain when selection is the “last stage” in the cycle.

In section 4.12 we demonstrate that the stationary distribution of the Markov chain

associated to most evolutionary algorithms in the presence of selection can never be

uniform when mutation rate is small enough, even if the ﬁtness function is constant.

The material in sections 4.10, 4.11 and 4.12 is independent of the results in sections

5 - 9. Thus, the reader has an option of jumping to read section 4.10 right after section

4.2 Notation

Ω is a ﬁnite set, called a search space.

15 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

f :Ω→ (0, ∞) is a function, called a ﬁtness function. The goal is to ﬁnd a

maximum of the function f.

is a collection o f q-ary operations on Ω. Intuitively F

can be thought of as the

collection of reproduction operators: some q parents produce one offspring. In nature

often q =2, for every child has two parents, but in the artiﬁcial setting there seem s to

be no special reason to assume that every child has no more than two parents. When

q =1, the family F

can be thought of as asexual reproductions or mutations. The

following deﬁnitions will be used in section 4.3 to describe the general evolutionary

search algorithm. This approach makes it easy to state the Geiringer Theorem.

Deﬁnition 4.2.1 A population P of size m is simply an element of Ω

. (Intuitively it

is convenient to think of a population as a “column vector”.)

Remark 4.2.1 There are 2 primary methods for representing populations: multi-sets

and ordered multi-sets. Each has advantages, depending upon the particular analyt-

ical goals. Lothar Shmitt has published a number of papers which use the ordered

multi-set representation to advantage (see, for insta nce, [15] and [16]). According to

deﬁnition 4.2.1, in the current paper we continue the development o f analysis based

upon the presentation pioneered by Lothar Schmitt. The following example illustrates

an aspect of the representation which the reader would do well to keep in mind:

Example 4.2.1 Let Ω={0, 1}

. Consider the populations

⎛

⎝

000

111

⎞

⎠

⎛

⎝

111

000

111

⎞

⎠

and

⎛

⎝

111

000

⎞

⎠

. According to deﬁnition 4 .2.1 (the ordered multi-set model which is

exploited in the current paper) these are distinct populations despite the fact that they

represent the same population under the multi-set model.

An elementary step is a probabilistic rule which takes one population as an input and

produces another population of the same size as an output. For example, the follow-

ing elementary step corresponds to the ﬁtness-proportional selection which has been

studied in detail by Wright and Fisher (see [24] and [3]).

Deﬁnition 4.2.2 An elementary step of type 1 (alternatively, of type selection) takes

a given population P =

⎛

⎜

⎝

⎞

⎟

⎠

with x

∈ Ω as an input. The individuals of P are

evaluated:

⎛

⎜

⎝

⎞

⎟

⎠

→ f(x

)

→ f(x

)

→ f(x

)

16 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

A new population



⎛

⎜

⎝

⎞

⎟

⎠

is obtained where y

’s are chosen independently m times form the individuals of P and

= x

with probability

f(x

)

l=1

f(x

)

In other words, all of the individuals of P



are among those of P , and the expec-

tation of the number of occurrences of any individual of P in P



is proportional to the

number of occurrences of that individual in P times the individual’s ﬁtness value. In

particular, the ﬁtter the individual is, the more copies of that individual are likely to be

present in P



. On the other hand, the individuals having relatively small ﬁtness value

are not likely to enter into P



at all. This is designed to imitate the natural survival of

the ﬁttest principle.

Population P



is the output of this elementary step.

In order to deﬁne an elementary step of type 2 (reproduction) in a general setting which

uses the ordered multi-set repr e sentation (see remark 4.2.1 and example 4.2.1) one

needs to introduce the following deﬁnitions:

Deﬁnition 4.2.3 Fix an ordered k-tuple of integers q =(q

, ...,q

).LetK de-

note a partition of the set {1, 2,...,m} for some m ∈ N. We say that partition K is

q-ﬁtifeveryelementofK consists of exactly q

elements for some i. In logical symbols

this means that if K = {P

,...,P

} then K is q-ﬁtif∀ 1 ≤ j ≤ l ∃ 1 ≤ i ≤ k

such that |P

| = q

. Denote by E

the family of all q-ﬁt partitions of {1, 2,...,m} (i.

e. E

= {K |K is a q-ﬁt partition of {1, 2,...,m}}).

Deﬁnition 4.2.4 Let Ω be a set, F

, F

,...,F

be some ﬁxed families of q

-ary op-

erations on Ω (F

is simply a family of functions from Ω

into Ω), and p

,...,p

be probability distributions on (F

)

, (F

)

,...,(F

)

respectively. Let q =

, ...,q

). Finally, let ℘

be a probability distribution o n the collection E

partitions of {1, 2,...,m} (see deﬁnition 4.2.3 above). We then say that the ord ered

2(k +1)-tuple (Ω, F

, F

,...,F

,...,p

,℘

) is a reproduction k-tuple

of arity (q

, ...,q

The following deﬁnition o f reproduction covers both, crossover and mutation. Deﬁni-

tion 4.2.6 (see also remark 4.2.2) will make it possible to combine different reproduc-

tion opera tors in a simple and natural way.

Deﬁnition 4.2.5 An elementary step of type 2 (alternatively, of type reproduction) as-

sociated to a given reproduction k-tuple (Ω, F

, F

,...,F

,...,p

,℘

)

takes a given population P =

⎛

⎜

⎝

⎞

⎟

⎠

with x

∈ Ω as an input.

17 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

The individuals of P are partitioned into pairwise disjoint tuples for mating accord-

ing to the probability distribution ℘

. For instance, if the partition selected according

to ℘

is K = {(i

,...,i

), (i

,...,i

),...,(i

,...,i

) ...} the corre-

sponding tuples are

⎛

⎜

⎝

⎞

⎟

⎠

⎛

⎜

⎝

⎞

⎟

⎠

... Q

⎛

⎜

⎝

⎞

⎟

⎠

...

Having selected the partition, replace every one of the selected q

-tuples Q

⎛

⎜

⎝

⎞

⎟

⎠

with the q

-tuples



⎛

⎜

⎝

,...,x

)

,...,x

)

,...,x

)

⎞

⎟

⎠

for a q

-tuple of transformations (T

,...,T

) ∈ (F

)

selected randomly ac-

cording to the probability distribu tion p

on (F

)

. This gives us a new population



⎛

⎜

⎝

⎞

⎟

⎠

which serves as the output of this elementary step.

Notice that a single child does not have to be produced by exactly two parents. It is

possible that a child has more than two parents. Asexual reproduction (mutation) is

also allowed.

Deﬁnition 4.2.6 A cycle is a ﬁnite sequence of elementary steps, say {s

}

n=1

,which

are either of type 1 or of type 2 and such that all of the steps in the sequence {s

}

n=1

have the same underlying search space and the same arity of input/output.

Remark 4.2.2 Intuitively, these steps are linked together in such a way that the output

of the step s

is the input of the step s

i+1

. This is why all of the steps in the same

cycle must have the same underlying search space and the same arity of input/output

(otherwise the input/output relationship does not make sense).

We are ﬁnally ready to describe a rather wide class of evolutionary heuristic search

algorithms.

18 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

4.3 How Does a Heuristic Search Algorithm Work?

A general evolutionary search algorithm works as follows: Fix a cycle,sayC =

}

n=1

(see deﬁnition 4.2.6). Now start the algorithm with an initial population

P =

⎛

⎜

⎝

⎞

⎟

⎠

The initial population P may b e selected completely randomly, or it

may also b e predetermined depending on the circumstances. The actual method of se-

lecting the initial population P is irrelevant for the purposes of the current paper. To

run the algorithm with cycle C = {s

}, simply input P into s

,runs

, then input the

output of s

into s

... input the output of s

j−1

into s

and produce the new output, say



.NowuseP



as an initial population and run the cycle C again. Continue this loop

ﬁnitely many times depending on the circumstances.

Deﬁnition 4.3.1 A sub-algorithm of a given evolutionary search algorithm deﬁned by

a cycle C = { s

}

n=1

is simply an evolutionary search algorithm deﬁned by a subse-

quence {s

}

q=1

of the sequence C of elementary steps.

A recombination sub-algorithm is sub-algorithm deﬁned by a sequence of elemen-

tary steps of type 2 (Reproduction) only.

4.4 The Markov Chain Associated to an Evolutionary

Algorithm

In [22] it has been pointed out that heuristic search algorithms give rise to the following

Markov process

(see also [2], for instance): The state space of this Markov process

is the set of all populations of a ﬁxed size m. This set, in our notation, is simply Ω

The transition probability p

is simply the probab ility that the population y ∈ Ω

is obtained from the population x by going through the cycle once (where the notion

of a cycle is described in section 4.3: see deﬁnition 4 .2 .6 and remark 4.2 .2 ) . The

aim o f the current paper is to establish a few rather general properties of this Markov

chain. In case when there are several algorithms present in our discussion we shall

write {p

}

x,y∈Ω

to denote the Markov transition matrix associated to the algorithm

A while {p

}

x,y∈Ω

would denote the Markov transition matrix associated to th e

algorithm B.

Deﬁnition 4.4.1 Fix an evolutionary search algorithm A. Denote by p

x,y

the prob-

ability that a population y is obtained from the population x upon the completion of

n complete cycles (in the sense of deﬁnition 4.2.6 and remark 4.2 .2) of the algorithm.

We say that a population x leads to a population y under A if and only if p

x,y

> 0

for some n. We also write x

−→ y as a shorthand notation for x leads to y.(This

terminology is adopted from [2].)

In the current paper the state space of this process is slightly modi ﬁed for technical reasons which will

be seen later.

19 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

4.5 A Special Kind of Reproduction Steps and the Ex-

tended Geiringer Theorem

To understand the intuitive meaning of the deﬁnition below, see sections 4.2 and 4.3.

Deﬁnition 4.5.1 Given a set Ω and a family of transformations F

from Ω

into Ω, ﬁx

a q-tuple of transformations (T

, ...,T

) ∈ (F

)

. Now consider the transforma-

tion T

, ...,T

 :Ω

→ Ω

sending any given element

⎛

⎜

⎝

⎞

⎟

⎠

∈ Ω

into

⎛

⎜

⎝

,...,x

)

,...,x

)

,...,x

)

⎞

⎟

⎠

∈ Ω

We say that the transformation T

, ...,T

 is the tupling of the ordered q-tuple

, ...,T

Deﬁnition 4.5.2 Given an elementary step of type 2 (reproduction) associated to the

reproduction k-tuple Ω=(Ω, F

, F

,...,F

,...,p

,℘

), ﬁx some index

i with 1 ≤ i ≤ k and denote by

G(Ω,q

)={T

, ...,T

 :Ω

→ Ω

| T

∈F

, ...,T

) > 0}

the family of all tuplings which have a positive probability of being selected.

Remark 4.5.1 The family of tupling transformations G(Ω,q

) described in deﬁni-

tion 4.5.2 represents the family of q parents → q children crossover transformations

while the family F

represents the family of q parents → 1 child crossovers. Depend-

ing on the circumstances it may be more convenient to specify the family of q parents

→ q children crossover transformations directly rather than specifying the families F

individually. We shall see an example of this situation in section 4.6. The family F

of q parents → 1 child crossovers can then be recovered from the family of q parents

→ q children crossover transformations by using coordinate p rojections.

As mentioned in section 4.2, in nature often the arity of the reproduction transfor-

mations is 2 meaning that every child has 2 parents.

It turns out that quite many evolutionary algorithms, including the classical genetic

algorithm and nonlinear (as well as linear) genetic programming are equipped with the

reproduction steps having the following nice property which has been introduced and

investigated in [5].

Deﬁnition 4.5.3 A given elementary step of type 2 (reproduction) associated to the re-

production k-tuple (Ω, F

, F

,...,F

,...,p

,℘

) is said to be bijective

(and self-transient) if it satisﬁes conditions 1 (and 2) stated below:

1. ∀ 1 ≤ i ≤ k we have p

, ...,T

) > 0=⇒T

, ...,T

 (see

deﬁnition 4.5.1 for the meaning of T

, ...,T

) is a bijection (a one-to-one and

onto map of Ω

onto itself).

20 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

2. ∀ 1 ≤ i ≤ k ∃ (T

, ...,T

) ∈ (F

)

such that p

, ...,T

) > 0

and T

, ...,T

 = 1 where 1 :Ω

→ Ω

denotes the identity map (i. e. ∀ x ∈

we have T

, ...,T

(x)=x). We say that a recombination sub-algorithm

(see deﬁnition 4.3.1) of a given evolutionary search algorithm is bijective (and self-

transient) if every given term of the subsequence, s

by which the sub-algorithm is

deﬁned is bijective (an d self-transient).

Remark 4.5.2 Notice that conditions 1 and 2 of deﬁnition 4.5.3 ca n be restated in

terms of the family G(Ω,q

) as follows:

1. Every transformation in the family of tuplings, G(Ω,q

) is a bijection.

2. 1 ∈G(Ω,q

) where 1 :Ω

→ Ω

denotes the identity map.

In [5] the following nice facts have been established:

Proposition 4.5.1 Let A denote a bijective and self-transient algorithm (see deﬁni-

tion 4.5.3). Then

−→ is an equivalence relation.

Proposition 4.5.1 motivates the following deﬁnition:

Deﬁnition 4.5.4 Given a bijective and self-transient alg orithm A and a population

P ∈ Ω

, denote b y [P ]

the equivalence class of the population P under the equiva-

lence relation

−→ .

To alleviate the level of abstraction we illustrate proposition 4.5.1 and deﬁn ition 4.5.4

with a couple of examples.

Example 4.5.1 Consider a binary genetic algorithm over the search space Ω={0, 1}

under the action of crossover alone. Let the population size be some even number m.

Consider the following family of masked crossover transformations: F = {F

| M ⊆

{1, 2,...,n}} where each F

is a binary operation (i. e. a function from Ω

into Ω)

deﬁned as follows: For every a =(a

,...,a

) and b =(b

,...,b

) ∈ Ω

(a, b)=x =(x

,...,x

) ∈ Ω

where



if i ∈ M

otherwise

Let A denote the evolutionary algorithm determined by a single elementary step of type

2 (crossover) which is associated to the reproduction

-tuple

Ω=(Ω, F, F,...,F,p

,...,p

,℘

)

(see deﬁnitions 4.2.4 and 4.2.5) where the probability distributions p

have the property

that p

) =0only if K = M

(here M

denotes the complement of M in

{1, 2,...,n}). This assumption on the distributions p

ensures that the elementary

step of crossover associated to the reproduction

-tuple Ω is bijective. Depending on

the further properties of the distributions p

and the distribution ℘

, different types

of equivalence relations

−→ would be induced. Typically, in case of a classical GA

crossover, the distributions p

are all identical (i. e. p

= p

= ... = p

= p)where

21 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

p is the uniform distribution on {1, 2,...,n} and the distribution ℘

is uniform over

all partitions of {1, 2,...,n} into 2-element subsets. In such a case the equivalence

relation

−→ is determined by the numbers of 0’s in the columns (or, equivalently, by

the numbers of 1’s in the columns). The reason this is so is that a population Q can

be reached from a population P in by performing a sequence of crossover elementary

steps only if it has the same amount of “genetic material” in every column since alleles

are neither lost nor created during homologous crossover. Using the fact that every

permutation can be obtained by performing enough transpositions, one can show the

converse of this fact. This fact is a particular case of lemma 47 of [5]. For instance, if

n =5and m =4we have

⎛

⎜

⎝

01011

01010

10101

00101

⎞

⎟

⎠

−→

⎛

⎜

⎝

01001

10101

00010

01111

⎞

⎟

⎠

Indeed, the number of 0’s in both populations in the ﬁrst column is 3,inthe2

, 3

and 4

columns is 2 and in the last column is 1. Thus the equivalence class cor-

responding to a given population P can be described by an ordered n-tuple [c]

,...,c

) of numbers between 0 and m where c

is the number of 0sinthei

column of P . For example, if P is either one of the equivalent populations above then

[c]

=(3, 2, 2, 2, 1).

Example 4.5.2 Continuing with example 4.5.1, consider the following family of muta-

tion transformations M = { T

| u ∈ Ω} where each transformation T

is deﬁned as

follows: Denote by +

the addition modulo 2 (0+

0=0, 1+

0=1, 0+

1=1,

1=0). We then deﬁne T

to be the function from Ω into itself which sends every

a =(a

,...,a

) to T

(a)=a ⊕ u where ⊕ is componentwise addition modulo

2, i. e. given x =(x

,...,x

) and y =(y

,...,y

) ∈ Ω

,the⊕ operation

is deﬁned as follows: x ⊕ y = z where z =(z

,...,z

) with z

= x

Notice ﬁrst that every transformation T

is bijective (in fact T

◦ T

= 1 where 1 is

the identity map on Ω). Since every mutation transformation T

is uniquely determined

by the element u ∈ Ω,deﬁning a probability distribution on the family M amounts to

deﬁning a probability distribution o n Ω={0, 1}

. To achieve a situ ation equivalent

to the classical case where every b it is mutated independently with a small probability

>0 and remains unchanged with probability 1 − , we choose 1 with probability 

and 0 with probability 1 −  independently n times. Given a population of size m we

let mutation be the elementary step associated to the reproduction m-tuple

mutation

=(Ω, M, M,...,M, p, p,...,p,℘

)

where p is the probability distribution on M described above and ℘

is the unique

trivial p robability distribution o n the one-element set (since there is exactly one way to

partition a given set into singleton subsets). Now let B denote the algorithm determined

by the elementary step of crossover as described in example 4.5.1 followed by the

One point crossover under reasonable assumptions will produce the same equivalence relation.

22 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

elementary step of mutation as described above. Then the algorithm B is ergodic in the

sense of deﬁnition 58 of [5] which means that the equivalen ce relation

−→ is trivial,

i.e. there is only one equivalence class or, in other words, for any two populations

P and Q we have P

−→ Q. Indeed, thanks to the availability of mutation, any given

population can be reached from any other given population in a single step with a small

but a positive p robability which means that any two g iven populations are equivalent

under

−→ .

The main result of [5] is the following fact:

Theorem 4.5.2 Let A denote a bijective and self-transient algorithm. Then the Markov

chain initiated a t some population P ∈ Ω

is irreducible and its unique stationary dis-

tribution is the uniform distribution (on [P ]

The classical versions of Geiringer theorem, such as the ones established in [4]

and in [12] are stated in terms of the “limiting frequency of occurr e nce” of a certain

element of the search space. The following deﬁnitions, which also appear in [5], make

these notions precise in the ﬁnite population setting:

Deﬁnition 4.5.5 We d eﬁne the characteristic function X :Ω

×P(Ω) → N ∪{0}

as follows: X (P, S)=the number of individuals of P which are the elements of S.

(Recall that P ∈ Ω

is a population consisting of m individuals and S ∈P(Ω) simply

means that S ⊆ Ω.)

Example 4.5.3 For instance, suppose Ω={0, 1}

, P =

⎛

⎜

⎝

01010

10101

00101

01010

10101

⎞

⎟

⎠

and

S ⊆ Ω={0, 1}

is determined by the Holland schema (∗, 1, ∗, 1, ∗).ThenX (P, S)=

3 because exactly three rows of P ,the1

,the2

, and the 5

are in S.

Deﬁnition 4.5.6 Fix an evolutionary algorithm A and an initial population P ∈ Ω

Let P (t) denote the population obtained upon the completion of t reproduction steps

of the algorithm A in the absence of selection and mutation. For instance, P (0) = P .

Denote by Φ(S, P, t) the proportion of individuals from the set S which occur before

time t. That is, Φ(S, P, t)=

s=1

X (P (s),S)

. (Notice that tm is simply the total

number of individuals encountered before time t. The same individual may be repeated

more than once and the multiplicity co ntributes to Φ.) Denote by X (2,S):Ω

→ N

the restriction of the function X when the set S is ﬁxed (the notation suggests that one

plugs a population P into the box).

Intuitively, Φ(S, P, t) is the frequency of encountering the individuals in S before time

t when we run the algorithm starting with the initial population P .

23 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

4.6 Nonlinear Genetic Programming (GP) with Homol-

ogous Crossover.

In genetic programming, the search space, Ω, consists of the parse trees which usually

represent various computer programs.

Example 4.6.1 A typical parse tree representing the program (+(sin(x), ∗(x, y))) is

drawn below:

Since computers have only a ﬁnite amount of memory, it is reasonable to assume that

there are ﬁnitely many basic operations which can be used to construct programs and

that every program tree has d epth less than or equal to some integer L. Under these

assumptions Ω is a ﬁnite set. We may then deﬁne the search space as follows:

Deﬁnition 4.6.1 Fix a signature Σ=(Σ

, Σ

,...,Σ

) where Σ

’s are ﬁnite

sets.

We assume that Σ

= ∅ and |Σ

| =1∀ j

. The search space Ω consists of all

parse trees having depth at most L. Interior nodes having i children are labelled by

the e lements of Σ

. The leaf nodes are labelled by the elements of Σ

In order to study the appropriate family of reproduction (crossover) transformations

with the aim of applying the generalized Geiringer theorem, it is most convenient to

exploit Poli hyperschemata ([9] for a more detailed description).

Deﬁnition 4.6.2 A Poli hyperschema is a rooted parse tree which may have two ad-

ditional labels for the nodes, namely # and = signs (it is assumed, of course, that

neither one of these denotes an operation). The = sign may label any interior node v

of the tree. Since v does occur in the tree, we must have |Σ

| > 0.) The # sign can

only label a leaf node. A given Poli hyperschema represents the set of all programs

whose parse tree can be obtained by replacing the = signs with any operation of the

appropriate arities and attaching any program trees in place of the # signs. Different

occurrences of # or = may be replaced differently. We shall denote by S

the set of

programs represented by a hyperschema t.

Consider, for instance, the hyperschema t deﬁned as (+(= (#,x), ∗(sin(y), #)) which

is pictured below:

Intuiti vely Σ

is the set consisting of i-ary operations and Σ

consists of the input variables. Formally

this does not have to be the case though.

The assumption that |Σ

| =1∀ j does not cause any problems since we are free to select any elements

from the search space that we want. On the other hand, this assumption helps us to av oid unnecessary

complications when dealing with the poset of Poli hyperschemata later

24 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

A couple of p rograms ﬁtting the hyperschema t are shown below:

In order to model the family of reproduction (crossover) transformation in a way which

makes it obvious that GP is a b ijective and self-transient algorithm, we shall introduce

a partial order on the set of all Poli hyperschema so that every two elements have the

least upper bound. The notion of the least upper bound will be also used to deﬁne

the common region (see [11] for an alternative description of the notion of a common

region).

Deﬁnition 4.6.3 Denote by O the set of all basic operations which can be used to

construct the programs (i. e. O =Σ

∪ ...,∪Σ

) and by V the set of all variables (i.

e. V =Σ

). Put the following partial order, ,onthesetO∪V∪{=, #}:

1. ∀ a, b ∈O∪Vwe have a  b ⇐⇒ a = b.

2. ∀ a ∈Owe have a =.

3. ∀ a ∈O∪Vwe have a  #.

4. ==, #  # and = #.

We shall also write a  b to mean b  a.

It is easy to see that  is, indeed a partial order. Moreover, every collection of elem e nts

of O∪V∪{=, #} has the least upper bound under . We are now ready to deﬁne the

partial order relation on the set o f all Poli hyperschemata:

Deﬁnition 4.6.4 Let t

and t

denote two Poli hyperschemata. We say that t

≥ t

and only if the following two conditions are satisﬁed:

1. the tree corresponding to t

when all of the labels are deleted is a subtree of the

tree corresponding to t

with all of the labels deleted.

2. Every one of the labels (which represents an operation or a variable) of t

is 

the label o f the node in the corresponding position of t

25 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Example 4.6.2 For instance, the hyperschema t

=(+(=(#,x)), ∗(sin(y), #)) ≥

= (+(+(∗(sin(x),y),x)), ∗(sin(y), = (#))). Indeed, the parse trees of t

and t

appear on the picture below:

When all the labels in the dashed subtree of the parse tree of t

are deleted one gets

the tree isomorphic to that obtained from t

by deleting all the labels. Thus condition 1

of deﬁnition 4.6.4 is satisﬁed. To see that condition 2 is fulﬁlled as well, we notice th at

the labels of t

are  to the corresponding labels of the dashed subtree of t

: Indeed,

we have +  +, = +, ∗∗, # ∗, x  x, sin  sin, # = and y  y.

Again it is easy to check that ≥ is, indeed, a partial order relation on th e collection of

Poli hyperschemata. Proposition 4.6.1 below tells us even more:

Proposition 4.6.1 Any given collection of Poli h yperschemata has the least upper

bound under ≥.

Proof: Denote by S a given collection of Poli hyperschemata. We provide an algo-

rithm to construct the least upper bound of S as follows: Copies of all the trees in S are

recursively jointly traversed starting from the root nodes to identify the parts with the

same shape, i. e. the same arity in the nodes visited. Recursion is stopped as soon as

an arity mismatch between corresponding nodes in some two trees from S is present.

All the nodes and links encountered are stored. This way we obtain a tree. It remains

to stick in the labels. Each one of the interior nodes is labeled by the least upper bound

of the corresponding labels of the trees in S. The label of a leaf node is a variable, say

x, if all the labels of the corresponding nodes of the trees in S are x (which implies

that they are leaf nodes themselves). In all other cases the label of the leaf node is the

# sign. It is not hard to see that this produces the least upper bound of the collection

S of parse trees.

It was pointed out before, that programs themselves are Poli hyperschemata. The fol-

lowing fact is almost immediate from the explicit construction of the least upper bound

carried out in the proof of proposition 4.6.1:

Proposition 4.6.2 A given Poli hypersch ema t is the least upper bound of the set S

programs determined by t.

26 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

From proposition 4.6.2 it follows easily that ≥ is order isomorphic to the collection of

subsets determined by the Poli hyperschemata:

Proposition 4.6.3 Let t and s denote Poli hyperschemata. Denote by S

and S

the

subsets of the search space determined by the hyperschemata t and s respectively.

Then t ≥ s ⇐⇒ S

⊇ S

There is another type of schemata which is useful to introduce in order to deﬁne the

family of reproduction (crossover) transformations:

Deﬁnition 4.6.5 A shape schema is just a rooted ordered tree. If

t is a given shape

schema then S

is just the set of all programs whose underlying tree when all the

labels are deleted is precisely

t. Given a Poli hyperschema s, we shall denote by ˜s the

underlying shape schema of s, i. e. the tree obtained by deleting all the labels in s.

The notion of a common region which is equivalent to the one deﬁned below also

appears in [11]:

Deﬁnition 4.6.6 Given two Poli hyperschemata t and s we deﬁne their c ommon region

to be the underlying shape schema of the least upper bound of t and s.

Deﬁnition 4.6.7 Fix a shape schema

t. We shall say that the set C

= {(a, b) | a, b are

program trees and

t is the common region of a and b} is a component corresponding

to the shape

Notice that sets determined by the shape schemata partition the search space:

Remark 4.6.1 Notice that Ω



t is a shape

. Moreover, C

∩C

˜s

= ∅ for t = s.(This

is so because least upper bounds in a poset are uniquely determined and so the function

sending (a, b) → sup(a, b) → the underlying shape of sup(a, b) is well deﬁned. But

then the sets C

are simply the pre-images under this function of the individual shape

schemata and, hence, form a partition of Ω

We now proceed to deﬁne the family of reproduction transformations. Our goal is to

introduce a family of functions on Ω

in such a way that each one of them is easily seen

to be bijective (see theorem 4.5.2, deﬁnition 4.5.2 , deﬁnition 4.5.3 and remar k 4.5.2 ) .

Theideaistodeﬁne these transformations on each of the components ﬁrst:

Deﬁnition 4.6.8 Fix a shape schema

t. Fix a node, v of

t. A one-point partial ho-

mologous crossover transformation T

: C

→ C

is deﬁned as follows: For given

(a, b) ∈ C

let T

(a, b)=(c, d) where c and d are obtained from the program trees of

a and b as follows: First identify the node v in the parse trees of a and b respectively.

Now obtain the pair (c, d) by swapping the subtrees of a and b rooted at v. (This pro-

cedure is described in detail in [11] and it is also illustrated in the example below).

Let G

= {T

| v is a node of

t} denote the family of all partial homologous one-point

crossover transformations associated to the shape

The following example illustrates the concepts in deﬁnitions 4.6.5, 4.6.6 and 4.6.8:

27 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Example 4.6.3 In the upper left part of the picture parse trees of the two sample pro-

grams a and b are shown. Then on the upper right one can see the least upper bound

of a and b. On the lower right the underlying tree of the least upper bound of a and b

is drawn. According to deﬁnitio n 4.6.6, this tree is precisely the common region of the

programs a and b. The isomorphic subtrees inside both, a and b, are emphasized inside

the dashed areas:

A node v is selected inside the common region. The pair of children (c, d)=T

(a, b)

appears on the lower left of the picture above. The subtrees rooted at v which are

swapped during crossover are emphasized inside the dashed area.

Remark 4.6.2 One does need to show that for (a, b) ∈ C

we have T

(a, b) ∈ C

A rigorous argument can be given as follows: Clearly T

: C

→



t is a shape

is a

well-deﬁned map. Moreover, since v is a node of the least upper bound of a and b and

the pair (c, d) is obtained simply by swapping the corresponding subtrees rooted at

v,wegets =sup{c, d}≤sup{a, b}. Now consider the transformation F

: C

˜s

→



t is a shape

and notice that, by deﬁnition, we have F

(c, d)=(a, b).Butthen,

according to the reasoning above, we have sup{c, d}≤sup{a, b}. Thereby, we get

sup{c, d}≤sup{a, b}≤sup{c, d} =⇒ sup{c, d} =sup{ a, b} =⇒

t =˜s.This

shows that T

does, indeed, map into C

˜v

. Moreover, in the process, we have also

observed a couple of very important facts:

1. T

◦ T

= 1

where 1

denotes the identity map on C

. This shows, in

particular, that T

is a bijection.

2. T

preserves the least upper bounds: sup{a, b} =supT

(a, b).

We ar e ﬁnally ready to deﬁne the family of reproduction transformations on the search

space Ω of all programs:

Deﬁnition 4.6.9 For every shape schema

t ﬁx a node v

t.Deﬁne a one point

crossover transformation T

}

is a shape schema

:Ω

→ Ω

to be the set-theoretic union

of all partial crossover transformations of the form T

. More explicitly, this means

that whenever a given pair (a, b) ∈ Ω

we must have (a, b) ∈ C

˜s

for a unique shape

schema ˜s (since, a ccording to remark 4.6.1, Ω

is a disjoint union of components cor-

responding to various shapes). But then T

}

t is a shape schema

(a, b)=T

˜s

(a, b). Denote by

28 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

G the family of all crossover transformations together with the id entity map on Ω

.For

simplicity of notation we shall denote the transformations in G by plain English letters:

T , F etc., keeping in mind that every such transformation is determined by making

choices of partial crossover transformations on every one of the components.

Remark 4.6.3 Thanks to remark 4.6.2, every one of the crossover transformations in

the family G is bijective (since it is a union of bijections on the pieces of a partition). It

follows now that the generalized Geiringer theorem (theorem 4.5.2) applies to the case

of homologous GP.

Remark 4.6.4 It is also possible to model uniform GP crossover (this type of crossover

is examined in detail in [11]) in the analogous manner. All o f the results established in

the current paper apply to this case without any modiﬁcation.

4.7 The Statement of the Schema-Based Version of Geiringer’s

Theorem for Non-linear GP under Homologous Crossover.

As mentioned before, the schema-based version of Geiringer’s theorem for non-linear

GP is stated in terms of Poli hyperschemata.

Deﬁnition 4.7.1 A Poli hyperschema of order i is a Poli hyperschema which has ex-

actly i nodes whose label is not a # or an = sign.

Aconﬁguration schema is a 0-order Poli hyperschema (i.e a hyperschema which

has only the equal signs in the interior nodes and # signs in the leaf nodes.)

An operation schema is a Poli hyperschema of order 1 (i. e. a hyperschema which

has exactly one node whose label is not a # or an = sign).

Fix an individual (a parse tree) u ∈ Ω.Letv denote any node of u.LetB(v)

denote the branch of the shape schema of u from the root down to the node v.Let

(v)=B(v) ∪{w | w is a child of some node z of B with z = v}. Now deﬁne cs(v)

to be the conﬁguration schema whose underlying shape schema is B

(v).Leto denote

an operation or a variable (an element of Σ

for some i between 0 and N ). Now obtain

the operation schema os

from cs(v) by attaching the node labelled by o in place of the

# sign at the node corresponding to v of cs(v).Unlessv is the leaf node of u, all the

children of this new node are the leaf nodes of os

labelled by the # sign. When o is

the operation (or the variable) labelling the node v of u, we shall write os(v) instead

of os

Notice that if v is a root node then cs(v) is just the schema which determines the entire

search space, i. e. the parse tree consisting of a single node labelled b y the # sign.

Example 4.7.1 illustrates deﬁnition 4.7.1.

Example 4.7.1 Below we list all of the conﬁguration schemata and operation schemata

for the individual of example 4.6.1:

29 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Recall from deﬁnition 4.5.5 that X (P, S) denotes the number of individuals in the

population P which are the elements of S ⊆ Ω. The following deﬁnition makes it

more convenient to state the schema-based version of Geiringer’s theorem:

Deﬁnition 4.7.2 Given a Poli hyperschema H, we shall write |H(P )| in place of

X (P, S

) (see deﬁnition 4.6.2) to denote the number of individuals (counting repe-

titions) in the population P ﬁtting the hyperschema H.

We can now ﬁnally state the Geiringer’s theorem for non-linear GP under homologous

crossover:

Theorem 4.7.1 Fix an initial population P ∈ Ω

and an individual u ∈ Ω. Suppose

every pair of individuals has a positive probability to be paired u p for crossover and

30 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

every transformation in G has a positive probability of being chosen

. Then the limiting

frequency of occurrence of a given individual u,

lim

t→∞

Φ(u,P,t)=



v is a node of u

|os(v)(P )|

|cs(v)(P)|

Example 4.7.2 To illustrate how theorem 4.7.1 can b e applied in practice, suppose

we are interested in computing the frequency of encountering the individual u from

examples 4.6.1 and 4.7.1 when the initial population of 6 individuals pictured below is

chosen:

The number of individuals in P ﬁtting the operation schema os(v

) is 2 (these are

and x

) while every individual ﬁts the con ﬁguration schema cs(v

). Therefore

|os(v

)(P )|

|cs(v

)(P )|

. 4 individuals, namely x

, x

and x

ﬁt cs(v

)=cs(v

among these only 2 individuals, namely x

and x

, ﬁt os(v

) and 2 individuals, x

and

ﬁt os(v

) so that

|os(v

)(P )|

|cs(v

)(P )|

|os(v

)(P )|

|cs(v

)(P )|

. Individuals x

, x

and x

ﬁt

the conﬁguration schema cs(v

) while only x

ﬁts the operation schema os(v

) so that

|os(v

)(P )|

|cs(v

)(P )|

. x

, x

and x

ﬁt cs(v

)=cs(v

). Among these only x

and x

ﬁt os(v

) while only x

ﬁts os(v

) so that

|os(v

)(P )|

|cs(v

)(P )|

and

|os(v

)(P )|

|cs(v

)(P )|

Thereby, according to theorem 4.7.1, we obtain:

lim

t→∞

Φ(u,P,t)=



i=1

|os(v

)(P )|

|cs(v

)(P )|

288

Roughly speaking, this means that if we run GP starting with the population P pictured

above, in the absence of mutation and selection (crossover being the only step) for an

inﬁnitely long time, the individual u will be encountered on average 1 out of 288 times.

These conditions can be slightly relaxed, but we try to present the main idea only

31 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Example 4.7.3 Notice that linear GP (or, equivalently, variable length GA) as de-

scribed in [12] is a special case of nonlinear GP when ∀ i>1Σ

= ∅ and Σ

and

= ∅. Indeed, the elements of such a search space are parse trees such that every

interior node has exactly one child and the depth of the tree is bounded by some integer

N. One can think of such a tree as a sequence of labels (a

,...,a

),theﬁrst la-

bel afﬁliated with the root node, second label with the child of the root node and so on.

The label a

is afﬁliated with the leaf node. This gives us a one-to-one correspondence,

call it φ between the search space for nonlinear GP in our speciﬁccasewhen∀ i>1

= ∅ while Σ

and Σ

= ∅ and the search space for linear GP which preserves

crossover. The following types of schemata have been introduced in [12]:

Deﬁnition 4.7.3 The schema H =(∗

i−1

, #) represents the subset S

= {x =

,...,x

) | l>iand x

= h

}. In words, S

is simply the set of all individuals

whose length is at least i +1and whose i

allele is h

Deﬁnition 4.7.4 The schema H =(∗

, #) represents the subset

= {x =(x

,...,x

) | l>i}.

In word s, S

is simply the subset of all individuals whose length is at least i +1.

Deﬁnition 4.7.5 The schema H =(∗

i−1

) represents the subset

= {x =(x

,...,x

) | x

= h

}

of the search space which is simply the set of all individuals of length exactly equal to

i whose i

(last) allele is h

The reader may check that under the correspondence φ th e conﬁguration schemata

correspond to the schemata H

=(∗

, #) for i ≥ 1, operation schemata correspond

to the schemata of the form H =(∗

i−1

, #) and of the form H =(∗

i−1

) for

i>1. Finally, the hyperschema t

(1, 1)

corresponds to the schema H =(h

, #).

Fix a population P ∈ Ω

. Recall that we denote by |H| the number of individuals

in P whic h ﬁ t the schema H counting repetitio ns. Also recall from deﬁnition 4.5.6

that Φ(S

,P,1) =

|H|

denotes the fraction of the number of individuals of P which

ﬁt the schema H. To abbreviate the notation we shall write Φ(H, P, 1) instead of

Φ(S

,P,1). Fix an individual u =(h

,...,h

) ∈ Ω. Theorem 4.7.1 tells us

that

lim

t→∞

Φ(u,P,t)=

|(h

, #)|

· (

n−2



i=1

|(∗

i+1

, #)|

|(∗

, #)|

) ·

|(∗

n−1

|(∗

n−1

, #)|

|(h

, #)|

· (

n−2



i=1

|(∗

i+1

, #)|

|(∗

, #)|

) ·

|(∗

n−1

|(∗

n−1

, #)|

Φ(h

, #) · (

n−2



i=1

Φ(∗

i+1

, #)

Φ(∗

, #)

) ·

Φ(∗

n−1

)

Φ(∗

n−1

, #)

32 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

=Φ(∗

n−1

) ·



i=n−2

Φ(∗

i+1

, #)



i=n−1

Φ(∗

, #)

=Φ(∗

n−1

) ·

i=1



i=n−1

Φ(∗

i−1

, #)

Φ(∗

, #)

which is precisely the formula obtained in [12].

4.8 How Do We Obtain Theorem 4.7.1 from Theorem 4.5.2?

The following couple of corollaries from [5] are useful in obtaining the schema-based

versions of Geiringer theorem for various evolutionary algorithms. Throughout, we

shall d enote by 

[P ]

the uniform probability distribution on the set [P ]

(see deﬁni-

tion 4.5.4).

Corollary 4.8.1 Fix a bijective and self-transient algorithm A and an initial popula-

tion P ∈ Ω

.FixasetS of individuals in Ω (S ⊆ Ω). Then lim

t→∞

Φ(S, P, t)=



[P ]

(X (2,S)) (here E



[P ]

(f) denotes the expectation of the random variable

f with respect to the uniform distribution on the set [P ]

To state the next corollary which brings us one step closer to deriving results similar

in ﬂavor to Geiringer’s original theorem we need one more, purely formal, assumption

about the algorithm:

Deﬁnition 4.8.1 We say that a given algorithm A is regular if the following is true:

for every population P =(x

,...,x

) ∈ Ω

and for every permutation π ∈

, the population obtained by permuting the elements of P by π, namely π(P)=

π(1)

π(2)

,...,x

π(m)

) ∈ [P ]

. In words this says that the equivalence classes

[P ]

are permutation invariant.

Remark 4.8.1 Deﬁnition 4.8.1 is only needed because our description of an evolu-

tionary search algorithm uses the ordered multi-set model. This makes the generalized

Geiringer theorem (theorem 4.5.2) look nice (the stationary distribution is uniform on

[P ]

). A disadvantage of the multi-set model is that it allows algorithms which are not

regular. If we were to use the model of [22] where the order of elements in a population

is not taken into account (a reasonable assumption since most evolutionary algorithms

used in practice are, indeed, regular) then the Generalized Geiringer theorem would

have to be modiﬁed accordingly since the stationary distribution of the corresponding

Markov process would be different from uniform (it is not difﬁcult to compute it though

since the corresponding Markov chain is just a “projection” of the one used in the

current paper).

Corollary 4.8.2 Fix a regular bijective and self-transient algorithm A and an ini-

tial population P ∈ Ω

. Denote by 

[P ]

the uniform probability distribution on

[P ]

(see deﬁnition 4.5.4). Fix a set S of individuals in Ω (S ⊆ Ω). Then we have

lim

t→∞

Φ(S, P, t)=

[P ]

) where

= {P | P ∈ [P ]

and the 1

individual of P is an element o f S}.

Throughout the paper , wheneve r a limit is involved, the equality is meant to hold for almost every inﬁ nite

sequence of trials.

33 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Corollaries 4.8.1 and 4.8.2 are proved in section 6 of [5]. When d eriving schema-based

versions of Geiringer theorem for a speciﬁc algorithm the following strategy may be

implemented: Continuing with the notation in corollaries 4.8.1 and 4.8.2, suppose we

are given a nested sequence o f subsets of the search space: S

⊇ S

⊇ ... ⊇ S

According to corollary 4.8.2,

lim

t→∞

Φ(S

,P,t)=

[P ]

|[P ]

n−1

|[P ]

n−1

n−2

· ...·

|[P ]

= 

[P ]

) ·

n−2



j=0

n−j

n−j− 1



[P ]

(X (2,S)) ·

n−2



j=0

n−j

n−j− 1

Notice that

j−1

is just the proportion of populations in [P ]

whose ﬁrst individual

is a member of S

inside the set of populations in [P ]

whose ﬁrst individual is a

member of S

j−1

Corollary 4.8.3 Fix a regular, bijective and self-transient algorithm A and an ini-

tial population P ∈ Ω

. Fix a nested sequence of subsets S

⊇ S

⊇ ... ⊇ S

of individuals in Ω (S

⊆ Ω). Then lim

t→∞

Φ(S

,P,t)=



[P ]

(X (2,S)) ·



n−2

j=0

n−j

n−j− 1

where, as before, V

denotes the set of all populations whose ﬁrst

individual is a member of S for a given subset S ⊆ Ω.

Denote by A a given GP algorithm. Fix an individual u ∈ Ω. In order to apply

corollary 4.8.3, we may choose a descending chain of Poli hyperschemata t

≥ t

≥

...≥ t

= u. Fix an initial population P . To avoid putting many subscripts, we shall

write V

instead of V

for the set of all populations in [P ]

(see deﬁnition 4.4.1) whose

individual is a member of S

(the set of individuals determined by the hyperschema

t). In order to construct the desired sequence of nested hyperschemata, we assign the

following numerical labelling to the nodes of the parse tree of u: The nodes are labelled

by the pairs of integer coordinates. The ﬁrst coordinate shows the depth of the tree and

the second coordinate shows how far to the right a given node at the depth speciﬁed by

the ﬁrst coordinate is located. Notice, for instance, that the root node is labelled by the

coordinates (1, 1). We also introduce the following lexicographic linear ordering on

the set of coordinate pairs:

Deﬁnition 4.8.2 (a, b) ≤ (c, d) if and only if either a ≤ c or (a = c and b ≤ d).

It is well known and easy to verify that this deﬁnes a linear ordering.

Deﬁnition 4.8.3 Given a pair of coordinates (i, j), denote by ↑ (i, j) the immediate

successor of (i, j) under the lexicographic ordering deﬁned above. Explicitly,

↑ (i, j)=



(i +1, 1) if (i, j) labels the rightmost node of u at depth i

(i, j +1)otherwise

34 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

We obtain the desired nested sequence o f hyperschemata for the given individual u

recursively in the following manner:

Deﬁnition 4.8.4 Deﬁne t

(1,1)

to be the hyperschema whose root node has the same

label (operation) and arity as that of the root node of u. All children of the root node

are the leaf nodes labelled by the # sign. Once the hyperschema t

(i,j)

has been con-

structed, we obtain the hyperschema t

↑(i,j)

by attaching the node of u with coordinate

↑ (i, j) in place of the # sign at coordinate ↑ (i, j) to the parse tree of t

(i,j)

.Unless

this node, call it v, is a leaf node of u, all children of this new node are the leaf nodes

of t

↑(i,j)

labelled by the # sign.

We illustrate the co nstruction with an explicit exam ple:

Example 4.8.1 Below, the nested sequence t

(1, 1)

≥ t

(2, 1)

≥ t

(2, 2)

≥ t

(3, 1)

, ≥

(3, 2)

≥ t

(3, 3)

corresponding to the program of example 4.6.1 is drawn explicitly:

The formula for the limiting frequency of occurrence of a given program u in corol-

lary 4.8.3 involves the ratios of the form

↑(i, j)

(i, j)

. It turns out that these ratios can

be expressed nicely in terms of the presence of certain conﬁguration and operation

schemata in the initial population P :

Deﬁnition 4.8.5 Given a program tree u and the corresponding nested sequence t

(1, 1)

≥

(2, 1)

≥ ... ≥ t

(i, j)

≥ t

↑(i, j)

, ≥ ... ≥ t

(l, k)

= u of hyperschemata as in deﬁni-

tion 4.8.4, for every (i, j) =(l, k), denote by cs

(i, j)

(os

(i, j)

)theconﬁguration schema

cs(v) (operation schema os(v))wherev is the node of u with coordinate ↑ (i, j).

Example 4.8.2 Continuing with examples 4.6.1 and 4.7.1 notice that for the individual

in these examples we have cs

(1,1)

= cs

(2,1)

= cs(v

)=cs(v

) while os

(1,1)

= os(v

)

and os

(2,1)

= os(v

) (see example 4.7.1), cs

(2,2)

= cs(v

) while os

(2,2)

= os(v

) and

(3,1)

= cs

(3,2)

= cs(v

)=cs(v

) while os

(3,1)

= os(v

) and os

(3,2)

= os(v

The following “orbit description” lemma is the reason for introducing conﬁguration

and operation schemata: We prove the lemma under the following special assumption:

35 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Deﬁnition 4.8.6 We say that a population P is special with respect to the individual u

if for every node v of u and for every operation (or variable) o we have |os

(P )|≤1

where os

is obtained from cs(v) by means of attaching the operation o at the leaf node

of cs(v) corresponding to v as described in deﬁnition 4.7.1.

Deﬁnition 4.8.6 basically requires that no 2 operations (or variables) occurring in P

at the speciﬁed location are the same. It turns out that the orbit description lemma

stated below is a lot more convenient to prove under this special assumption. The

general case will then follow by introducing enough extra labels for the operations and

variables involved and then deleting the extra labels.

Lemma 4.8.4 Fix a n initial population P and a program u ∈ Ω Assume that the

population P is special with resp ect to the individual u. Suppose every pair of individ-

uals has a positive probability to be paired up for crossover and every transformation

in G has a positive probability of being chosen

. Consider the sequences of hyper-

schemata t

(1, 1)

≥ t

(2, 1)

≥ ... ≥ t

(i, j)

≥ t

↑(i, j)

, ≥ ... ≥ t

(l, k)

= u, {cs

(i, j)

| (i, j)

is a coordinate of u, (i, j) is not the maximal coordinate } and {os

(i, j)

| (i, j) is a

coordinate of u, (i, j) is not the maximal coordinate } corresponding to the individ-

ual u. For a given hypersch ema t, denote by |t(P )| the number of individuals in P

which ﬁt the hyperschema t counting repetitions. Suppose ∀ non-maximal pairs of co-

ordinates (i, j) we have |os

(i, j)

(P )| =0and |t

(1, 1)

(P )| =0. Then it is true that

∀ (i, j)

↑(i, j)

(i, j)

|cs

(i, j)

(P )|

Proof: The key idea is to observe the following fact:

Claim: Fix a coordinate (i, j). Fix any two operation schemata os

and os

which

are obtained from cs

(i, j)

by attaching either a variable or an operation at the node

(i, j). Suppose ∃ individuals in P ﬁtting both, os

and os

.Then|V

(i, j)

∩V

| =

(i, j)

∩V

|. Proof: Consider the map F :[P ]

→ [P ]

deﬁned as follows:

Given a population, say Q ∈ [P ]

, notice that ∃ an individual, say x

,inQ ﬁtting

the oper ation schema os

(due to the way crossover is deﬁned, the number of individ-

uals ﬁtting the operation schema os

(Q) is the same in every population Q ∈ [P ]

Moreover, such an individual is unique since we assumed that all operations appearing

in the individuals of P are distinct. Likewise, ∃ unique individual in Q,sayx

ﬁtting

the operation schema os

. Pair up individuals x

and x

and pair up the rest of the

individuals arbitrarily for crossover. Select the cro ssover tra nsformation T

where v

is the node with coordinate (i, j) for the pair (x

, x

) and choose the identity trans-

formation for the rest of th e pairs. Now let F (Q) be the population obtained upon

the completion of the reproduction step described above (notice that F (Q) ∈ [P ]

deﬁnition of [P ]

). Notice also that F is its own inverse (i. e. F ◦ F = 1

[P ]

). This

tells us, in particular, that F is bijective. Moreover, it is clear from the deﬁnitions that

F (V

(i, j)

∩V

) ⊆V

(i, j)

∩V

and, likewise, F (V

(i, j)

∩V

) ⊆V

(i, j)

∩V

The desired conclusion follows at once.

Now observe that t

↑(i, j)

= t

(i, j)

∩ os

(i, j)

so that V

↑(i, j)

= V

(i, j)

∩V

(i, j)

and

(i, j)



o is an operation or a variable

(i, j)

∩ os

) where os

is obtained from cs

(i, j)

These conditions can be slightly relaxed, but we try to present the main idea only

36 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

attaching the operation (or variable) o at the node ↑ (i, j). Therefore we also have

(i, j)



o is an operation or a variable,

(i, j)

∩V

). Since operations can not appear or

disappear from a population during crossover, V

= ∅ =⇒∃an individual in P

ﬁtting th e operation schema os

. Thus the only sets of the form V

(i, j)

∩V

which

may possibly contribute to the union above are these for which ∃ an individual in P

ﬁtting the operation schema os

. According to the claim above, all such sets contribute

exactly the same amount. Moreover, by assumption os

(i, j)

(P ) = ∅, and so we have

(i, j)

| = n ·|V

(i, j)

∩V

(i, j)

| = n ·|V

(i, j)

∩os

(i, j)

| = n ·|V

↑(i, j)

| =⇒

↑(i, j)

(i, j)

where n is the number of operation schemata of the form os

which are obtained from

(i, j)

by attaching a variable or an operation at the node with coordinate (i, j) and

for which ∃ an individual in P ﬁtting the operation schema os

and the last implica-

tion holds under the condition that |V

(i, j)

| =0. This condition is, indeed satisﬁed.

(Suppose not. Let (a, b) denote the smallest coordinate such that |V

(a, b)

| =0. Notice

that (a, b) =(1, 1) since |V

(1, 1)

| =0. (By assumption ∃ an individual, say x,inP

ﬁtting the hyperschema t

(1, 1)

.Evenifx is not the 1

individual of P , by perform-

ing crossover of x with the 1

individual of P at the root node one gets a population

Q ∈V

(1, 1)

.) But then (a, b)=↑ (i, j) for some coordinate (i, j) and according to the

equation above we have |V

(i, j)

| = n ·|V

↑(i, j)

| = n ·|V

(a, b)

| =0which contradicts

the minimality of the coordinate (a, b). So we conclude that |V

(i, j)

| =0) Thereby

we have

↑(i, j)

(i, j)

.Butcs

(i, j)



o is an operation or a variable

=⇒ cs

(i, j)

(P )=



o is an operation or a variable

(P ). Since we assumed that all of the operations and vari-

ables ar e d istinct, ∃ at most one individual in P ﬁtting the operation schema os

and it

now follows that |cs

(i, j)

(P )| = the number of operation schemata of the form os

such

that os

(P ) = ∅ which is pr ecisely the number n.Weﬁnally obtain

↑(i, j)

(i, j)

|cs

(i, j)

which is precisely the conclu sion of the lemma.

Remark 4.8.2 Given an individual u and a population P consisting of m individuals,

observe that the number of individuals ﬁtting the hyperschema t

(1, 1)

is the same in

every population from [P ]

,i.e.∀ Q ∈ [P ]

we have |t

(1, 1)

(Q)| = |t

(1, 1)

(P )| =1.

It follows immediately now that



[P ]

(X (2,S

(1, 1)

)) =

We now combine corollary 4.8.3, remark 4.8.2 and lemma 4.8.4 to obtain the following

special case of Geiringer theorem for nonlinear GP under homologous crossover in case

when all of the operations appearing in the individuals of the initial population P are

distinct:

lim

t→∞

Φ(u,P,t)=



(i, j) is not the maximal coordinate of u

|cs

(i, j)

(P )|



v is a node of u

|cs(v)(P)|

(recall that when v is the root node of u, cs(v) determines the entire search space, and

|cs(v)(P )|

) To obtain the general case, suppose we are given an initial popula-

tion P . For every node v of u consider the set of operations O(v)={o ||os

(P )|≥

37 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

1 wh ere os

is obtained from cs(v) as in deﬁnition 4.7.1}. For every Moreover, for ev-

ery operation (or variable) o ∈O(v) let x

, x

,...,x

|os

(P )|

denote an enumeration

of the individuals in P ﬁtting the operation schema os

(P ). Relabel the operation o

occurring in the node v of x

by the formally different operation (o, i) (i.e.bythe

ordered pair (o, i) whose ﬁrst element is the operation o itself and the second element

is the index telling us in which individual of P the operation o labels the node v). Af-

ter all of the relabelling is complete we obtain a new population P



which is special

with respect to the individual u in the sense of deﬁnition 4.8.6. Formally speaking,

we expand our signature Σ=(Σ

, Σ

,...,Σ

) as in deﬁnition 4.6.1 by adding the

operations (variables) (o, i) into Σ

where j is the arity of the operation o.Thisgives

us a new signature Σ

∗

=(Σ

∗

, Σ

∗

,...,Σ

∗

) where

∗

= {o | o ∈ Σ

and o/∈



v is a node of u

O(v)}∪

∪{(o, i) | o ∈O(v) for some v and 1 ≤ i ≤|os

(P )|}.

Denote by Ω

∗

the search space induced by the signature Σ

∗

. The natural projection

maps p

:Σ

∗

→ Σ

sending 0 → o when o/∈



v is a node of u

O(v) and (o, i) →

o when o ∈O(v) for some node v of u, induce the natural “deletion of the extra

labels” p rojection of the search spaces ϕ :Ω

∗

→ Ω where the individual ϕ(w) ∈ Ω is

obtained from the individual w ∈ Ω

∗

by replacing the label of every node w of w with

(w) where j is the arity of the node w. It is easily seen that the natural projection

ϕ commutes with the crossover transfo rmations in the sense that for any individuals

x, y ∈ Ω

∗

and for any crossover transformation T ∈G(see deﬁnition 4.6.9) we have

ϕ(T (x, y)) = T (ϕ(x),ϕ(y)).

Notice also that the population P can be obtained

from the population P



by applying the n atural projection ϕ to every individual of P



Therefore, running the algorithm with the initial population P is the same thing as

running the algorithm with the initial population P



and reading the output by applying

the natural projection ϕ. The special case does apply to the population P



, as mentioned

above, and so we have

lim

t→∞

Φ(u,P,t)=



w∈ϕ

−1

(u)

lim

t→∞

Φ(w,P,t)=



w∈ϕ

−1

(u)



v is a node of w

|cs(v)(P)|

Notice that w ∈ ϕ

−1

(u) precisely when the underlying shape schema of w is the

same as that of u, call this shape schema t

, and the label of every node v of w is

(o, i) where o is the label of the node v of u. According to the way the population P



was introduced, there are precisely |os(v)(P)| such labels (see also deﬁnition 4.7.1).

We can then identify the preimage ϕ

−1

(u) with the set



j=1

{i | 1 ≤ i ≤|os(v

)|}

of ordered K-tuples of integers where K is the number of nodes in the parse tree of

u and v

, v

,...,v

is any ﬁxed enumeration of the nodes of u, in the following

manner: The identiﬁcation map ı :



j=1

{i | 1 ≤ i ≤|os(v

)(P )|} → ϕ

−1

(u) sends

a given ordered K-tuple (i

,...,i

) into the tree w = ı((i

,...,i

)) whose

Of course, formally speaking, the two transformations T inv olved in the equation above are distinct,

as they have different domains (Ω

∗

and Ω respectively), but they are determined by the same set of shape

schemata and the same choice of nodes for crosso ver so we denote them by the same symbol.

38 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

underlying shape schema is t

and the label of a node v

of w is (o

) where o

the label of the node v

in the parse tree of u.Weﬁnally obtain:

lim

t→∞

Φ(u,P,t)=



w∈ϕ

−1

(u)



v is a node of w

|cs(v)(P)|



,...i

)∈

j=1

{i | 1≤i≤|os(v

)|}



v is a node of u

|cs(v)(P)|

|os(v

)(P )|



|os(v

)(P )|



...

|os(v

)(P )|





v is a node of u

|cs(v)(P)|



j=1

|os(v

)(P )|



|cs(v

)(P )|



v is a node of u

|os(v)(P )|

|cs(v)(P)|

which is precisely the assertion of theorem 4.7.1.

4.9 What Does Theorem 4.5.2 Tell Us in the Presence of

Mutation for Nonlinear GP?

In general, mutation is an elementary step of type 2 (see deﬁnition 4.2.5) which is de-

termined by the reproduction 1-tuple of the form (Ω, M,p, ℘

) where M is a family

of functions on Ω. Notice that the set of partitions of the set of m elements into 1-

element subsets consists of exactly one element – the partition into the singletons. This

forces ℘

to be the tr ivial probability distribution. We shall, therefore, omit it from

writing:

Deﬁnition 4.9.1 A mutation 1-tuple is a reproduction 1-tuple (Ω, M,p) where M

consists of functions on Ω and 1

∈M.(Here1

:Ω→ Ω denotes the identity map.)

An ergodic mutation 1-tuple is a mutation 1-tuple (Ω, M,p) such that ∀ x, and y ∈

Ω ∃ M ∈Mwith M (x)=y and p(M) > 0.

The following fact is a rather simple consequence of theorem 4.5.2 (see corollaries 7.1

and 7.2 of [5]):

Corollary 4.9.1 Let A denote a bijective and self-transient algorithm which involves

an elementary step determined by an ergodic mutation. Then the Markov chain asso-

ciated to the algorithm A is irreducible and the unique stationary distribution of this

Markov chain is uniform. In particular, the limiting frequency of occurrence of any

given individual x is lim

t→∞

Φ({x},P,t)=

|Ω|

(see deﬁnition 4.5.6 for the meanin g

of Φ({x},P,t)).

When dealing with nonlinear GP, depending on the circumstances, one may want to

consider different types of mutation. Below we deﬁne one such possible mutation:

39 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Deﬁnition 4.9.2 Let Ω denote the search space for nonlinear GP over the signature

Σ=(Σ

, Σ

,...,Σ

) where Σ

’s ar e ﬁnite sets (see deﬁnition 4.6.1). Consider

aconﬁguration schema t and a node v of t.Leti denote the arity of the node v and

let π denote a permutation of Σ

.Wedeﬁne a node mutation transformation M

t, v, π

Ω → Ω to be the function which sends a given program tree u which ﬁts the schema t

to the program M

t, v, π

(u) obtained from u by replacing the label a ∈ Σ

of the node v

of u with π(a) whenever u ﬁts the conﬁguration schema t (if u does not ﬁt the schema

t then M

t, v, π

(u)=u). We deﬁne the family of node mutations

node

= {M

t, v, π

:Ω→ Ω | π ∈S

where t is a conﬁguration schema and

i is the arity of the node v of t}.

As usual S

denotes the set of all permutations of the set X. Denote by Ω

NodeMut

(Ω, M

node

,p) the corresponding mutation 1-tuple.

Although node mutation described in deﬁnition 4.9.2 above is not ergodic in the sense

of deﬁnition 4.9.1, it deﬁnes a bijective elementary step (see deﬁnition 4.5.3) . Indeed,

it is easy to see that the transformation M

t, v, π

−1

is a 2-sided inverse of the trans-

formation M

t, v, π

. Thereby theorem 4.5.2 applies to nonlinear GP with homologous

crossover and node mutation. It is also possible to derive a formula for the limiting

frequency of occurrence of a given individual u, namely lim

t→∞

Φ(u,P,t) much in

the same way as in theorem 4.7.1. In order to state the corresponding result for non-

linear GP with homologous crossover and node mutation, it is convenient to introduce

the following deﬁnitions ﬁrst:

Deﬁnition 4.9.3 Fix an individual u ∈ Ω.Letv denote a node of u and consider

the conﬁguration schema cs(↑ v, i) obtained from the conﬁguration schema cs(v) by

attaching a node of degree i together with it’s i children in p lace of the # sign at the

node corresponding to v of cs(v). The newly attached nodes are then labelled by the =

and # signs respectively. If the newly attached node is of arity 0 then it is a leaf node

labelled by the = sign

. Furthermore, write cs(↑ v, u) in place of cs(↑ v, i) when i

is the arity of the node v in u. Also denote by os(v, o) the operation schema obtained

from the conﬁguration schema cs(v) by attaching a node labelled by the operation o

together with its appropriate number of children in place of the # sign. The children

of the newly attached node (if there are any) a re labelled by the # signs.

Deﬁnition 4.9.4 Given a mutation 1-tuple (Ω, M,p),aconﬁguration schema t (see

deﬁnition 4.7.1), and a node v of t having arity i, denote by G(t, v) the group generated

by all the permutations π ∈ Σ

such that p(M

s, v, π

) > 0 for some conﬁguration

schema s such that the common region of s and t contains the node v. Fix an operation

a ∈ Σ

.Let

O(t, v, a)={ o ∈ Σ

|∃g ∈ G(t, v) with g · a = o}

denote the orbit of the operation a under the action of the group G(t, v).

Formally speaking, according to deﬁnition 4.7.1, cs(↑ v, i) is not alwa ys a Poli hyperschema since it

may contain a leaf node labelled by the = sign. However, such a schema also deﬁnes a subset of the search

space Ω in much the same way as Poli hyperschemata. The only difference is that a leaf node labelled by the

= sign can be replaced by a variable only. One can not attach a nontrivial program tree to it.

40 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Suppose we are given a population P of size m consisting of program trees from Ω.

Recall from deﬁnition 4.7.2 that we denote by |H(P )| the number of individuals in the

population P ﬁtting the schema H.

Theorem 4.9.2 Let A denote an algorithm determined by 2 elementary steps of type

2 one of which is determined by the node mutation (see deﬁnition 4.9.2) and the other

one by a homologous GP crossover. Suppose every one of the transformations in the

family G of GP homologous crossovers has a positive probability of being chosen.

Fix an individual (a program tree) u ∈ Ω and an initial population P .Leto(u,v)

denote the operation labelling the node v of the program tree u. Denote by

u the

conﬁguration schema obtained from the shape schema,

u,ofu (see deﬁnition 4.6.5) by

labelling all the interior nodes of u with the = signs and all the leaf nodes with the #

signs. Suppose that the probability distribution on the collection of node mutations is

such that whenever v is a node of u we have p(M

s, v, π

) > 0=⇒ s = cs(v) where as

before cs(v) is the conﬁguration schema of u corresponding to the node v.

Then we

have

lim

t→∞

Φ(u,P,t)=



v is a node of u



o∈O (

u,v,o(u,v))

|os(v, o)(P )|



i=0



o∈Σ

|os(v, o)(P )|·|O(

u,v,o)|

Proof: The proof of theorem 4.9.2 is very similar to the proof of theorem 4.7.1

and contains essentially no new ideas. We leave most of the details for the interested

reader as an exercise and p rovide only the rough outline: Just like theorem 4.7.1, the-

orem 4.9.4 follows from corollary 4.8.3 by considering the nested sequence of hyper-

schemata t

(1, 1)

≥ t

(2, 1)

≥ ... ≥ t

(i, j)

≥ t

↑(i, j)

≥ ... ≥ t

(l, k)

= u corresponding

to the program u (see deﬁnition 4.8.4). First we consider a special case when every

set Σ

consists of ordered p airs (l, o) where l is an integer, and mutation is allowed to

modify only the operation o and is not allowed to change the integer l. We then prove

theorem 4.9.2 in the special case when all the labels contained in the initial population

P have distinct ﬁrst coordinates. The general case then follows by introducing the ex-

tra integer labels for the ﬁrst coordinate, applying the special case and then “erasing

the integer part from the labels” in exactly the same way as it was done in the proof of

theorem 4.7.1. The main difference lies in the claim proved inside lemma 4.8.4. The

corresponding claim for the proof of theorem 4.9.2 then says the following:

Lemma 4.9.3 Fix a node v with coordinate (i, j). Fix any two operation schemata

os(a) and os(b) which are obtained from cs

(i, j)

by attaching either a v ariable or

an operation at the node with coordinate (i, j). Suppose ∃ individuals in P ﬁ tting

both, os(c) and os(d) where a ∈O(cs(i, j),v,c) and b ∈O(cs(i, j),v,d).Then

(i, j)

∩V

os(a)

| = |V

(i, j)

∩V

os(b)

Just like the claim inside of the lemma 4.8.4, lemma 4.9.3 is proved by constructing

an explicit bijection between the sets V

(i, j)

∩V

os(a)

and V

(i, j)

∩V

os(b)

, The only

difference is that these bijections make use of mutations as well as crossover.

Again we remark that this condition can be slightly relaxed but it does not introduce any new ideas of

interest.

Notice that this implies that O(

u,v,o(u,v))=O(cs(v),v,o(u,v))

41 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

It may b e worth mentioning that theorem 4.7.1 is a special case of theorem 4.9.2. In-

deed, if the only mutation tran sformations chosen with positive probability are these

which assign positive probability only to the mutations deﬁned by the identity per-

mutations, then every orbit O(

u,v,o) consists of exactly one element so that ∀ t and

v we have |O(

u,v,o)| =1. To compress the language, we shall use



to denote

the union of disjoint sets. We then have



o∈O (

u,v,o(u,v))

os(v, o)(P )=os(v)(P )

since o(u,v) is the only operation inside of O(

u,v,o(u,v)) so that os(v)(P ) is

the only contributor to the disjoint union above. Moreover, we also have cs(v)=



i=0



o∈Σ

os(v, o) so that we obtain



i=0



o∈Σ

|os(v, o)(P )|·|O(

u,v,o)| =



i=0



o∈Σ

|os(v, o)(P )|·1=|cs(v)(P)|.

The f ormula in theorem 4.9.2 now simpliﬁes to the o ne in theorem 4.7.1.

Example 4.9.1 Continuing with example 4.7.2, suppose the signature Σ is deﬁned as

follows: Σ=(Σ

, Σ

) where Σ

= {x, y, z, w}, Σ

= {sin, cos, tan, cot, ln}

and Σ

= {+, −, ∗, } where  is a binary operation symbol different from +, ∗ and

−. (Of course, the semantics of the binary operation  is irrelevan t to the c ontent of

this example, but if the reader feels more comfortable with a concrete interpretation,

they may assume, for instance, that x  y =



dξ.) Now suppose the individual u

is the program (+(ln(x), (x, y)) pictured below (with nodes being enumerated just

like in example 4.7.1) (it has the same shape schema as the individual in that example):

Notice that this individual has exactly the same set of conﬁguration schemata as the

corresponding set of conﬁguration schemata in example 4.7.1 (the reader may see these

conﬁguration schemata pictured in that example). Suppose that the following mutation

transformations are the only ones chosen with positive probability:

cs(v

),v

, (+, −)

cs(v

),v

, (∗, )

cs(v

),v

, (ln, sin, cos)(tan, cot)

cs(v

),v

, (tan, cot)(sin, cos)

cs(v

),v

, (ln, sin)

cs(v

),v

, (+, , ∗)

cs(v

),v

, (−, ∗)

cs(v

),v

, (x, w)(y,z)

cs(v

),v

, (+, ∗)(−, )

cs(v

),v

, (x, y, z)

cs(v

),v

, (+, −, ∗, )

cs(v

),v

, (x, w)(y,z)

, and

cs(v

),v

, (x, w)

cs(v

),v

, (sin, cos,tan,cot)

cs(v

),v

, (+, −)

Here we represent permu tations in terms of their “disjoint cycle decompo sitions”: for

example, (ln, sin, cos)(tan, cot) rep resents the permutation on Σ

which sends ln into

sin, sin into cos and cos back into ln. Likewise, it sends tan into cot and cot back into

42 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

tan. If a cycle has length one (i.e. the element appearing in the cycle is a ﬁxed point of

the corresponding permutation) we omit that cycle from writing. For example,  and ∗

are the ﬁxed points of the permutation (+, −). The corresponding permutation groups

are:

G(cs(v

),v

)=(+, −), (∗, ),

G(cs(v

),v

)=(ln, sin, cos)(tan, cot), (tan, cot)(sin, cos), (ln, sin),

G(cs(v

),v

)=(+, , ∗), (−, ∗),

G(cs(v

),v

)=(x, w)(y, z), (+, ∗)(−, ),

G(cs(v

),v

)=(x, y, z), (+, −, ∗, ), and

G(cs(v

),v

)=(x, w)(y, z), (x, w)(sin, cos, tan, cot), (+, − ).

The cycle decomposition makes it easy to compute the corresponding orbits:

O(cs(v

),v

, +) = {+, −}, O (cs(v

),v

, ln) = {ln, sin, cos},

O(cs(v

),v

, )={+, −, ∗, }, O (cs(v

),v

,x)={x, w},

O(cs(v

),v

,x)={x, y, z} and O(cs(v

),v

,y)={y, z} .

Now suppose the initial population is the same as in example 4.7.2. In ord er to apply

theorem 4.9.2, for every node v of u we need to compute the number |os(v, o)(P )|.

Recall that the schema os(v, o) is obtained from the schema os(v) by attaching the

operation o at the node v and labelling its children nodes b y the # signs. For the pop-

ulation P in example 4.7.2 it was already computed that |os(v

, +)| = |os(v

)| =2.

There are exactly 2 individuals (namely x

and x

) ﬁtting the schema os(v

, ∗) and

so |os(v

, ∗)| =2. Exactly one individual, namely x

, and one individual, namely

, ﬁt the schemata os(v

, sin) and os(v

, cos) respectively and so |os(v

, sin)| =

|os(v

, cos)| =1. For all the other operations o ∈ (Σ

∪ Σ

) −{+, ∗, sin, cos}

there are no individuals in P ﬁ tting the schema os(v

,o) and so we have |os(v

,o)| =

0. There are no individuals in P ﬁtting the schema os(v

, ln) = os(v

) for the

individual u of the current example, and no individuals ﬁtting the schemata of the

form os(v

,o) wher e o/∈{∗, sin, cos} so that for such o we have |os(v

,o)(P )| =

0. Moreover, there is exactly one individual, namely x

ﬁtting the schema os(v

, ∗)

and exactly one, namely x

ﬁtting the schema os(v

, cos) so that |os(v

, ∗)(P )| =

|os(v

, cos)(P )| =1; exactly two individuals, namely x

and x

ﬁt the schema

os(v

, sin) so that |os(v

, sin)(P )| =2. Continuing in this manner with the rest

of the nodes of u we obtain |os(v

,o)(P )| =0for o/∈{+, ∗}; x

and x

ﬁt

os(v

, +) while x

and x

ﬁt os(v

, +) and so |os(v

, +)(P )| = |os(v

, ∗)(P )| =2.

|os(v

,o)(P )| =0for o/∈{x, y, +}; x

is the only individual ﬁtting the schema

os(v

,y), x

is the only individual ﬁ tting the schema os(v

,x) and x

is the only indi-

vidual ﬁtting the schema os(v

, +) and so we have |os(v

,x)(P )| = |os(v

,y)(P )| =

|os(v

, +)(P )| =1. |os(v

,o)(P )| =0for o/∈{∗,x,y}; x

is the only individual

ﬁtting the schema os(v

, ∗) and x

is the only individual ﬁtting the schema os(v

,y)

while the individuals x

and x

are the only two which ﬁt the schema os(v

,x) so that

we have |os(v

, ∗)(P )| = |os(v

,y)(P )| =1and |os(v

,x)(P)| =2. |os(v

,o)(P )| =

43 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

0 for o/∈{sin,x,y}; moreover, x

is the only individual ﬁtting the schema os(v

, sin)

and x

is the only individual ﬁtting the schema os(v

,y) while the individuals x

and

are the only two which ﬁt the schema os(v

,x) so that we have |os(v

, sin)(P )| =

|os(v

,y)(P )| =1and |os(v

,x)(P)| =2.

Finally for every node v and for every operation o ∈ Σ

∪ Σ

such that

|os(v, o)(P )| =0we need to compute |O(

u,v,o)|. For the node v

these are

u,v

, +) = O(cs(v

),v

, +) = {+, −} so that |O(cs(v

),v

, +)| =2, and,

likewise, from the description of the groups G(cs(v

),v

) given above, it is easy to com-

pute that O(cs(v

),v

, ∗)={∗, }, O(cs(v

),v

, sin) = {sin} and O(cs(v

),v

, cos) =

{cos} so that

|O(cs(v

),v

, sin)| = |O(cs(v

),v

, cos)| =1.

O(cs(v

),v

, ∗)={∗}, O(cs(v

),v

, sin) = O(cs(v

),v

, cos) = {ln, sin, cos}

and so

|O(cs(v

),v

, sin)| = |O(cs(v

),v

, cos)| =3;

O(cs(v

),v

, ∗)=O(cs(v

),v

, +) = Σ

so that

|O(cs(v

),v

, ∗)| = |O(cs(v

),v

, +)| =4;

O(cs(v

),v

,x)={x, w} and O(cs(v

),v

,y)={y, z} so that

|O(cs(v

),v

,x)| = |O(cs(v

),v

,y)| =2;

O(cs(v

),v

, +) = {+, ∗} so that |O(cs(v

),v

, +)| =2; O(cs(v

),v

, ∗)=Σ

O(cs(v

),v

,x)=O(cs(v

),v

,y)={x, y, z} and so

|O(cs(v

),v

,x)| = |O(cs(v

),v

,y)| =3;

O(cs(v

),v

, sin) = {sin, cos, tan, cot}, O(cs(v

),v

,x)={x, w} and, ﬁ nally,

O(cs(v

),v

,y)={y, z} so that

|O(cs(v

),v

,x)| = |O(cs(v

),v

,y)| =2.

Now we are ready to compute the ratios of the form

o∈O(

u,v

,o(u,v

))

|os(v

,o)(P )|

i=0

o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|

From the data computed above we have



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

, +)(P )| + |os(v

, −)(P )| =2+0=2

and x

are the only two individuals in P which ﬁt the schema os(v

, +) while no

individual in P ﬁts os(v

, −));



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

, +)(P )|·|O(

u,v

, +)(P )|+

+|os(v

, sin)(P )|·|O(

u,v

, sin)(P )| + |os(v

, ∗)(P )|·|O(

u,v

, ∗)(P )|+

44 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

+|os(v

, cos)(P )|·|O(

u,v

, cos)(P)| =2· 2+1· 1+2· 2+1· 1=10

and so



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|

Continuing in this manner, we obtain



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

, ln)(P )| + |os(v

, sin)(P )|+

+|os(v

, cos)(P )| =0+2+1=3

and



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

, ∗)(P )|·|O(

u,v

, ∗)(P )|+

+|os(v

, sin)(P )|·|O(

u,v

, sin)(P )| + |os(v

, cos)(P)|·|O(

u,v

, cos)(P)| =

=1· 1+2· 3+1· 3=10

so that



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

, )(P )| + |os(v

, +)(P )|+

+|os(v

, −)(P )| + |os(v

, ∗)(P )| =0+2+0+2=4

and



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

, +)(P )|·|O(

u,v

, +)(P )|+

+|os(v

, ∗)(P )|·|O(

u,v

, ∗)(P )| =2· 4+2· 4=16

and so



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

,x)(P )| + |os(v

,w)(P )| =1+0=1

and



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

,y)(P )|·|O(

u,v

,y)|+

+|os(v

,x)(P)|·|O(

u,v

,x)|+|os(v

, +)(P )|·|O(

u,v

, +)| =1·2+1·2+1·2=6

45 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

and so



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

,x)(P)| + |os(v

,y)(P )|+

+|os(v

,z)(P )| =2+1+0=3

and



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

, ∗)(P )|·|O(

u,v

, ∗)|+

+|os(v

,x)(P)|·|O(

u,v

,x)|+|os(v

,y)(P )|·|O(

u,v

,y)| =1·4+2·3+1·3=13

and so



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|

Finally,



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )| = |os(v

,y)(P )| + |os(v

,z)(P )| =1+0=1

and



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)| = |os(v

, sin)(P )|·|O(

u,v

, sin)|+

+|os(v

,x)(P)|·|O(

u,v

,x)|+|os(v

,y)(P )|·|O(

u,v

,y)| =1·4+2·2+1·2=10

so that



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|

Now we ﬁnally compute the product of these ratios and obtain:

lim

t→∞

Φ(u,P,t)=



i=1



o∈O (

u,v

,o(u,v

))

|os(v

,o)(P )|



i=0



o∈Σ

|os(v

,o)(P )|·|O(

u,v

,o)|

52000

At the opposite extreme is the case when every mutation transformation in the family

node

has a positive probability of being chosen. In this case O(

u,v,o(u,v)) = Σ

where i is the arity of the operation o. In particular, for every operation o we have

o ∈O(

u,v,o(u,v)) if and only if o ∈ Σ

. But then we have



o∈O (

u,v,o(u,v))

os(v, o)=cs(↑ v, u)

46 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

and so



o∈O (

u,v,o(u,v))

|os(v, o)(P )| = |cs(↑ v, u)(P )|.

We also have



o∈Σ

os(v, o)=cs(↑ v, i) so that



o∈Σ

|os(v, o)(P )|·|O(

u,v,o)| = |Σ

|·



o∈Σ

|os(v, o)(P )| = |cs(↑ v, i)(P)|·|Σ

Combining these equations with theorem 4.9.2 we obtain:

Corollary 4.9.4 Let A denote an algorithm determined by 2 elementary steps of type 2

one of which is determined by the node mutation (see deﬁnition 4.9.2) and the other one

by a homologous GP crossover. Suppose every one of the transformations in the family

G of GP homologous crossovers has a positive probability of being chosen. Suppose

also that for every node v of u of arity i and for every permutation π of Σ

we have

p(M

u,v,π

)=p(M

cs(v),v,π

) > 0. Fix an individual (a progra m tree) u ∈ Ω and an

initial population P . Then we have

lim

t→∞

Φ(u,P,t)=



v is a node of u

|cs(↑ v, u)(P )|



i=0

|cs(↑ v, i)(P )|·|Σ

Example 4.9.2 Suppose the signature Σ=(Σ

, Σ

), the initial population P and

the individual u are exactly as in example 4.9.1. Now suppose, (unlike in example 4.9.1,

that for every permutation π of Σ

we have p(M

u,v,π

) > 0. Now corollary 4.9.4

applies and we can compute the frequency of occurrence of the individual u according

to the formula given there. To apply this formula we need to compute the numbers |cs(↑

,i)(P )| where 1 ≤ j ≤ 6 and 0 ≤ i ≤ 2 (the numbers |cs(↑ v, u)(P )| are among

these). The conﬁguration schemata cs(v

) for the individual u are exactly the same

as these for the individual of example 4.7.1 (since these two individuals have the same

underlying shape schema) and they are pictured in that example. Below we display

only these schemata |cs(↑ v

,i)(P )| for which |cs(↑ v

,i)(P )| =0. According to

deﬁnition 4.9.3 they are obtained from the corresponding schemata cs(v

) by attaching

a node which has i children (if i =0it has no children) in place of the # sign at the

node v

(which means that the # sign can be replaced with an arbitrary variable but

not with an operation symbol):

47 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

There are exactly 2 individuals, namely x

and x

in P ﬁtting the schema cs(↑ v

, 1)

so that |cs(↑ v

, 1)(P )| =2; x

, x

and x

are the only individuals in P which ﬁt

the schema cs(↑ v

, 2) = cs(↑ v

, u) so that |cs(↑ v

, 2)(P )| = |cs(↑ v

, u)(P )| =

4; x

, x

and x

are the only individuals in P which ﬁt the schema cs(↑ v

, 1) = cs(↑

, u) so that |cs(↑ v

, 1)(P )| = |cs(↑ v

, u)(P )| =3; x

is the only individual

ﬁtting the schema cs(↑ v

, 2) so that |cs(↑ v

, 2)(P )| =1; x

, x

and x

are

the only individuals in P which ﬁt the schema cs(↑ v

, 2) = cs(↑ v

, u) so that |cs(↑

, 2)(P )| = |cs(↑ v

, u)(P )| =4; x

and x

are the only individuals in P which ﬁt

the schema cs(↑ v

, 0) = cs(↑ v

, u) so that |cs(↑ v

, 0)(P )| = |cs(↑ v

, u)(P )| =

2; x

is the only individual ﬁtting the schema cs(↑ v

, 2) and so |cs(↑ v

, 2)(P )| =

1; x

, x

and x

are the only individuals in P ﬁtting the schemata cs(↑ v

, 0) =

cs(↑ v

, u) and/or cs(↑ v

, 0) = cs(↑ v

, u) and so we have |cs(↑ v

, 0)| = |cs(↑

, u)| = |cs(↑ v

, 0)| = |cs(↑ v

, u)| =3and x

is the only individual ﬁtting the

either and both schemata cs(↑ v

, 2) and/or cs(↑ v

, 1) so that |cs(↑ v

, 2)| = |cs(↑

, 1)| =1. From the deﬁnition of the signature Σ=(Σ

, Σ

) in example 4.9.1

we see that |Σ

| =4, |Σ

| =5and |Σ

| =4. We are now ready to compute the ratios:

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 2)(P )|·|Σ

| + |cs(↑ v

, 1)(P )|·|Σ

4 · 4+2· 5

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 2)(P )|·|Σ

| + |cs(↑ v

, 1)(P )|·|Σ

1 · 4+3· 5

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 2)(P )|·|Σ

4 · 4

48 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 0)(P )|·|Σ

| + |cs(↑ v

, 2)(P )|·|Σ

2 · 4+1· 4

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 0)(P )|·|Σ

| + |cs(↑ v

, 2)(P )|·|Σ

3 · 4+1· 4

|cs(↑ v

, u)(P )|



i=0

|cs(↑ v

,i)(P )|·|Σ

|cs(↑ v

, u)(P )|

|cs(↑ v

, 0)(P )|·|Σ

| + |cs(↑ v

, 1)(P )|·|Σ

3 · 4+1· 5

And now corollary 4.9.4 tells us that

lim

t→∞

Φ(u,P,t)=



i=1

|cs(↑ v

, u)(P )|



j=0

|cs(↑ v

,j)(P )|·|Σ

268736

It is possible to introduce mutation operators for nonlinear GP which are ergodic in the

sense of deﬁnition 4.9.1, but the easiest thing to do is probably ju st to deﬁne the family

erg

to be the family of all permutations of the search space Ω. The probability distri-

bution p must then be concentrated on any subset of M which satisﬁes the ergodicity

requirement of deﬁnition 4.9.1. This would en su re tha t corollary 4.9.1 applies.

4.10 What Can Be Said in the Presence of Selection in

the General Case?

Theorem 4.5.2 established in [5] which allows us to deduce r esults such as theo-

rems 4.7.1 and 4.9.2, applies only in the absence of selection. The theme of the re-

mainder of the current paper is to establish a few basic properties of the Markov chains

associated to evolutionary algorithms in the presence of ﬁtness-proportional selection

(as described in deﬁnition 4.2.2). Throughout the rest of the paper we shall break up

our algorithm, call it A into sub-algorithms and then consider their composition. This

idea will be made clear below:

49 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Proposition 4.10.1 Denote by A an evolutionary algorithm determined by the cycle

,...,s

).Fixi with 1 <i<nand let B and C denote the sub-algorithms deter-

mined by the cycles (s

,...,s

) and (s

i+1

,...,s

) respectively. Recall from

section 4.5 that {p

}

x,y∈Ω

, {p

}

x,y∈Ω

and {p

}

x,y∈Ω

denote the Markov

transition matrices associated to the algorithms A, B and C respectively. Then we

have

}

x,y∈Ω

= {p

}

x,y∈Ω

·{p

}

x,y∈Ω

where · denotes the usual matrix multip lication.

Proof: Denote by λ a probability distribution on Ω

. Completing a cycle of the

algorithm A amounts to completing a cycle of B and then completing a cycle of C.

The next generation probability distribution upon the completion of the cycle of B with

the input distribution λ is {p

}

x,y∈Ω

· λ. Likewise the next generation distribution

obtained upon the completion of a cycle of the algorithm C with the input distribution

}

x,y∈Ω

· λ is just

}

x,y∈Ω

· ({p

}

x,y∈Ω

· λ)=({ p

}

x,y∈Ω

·{p

}

x,y∈Ω

) · λ

which means that {p

}

x,y∈Ω

= {p

}

x,y∈Ω

·{p

}

x,y∈Ω

since the equation

above holds for an arbitrary input distribu tion λ.

We now proceed to study the effects of selection alone. First of all it is convenient to

observe the following general fact:

Deﬁnition 4.10.1 Let {p

}

x,y∈X

denote a Markov transition matrix on a ﬁnite set X .

Fix x ∈X.Wedeﬁne the transition support of x to be the set S(x)={z | p

> 0} of

all states z from which it is possible to get to x.

Deﬁnition 4.10.2 Let {p

}

x,y∈X

denote a Markov transition matrix on a ﬁnite set

X .Fixx and y ∈X. We say that y  x if S(y) ⊇ S(x) and ∀ z ∈ S(y) we have

≥ p

. Moreover, if either S(y)  S(x) or p

 p

for some z ∈ S(x) we

write y  x.

Proposition 4.10.2 below provides the reason for deﬁnitions 4.10.1 and 4.10.2:

Proposition 4.10.2 Let {p

}

x,y∈X

denote a Markov transition matrix on a ﬁnite set

X .Fixu and v ∈Xwith u  v and an input probability distribution λ on X .

Denote by ρ the output distribution (ρ = {p

}

x,y∈X

· λ). Then we have ρ(u) ≥ ρ(v).

Moreover, if u  v and λ(x) > 0 for every x ∈Xthen ρ(u)  ρ(v).

Proof: This is a straightforward veriﬁcation of the deﬁnitions:

ρ(u)=



z∈X

λ(z)p



z∈S(u)

λ(z)p





z∈S(v)

λ(z)p



z∈X

λ(z)p

= ρ(v)

where =



≥ if u  v

 if u  v

50 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

The following mild technical condition on a Markov transition matrix (which is easily

satisﬁable by most transition matrices modeling crossover and mutation) will extend

proposition 4.10.2.

Deﬁnition 4.10.3 We call a Markov transition matrix {q

}

x,y∈X

non-annihilating if

∀ y ∈X ∃x ∈Xsuch that q

> 0.

The main reason for introducing deﬁnition 4.10.3 is the following fact:

Proposition 4.10.3 A given Markov transition matrix {q

}

x,y∈X

is non-annihilating

if and only if for every input probability distribution λ on X with λ(x) > 0 for every

x ∈X, the output distribution ρ = {q

}

x,y∈X

· λ also satisﬁes the property that

ρ(x) > 0 for every x ∈X.

Proof: Given an input distribution λ with λ(x) > 0 for every x ∈Xand any state

y ∈X,wehaveρ(y)=



x∈X

λ(x) · q

> 0 if and only if λ(z) · q

> 0 for

some z ∈ X if and only if q

> 0 for some z ∈ X (since λ(z) > 0 automatically b y

assumption) if and only if the transition matrix {q

}

x,y∈X

is non-annihilating.

Before proceeding any further it is worthwhile to mention that a product of non-

annihilating transition matrices is non-annihilating:

Corollary 4.10.4 Given non-annihilating Markov transition matrices {q

}

x,y∈X

and

}

x,y∈X

, the matrix {r

}

x,y∈X

= {m

}

x,y∈X

·{q

}

x,y∈X

is non-annihilating

as well.

Proof: Given an input distribution λ with λ(x) > 0,since{q

}

x,y∈X

is non-

annihilating, the “intermediate” output distribution μ = {q

}

x,y∈X

(λ) also has the

property that μ(x) > 0 for all x ∈X.Nowwehave

ρ = {r

}

x,y∈X

· λ = {m

}

x,y∈X

· ({q

}

x,y∈X

· λ)) = {m

}

x,y∈X

· μ

also has the property that ρ(x) > 0 for all x ∈Xsince it is an output of μ under the

non-annihilating transition matrix {m

}

x,y∈X

. By proposition 4.10.3, the transition

matrix {r

}

x,y∈X

is non-annihilating as well.

Though quite elementary, proposition 4.10.2 readily implies subtle and rather general

inequalities about the stationary distributions of the Markov chains for which the last

elementary step is selection:

Corollary 4.10.5 Let {q

}

x,y∈X

and {p

}

x,y∈X

denote Markov transition matri-

ces on a ﬁnite set X .Fixu and v ∈Xwith u  v where the  and  relations are

meant with respect to the matrix {p

}

x,y∈X

and an input probability distribution λ

on X . Denote by ρ the output distribution of the composed matrix {p

}

x,y∈X

·{q

}

(ρ = {p

}

x,y∈X

·{q

}

x,y∈X

· λ). Then we have ρ(u) ≥ ρ(v). Suppose, in addition,

the matrix {q

}

x,y∈X

is non-annihilating. Now, if u  v, and λ(x) > 0 for every

x ∈X then ρ(u)  ρ(v).

51 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Proof: Since

}

x,y∈X

·{q

}

x,y∈X

· λ = {p

}

x,y∈X

· ({q

}

x,y∈X

· λ)={p

}

x,y∈X

· μ

where μ = {q

}

x,y∈X

· λ, the desired conclusions follow by applying proposi-

tion 4.10.2 to the matrix {p

}

x,y∈X

and the input distribution μ. For the second

conclusion we use the assumption that {q

}

x,y∈X

is non-annihilating to deduce that

μ(x) > 0 for every x.

As an almost immediate consequence we deduce the following fact:

Corollary 4.10.6 Let {q

}

x,y∈X

, {m

}

x,y∈X

and {p

}

x,y∈X

denote Markov tran-

sition matrices on a ﬁnite set X . Suppose that the matrices {q

}

x,y∈X

and {p

}

x,y∈X

are non-annihilating while the matrix {m

}

x,y∈X

has the property that ∀ x, y ∈

X m

> 0.Fixu and v ∈Xwith u  v where the  and  relations are

meant with respect to the matrix {p

}

x,y∈X

. Then the Markov chain determined

by either one of the composed matrices {p

}

x,y∈X

·{m

}

x,y∈X

·{q

}

x,y∈X

}

x,y∈X

·{q

}

x,y∈X

·{m

}

x,y∈X

is irreducible Let π denote the unique sta-

tionary distribution of the composed chain. Then we have π(u) ≥ π(v). Suppose, in

addition, the matrix {q

}

x,y∈X

is non-annihilating. Now, if u  v , and λ(x) > 0 for

every x ∈X then π(u)  π(v).

Proof: The irreducibility of the composed chain is left as an exercise for the reader.

As a hint, the reader may notice that from the assumptions that {m

}

x,y∈X

has all

positive entries while {p

}

x,y∈X

and {q

}

x,y∈X

are non-annihilating, it follows

that every one of the composed matrices has all positive entries and, hence, deter-

mines an irreducible Markov chain. The second conclusion follows from the fact that

}

x,y∈X

is the leftmost matrix in the composition by applying corollary 4.10.5 to

the matrix {p

}

x,y∈X

·{a

}

x,y∈X

where {a

}

x,y∈X

= {m

}

x,y∈X

·{q

}

x,y∈X

or {a

}

x,y∈X

= {q

}

x,y∈X

·{m

}

x,y∈X

with π being the input distribution which

is then also the output distribution by stationar ity. The condition of corollary 4.10.5 is

satisﬁed thanks to corollary 4.10.4.

When applying corollary 4.10.6 we have in mind that {q

}

x,y∈X

is the Markov tran-

sition matrix corresponding to recombination (i. e. a sub-algorithm determined by

a single elementary step of type 2: see deﬁnitions 4.3.1 and 4.2.5), {p

}

x,y∈X

the Markov transition m atrix corresponding to selection (i. e. a sub-algorithm deter-

mined by a single elementary step of type 1: see deﬁnition 4.2.2) and {m

}

x,y∈X

is the Markov transition m atrix corresponding to mutation. In order to apply propo-

sition 4.10.2 to the case of ﬁtness-proportional selection we need to determine the

relation  and  for this special case. Although this task is not difﬁcult, it requires

a careful “bookkeeping” analysis. This will be the subject of the next section. We

end the current section with an immediate consequence (basically a restatement) of

corollary 4.10.6:

It is worth mentioning that ﬁtness-proportional selection is not the only possible type of selection. Other

elementary steps of type 1 include, for instance, tournament selection and rank selection.

52 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Corollary 4.10.7 Suppose we are given an evolutionary algorithm A determined by

the elementary steps s

, s

and s

where s

are and s

are any elementary step (usu-

ally one of them is selection and the other is mutation) which deﬁne non-annihilating

Markov transition matrices and such that one of these matrices has all positive entries,

while s

is the elementary step of type 1, i.e. selection. As b e fore, let {p

}

x,y∈X

denote the Markov transition matrix determined by the elementary step s

and  and

 are the deﬁned with respect to the transition matrix {p

}

x,y∈X

. Then the Markov

chain determined by the algorithm A with state space X =Ω

is irreducible and its

unique stationary distribution π satisﬁes π(x) ≥ π(y) and π(x) >π(y) whenever

x  y and x  y respectively.

4.11 What are the relations  and  for the case of

ﬁtness-proportional selection?

This section is devoted to classifying the relations  and  for the case of ﬁtness-

proportional selection. Although this task is not difﬁcult, it requires a careful step-by-

step analysis. The reader who is interested only in the net results can read only deﬁni-

tions 4.11.1 and 4.11.2, example 4.11.1, theorem 4.11.5 followed by examples 4.11.3,

4.11.4, 4.11.5 and 4 .11.6 and theorem 4.11.6 which is illustrated by example 4.11.7. It

is recommended (but not essential for understanding) that the reader does not omit the

discussion between example 4.11.6 and theorem 4.11.6. We also strongly recommend

that the reader makes him/herself familiar with lemma 4.11.1 since this fact is rather

simple and reveals a very important step in the classiﬁcation process.

Deﬁnition 4.11.1 Fix a population x =(x

,...,x

) ∈ Ω

and denote by I(x)=

{x | x = x

for some i with 1 ≤ i ≤ m} the set of all individuals in the population x.

Lemma 4.11.1 Given populations x and y, we have S(x) ⊇ S(x) if and only if

I(x) ⊆ I(y). In particular, a necessary condition for x  y is that I(x) ⊆ I(y).

Moreover, if I(x)  I(y) then x  y.

Proof: Since individuals can only disappear (and new individuals can not appear)

upon the completion of the elementary step of ﬁtness-proportional selection (see deﬁ-

nition 4.2.2) it follows immediately that for any populations z and w we have p

z,w

 0

if and only if I(z) ⊇ I(w).InotherwordsS(w)={z | I(z) ⊇ I(w)}. It follows

immediately now that if I(y) ⊇ I(x) then S(x) ⊇ S(y). On the other hand, if

S(x) ⊇ S(y), then, since y ∈ S(y) ⊆ S(x) we also have I(y) ⊇ I(x) according

to the characterization given above. We deduce n ow that I(y) ⊇ I(x) if and only if

S(x) ⊇ S

(y). In p articular, it follows immediately from the previous statement that

I(y)  I(x) if and only if S(x)  S(y). All of the remaining conclusions follow

immediately from deﬁnition 4.10.2.

Deﬁnition 4.11.2 Given a population x =(x

,...,x

) and an individual x ∈

I(x), denote by n(x,x)=|{i | x = x

}| the number of times x occurs in the popula-

tion x.

53 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Example 4.11.1 Suppose

x =(a, a, a, b, c, a, b, b, b) and y =(b, c, c, c, a, b, b, d, b).

Then I(x)={a, b, c} and I(y)={a, b, c, d}. We also have

n(x,a)=n(x,b)=4and n(x,c)=1.

Likewise,

n(y,a)=1,n(x,b)=4,n(x,c)=3and n(x,d)=1.

According to d eﬁnition 4.2 .2, when performing ﬁtness-proportional selection, the in-

dividuals are chosen independently with probability proportional to their ﬁtness. Thus,

if z =(z

,...,z

) and x =(x

,...,x

) is obtained from z by performing

ﬁtness-proportional selection, then the probability that x

= z for a given z ∈ I(z)

n(z,z)·f (z)

i=1

f(z

)

. Thus p

z,x



j=1

n(z,x

)·f (x

)

i=1

f(z

)

. Moreover , every x ∈ I(x) occurs in

the above product n(z,x

) times while every z ∈ I(z) occurs n(z,z) times in the

denominator sum of each of the multiples and so we deduce the following:

Proposition 4.11.2 Given populations x =(x

,...,x

) and z =(z

,...,z

)

we have



(

z∈I(z)

n(z,z)·f(z)

)



x∈I(x)

(n(z,x))

n(x,x)

· (f(x))

n(x,x)

if I(x) ⊆ I(z)

0 otherwise.

In particular, p

does not depend on the way the individuals in z and in x are

ordered, but only depends on the sets I(x) and I(x) and the numbers n(x,x) for

x ∈ I(x) and n(z,z) for z ∈ I(z). In other words, if σ and τ demote arbitrary

permutations of the set {1, 2,...m} ,Ifx

=(x

σ(1)

σ(2)

,...,x

σ(m)

) and z

τ (1)

τ (2)

,...,z

τ (m)

) then p

= p

In order to continue the investigation of the  relation for the case of ﬁtness-proportional

selection, it is convenient to introduce the following notions:

Deﬁnition 4.11.3 Given populations x and y of size m let

I(y|x)={y | y ∈ I(y),n(y,y) >n(x,y)}

(if y/∈ I(x) then n(x,y)=0). Moreover, for y ∈ I(y|x) let κ(y|x,y)=n(y,y) −

n(x,y)}.

Example 4.11.2 Continuing with example 4.11.1, we have n(x,x) >n(y,x) if and

only if x

= a and so I(x|y)={a}. Likewise, n(y,y) <n(y,y) if and only if y = c

or y = d (since d/∈ I(x) according to deﬁnition 4 .11.3 we have n(x,d)=0< 1=

n(x,d)) and so I(y|x)={ c, d}. Moreover, we also have κ(x|y,a)=4− 1=3,

κ(y|x,c)=3− 1=2and κ(y|x,d)=1− 0=1.

The sets I(y|x)

play a crucial role in discovering a sufﬁcient and necessary co ndition

for a population x  y in view of the fact below:

54 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Lemma 4.11.3 Given populations z, y and x with I(z) ⊇ I(y) ⊇ I(x), have the

following:



x∈I(x|y)

κ(x|y,x)=



y∈I(y|x)

κ(y|x,y)



x∈I(x|y)

(n(z,x))

κ(x|y ,x)

· (f(x))

κ(x|y ,x)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

· (f(y))

κ(y|x ,y)

Proof: Given populations z, y and x, from deﬁnitio n 4.11.3 it fo llows that for every

x ∈ I(x) we have

n(x,x)=



min(n(x,x),n(y,x)) if x/∈ I(x|y)

min(n(x,x),n(y,x)) + κ(x|y,x) if x ∈ I(x|y)

Likewise, for every y ∈ I(y) we have

n(y,y)=

⎧

⎪

⎨

⎪

⎩

min(n(x,y),n(y,y))

if y/∈ I(y|x) and y ∈ I(x)

min(n(x,x),n(y,x)) + κ(y|x,x) if y ∈ I(y|x) and y ∈ I(x)

κ(y|x,x) if y ∈ I(y|x) and y/∈ I(x)

Since there are totally m elements in every population we must have



y∈I(y)

n(y,y)=



x∈I(y)

n(x,x)=m.

Rearranging the terms in both sides of the last equation according to the observations

made above, we obtain



x∈I(x)

min(n(x,x),n(y,x)) +



x∈I(x|y)

κ(x|y,x)=



y∈I(x)

min(n(x,y),n(y,y)) +



y∈I(y|x)

κ(y|x,y)

and the ﬁrst desired equation follows b y subtracting



x∈I(x)

min(n(x,x),n(y,x))

from both sides. The second equation follows by rearranging the multiples in the

formula of proposition 4.11.2 according to the equation above and letting k(z)=

(

z∈I(z)

n(z,z)·f(z)

)

so that we can write:

= k(z) ·



x∈I(x)

(n(z,x))

min(n(x,x),n(y,x))

· (f (x))

min(n(x,x),n(y,x))

)×



x∈I(x|y)

(n(z,x))

κ(x|y ,x)

· (f(x))

κ(x|y ,x)

)

and, likewise,

= k(z) ·



y∈I(x)

(n(z,y))

min(n(x,y),n(y,y))

· (f(y))

min(n(x,y),n(y,y))

)×

55 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

· (f (y))

κ(y|x ,y)

Now the common factor

k(z) ·



x∈I(x)

(n(z,x))

min(n(x,x),n(y,x))

· (f(x))

min(n(x,x),n(y,x))

)

on the top and the bottom of the ratio

is canceled out and we obtain the desired

formula.

In fact, according to lemma 4.11.1, we have x  y =⇒ I(y) ⊇ I(x)). Moreover,

since new individuals can not appear as a result of selection, whenever z ∈ S(y) (see

deﬁnition 4.10.1 for the m eaning of S(y))wemusthaveI(z) ⊇ I(y). Therefore,

x  y if and only if I(y) ⊇ I(x)) and ∀ z such that I(z) ⊇ I(y) we have p

≥ p

The condition p

≥ p

can be restated equivalently as

≥ 1. But, thanks to

lemma 4.11.3, we have



x∈I(x|y)

(n(z,x))

κ(x|y ,x)

· (f (x))

κ(x|y ,x)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

· (f (y))

κ(y|x ,y)



x∈I(x|y)

(n(z,x))

κ(x|y ,x)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)



x∈I(x|y)

(f(x))

κ(x|y ,x)



y∈I(y|x)

(f(y))

κ(y|x ,y)

≥ 1

⇐⇒



x∈I(x|y)

(n(z,x))

κ(x|y ,x)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

≥



y∈I(y|x)

(f(y))

κ(y|x ,y)



y∈I(x|y)

(f(x))

κ(x|y ,x)

Observing that



y∈I(y|x)

(f(y))

κ(y|x ,y)



y∈I(x|y)

(f(x))

κ(x|y ,x)

does not depend on z at all we deduce the following:

Lemma 4.11.4 Given populations x and y of size m, we have x  y if and only if

I(y) ⊇ I(x) and

min

I(z)⊇I(x)



x∈I(x|y)

(n(z,x))

κ(x|y ,x)



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

≥



y∈I(y|x)

(f(y))

κ(y|x ,y)



y∈I(x|y)

(f(x))

κ(x|y ,x)

Thanks to lemma 4.11.4, the rest of our analysis boils down to constructing a pop-

ulation z which minimizes the ratio over z with I(z) ⊇ I(y). In view of proposi-

tion 4 .11.2, without loss of generality, we can assume that the ﬁrst |I(y)| individuals of

z enumerate the elements of I(y),i.e. z = {y

,...,y

|I(y)|

,...z

m−|I(y)|

Our goal is then to select z

,...,z

m−|I(y)|

in a way which m inimizes this ra-

tio. First, it is worth pointing out, that unless y = x

for some permutation σ of

{1, 2,...m} in the sense described in proposition 4.11.2 (in which case we trivially

have x  y thanks to proposition 4.11.2), we can assume that I(y|x) = ∅. (Indeed,

56 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

according to lemma 4.11.3, we have



x∈I(x|y)

κ(x|y,x)=



y∈I(y|x)

κ(y|x,y).

If I(y|x) = ∅ then



x∈I(x|y)

κ(x|y,x)=



y∈I(y|x)

κ(y|x,y)=0which forces

I(x|y)=∅. But then for every y ∈ I(y) we have y/∈ I(y|x)=⇒ I(y) ⊆ I(x) and

n(y,y) ≤ n(x,y) and, since I(x|y)=∅,alson(y,y) ≥ n(x,y). Summarizing, we

obtain n(y,y)=n(x,y) ∀ y ∈ I(y)=I(y) which means that y = x

.) Next, we

observe that ∀ i we have z

∈ I(y|x). (If not, then for some i we have z

/∈ I(y|x).

In such a case, since replacing z

with an element of I(y|x) = ∅ will increase the de-

nominator and either decrease (in case if z

∈ I(x|y)) or not inﬂuence the numerator

in any way (since it is clear from deﬁnition 4.11.3 that I(y|x) ∩ I(x|y)=∅)ofthe

ratio on the L.H.S. of the inequa lity of lemma 4.11.4. This in turn would only decrease

this ratio so that z can not minimize it.) Since z

s are chosen from the set I(y|x),and

I(y|x) ∩ I(x|y)=∅,foreveryx ∈ I(x|y) x = z

for 1 ≤ i ≤ m −|I(y)| and x = y

for a unique j with 1 ≤ j ≤|I(y)| (since I(y) ⊇ I(x) and y

,...,y

|I(y)|

enumer-

ate the elements of I(y))wehaven(z,x)=1for every x ∈ I(x|y). But then the nu-

merator of the ratios on the L.H.S. of lemma 4.11.4,



x∈I(x|y)

(n(z,x))

κ(x|y ,x)

and the L.H.S. of the inequality in lemma 4.11.3 simpliﬁes to

min

z∈Q



y∈I(y|x)

(n(z,y))

κ(y|x ,y)

where Q = {z | z =(y

,...,y

|I(y)|

,...,z

m−|I(y)|

),y

,...,y

|I(y)|

enumerate I(y) and z

∈ I(y|x)}. Moreover, notice that z

s can be chosen arbitrarily

from the set I(y|x) while for every y ∈ I(y|x) there exists exactly one 1 ≤ j ≤|I(y)|

with y = y

.Wethenhaven(z,y)=1+|{i | 1 ≤ i ≤ m −|I(y)|,z

= y}|

and



y∈I(y|x)

n(z,y)=|I(y|x)| + m −|I(y)|. On the other hand, given a ﬁnite

sequence of n atural numbers {n

}

y∈I(y|x)

satisfying the constraint



y∈I(y|x)

|I(y|x)| + m −|I(y)|, we can construct z = {y

,...,y

|I(y)|

,...z

m−|I(y)|

}

with n(z,y)=n

by picking exactly n

− 1 z

s equaling to y for every y ∈ I(y|x).

All of this is summarized in the main theorem below:

Theorem 4.11.5 Given populations x and y of size m, we have x  y with respect

to ﬁtness-proportional selection as described in deﬁnition 4 .2.2, if and on ly if I(y) ⊇

I(x) and

max

}

y∈I(y|x)

∈Q(y|x)



y∈I(y|x)

)

κ(y|x ,y)

≤



x∈I(x|y)

(f(x))

κ(x|y ,x)



y∈I(y|x)

(f(y))

κ(y|x ,y)

where

Q(y|x)={{n

}

y∈I(y|x)

|∀y ∈ I(y|x) n

∈ N,



y∈I(y|x)

= |I(y|x)|+m−|I(y)|}.

Below we illustrate theorem 4.11.5 with a few simple examples:

Example 4.11.3 Continuing with examples 4.11.1 and 4.11.2, notice that we do have

I(y)  I(x) and |I(y|x)|+m−|I(y)| =2+9−4=7. so according to theorem 4.11.5

57 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

we have x  y if and only if

f(a)

f(c)

· f (d)

≥ max

=7,n

≥1 and n

≥1

· n

There are 6 possible pairs (n

) over which we want to maximize the product n

·n

These are (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1). Moreover, by symmetry,

since the power of the coefﬁcient n

in the product is bigger than that of n

we only

have to cheque 3 of these pairs: (4, 3), (5, 2) and (6, 1). The corresponding products

are 4

· 3=48, 5

· 2=50and 6

· 1=36. Then biggest one among these is 50 and

so we deduce that x  y if and only if

f(a)

f(c)

·f (d)

≥ 50.

Example 4.11.4 Suppose y = {y

,...,y

} with y

= y

for i = j (i.e. y is

a population consisting of distinct individuals). Now let x = {x

,...,x

} with

I(y) ⊇ I(x). Notice that in this example I(y|x)=I(y) − I(x) while I(x|y)={x |

there is more than one i s. t. x = x

}. Moreover, ∀ x ∈ I(x|y) we have κ(x|y,x)=

n(x,x) − 1 (since n(y,x)=1) and ∀ y ∈ I(y|x) we have n(y,y)=1so that

0 <κ(y|x,y) ≤ n(y,y) and we have κ(y|x,y)=1. Finally, observe that the set

Q(y|x)={{1, 1, 1,...,1}} since |I(y)| = m and we must have



y∈I(y|x)

|I(y|x)| + m −|I(y)| = |I(y|x)| and n

≥ 1 which forces n

=1∀ y ∈ I(y|x).

According to theorem 4.11.5 we have x  y if and only if

x∈I(x|y)

(f(x))

κ(x|y,x)

y∈I(y|x)

(f(y))

κ(y|x,y)

≥ 1

if and only if



x∈I(x|y)

(f(x))

n(x,x)−1

≥



y∈I(y|x)

f(y).

Example 4.11.5 Continuing with example 4.11.4, suppose, in addition, that there is

exactly one individual in x which occurs more than once in this population. That

is, without loss of generality, let x =(y

,...,y

) and y =

,...,y

k+1

,...,y

) where y

= y

for i = j and k<m.Thisisaspecial

case of example 4.11.4 where I(x|y)={y

} and I(y|x)={y

k+1

k+2

,...,y

m−1

}

According to the conclusion of example 4.11.4 we have x  y if and only if

(f(y

))

m−(k+1)

≥

m−(k+1)



i=1

f(y

k+i

) if and only if f (y

) ≥

m−(k+1)







m−(k+1)



i=1

f(y

k+i

)

which, in words, says that x  y if and only if the ﬁtness of the unique repeated indi-

vidual of x is at least as large as the geometric mean of the ﬁtness of all the individuals

in y which do not occur in x. It is also worth pointing out that even if the inequality

above is an equality we still have x  y since I(y)  I(x) and so S(x)  S(y).

In particular, even if the ﬁtness function is ﬂat, the relation  = ∅ in case one uses

ﬁtness-proportional selection.

Example 4.11.6 Now consider an “opposite extreme” to example 4.11.4 (in the sense

of the diversity of elements in the population) where I(y)=I(x)={x, y}.let’s

say n(x,x)=k (which implies that n(x,y)=m − k) and n(y,x)=l<k

58 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

(hence n(y,y)=m − l). It follows then that I(x|y)={x} and I(y|x)={y}.

Moreover, κ(y|x,y)=κ(x|y,x)=k − l.Since|I(y|x)| = |{y}|, it follows that

Q(y|x)={{k − l}} and which makes the maximization procedure trivial. According

to theorem 4.11.5, we have x  y if and only if (k − l)

k−l

≤

f(x)

k−l

f(y)

k−l

if and only if

f(x) ≥ (k − l) · f (y).

Theorem 4.11.5 tells us that in order to cheque if x  y with respect to ﬁtness-

proportional selection we need to solve an integer optimization problem subject to

linear constraints. Examples 4.11.4, 4.11.5 and 4.11.6 are particularly simple mainly

because the sets Q(y|x) were singletons so there was not much choice for the maximiz-

ing domain element. Although we do not intend to pursue studying this optimization

problem in much detail since it is not the main subject of the current paper, it is worth

mentioning that the method of Lagrange multipliers allows us to give an upper bound

on the

max

}

y∈I(y|x)

∈Q(y|x)



y∈I(y|x)

)

κ(y|x ,y)

by letting n

’s range over positive real numbers subject to the linear constraint



y∈I(y|x)

|I(y|x)| + m −|I(y)|. Moreover, if one wants an exact solution then the method al-

lows to narrow down the choice of suitable integer sequences signiﬁcantly: Indeed,

according to the method of Lagrange multipliers, if any local maximum of a differ-

entiable function f(

−→

n ) on an open set D ⊆ R

subject to the constraint g(

−→

n )=c

where g is another differentiable function on D is achieved at a point q, then we must

have ∇f(q)=λ ·∇g(q) where ∇ denotes the gradient (derivative of a real-valued

function) operator and λ is some constant proportionality coefﬁcient (in other words,

the gradients of f and g evaluated at the point q must be collinear vectors). In our

case f, g : U ⊆ R

I(y|x)

→ R where U = {

−→

n |

−→

n ∈ R

I(y|x)

and n

≥ 0}

are deﬁned according to the following formulas: f (

−→

n )=



y∈I(y|x)

)

κ(y|x ,y)

and g(

−→

n )=



y∈I(y|x)

. Our goal is to maximize f subject to the constraint

−→

n )=|I(y|x)| + m −|I(y)| where

−→

n = {n

}

y∈I(y|x)

. Clearly ∀ n

we have

∂g

∂n

=1and so the condition ∇f(q)=λ ·∇g(q) boils down to the condition

∂f

∂n

∂f

∂n

for every u and v ∈ I(y|x). For any given w ∈ I(y|x) we have

∂f

∂n

= κ(y|x,w) · (n

)

κ(y|x ,w)−1



y∈I(y|x),y=w

)

κ(y|x ,y)

Therefore, the equation

∂f

∂n

∂f

∂n

holds for every u and v ∈ I(y|x) if and only if

for every u and v ∈ I(y|x) we have κ(y|x,u) · n

= κ(y|x,v) · n

if and only if

κ(y|x ,u)

κ(y|x ,v)

for all u and v ∈ I(y|x). In other words, the equation

∂f

∂n

∂f

∂n

holds for every u and v ∈ I(y|x) if and only if the ratio

κ(y|x ,y)

= α is a constant

independent of y ∈ I(y|x). Moreover , this also gives us n

κ(y|x ,v)

· κ(y|x,u)=

α · κ(y|x,u) for every u ∈ I(y|x) and, according to the constraint, we also h ave



y∈I(y|x)

= α ·



y∈I(y|x)

κ(y|x,y)=|I(y|x)| + m −|I(y)|

59 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

which gives

α =

|I(y|x)| + m −|I(y)|



y∈I(y|x)

κ(y|x,y)

Notice that the point

−→

q with coordinates n

|I(y|x)|+m−|I(y)|

y∈I(y|x)

κ(y|x ,y)

· κ(y|x,y) is the

unique point which satisﬁes ∇f(

−→

q )=λ ·∇g(

−→

q ). We argue that this point must

be the global maximum of the function f on the domain D = { n

| n

≥ 0}∩

−1

({|I(y|x)| + m −|I(y)|}) which is a closed and bounded subset of R

I(y|x)

and,

hence, is compact. Clearly the function f is continuous on D and, since D is compact

it must achieve a minimum and a maximum on D. The only interesting case to con-

sider is when |I(y|x)| > 1 (indeed, if |I(y |x)| =1,thenD is a singleton set whose

only point is

−→

q so that it is trivially a global maximum). If maximum of f was not the

point

−→

q then it must be the point on the boundary of D (since it is the only interior

point satisfying ∇f(

−→

q )=λ ·∇g(

−→

q )). But every boundary point of D has at least

one zero coordinate so that f(

−→

y )=0for every boundary point

−→

y of D. On the other

hand f (

−→

q ) > 0. Thus we deduce that f achieves a global maximum at the point

−→

q .

We then have the following sufﬁcient con dition for

x  y:

Theorem 4.11.6 Given populations x and y of size m, we have x  y with respect to

ﬁtness-proportional selection as described in deﬁnitio n 4.2.2, if I(y) ⊇ I(x) and



x∈I(x|y)

(f(x))

κ(x|y ,x)



y∈I(y|x)

(f(y))

κ(y|x ,y)

≥

≥ (

|I(y|x)| + m −|I(y)|



y∈I(y|x)

κ(y|x,y)

)

y∈I(y|x)

κ(y|x ,y)



y∈I(y|x)

κ(y|x,y)

κ(y|x ,y)

Example 4.11.7 Continuing with examples 4.11.1, 4.11.2 and 4.11.3, according to

corollary 4.11.6 we have x  y (recall that we do have I(y) ⊇ I(y))if

f(a)

f(c)

· f(d)

≥

≥ (

|I(y|x)| + m −|I(y)|

κ(y|x,c)+κ(y|x,d)

)

κ(y|x ,c)+κ(y|x,d)

· κ(y|x,c)

κ(y|x ,c)

· κ(y|x,d)

κ(y|x ,d)

)

· 2

· 1

=50.(814).

Notice that the bound is only slightly larger than the exact one given in example 4.11.3.

Moreover, although corollary 4.11.6 itself only provides a numerical bound, the method

of Lagrange multipliers which was used to establish corollary 4.11.6, suggests how one

can narrow down the search for the optimizing choice of coefﬁcients by considering

only the pairs (n

) with integer coordinates which are closest to the point with

coordinates x

|I(y|x)|+m−|I(y)|

y∈I(y|x)

κ(y|x ,y)

· κ(y|x,u) in “every direction”. In our speciﬁc

example, this point is (

· 2,

· 1) = (4

, 2

) and so the only potential candidates

are (4, 3) and (5, 2). We saw in 4.11.3 that the point (5, 2) is the winner. Of course,

this “narrowing down” procedure is particularly useful for the cases when |I(y|x)| is

a large number.

60 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

4.12 What Can Be Said when the Last Elementary Step

is Mutation?

Although not nearly as much can be said when the last elementary step is mutation, the

following result is a rather general “anti-communism” theorem. It should be noted that

a much stronger and more informative result which depends on the assumption that

crossover is “pure” in the sense of [14] (meaning that identical pair of parents produce

a pair of the same identical children) shall be established in a sequel paper.

Theorem 4.12.1 Let {q

}

x,y∈X

and {p

}

x,y∈X

denote Markov transition matri-

ces on a ﬁnite set X . Suppose {q

}

x,y∈X

is non-annihilating in the sense of deﬁni-

tion 4.10.3. Also let {{m

}

x,y∈X

| 0 <δ<1} denote an indexed family of Markov

transition matrices such that for every >0 there exists r>0 such that for all δ<r

we have {m

}

x,y∈X

− I <for some norm on the ﬁnite dimensional vector space

of |X | × |X | matrices

. Suppose also that for all δ>0 with δ<1 the composed

Markov chain M(δ)={m

}

x,y∈X

·{p

}

x,y∈X

·{q

}

x,y∈X

is irreducible. Let 

denote the relation associated with the Markov transition matrix {p

}

x,y∈X

(see def-

inition 4.10.2). Finally, let π

denote the unique stationary distribution of the Markov

chain M(δ). Then, for all small enough δ, either there exists a state z ∈Xsuch that

(z) <

|X |

or, whenever x  y, we also have π

(x) >π

(y). In particular, as long

as  = ∅, the stationary distribution of the Markov chain determined by the transition

matrix M(δ) is never uniform for all sufﬁciently small “mutation rates” δ.

Proof: Denote by Λ={{λ

}

z∈X



z∈X

=1λ

≥ 0} the probability simplex

and let Λ

|X |

= {{λ

}

z∈X



z∈X

=1,λ

≥

2|X |

}. For any given x  y ∈X

consider a function f

x, y

:Λ

|X |

→ R which sends a given λ ∈ Λ

|X |

to the number

}

x,y∈X

·{q

}

x,y∈X

(λ)(x) −{p

}

x,y∈X

·{q

}

x,y∈X

(λ)(y) > 0

thanks to proposition 4.10.5. From basic point-set topology we know that the set

|X |

is a compact topological space (it is a closed and bounded subset of R

|X |

with

|X | < ∞) and, moreover, the function f

x, y

is continuous (it is a restriction of a lin-

ear map). It follows then that the function f

x, y

achieves a minimum, min(f

x, y

),on

|X |

. Thanks to proposition 4 .10.5 this minimum must be a positive number since

the matrix {q

}

x,y∈X

is non-annihilating and every λ ∈ Λ

|X |

has the property that

λ(z) ≥

2|X |

> 0 for every z ∈X. We now conclude that

α =min{min{f

x, y

(λ) | λ ∈ Λ

|X |

}|x  y ∈X}> 0.

Now choose r>0 small enough so that whenever 0 <δ<rwe have

{m

}

x,y∈X

− I

< min{

3|X |

It is a fact that all the norms on ﬁnite-dimensional vector spaces are equivalent. It is then irrele-

vant which norm we consider. For practical applications it is con venient to use {a

}

x,y∈X



max

max{|a

||x, y ∈X}. For the purpose of proving the theorem it seems most convenient to

use the operator norm deﬁned as {a

}

x,y∈X



=sup{{a

}

x,y∈X

(v)|v =1} where

(v

,...,v

|X |

) =

|X |

i=1

61 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Choose any δ satisfying 0 <δ<rNow there are exactly two mutually exclusive and

exhaustive cases:

Case 1: ∃ n ∈ N such that {p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(Λ) ⊆ Λ

|X |

In this case, let γ

= {p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(π

).Sinceπ

is the sta-

tionary distribution of M(δ) (see the statement of the theorem), it is also the stationary

distribution of M(δ)

n+1

and it follows that

}

x,y∈X

(γ

)={m

}

x,y∈X

· ({p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(π

)) =

=({m

}

x,y∈X

·{p

}

x,y∈X

·{q

}

x,y∈X

) ·M(δ)

(π

)=M(δ)

n+1

(π

)=π

and so

γ

− π

 = (I −{m

}

x,y∈X

)(γ

)≤I −{m

}

x,y∈X



In particular, ∀ x  y ∈Xwe have

|γ

(x) − π

(x)| <

and |γ

(y) − π

(y)| <

so that

(x) >γ

(x) −

and π

(y) <γ

(y)+

and, ﬁnally,

(x) − π

(y) >γ

(x) −

− (γ

(y)+

)=γ

(x) − γ

(y) −

2α

> 0

thanks to the choice of α, and it follows, in this case, th at π

(x) >π

(y).

Case 2: ∀ n ∈ N we have {p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(Λ)  Λ

|X |

In this case, ﬁrst we claim that for every n ∈ N there exists a distribution γ ∈

M(δ)

n+1

(Λ) such that γ(z) <

6|X |

for some z ∈X. Indeed, the assumption of case

2 says that there exists a distribution λ ∈{p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(Λ) such

that λ(z) <

.Butthenγ = {m

}

x,y∈X

(λ) is the distribution with the desired

property. Indeed, since λ ∈{p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(Λ), it follows that

λ = {p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(η) for some distribution η ∈ Λ.Butthen

γ = {m

}

x,y∈X

· ({p

}

x,y∈X

·{q

}

x,y∈X

·M(δ)

(η)) =

=({m

}

x,y∈X

·{p

}

x,y∈X

·{q

}

x,y∈X

) ·M(δ)

(η)=

= M(δ)

n+1

(η) ∈M(δ)

n+1

(Λ).

Moreover, since δ<rwe have

|γ(z) − λ(z)|≤γ − λ = {m

}

x,y∈X

(λ) − λ =

= ({m

}

x,y∈X

− I)(λ)≤({m

}

x,y∈X

− I)

3|X |

62 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

But then we also have γ(z) ≤ λ(z)+

3|X |

2|X |

3|X |

6|X |

as desired. So we

deduce every one of the sets M(δ)

n+1

(Λ) contains a point γ

n+1

with γ

n+1

(z) <

6|X |

for some z ∈X. It is well-known from Markov chain theory that the sequence of

convex compact sets {M(δ)

n+1

(Λ)}

∞

n=1

is nested (M(δ)

n+1

(Λ) ⊇M(δ)

n+2

(Λ))

and



∞

n=1

M(δ)

n+1

(Λ) = {π

} where π

is the unique stationary distribution of

the Markov chain determined by the matrix M(δ). Also, all the elements of the se-

quence {γ

n+1

}

∞

n=1

inside of the compact set Λ, and, hence, the sequence {γ

n+1

}

∞

n=1

has a convergent subsequence {γ

(n+1)

}

∞

k=1

.Butthenγ

(n+1)

→ π

as k →∞

(since the limit point must lie inside of every one of the compact sets M(δ)

n+1

(Λ)

and there intersection consists of a single point π

). Moreover, notice that since X is

a ﬁnite set while {γ

(n+1)

}

∞

k=1

is an inﬁnite sequence, according to the “pigeonhole

principle” it follows that ∃ z ∈Xsuch that inﬁnitely many elements of the subse-

quence {γ

(n+1)

}

∞

k=1

have the property that {γ

(n+1)

}

∞

k=1

(z) <

6|X |

.Inotherwords,

∃ z ∈Xfor which we can extract a subsequence {γ

(n+1)

}

∞

s=1

of the convergent

sequence {γ

(n+1)

}

∞

k=1

with the property that γ

(n+1)

(z) <

6|X |

. In particular,

(n+1)

(z) → π

(z) as s →∞and it follows that π

(z) ≤

6|X |

|X |

which is

what we were after.

When applying theorem 4.12.1 we have in mind that {q

}

x,y∈X

is the Markov tran-

sition matrix corresponding to recombination ( i. e. a sub-algorithm determined by a

single elementary step of type 2: see deﬁnitions 4.3.1 and 4.2.5), {p

}

x,y∈X

is the

Markov transition matrix corresponding to selection (i. e. a sub-algorithm d etermined

by a single elementary step of type 1: see deﬁnition 4.2.2) and {m

}

x,y∈X

is the

Markov transition matrix corresponding to mutation with some “rate” δ. For the pur-

pose of the current section, thanks to the generality of theorem 4.12.1, it is sufﬁcient to

assume only that m

> 0 ∀ x, y and that max({m

| x = y ∈X}) → 0 as δ → 0.

The following proposition tells us when mutation determined by the reproduction 1-

tuple (Ω, M,p) satisﬁes conditions of theorem 4.12.1:

Deﬁnition 4.12.1 An ergodic family of mutations is an indexed family of ergodic mu-

tation 1-tup les (see deﬁnition 4.9.1) of the form {(Ω, M,p

)}

δ∈ (0, 1)

where p

) ≥

1 − δ.

Proposition 4.12.2 Suppose {(Ω, M,p

)}

δ∈ (0, 1)

is an ergodic family of mutations

as in deﬁn ition 4.12.1. Then ∀ δ ∈ (0, 1) the Markov transition matrix {m

}

x,y∈X

associated to the sub-algorithm determined by the mutation 1-tuple (Ω, M,p

) has

the property that I −{m

}

x,y∈X

→0 as δ → 0.

Proof: Notice that I −{m

x, y

}

x,y∈X

 =max{m

| x = y} andsoitsufﬁces

to show that for every x = y we have m

x, y

→ 0 as δ → 0 (since the state space is

ﬁnite). No tice also that ∀ x = y we have 0 <m

x, y

< 1 − m

x, x

.Itnowsufﬁces to

show only that ∀ x ∈X =Ω

we have 1 − m

x, x

→ 0 as δ → 0, or, equivalently, that

∀ x ∈X =Ω

we have m

x, x

→ 1 as δ → 0. If we write x =(x

,...,x

) ∈

then, since 1

)=x

we see that 1 ≥ m

x, x

≥ (p

))

≥ (1 − δ)

→ 1 as

δ → 0 and the desired conclusion follows.

63 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Combining theorem 4.12.1 with the conclusion of example 4.11.5 (saying that  = ∅

for ﬁtness-proportional selection) we deduce the following:

Corollary 4.12.3 Suppose for every 0 <δ<1 we are given an evolutionary algorithm

determined by the cycle s

where s

is any elementary step (but usually it is

an elementary step of type 2), s

is the elementary step of type 1 (ﬁtness-proportional

selection as described in deﬁn ition 4.2.2 ) and s

is an elementary step of type 2 de-

termined by an ergodic mutation 1-tuple chosen from an ergodic family of mutations

(see deﬁnition 4.12.1). Then the Markov chain determined by the algorithm A

with

state space X =Ω

is irreducible and, for all small enough δ, the unique stationary

distribution of this Markov chain is not uniform.

Corollary 4.12.3 tells us, in particular, that the stationary distribution of the Markov

chain associated to an algorithm A with the second elementary step being of type 1

(selection) is never uniform, even when the ﬁtness function is ﬂat. It is still reason-

able to conjecture though, that in case of ﬂat-ﬁtness selection, under certain symmetry

assumptions on recombination and mutation, everyone of the individuals in a given

population is equally likely to occur “in the long run” in the sense of deﬁnition 4.5 .6.

Results of this nature (and even stronger) shall be established in the upcoming paper.

4.13 Conclusions

In the current paper we applied the methods developed in [5] to obtain a schema-

based version of Geiringer’s theorem for non-linear GP with homologous crossover.

The result enables us to calculate exactly the lim iting distribution of the Markov chain

associated with the evolution of a ﬁnite (ﬁxed size) population under the action of

repeated crossover, or the action of the mixture of crossover and mutation. This is

an extension of the results for ﬁxed and variable length strings given in [5] for ﬁnite

populations.

The main result established in [5] applies only in the absence of selection and only

when crossover and mutation are bijective (which is often, but not always the case). In

the current paper we established a property of the stationary distribu tion of the Markov

chain for a rather wide class of EAs. More speciﬁcally, we introduced a pre-order

relation on the state space of a Markov chain which allows us to establish rather general

inequalities concerning the stationary distribution of the Markov chain determ ined by

an EA. This pre-order relation depends primar ily on selection and not on the other

stages d etermining an EA. In section 4.11 this partial order is completely classiﬁed for

the case of ﬁtness-proportional selection in section 4.11. More results on this issue,

as well as some connection between the inﬁnite and the ﬁnite population Geiringer

theorems will appear in a forthcoming paper.

64 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Bibliography

[1] G Briscoe and P De Wilde. D6.6 high- level design speciﬁcation of the distributed

intelligence system. Digital Business Ecosystem, Contract no 507953, 2006.

[2] S. Coffey. An applied probabilist’s guide to genetic algorithms. Master’s thesis,

The University of Dublin, 1999.

[3] R.A.Fisher.The genetical theory of natural selection. Oxford: Clarendon Press,

1930.

[4] H. Geir inger. On the probability of linkage in Mendelian heredity. Annals of

Mathematical Statistics, 15:25–57, 1944.

[5] B. Mitavskiy and J. Rowe. An extension of geiringer theorem for a wide class of

evolutionary algorithms. Evolutionary Computation, 14, 2006.

[6] Heinz Muhlenbein and Thilo Mahnig. Evolutionary algorithms and the Boltz-

mann distribution. In Foundations of Genetic Algorithms (FOGA2002). Morgan

Kaufmann Publishers, 2002.

[7] Heinz Muhlenbein and Thilo Mahnig. Evolutionary computation and Wright’s

equation. Theoretical Computer Science, 2002.

[8] Liviu Panait and Sean Luke. Alternative bloat control methods. In Genetic

and Evolutionary Computation – GECCO-2004, pages 630–64. Springer-Verlag,

2004.

[9] R. Poli. Hyperschema theory for GP with one-point crossover, building blocks,

and some new results in GA theory. In R. Poli and W. Banzhaf et al, editors,

Genetic Programming, Pro ceedings of EuroGP’2000, pages 163–180. Springer-

Verlag, 2000.

[10] R. Poli. A simple but theoretically-motivated method to control bloat in genetic

programming. In Genetic Programming, Proceedings of the 6th European Con-

ference, EuroGP 2003, pages 211–223. Springer-Verlag, 2003.

[11] R. Poli and W. Langdon. On the search properties of different crossover operators

in genetic programming. In Proceedings of the Third Annual genetic program-

ming conference, pages 293–301, 1998.

65 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

[12] R. Poli, C. Stephens, A. Wright, and J. Rowe. A schema-theory-based extension

of geiringer’s theorem for linear GP and variable-length GAs under homologous

crossover. In K. De Jong, R. Poli, and J. E. Rowe, editors, Foundations of Genetic

Algorithms, volume 7, pages 45–62, 2002.

[13] Y. Rabani, Y. Rabinovich, and A. Sinclair. A computational view of population

genetics. In Annual ACM S ymposium on the Theory of Computing, pages 83–92,

1995.

[14] N. Radcliffe. The algebra of genetic algorithms. Annals of Mathematics and

Artiﬁcial Intelligence, 10:339–384, 1994.

[15] L. Schm itt. Theory of genetic algorithm s. Theoretical Computer Science, 259:1–

61, 2001.

[16] L. Schmitt. Theory of genetic algorithms ii: models for g enetic operators over the

string-tensor representation of populations and convergence to global optima for

arbitrary ﬁtness function under scaling. Theoretical Computer Science, 310:181–

231, 2004.

[17] W. Sp ears. The equilibrium and transient behavior of mutation and recombina-

tion. In W. Martin and W. Spears, editors, Foundations of genetic Algorithms,

volume 6, pages 241–260, 2000.

[18] STU. Report on evolutionary and distributed ﬁtness environment. Internal, 2006.

[19] M De Tommasi. D15.3 BML framework 2nd release. Digital Business Ecosystem,

2005.

[20] UBHAM. Report on population dynamics for variable-sized structures. DBE

Deliverable 8.2 .

[21] UBHAM. Report on the evolution of high-level software components. DBE

Deliverable 8.1 .

[22] M. Vose. The simple genetic algorithm: foundations and theory. MIT Press,

1999.

[23] A. H. Wright, J. E. Rowe, R. Poli, and C. R. Stephens. A ﬁxed point analysis of

a genepool GA with mutation. In Proceedings of the Genetic and Evolutionary

Computation Conference (GECCO 2002). Morgan Kaufmann Publishers, 2002.

[24] S. Wright. Evolution in mendelian populations. Genetics, 16:97–159, 1931.

66 / 66

Del 8.3 Report on Population dynamics in EvE

DBE Project (Contract n° 507953)

Download
Save PDF to desktop

Email
Email completed PDF

Send for Signing
Email for others to sign

Print
Print document

NAME

Del 08.3 DBE Report On Population Dynamics In EvE Del_08.3_DBE_Report_on_Population_dynamics_in_EvE

View Audit Log
Print With Audit Log
Duplicate Document

Fill Online, Printable, Fillable, Blank Del 08.3 DBE Report On Population Dynamics In EvE Del_08.3_DBE_Report_on_Population_dynamics_in_EvE Form

Related forms

Fillable Del 08.3 DBE Report On Population Dynamics In EvE Del_08.3_DBE_Report_on_Population_dynamics_in_EvE

Fill Online, Printable, Fillable, Blank Del 08.3 DBE Report On Population Dynamics In EvE Del_08.3_DBE_Report_on_Population_dynamics_in_EvE Form

Related forms

First 20 documents completely FREE!