On the Convergence of Multi-Parent Genetic
Algorithms
Chuan-Kang Ting
International Graduate School of Dynamic Intelligent Systems
University of Paderborn, 33100 Paderborn, Germany
ckting@upb.de

Abstract— This paper presents a Markov model for the convergence of multi-parent genetic algorithms (MPGAs). The proposedmodel formulates the variation of gene frequency caused by
selection, multi-parent crossover, and mutation. In addition, it
reveals the pairwise equivalence phenomenon in the numberof parents and identifies the correlation between this number
and the mean fitness in the OneMax problem. The good fit
between theoretical and experimental results demonstrate thecapability of this model. Moreover, the superiority of multiparent crossover in convergence fitness over 2-parent crossoveris validated theoretically as well as empirically.

for MPGAs in the OneMax problem is derived accordingly.
These theoretical results are further verified by a series ofexperiments.
The rest of this paper is organized as follows. Section 2
describes OB-Scan and Section 3 analyzes the gene frequency
affected by the MPGA operators. Next, in Section 4 wemodel MPGAs with Markov chains. Theoretical results andexperimental validation are presented in Section 5. Finally,
conclusions are drawn in Section 6.

I. I NTRODUCTION
Multi-parent genetic algorithms (MPGAs) are genetic algorithms using multi-parent crossovers. Traditionally, genetic
algorithms (GAs) adopt two parents in crossover to reproduce
offspring. This idea is reasonable because, to the best of
our knowledge, the form of sexual reproduction on the Earthis absolutely of two parents. Multi-parent crossovers breakthrough this natural limitation by allowing more than twoparents in the process of crossover. In a sense, multi-parent
genetic algorithms are said to be multi-parent generalizationof genetic algorithms.
Several multi-parent crossovers have been proposed for
MPGAs and shown their power in a variety of optimization
problems [8], [10], [21]. However, most of these crossovers
are validated empirically. Theoretical analysis on the effect ofmultiple parents upon crossover or upon the whole MPGA islacking. Thus, the role of parent numbers in MPGAs is still
open.
This paper presents a Markov model for exploring theinfluence of raising parents in MPGAs. Specifically, we investigate occurrence based scanning crossover (OB-Scan) [11]— a multi-parent generalization of uniform crossover [19]. In
addition, this paper focuses on the OneMax problem. Even
though the OneMax problem is relatively easy, the analysis
on it founds a basic understanding of how the GA operators
work and interact in the course of evolution. Furthermore, theanalytical models for the OneMax problems are promisingly
applicable to other problem domains.
In the procedures for analysis, first we investigate the genefrequency affected by selection, multi-parent crossovers, andmutation individually. Based on gene frequency, we model by
Markov chains the behavior of MPGAs. This Markov model
formulates the variation of gene frequency in the course of
MPGA’s evolution. Additionally, the mean convergence fitness

II. O CCURRENCE BASED S CANNING C ROSSOVER(OB-S CAN )Occurrence based scanning crossover is one of the scanningcrossovers [11] — a multi-parent generalization of uniform
crossover. In uniform crossover, the donor for each offspringgene is randomly picked from two parents. Extended to morethan two parents, scanning crossovers choose the donor at
random or using heuristics. According to different strategies, Eiben et al. [11] proposed three variations of scanningcrossovers: uniform scanning crossover (U-Scan), occurrence
based scanning crossover (OB-Scan), and fitness based scanning crossover (FB-Scan). In this paper, we only discuss OBScan.
Rather than random, OB-Scan determines offspring genes
depending on the occurrence of parental genes at that locus.
Specifically, it picks the majority of parental gene values as
the offspring gene for each locus. Note that in this paper OBScan is defined to break ties by randomly1 choosing a binary.
Examples of 2-parent OB-Scan (corresponding to uniform
crossover) and 4-parent OB-Scan are given in Fig. 1. The
formal definition of the components of GAs and OB-Scan are
drawn below.
Parent 1 1 0 1 1 0 0 0 1

Parent 1 1 0 1 1 0 0 0 1

Parent 2 1 1 0 1 1 1 0 1

Parent 2 1 0 0 1 1 1 0 1

Offspring 1 1 0 1 0 1 0 1

Parent 3 0 0 1 0 1 1 0 0

the majority
random selection

Fig. 1.

Parent 4 0 1 1 0 1 0 1 1
Offspring 1 0 1 0 1 1 0 1

Examples of 2-parent OB-Scan (left) and 4-parent OB-Scan (right)

1 The original OB-Scan [11] breaks ties by directly inheriting the genes ofthe first selected parent. However, random tie break conforms to generalizationof uniform crossover.

Definition 1 (Chromosome and Population):
def1) A chromosome ~c is encoded as a bit string, i.e. ~c =(c1 , . . . , cl ) ∈ {0, 1}l , where ci denotes a gene and l isthe chromosome length.
def2) A population C is a set of chromosomes: C =l{~c1 , . . . , ~cm }, where ~ci ∈ {0, 1} and m is the population size.
Definition 2 (OB-Scan): Given n parents ~c1 , . . . , ~cn ∈ Cselected from population C, OB-Scan reproduces the offspring~c0 = Xob (~c1 , . . . , ~cn ) = (c01 , . . . , c0l ) by

Pn

if
cj )i < n20
j=1 (~
Pnc0i = 1
ifcj )i > n2 for i = 1, . . . , l,j=1 (~

rand(0, 1) otherwise
where (~cj )i denotes the ith gene of the chromosome ~cj , andrand (0, 1) is a binary random function.
III. VARIATION OF G ENE F REQUENCY
Gene frequency is widely used as a quantitative measure ofgenetic variation in population genetics [15]. It also suffices toclue us in on the course of evolution in GAs. In this section weanalyze the variation of gene frequency caused by selection,
OB-Scan, and bit-flip mutation.
Definition 3 (Gene Frequency): The
genefrequencypk (α, t) is defined as the proportion of allele α at locus
k in the population at time t. Let C = {~c1 , . . . , ~cm } be a
population at time t and let Ck (α) = {~c ∈ C | ck = α} bethe subset in which chromosomes possess allele α at locus k.
The gene frequency
def |Ck (α)|

pk (α, t) =

|C|

,

c∈C
def
2
σk (t) = Var(ck ) = pk (1 − pk ).

(2)
Definition 4 (Variation of Gene Frequency in GAs): Let s,
x, m, and r denote the selection, crossover, mutation, andreplacement (survivor), respectively. The process of GA withrespect to gene frequency can be expressed asxm

A. Variation by Selection
This section examines how selection affects gene frequency.
Recall the fact that most of the selection operators in GAs
depend on fitness — a phenotypic property of chromosomes.
Conversely, gene frequency concerns the genotypes of chromosomes. The mapping from genotypes to phenotype is
problem-dependent in essence. In this paper we focus on
the OneMax problem. The fitness of the OneMax problem
provides a direct way to bridge this gap between phenotype
and genotype.
Definition 5 (The OneMax Problem): The OneMax problem is to find the binary string ~c = (c1 , . . . , cl ) ∈ {0, 1}l ,which maximizes the following function f : {0, 1}l →{0, 1, . . . , l}:lXf (~c) =ci .
k=1

Lemma 1: In GAs, the covariance of the genes at any twoloci u, v ∈ {1, . . . , l} has
Cov(cu , cv ) = 0.
Proof: Let Ck be the subset in which chromosomes
possess allele α at locus k. Since
E[cu cv ] =1|Cu | |Cv | = pu pv ,m2

The covariance

where |C| and |Ck (α)| represent the cardinality of set C andCk (α), respectively.
In GAs chromosomes are represented as binary strings. Thus
there exist two gene frequencies pk (1, t) and pk (0, t) withpk (1, t) = 1 − pk (0, t) for every locus k and time t. For
simplicity, we refer to the gene frequency pk (1, t) as pk (t)and refer to pk (0, t) as (1 − pk (t)). Incidentally, the symbolpk (t) is referred to as pk while the indication of time t is notin effect.
Remark 1: Let ck be the k th gene of chromosome ~c. In
GAs, for a population C at time t
1 X
def
pk (t) = E[ck ] =
ck ,
(1)
m

s

frequency. In the analysis we will make use of the well-known
binomial distribution. The probability mass function (p.m.f) of
binomial distribution B(n, p) isµ ¶n xB(x; n, p) =p (1 − p)n−x .
xrpk (t) −→ psk (t) −→ pxk (t) −−→ pm→ pk (t + 1). (3)k (t) −The successive sections will investigate the influence of selection, multi-parent crossovers, and mutation on the gene

Cov(cu , cv ) = E[cu cv ] − E[cu ]E[cv ] = pu pv − pu pv = 0.
Next, we give a definition of mean fitness, which will be
extensively discussed in this paper. The relation between mean
fitness and gene frequency will be presented afterwards.
Definition 6 (Mean Fitness): The mean fitness of a population C is defined as
1 Xf¯ =f (~c).
|C|~c∈C
Lemma 2: Let pk be the gene frequency at locus k. In the
OneMax problem we have the mean f¯ and variance σF2 of
fitness:
f¯ =
σF2 =

l
X
k=1
l
X

pk
σk2 =

k=1

l
X

pk (1 − pk )k=1

Proof: The fitness mean can be simply derived by (1):
" l
#
l
l
X
X
X
f¯ = E[f ] = E
ck =E [ck ] =
pk .
k=1

k=1

k=1

s
I
E [I p ] = √Using Lemma 1, we have the fitness variance
Ã l
!
X
2
σF = Var(f ) = Var
ck
=

k=1

Var(ck ) +X

Cov(cu , cv ) =

u6=v

l
X

σk2 .

k=1

To compute the variation of gene frequency caused by selection, here we introduce the concept of selection intensity,
which originates from quantitative genetic [12] but now is
widely used in evolutionary computation community as aquantitative measure of selection pressure [5], [16]. The definitions of selection differential and selection intensity are given
as follows.
Definition 7 (Selection Differential): Let f¯(t) and f¯s (t) be
the mean fitness of the population and that of selected parents
at generation t, respectively. The selection differential S(t) isdefined as
S(t) = f¯s (t) − f¯(t).
Definition 8 (Selection Intensity): Let S(t) be the selection
differential and σF (t) be the standard deviation of fitness ina population at generation t. The selection intensity is definedasS(t)f¯s (t) − f¯(t)I(t) ==.
(4)
σF (t)σF (t)In this paper we additionally define a selection intensity forgene frequency to measure the effect of selection upon genefrequency.
Definition 9 (Selection Intensity for Gene Frequency):
The selection intensity Ikp for gene frequency at locusk ∈ {1, . . . , l} is defined ass
def pk − pk

Ikp =

.
σk
Lemma 3: In the OneMax problem, the expected selection
intensity for gene frequencys
Var(σ)Ip
E [I ] = √ 1 + 2
.
(5)
E [σ]
l
Proof: The definition of selection intensity for genefrequency tells
psk − pk = Ikp σk .
Since Ikp and σk are independent, averaging all loci gives
E[ps ] − E[p] = E [I p ] E[σ].

Var(σ).
E2 [σ]

I
E [I p ] ≈ √ .
lIn this paper we utilize the above expectation as the selection
intensity for gene frequency at any locus k. Consequently, thevariation of gene frequency caused by selection approximates
to
µ ¶
I
s
(7)
pk ≈ pk + √ σk .
lA practical advantage of (7) is its correlation to selection
intensity I. Accordingly, we can utilize the existing analytical results on the selection intensity I of diverse selection
operators in GAs, e.g. [5]. Note that the selection intensity forgene frequency in (7) is based on the assumption Var(σ) ¿E2 [σ]. Even though this assumption does not necessarily holdin the course of evolution, we will empirically show thisapproximation can work well in Section 5.
B. Variation by OB-Scan
Here we analyze the gene frequency affected by OB-Scan.
Since OB-Scan is a multi-parent generalization of uniform
crossover, the analyses and results presented here are applicable to uniform crossover as well.
Before conducting the analysis of OB-Scan, we introduce theincomplete beta function for simplifying the expression ofequations .
Definition 10 (Incomplete Beta Function): The incomplete
beta function is defined as
Z x
1
def
Ix (a, b) =ta−1 (1 − t)b−1 dt,
Beta(a, b) 0
where a, b > 0 and Beta(a, b) is the beta function.
The incomplete beta function holds the following properties:
1) (26.5.24 [1]) For binomial distribution B(n, p),
n
X

(6)

B(i; n, p) = Ip (a, n − a + 1).

(8)

i=a

2) (26.5.16 [1])Ix (a, b) =According to Lemma 2 and eq. (4), the above equation canbe rewritten asf¯s − f¯
IσF
E[ps ] − E[p]==E [I p ] =
E[σ]
lE[σ]
lE[σ]
qP
s
p
l
2
I
I lE[σ 2 ]I
E[σ 2 ]
k=1 σk
=
=
=√
.
lE[σ]
lE[σ]
l E2 [σ]The variance Var(σ) = E[σ 2 ] − E2 [σ]. Thus,l1+

Remark 2: As Var(σ) ¿ E2 [σ], the expected selection
intensity for gene frequency becomes

k=1
l
X

s
E2 [σ] + Var(σ)
I=√E2 [σ]l1xa (1 − x)b + Ix (a + 1, b). (9)a · Beta(a, b)

Now we embark on the analysis of OB-Scan’s influence on
gene frequency.
Lemma 4: Suppose we have the gene frequency psk of theselected parents. The gene frequency, denoted by pob
k , of theoffspring reproduced by n-parent OB-Scan Xob with n ∈ N>1
haspob
k = Ipsk (a, a),§ ¨
where Ip denotes the incomplete beta function and a = n2 .
Proof: Let X be the number of parents possessing theallele 1 at locus k among n selected parents. Since the process

of random selection is independent, it is a Bernoulli process.
Performing this selection n times, the number X holds abinomial distribution with p.m.f.
µ ¶
n
x
n−x
s
Pr(X = x) = B(x; n, pk ) =(psk ) (1 − psk ).
x
Let D1 denote the event that OB-Scan assigns the allele 1
to the offspring locus k. According to Definition 2, OB-Scanyields1 if x > n/2,
Pr(D1 | X = x) = 0 if x < n/2,
1
if x = n/2.
2
For OB-Scan with odd number of parents (n = 2a − 1 witha ∈ N>1 ), from (8) we havepobk = Pr(D1 ) ==n
X

Pr(D1 | X = x) · Pr(X = x)

x=0
2a−1
X

B(x; 2a − 1, psk ) = Ipsk (a, a).

x=aSimilarly, for OB-Scan with even number of parents (n = 2awith a ∈ N), we have
pob
k =

2a
X

1
B(x; 2a, psk ) + B(a; 2a, psk )
2
x=a+1

1
a
a
(ps ) (1 − psk )= Ipk (a, a) −aBeta(a, a) k
µ ¶
1 2a
a
a
+
(psk ) (1 − psk )(from (9))
2 a¸·
1 (2a)!
Γ(2a)aa= Ipsk (a, a) + −+(psk ) (1 − psk )aΓ(a)Γ(a) 2 a!a!
= Ipsk (a, a).
ob(n)Corollary 1 (Pairwise Equivalence): Let pk
be the genefrequency pob
corresponding
ton-parent
OB-Scan.
For n ∈
k
2N and n ≥ 4,ob(n)ob(n−1)
pk § =¨pk §.¨nProof: Trivial (since 2 = n−1
in Lemma 4).
2
C. Variation by Mutation
In this work, the analysis of mutation focuses on themost popular mutation — bit-flip mutation. Bit-flip mutation
randomly chooses a locus and then flips the gene at this locus,
i.e. 0 → 1 and 1 → 0. A parameter γm , called mutation rate,
was introduced to determine the probability for a gene to be
mutated. The variation of gene frequency caused by bit-flip
mutation is calculated in the following lemma.
Lemma 5: Suppose we have the gene frequency pxk . Given
the mutation rate γm , the gene frequency of the offspring
mutated by bit-flip mutation hasxxpm
k = pk + γm (1 − 2pk ).
Proof: Considering bit-flip mutation, the cases to yield
the gene 1 at locus k are: 0 → 1 (mutated) and 1 → 1 (notmutated). Let ck be the gene at locus k before mutation andc0k be the gene after mutation. The gene frequency0pm
k = Pr{ck = 1 | ck = 0} Pr{ck = 0}
+ Pr{c0k = 1 | ck = 1} Pr{ck = 1}
= γm (1 − pxk ) + (1 − γm )pxk
= pxk + γm (1 − 2pxk ).

IV. M ODELING WITH M ARKOV C HAINS
Markov chains have been used to model the exact behaviorof GAs [2], [13], [20] and to analyze the convergence of GAs[7], [9], [17], [18]. In this paper, we use Markov chains tomodel the evolution of gene frequency. Furthermore, the mean
fitness in the OneMax problem is derived from this Markov
model.
A. The Model for Gene Frequency
In light of gene frequency, GA can be viewed as a stochastic
process manipulating the number of allele 1 (or 0) in the
population: Let random variables Gk (t) ∈ {0, 1, . . . , m} bethe number of allele 1 at locus k at generation t. The processof GAs on gene frequency can be represented as {Gk (t) :t ∈ Z∗ }. Since for every i0 , i1 , . . . , it+1 ∈ {0, 1, . . . , m} theprocess {Gk (t)} satisfies
Pr{Gk (t + 1) = it+1 | Gk (t) = it , . . . , Gk (0) = i0 }= Pr{Gk (t + 1) = it+1 | Gk (t) = it },the process {Gk (t)} is a Markov chain. The formal definitionof the Markov chain for gene frequency is given as follows.
Definition 11 (Markov Chain for Gene Frequency): In theMarkov chain {Gk (t)} for gene frequency at locus k ∈{1, . . . , l} in GAs,
1) the state is defined as the number of allele 1 at locus k inthe population; thereby the state space is {0, 1, . . . , m}.
A state i in {Gk (t)} gives the gene frequency
pk =

i
.
m
def

2) The transition matrix of {Gk (t)} is defined as P =(ρij ), where ρij is the transition probability of state ito state j.
defρij = Pr{Gk (t + 1) = j | Gk (t) = i}.
The previous section has shown how selection, OB-Scan, andmutation affect gene frequency. From those formulae, we canderive the transition probabilities of the Markov chain {Gk (t)}for the evolution of gene frequency in MPGA.
Theorem 1: For a GA using selection with selection intensity I, n-parent OB-Scan, and bit-flip mutation with γm ,the transition probability ρij of the Markov chain {Gk (t)}corresponding to that GA isρij = B(j; m, p0k )with³l n m l n m´
p0k = I i q i(m−i)
,
2
2
m +I
m2 l
µ
³l n m l n m´¶+ γm 1 − 2I i q i(m−i)
,
2
2
m +I
m2 l
Proof: The state i of transition probability ρij suggests
the gene frequency pk = mi . Given this frequency pk , fromeq. (7), Lemma 4, and Lemma 5, we can compute the genefrequency p0k of the offspring reproduced by the predefinedGA:
p0k = pxk + γm (1 − 2pxk )³³l n m l n m´´³l n m l n m´,
+ γm 1 − 2Ipsk,= Ipsk2
2 ³l m l m´
2
2
n
n
q
=Ii
,
i(m−i)
2
2
2
m +I
µ ml
³l n m l n m´¶q+ γm 1 − 2I i,
i(m−i)
2
2
m +I
m2 l
In generational GAs, population is completely replaced withthe subpopulation consisting of m offspring reproduced bym times of selection-crossover-mutation process. Since thisprocess is independent, the number of allele 1 holds a binomial
distribution B(m, p0k ). Therefore, the transition probabilityρij = Pr{Gk (t + 1) = j | Gk (t) = i}
= B(j; m, p0k ).

Proposition 1: The Markov chain {Gk (t)} for the GA
given in Theorem 1 is time homogeneous.
Proof: According to Theorem 1, the transition probabilityρij of the Markov chain {Gk (t)} is independent of time t.
Therefore, the Markov chain {Gk (t)} is time homogeneous.
Now we can utilize (10) to compute the state distribution andfurther the mean fitness at generation t.
Theorem 3: For the GA defined in Theorem 1, given thestate distribution ~π (t), we have the mean fitness f¯(t) andvariance σF (t) in the OneMax problem at generation t:ml Xf¯(t) =jπj (t)m j=0m
l X
j(m − j)πj (t)m2 j=0
Proof: Given the state distribution ~π (t) at generation t.
The gene frequency pk (t) at any locus k ∈ {1, . . . , k}
¶
m µ
m
X
1 X
j
pk (t) =Pr{Gk (t) = j} =jπj (t).
m
m j=0
j=0

σF2 (t) =With the above equation, from Lemma 2 we obtain the mean
fitness at generation tf¯(t) =lX
k=1

A Markov chain consists of a family of random variables;
therefore it has a probability distribution of states for eachrandom variable. In terms of Markov processes, this probability distribution is called state distribution.
Definition 12 (State Distribution):1) Denoted by a probability vector ~π (t)=(π0 (t), . . . , πN (t)), the state distribution of a Markov
chain {X(t)} with state space S = {0, . . . , N }represents the unconditional probabilities of states.
Precisely, for t ∈ Z∗ and i ∈ SXdef
πi (t) = Pr{X(t) = i} andπi (t) = 1.
i∈S2) The vector ~π (0) is called the initial distribution of{X(t)}.
Next, we introduce the time homogeneity of Markov chains.
The state distribution of time homogeneous Markov chain canbe computed by a direct way given in the following theorem.
Definition 13 (Time Homogeneous): A Markov chain issaid to be time homogeneous if its transition probabilities are
independent of time. That is, for all t ∈ Z∗
ρij = Pr{X(t + 1) = j | X(t) = i}.
Theorem 2 ([6, pp.57]): Suppose we have a time homogeneous Markov chain with transition matrix P. Given the initial
distribution ~π (0), the state distribution at generation t can beobtained by~π (t) = ~π (0)Pt .
(10)m

pk (t) =l X
jπj (t),
m j=0

and the variance
σF2 (t) =

l
X
¡
k=1

m
¢
l X
j(m − j)πj (t).
pk (t) − p2k (t) = 2
m j=0

B. Convergence
Theorem 1 gave the transition matrix of the Markov chain{Gk (t)} for the GA using selection with selection intensity
I, n-parent OB-Scan, and bit-flip mutation with mutation rate
γm . Of particular interest to us is, if at all, the convergenceof {Gk (t)} — at that time the state distribution will stayinvariant once the Markov chain achieves it. Such a state distribution is referred to as stationary distribution (or equilibrium
distribution) and this chain is called stationary [6]. In thissection we will show that the MPGA given in Theorem 1 has
this convergence property. Furthermore, the mean convergencefitness in the OneMax problem will be derived.
Definition 14 (Stationary Distribution): A state distribution~π is said to be the stationary distribution for the Markov chain
with transition matrix P, if~π P = ~π .
(11)Lemma 6 (Ergodicity [4, pp.50]): A Markov chain is ergodic if and only if∃t ∈ Z+ : Pt > 0,
where 0 denotes zero matrix, i.e. all components in 0 are zeros.

Theorem 4 (Existence of Stationarity [4, pp.50]): For an
ergodic Markov chain with state space {0, 1, . . . , m},1) the powers Pt of the transition matrix P converge
componentwise to a matrix whose all rows are equal.
If we denote a typical
Prow by ~π = (π0 , . . . , πm ), thenwe have πi > 0 and i πi = 1 for all i ∈ {0, . . . , m}.
2) ~π is the unique vector such that ~π P = ~π .
This unique ~π is called the stationary distribution associatedwith the chain.
To prove the existence of convergence for the Markov chain{Gk (t)}, we need to show this chain is ergodic.
Proposition 2: With mutation rate 0 < γm < 1, the Markov
chain corresponding to the GA given in Theorem 1 is ergodic.
Proof: Considering the case t = 1, from Theorem 1 wehave
ρij = 0 ⇐⇒ B(j; m, p0k ) = 0
with
p0k = pxk + γm (1 − 2pxk ).

(12)

The above binomial distribution equals zero if and only if theprobability p0k = 0 or 1. In case of 0 < γm < 1, the solutions
for p0k = 0 or p0k = 1 in (12) are
pxk < 0or

pxk > 1.

Both solutions violate the Probability Axiom for pxk , that is,
0 ≤ pxk ≤ 1. This implies for all i, j ∈ {0, . . . , m}
ρij > 0.
According to Theorem 4, the chain {Gk (t)} is proven to be
ergodic.
Theorem 5: Suppose we have the GA defined in Theorem 1
with 0 < γm < 1. Let {Gk (t)} be the corresponding Markov
chain at locus k ∈ {1, . . . , l}. We have the stationary distribution ~π = (π1 , . . . , πl ), which gives for all j ∈ {0, . . . , m}lim Pr{Gk (t) = j} = πj .
Proof: Proposition 2 shows the Markov chain {Gk (t)}is ergodic. According to Theorem 4, there exists the uniquestationary distribution ~π giving for all j ∈ {0, . . . , m}t→∞

πj = lim Pr{Gk (t) = j}.
t→∞Corollary 2 (Mean Convergence Fitness): For the GA defined in Theorem 1 with 0 < γm < 1, the mean and varianceof convergence fitness in the OneMax problem are
m
l X
f¯∗ =
jπj
m j=0
m
l X
j(m − j)πj
m2 j=0
Proof: Substitute stationary distribution ~π given in Theorem 5 into the equations in Theorem 3; then we complete
the proof.
∗

σF2 =

V. T HEORETICAL R ESULTS AND E XPERIMENTAL
VALIDATIONThis section demonstrates the theoretical results obtained
from the above theorems. Moreover, we conduct several experiments on the OneMax problem to verify our theoreticalarguments. The setting of MPGA used in our experiments
is generational GA, bit-string representation, population size
m = 128, OB-Scan, bit-flip mutation, and 1000 generations
for terminal condition. The size of OneMax problem is set to
be 100 bits, i.e. l = 100. Each experiment setting includes 100
independent runs.
In this paper we adopt linear ranking selection [14] as
the selection operator. The linear ranking selection, as its
name tells, assigns the probability for a chromosome to be
selected according to a linear formula based on the rank ofthis chromosome. Let i ∈ {1, . . . , m} be the rank (1 for the
worst chromosome and m for the best one), the probability
·
¸
1
i−1
Pr{~ci to be selected} =η − + (η + − η − ),m
m−1
where 1 ≤ η + ≤ 2 and η − = 2 − η + are two parameters−
used to control the linear relation [3]. Precisely, ηm andη+m are the expected probabilities for the worst and the bestchromosome to be selected, respectively. For the linear ranking
selection, Blickle and Thiele [5] derived its selection intensity.
In the following text we will use their formula to compute theselection intensity of linear ranking selection:1
1
IR = (1 − η − ) √ = (η + − 1) √ .
(13)ππFigure 2 compares the variation of mean fitness computedby Theorem 3 with the mean fitness averaged over 100
experiments. First, this figure shows the theoretical and theexperimental results fit very well. Second, we can see theprofiles of OB-Scan with even number n are very close to
those of OB-Scan with the number n − 1. This confirms the
pairwise equivalence claimed in Corollary 1. In addition, formutation rates γm ≥ 0.05, OB-Scan with n > 2 achieves
higher fitness and even faster convergence than OB-Scan withn = 2, viz uniform crossover. Nevertheless, there is no winner
for all these four mutation rates; the best number of parents
is dependent upon the mutation rate. It is noteworthy that the
profiles for 7- and 8-parent OB-Scan at γm = 0.2 continues
climbing after 20 generations while others turn into steadythen. This condition also occurs for 3- and 4-parent OBScan at γm = 0.1. Although the mutation rates in these twocases are relatively strong to the common setting γm = 1l ,they keep the MPGA using OB-Scan on advancing in fitness.
These results indicate the important role of mutation in theperformance of MPGA using OB-Scan.
Furthermore, we examine the solution quality for 1000 generations. Figure 3 depicts the experimental and the theoretical
fitness means in 1000 generations (t = 1000); additionallyit plots the theoretical mean convergence fitness (t → ∞)according to Corollary 2. First, we can see that the theoreticaland the experimental results fit very well except two cases:

90

90
n=2
n=3
n=4
n=7
n=8
n=15
n=16

80

70

Fitness Mean

Fitness Mean

80

n=2
n=3
n=4
n=7
n=8
n=15
n=16

85
60

80

80
75
70
40

70

60

75

75

70

70

50

45

50
65

65
60
40

40
0

20

40

45
60

40

40
80

100

0

20

40

Generations(a) γm = 1/l = 0.01

80

100

80

100

(b) γm = 0.05

90

90
n=2
n=3
n=4
n=7
n=8
n=15
n=16

80

n=2
n=3
n=4
n=7
n=8
n=15
n=16

80

70

Fitness Mean

Fitness Mean

45
60

Generations

60

50

70

60

50

40

40
0

20

40

60

80

100

Generations(c) γm = 0.1

0

20

40

60
Generations(d) γm = 0.2

Fig. 2. Comparison of mean fitness obtained from theory (black bold lines) and experiment (color thin lines) for the MPGA using linear ranking selection
with η + = 1.5, n-parent OB-Scan, and bit-flip mutation with γm = 0.01, 0.05, 0.1, and 0.2

n = 3, 4 at γm = 0.1 and n = 9, 10 at γm = 0.2. Inthese two cases experimental fitness is higher than theoreticalone. We reason this discrepancy results from violation of
the assumption Var(σ) ¿ E2 [σ] in the approximation of theintensity Ikp . Once this assumption does not hold, eq. (5)tells that the consequent gene frequency psk will be higher
than the value computed by (7). In the OneMax problem it
leads to a higher fitness, which is reflected in the discrepancy
between theoretical and experimental fitness in those twocases. Second, as shown in Fig. 3, the closeness in mean fitness
between n-parent and (n − 1)-parent OB-Scan for n ∈ 2N
reconfirms the pairwise equivalence. Third, in comparison of
the experimental mean fitness at t = 1000, the GA using 2parent OB-Scan performs best at γm = 0.01 but does worst atγm ≥ 0.05. Concerning the influence of mutation, the mean
fitness for 2-parent OB-Scan decreases monotonically with theincrease of mutation rate. Contrary, experimental results at
t = 1000 show that putting mutation rate up may improve
the GA using more than two parents in OB-Scan. However,as t → ∞, the mean fitness for OB-Scan with more than twoparents turns to decrease with mutation rate absolutely, whichis the same tendency with 2-parent OB-Scan. Fig. 3 further
points out that, in theory, all the GAs using OB-Scan withmore than two parents will converge to higher fitness thanthe GA using 2-parent does. Yet, there exists a gap in fitness

between t = 1000 and t → ∞. A reason for this gap is thatour prescribed terminal condition is not long enough for someof the test GAs to converge.
VI. C ONCLUSIONSThis paper proposes a Markov model to investigate theconvergence of multi-parent genetic algorithms. Specifically,
we probe into the mean fitness of the GA using occurrence
based scanning crossover (OB-Scan) — a multi-parent generalization of uniform crossover.
The theoretical results demonstrate several interesting
points. First, the analysis reveals the pairwise equivalence in
OB-Scan. That is, for an even number n, the performanceof n-parent OB-Scan equals to that of (n − 1)-parent OBScan. Second, it manifests the critical role of mutation in
the performance of MPGAs using OB-Scan. In the OneMax
problem, the theoretical results show that the MPGA using
more parents in OB-Scan together with mutation is capableof higher mean convergence fitness than the GA using 2parent OB-Scan, viz uniform crossover. All these theoreticalresults are examined by a series of experiments on the OneMax
problem. It shows that the theoretical and the experimental results fit very well. This consistency validates the capability ofour proposed model. Furthermore, the superiority of n-parent(n > 2) OB-Scan over 2-parent OB-Scan in the OneMax
problem is verified theoretically as well as empirically.

100

90

90

80

80

Fitness Mean

Fitness Mean

100

70

60

70

60

50

50
Theoretical (t → ∞)Theoretical (t=1000)
Experimental

Theoretical (t → ∞)Theoretical (t=1000)
Experimental

40

40
2

4

6

8

10

12

14

16

18

20

2

4

6

8

Number of Parents (n)(a) γm = 1/l = 0.01

12

14

16

18

20

(b) γm = 0.05

100

100

90

90

80

80

Fitness Mean

Fitness Mean

10

Number of Parents (n)

70

60

70

60

50

50
Theoretical (t → ∞)Theoretical (t=1000)
Experimental

Theoretical (t → ∞)Theoretical (t=1000)
Experimental

40

40
2

4

6

8

10
12
Number of Parents (n)

14

16

18

20

(c) γm = 0.1

2

4

6

8

10
12
Number of Parents (n)

14

16

18

20

(d) γm = 0.2

Fig. 3. The mean fitness of the MPGA using linear ranking selection with η + = 1.50, n-parent OB-Scan, and mutation with γm = 0.01, 0.05, 0.1, and 0.2

The proposed model established a theory concerning theindividual as well as the integral influence of multi-parent
crossover with selection and mutation on the performance ofMPGA. It also showed the power and the limit of OB-Scan,and manifested the key role of mutation in this crossover.
However, this analysis focuses only on the MPGA using OBScan in the OneMax problem. An extension to other crossovers
and problem domains remains to be investigated in the future.
R EFERENCES[1] M. Abramowitz and I.A. Stegun, editors. Handbook of Mathematical
Functions with Formulas, Graphs, and Mathematical Tables. Dover
Publications, 1972. ninth Dover printing.
[2] H. Asoh and H. Mühlenbein. On the mean convergence time ofevolutionary algorithms without selection and mutation. In Parallel
Problem Solving from Nature – PPSN III, volume 866 of LNCS, pages
88–97, Berlin, 1994. Springer.
[3] T. Bäck. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In Proceedings of the First IEEE
Conference on Evolutionary Computation, pages 57–62, 1994.
[4] E. Behrends. Introduction to Markov Chains. Vieweg, 2000.
[5] T. Blickle and L. Thiele. A comparison of selection schemes used in
genetic algorithms. TIK-Report 11, TIK Institut fur Technische Informatik und Kommunikationsnetze, Computer Engineering and Networks
Laboratory, ETH, Swiss Federal Institute of Technology, 1995.
[6] P. Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation,and Queues. Springer Verlag, 1999.
[7] T.E. Davis and J.C. Principe. A markov chain framework for the simple
genetic algorithm. Evolutionary Computation, 1(3):269–288, 1993.
[8] A.E. Eiben. Multiparent recombination in evolutionary computing. In
Advances in Evolutionary Computing, pages 175–192. Springer, 2002.
[9] A.E. Eiben, E.H.L. Aarts, and K.M. Van Hee. Global convergenceof genetic algorithms: A markov chain analysis. In Parallel Problem

Solving from Nature (PPSN 1), volume 496 of LNCS, pages 4–12.
Springer-Verlag, 1991.
[10] A.E. Eiben and T. Bäck. An empirical investigation of multiparent
recombination operators in evolution strategies. Evolutionary Computation, 5(3):347–365, 1997.
[11] A.E. Eiben, P.-E. Rau’e, and Zs. Ruttkay. Genetic algorithms with multiparent recombination. In Parallel Problem Solving from Nature – PPSN
III, volume 866 of LNCS, pages 78–87. Springer, 1994.
[12] D.S. Falconer and T.F.C. Mackay. Introduction to Quantitative Genetics.
Prentice Hall, 4 edition, 1996.
[13] D.E. Goldberg and P. Segrest. Finite markov chain analysis of genetic
algorithms. In Proceedings of the 2nd International Conference on Genetic Algorithms and their Applications, pages 1–8. Lawrence Erlbaum
Associates, 1987.
[14] J.J. Grefenstette and J.E. Baker. How genetic algorithms work: A criticallook at implicit parallelism. In Proceedings of the Third International
Conference on Genetic Algorithms, pages 20–27. Morgan Kaufmann
Publishers, 1989.
[15] D.L. Hartl and A.G. Clark. Principles of Poppulation Genetics. Sinauer
Associates, 1 edition, 1989.
[16] H. Mühlenbein. The equation for the response to selection and its use
for prediction. Evolutionary Computation, 5(3):303–346, 1998.
[17] A.E. Nix and M.D. Vose. Modeling genetic algorithms with markov
chains. Annals of Mathematics and Artificial Intelligence, 5:78–88, 1992.
[18] Günter Rudolph. Convergence analysis of canonical genetic algorithms.
IEEE Transactions on Neural Networks, 5(1):96–101, 1994.
[19] G. Syswerda. Uniform crossover in genetic algorithms. In Proceedingsof the 3rd International Conference on Genetic Algorithms, pages 2–9.
Morgan Kaufmann, 1989.
[20] D. Thierens, D.E. Goldberg, and Â.G. Pereira. Domino convergence,drift, and the temporal-salience structure of problems. In Proceedingsof 1998 IEEE Iternational Conference on Evolutionary Computation,
pages 535–540, 1998.
[21] S. Tsutsui and A. Ghosh. A study on the effect of multi-parent
recombination in real coded genetic algorithms. In Proceedings ofInternational Conference on Evolutionary Computation, pages 828–833,
1998.