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

Abstract. This paper investigates genetic drift in multi-parent genetic
algorithms (MPGAs). An exact model based on Markov chains is proposed to formulate the variation of gene frequency. This model identiﬁes the correlation between the adopted number of parents and themean convergence time. Moreover, it reveals the pairwise equivalence
phenomenon in the number of parents and indicates the acceleration ofgenetic drift in MPGAs. The good ﬁt between theoretical and experimental results further veriﬁes the capability of this model.

1

Introduction

Multi-parent genetic algorithms (MPGAs) are genetic algorithms using multiparent crossovers. Traditionally, genetic algorithms (GAs) adopt two parents incrossover to reproduce oﬀspring. This idea is reasonable because, to the best of
our knowledge, the form of sexual reproduction on the Earth is absolutely of twoparents. Multi-parent crossovers break through this natural limitation by allowing more than two parents in the process of crossover. In a sense, multi-parent
genetic algorithms can be viewed as multi-parent generalization of genetic algorithms. In light of MPGAs, several multi-parent crossovers have been proposedand shown their power in a variety of optimization problems [5,7,15]. However,most of these crossovers are validated empirically; only a few theoretical analysesof multi-parent crossovers are conducted.
Genetic drift is a phenomenon that a ﬁnite population, even if no selection
pressure is applied, will ultimately converge to a uniform population. The rateof genetic drift serves as an important index of how fast population diversity
is lost. Schippers [14] studied the genetic drift of two multi-parent crossovers:
uniform scanning crossover (U-Scan) and occurrence based scanning crossover(OB-Scan). His work revealed that U-Scan has no inﬂuence on genetic drift whilst
OB-Scan induces severe genetic drift, as the number of parents is increased.
Nevertheless, the strength of genetic drift in his work is determined by comparing
the probabilities of drift in and drift out. The rate of genetic drift in MPGAs isstill an open question.
This paper investigates in theory the rate of genetic drift in MPGA using
OB-Scan. Speciﬁcally, we propose an exact model for the mean convergence
M. Capcarrere et al. (Eds.): ECAL 2005, LNAI 3630, pp. 403–412, 2005.
c Springer-Verlag Berlin Heidelberg 2005
404

C.-K. Ting

time — the principal measure of genetic drift rate [2]. First, we analyze the genefrequency altered by multi-parent crossovers. Based on gene frequency, we model
the behavior of MPGAs through Markov chains. This Markov model aﬀords thecorrelation between parent numbers and mean convergence time. In addition, thetheoretical results reveal the pairwise equivalence of parent numbers in OB-Scan.
These theoretical results are further veriﬁed by a series of experiments.
The rest of this paper is organized as follows. Section 2 describes OB-Scan
and Section 3 analyzes its eﬀect on gene frequency. Next, we model MPGAs with
Markov chains. Theoretical results and experimental validation are presented in
Section 5. Finally, conclusions are drawn in Section 6.

2

Occurrence Based Scanning Crossover (OB-Scan)

Occurrence based scanning crossover is one of the scanning crossovers proposedby Eiben et al. [6]. Scanning crossovers are multi-parent generalization of uniform crossover — a widely used crossover in GAs. In uniform crossover, thedonor for each locus is randomly picked from two selected parents. Extended
to more than two parents, scanning crossovers choose the donor at random orusing heuristics. According to diﬀerent strategies, Eiben et al. proposed threevariations of scanning crossovers: uniform scanning crossover (U-Scan), occurrence based scanning crossover (OB-Scan), and ﬁtness based scanning crossover(FB-Scan). In this paper, we only discuss OB-Scan.
Rather than at random, OB-Scan determines oﬀspring genes depending on
the occurrence of parental genes at that locus. Speciﬁcally, it picks the majorityof parental gene values as the oﬀspring gene for each locus. Note that in thispaper OB-Scan is deﬁned to break ties by randomly1 choosing a binary. Examplesof 2-parent OB-Scan (corresponding to uniform crossover) and 4-parent OB-Scanare given in Fig. 1. The formal deﬁnitions of the components of GAs and OBScan 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

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

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

1

In the original version of OB-Scan [6], OB-Scan breaks ties by directly inheriting
the genes of the ﬁrst selected parent. However, random tie break conforms to generalization of uniform crossover.

On the Mean Convergence Time of Multi-parent Genetic Algorithms

405

Deﬁnition 1 (Chromosome and Population).
def

1. A chromosome c is encoded as a bit string, i.e. c = (c1 , . . . , cl ) ∈ {0, 1}l,where ci denotes a gene and l is the chromosome length.
def
2. A population C is a set of chromosomes: C = {c1 , . . . , cm }, where ci ∈l{0, 1} and m is the population size.
Deﬁnition 2 (OB-Scan). Given n parents c1 , . . . , cn ∈ C selected from population C, OB-Scan reproduces the oﬀspring c = Xob (c1 , . . . , cn ) = (c1 , . . . , cl )
by
⎧
n
n
⎪0
if
⎨
j=1 (cj )i < 2nn
ci = 1for i = 1, . . . , l,if
j=1 (cj )i > 2⎪⎩
rand(0, 1) otherwise
where (cj )i denotes the ith gene of the chromosome cj , and rand (0, 1) is a binary
random function.

3

Variation of Gene Frequency

Gene frequency is widely used as a quantitative measure of genetic variation in
population genetics [9]. It also suﬃces to clue us in on the course of evolution
in GAs. In this section we analyze the variation of gene frequency caused by
OB-Scan.
Deﬁnition 3 (Gene Frequency). The gene frequency pk (α, t) is deﬁned 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 of population where chromosomes possess allele α at locus k. The
gene frequency
def |Ck (α)|,
pk (α, t) =|C|
where |C|and |Ck (α)| represent the cardinality of set C and Ck (α).
As above deﬁned, chromosomes are represented as binary strings. Thus there
exists exactly two gene frequencies pk (1, t) and pk (0, t) with pk (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)).
Deﬁnition 4 (Variation of Gene Frequency in GAs). Let psk (t), pxk (t), pmk (t)be the gene frequencies after performing selection, crossover, and mutation at
generation t. The variation of gene frequency in GAs can be expressed as
selection

crossovermutationsurvivor→ pxk (t) −−−−−−→ pm−−−−→ pk (t + 1),
pk (t) −−−−−→ psk (t) −−−−−−
k (t) −

(1)

To investigate genetic drift, random selection and no mutation is assumed. In
this paper we focus on generational GAs. As a result, the gene frequency in406

C.-K. Ting

the process of GA is only aﬀected by the sampling of random selection and theprocess of crossover. These inﬂuences will be analyzed in Lemma 1. Incidentally,
the symbol pk (t) is referred to as pk while the indication of time t is not in eﬀect.
Before conducting the analysis of OB-Scan, we introduce the incomplete beta
function for simplifying the expression of equations .
Deﬁnition 5 (Incomplete Beta Function). The incomplete beta function
is deﬁned as
 x
1
def
ta−1 (1 − t)b−1 dt,
Ix (a, b) =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B(i; n, p) = Ip (a, n − a + 1).

(2)

1
xa (1 − x)b + Ix (a + 1, b).
a · Beta(a, b)

(3)

i=a

2. (26.5.16 [1])Ix (a, b) =Using the above deﬁnition and properties, we embark on the analysis of OBScan’s inﬂuence on gene frequency.
Lemma 1. Suppose we have the gene frequency pk of the population. The genefrequency, denoted by pob
k , of the oﬀspring reproduced by n-parent OB-Scan Xob
with n ∈ N>1 ispob
k = Ipk (a, a),where Ip denotes the incomplete beta function and a = n2 .
Proof. Let X be the number of parents possessing the allele 1 at locus k amongn 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 probability mass function
Pr(X = x) = B(x; n, pk ) =nxn−x(pk ) (1 − pk ).
x

Let D1 denote the event that OB-Scan assigns the allele 1 to the oﬀspring locus
k. According to Deﬁnition 2, OB-Scan yields⎧⎪⎨1 if x > n/2,
Pr(D1 | X = x) = 0 if x < n/2,⎪
⎩1
if x = n/2.
2

On the Mean Convergence Time of Multi-parent Genetic Algorithms

407

For OB-Scan with an odd number of parents (n = 2a − 1 with a ∈ N>1 ), from(2) we havepobk = Pr(D1 ) ==nPr(D1 | X = x) · Pr(X = x)

x=0
2a−1


B(x; 2a − 1, pk ) = Ipk (a, a).

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

2a


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

1
1 2a
a
a
a
a
(pk ) (1 − pk ) +(pk ) (1 − pk )aBeta(a, a)
2 a
1 (2a)!
Γ(2a)+= Ipk (a, a) + −(pk )a (1 − pk )aaΓ(a)Γ(a) 2 a!a!
= Ipk (a, a) −= Ipk (a, a).


ob(n)
Let pkbe the gene frequency pob
Corollary 1 (Pairwise Equivalence).
kcorresponding to n-parent OB-Scan. For n ∈ 2N and n ≥ 4,ob(n)Proof. Trivial (since

4

n
2

pk

=

 n−1
2

ob(n−1)= pk.

in Lemma 1).

Modeling with Markov Chains

Markov chains have been used to model the exact behavior of GAs [2,8,10] andto analyze the convergence of GAs [4,11,13]. In this paper, we use Markov chains
to model the evolution of gene frequency. From this Markov model, the mean
convergence time can be derived.
In light of gene frequency, a 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} be the number of allele 1 at locus k at generation t. The
process of GAs on gene frequency can be represented as {Gk (t) : t ∈ Z∗ }. Since
for every i0 , i1 , · · · , it+1 ∈ {0, 1, . . . , m} the process {Gk (t)} satisﬁes
Pr{Gk (t + 1) = it+1 | Gk (t) = it , Gk (t − 1) = it−1 , . . . , Gk (0) = i0 }= Pr{Gk (t + 1) = it+1 | Gk (t) = it },the process {Gk (t)} is a Markov chain. The formal deﬁnition of the Markov chain
for gene frequency is given as follows.

408

C.-K. Ting

Deﬁnition 6 (Markov Chain for Gene Frequency). In the Markov chain{Gk (t)} for gene frequency at locus k ∈ {1, . . . , l} in GAs,
1. the state is deﬁned as the number of allele 1 at locus k in the population andthe state space is thus {0, 1, . . . , m}. A state i in {Gk (t)} implies the genefrequency at locus k isi
pk = .
mdef

2. The transition matrix of {Gk (t)} is deﬁned as P = (ρij ), where ρij is thetransition probability of state i to state j:defρij = Pr{Gk (t + 1) = j | Gk (t) = i}.
The previous section has shown how OB-Scan changes the gene frequency. From
those formulae, we derive the transition probabilities of the Markov chain {Gk (t)}for the evolution of gene frequency in MPGAs.
Theorem 1. For a GA using random selection, n-parent OB-Scan, and no mutation, the transition probability ρij of the Markov chain {Gk (t)} corresponding
to this GA isρij = B(j; m, pk ) n   n 
,
.
m
2
2
Proof. The state i of transition probability ρij suggests the gene frequency pk =i

m . Given this frequency pk , from Lemma 1 we can obtain the gene frequency pk
of the oﬀspring reproduced by a GA using random selection, n-parent OB-Scan,and no mutation:
 n   n i,.
pk = pob
k = Im2
2
In generational GAs, population is completely replaced with the subpopulation,
consisting of m oﬀspring reproduced by m times of selection-crossover-mutation
process. Since this process is independent, the number of allele 1 holds a binomial
distribution B(m, pk ). Therefore, the transition probability
withpk = I i

ρij = Pr{Gk (t + 1) = j | Gk (t) = i}
= B(j; m, pk ).
For the Markov chain {Gk (t)}, of particular interest to us is, if at all, the convergence of {Gk (t)} — at that time the population turns out to be either all-zeros
or all-ones at each locus. For this, ﬁrst we introduce a special kind of Markov
chains, called absorbing Markov chains [3], which have this convergence property, i.e. absorption. Next, we will prove the Markov chain corresponding to
the aforementioned GA belongs to such kind of Markov chains; that is to say,the corresponding GA will converge. From the properties of absorbing Markov
chains we can further derive the mean convergence time.

On the Mean Convergence Time of Multi-parent Genetic Algorithms

409

Deﬁnition 7 (Absorbing States).
1. The closed set S c is a set of states whose transition probabilities ρij = 0 for/ S c.
all i ∈ S c , j ∈2. A state i is said to be absorbing if and only if ∃S c : S c = {i} ⇐⇒ ρii = 1.
3. A Markov chain with absorbing states is called an absorbing Markov chain.
Proposition 1. For the GA given in Theorem 1, its corresponding Markov
chain {Gk (t)} is an absorbing Markov chain with exactly two absorbing states:
0 and m.
Proof. According to the deﬁnition of absorption and Theorem 1, we know
(4)
{Gk (t)} is absorbing ⇐⇒ ∃i : ρii = 1 ⇐⇒ ∃i : B(i; m, pk ) = 1.



n
n
The solutions of B(i; m, pk ) = 1 subject to pk = I mi
and n ∈ N>1 are
2 , 2


(i) i = 0 with pk = 0 and (ii) i = m with pk = 1. This leads to, for the Markov
chain {Gk (t)}
ρ00 = ρmm = 1 =⇒ {Gk (t)} is absorbing .
Thus we complete the proof that the Markov chain {Gk (t)} is absorbing withexactly two absorbing states 0 and m.

The above proposition indicates the chain {Gk (t)} will get absorbed into state 0
or m. It means that the process of the predeﬁned GA will ‘drift’ into all-zeros or
all-ones for each locus, that is, reaching convergence. In addition to the existenceof convergence, we are interested in the mean time to reach it. To compute themean time for a chain to get absorbed, we introduce the fundamental matrix [3]and its related property below.
Deﬁnition 8 (Fundamental Matrix). For a Markov chain with b absorbing
states, the transition matrix can be rewritten as
P=

Ib 0
RQ

,

(5)

where Ib is a b × b identity matrix. The fundamental matrix for this absorbing
Markov chain is deﬁned asdef
F = (I − Q)−1 .
Theorem 2 ([12]). Let F be the fundamental matrix of an absorbing Markov
chain. The fundamental matrix F stands for the mean time τij that the process
spends at transient state j starting from transient state i.
Theorem 3 (The Mean Convergence Time of MPGA). Suppose we have
the GA given in Theorem 1. Let F = (τij ) be the fundamental matrix of theMarkov chain {Gk (t)} corresponding to this GA. For some locus k ∈ {1, . . . , l},given the initial state distribution π(0) = (π0 (0), . . . , πm (0)), the mean convergence time
m−1
 m−1

τ=
πi (0)τij .
i=1 j=1

410

C.-K. Ting

Proof. Let A be the set of absorbing states in {Gk (t)}. Proposition 1 gives A ≡{0, m}. According to Theorem 2, the fundamental matrix of {Gk (t)} represents
the mean time τij for i, j ∈ A. Hence, the mean time τi that the process spends
among transient states starting from transient state i can be derived by

τij .
τi =
j∈A

Given the initial state distribution π(0), we have the mean convergence time
τ=

m−1


τi Pr(i | t = 0) =

i=1

5

m−1


τi πi (0) =

i=1

m−1
 m−1


πi (0)τij .



i=1 j=1

Theoretical Results and Experimental Validation

This section demonstrates theoretical results obtained from the above theorems.
Moreover, we conduct experiments on single locus (l = 1) to verify these theoretical results. The setting of MPGA used in our experiments is generational GA,
bit-string representation, random selection, and no mutation. Each experimentsetting includes 1000 independent runs.
Figure 2 compares the mean convergence time obtained from Theorem 3 andfrom experiments. First, this ﬁgure shows that the theoretical and the experimental results ﬁt very well. In addition, it shows that for n ∈ 2N a MPGA
using n-parent OB-Scan performs correspondingly to that using (n−1)-parent
OB-Scan, which conﬁrms the pairwise equivalence claimed in Corollary 1. Second, this ﬁgure indicates the fact that, compared with two parents, using morethan two parents in OB-Scan causes a drastic decrease in mean convergence

11
400
10

The Mean Convergence Time (τ)

300
9

200

8

100
0
1

7

2

3

4

6

5
m=32
m=64
m=128
m=256
m=32 (exp)m=64 (exp)m=128 (exp)m=256 (exp)

4

3

2
1

2

3

4

5
6
Number of Parents ⎡n/2⎤

7

8

9

10

Fig. 2. Comparison of the theoretical (lines) and the experimental (symbols) mean
convergence time τ for n-parent OB-Scan and population size m

On the Mean Convergence Time of Multi-parent Genetic Algorithms

0.6

0.6

0.5

0.5

0.4

0.4

0.3

0.3

0.2

0.2

0.1

411

0.1

0
32

150
125

24
16
Number of allele 1

100
75
50

8

25
0 0

Generations

0
32
24
16
Number of allele 1

8
0 0

2

4

6

8

10

12

14

Generations

Fig. 3. The progress of genetic drift of 2-parent OB-Scan (left) and 3-parent OB-Scan
1(right) for population size m = 32 with initialization bias β = 32

time. Nonetheless, further raising parents yields a relatively small diﬀerence.
The mean convergence time (m = 256) for n = 2, for example, needs 351.55
generations while it takes only 10.17 generations for n = 3 (or 4) and 6.94 generations for n = 5 (or 6). This speedup in convergence reﬂects that OB-Scan withmore than two parents accelerates genetic drift.
Next, we examine the progress of genetic drift in case of a initialization
bias. We denote by β the bias of initial gene frequency to the allele 1. Figure
3 compares the progress of genetic drift of uniform crossover (i.e. 2-parent OBScan) and 3-parent OB-Scan for population size m = 32 under initialization bias
1
. As aforementioned, the genetic drift of 3-parent OB-Scan is much fasterβ = 32than that of uniform crossover. Interestingly, the distribution of convergence
probability of uniform crossover diﬀers from that of 3-parent OB-Scan either.
Asoh and Mühlenbein [2] have shown the convergence probability of uniform
crossover equals the initialization probability, which is reﬂected in Fig. 3. Yet,
adopting more parents does not follow this rule. The 3-parent OB-Scan gives
a probability (≈ 0.6) higher than the initialization probability ( 1732 ≈ 0.53).
This outcome suggests that using more parents in OB-Scan will intensify thepreference of the initialization.

6

Conclusions

This paper presents an exact model for exploration of genetic drift in MPGAs.
First we analyze the gene frequency altered by OB-Scan. Based on gene frequency, we model the behavior of MPGAs through Markov chains. The mean
convergence time is further derived from this model.
The theoretical results demonstrate that raising parents in OB-Scan shortens
the mean convergence time; that is, it accelerates genetic drift. This outcome not
only reconﬁrms Schippers’ claims about the genetic drift of scanning crossovers,
but also gives the expected time of convergence. In addition, our analysis reveals
the pairwise equivalence in OB-Scan: n-parent OB-Scan performs analogously

412

C.-K. Ting

with (n−1)-parent OB-Scan for n ∈ 2N. Moreover, the progress of genetic drift
under initialization bias suggests raising parents in OB-Scan will intensify thepreference of initialization for allele 0 or 1. The good ﬁt between theoretical andexperimental results validates our theoretical arguments and the capability ofthe proposed model.

References
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. Mühlenbein. On the mean convergence time of evolutionary algorithms without selection and mutation. In Parallel Problem Solving from Nature –PPSN III, volume 866 of LNCS, pages 88–97, Berlin, 1994. Springer.
3. P. Brémaud. Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues.
Springer Verlag, 1999.
4. T.E. Davis and J.C. Principe. A markov chain framework for the simple genetic
algorithm. Evolutionary Computation, 1(3):269–288, 1993.
5. A.E. Eiben. Multiparent recombination in evolutionary computing. In Advancesin Evolutionary Computing, pages 175–192. Springer, 2002.
6. A.E. Eiben, P.-E. Rau’e, and Zs. Ruttkay. Genetic algorithms with multi-parent
recombination. In Parallel Problem Solving from Nature – PPSN III, volume 866
of LNCS, pages 78–87. Springer, 1994.
7. A.E. Eiben and C.H.M. van Kemenade. Diagonal crossover in genetic algorithms
for numerical optimization. Journal of Control and Cybernetics, 26(3):447–465,
1997.
8. D.E. Goldberg and P. Segrest. Finite markov chain analysis of genetic algorithms.
In Proceedings of the 2nd International Conference on Genetic Algorithms andtheir Applications, pages 1–8. Lawrence Erlbaum Associates, 1987.
9. D.L. Hartl and A.G. Clark. Principles of Poppulation Genetics. Sinauer Associates,
1 edition, 1989.
10. J. Horn. Finite markov chain analysis of genetic algorithms with niching. In
S. Forrest, editor, Proceedings of the Fifth International Conference on Genetic
Algorithms, pages 110–117. Morgan Kaufmann Publishers, 1993.
11. A.E. Nix and M.D. Vose. Modeling genetic algorithms with markov chains. Annalsof Mathematics and Artiﬁcial Intelligence, 5:78–88, 1992.
12. A. Papoulis and S.U. Pillai. Probability, Random Variables, and Stochastic Processes. McGraw-Hill, New York, NY, USA, 4 edition, 2002. ISBN 0-07-048477-5.
13. G. Rudolph. Convergence analysis of canonical genetic algorithms. IEEE Transactions on Neural Networks, 5(1):96–101, 1994.
14. C.A. Schippers. Multi-parent scanning crossover and genetic drift. In Theoretical
Aspects of Evolutionary Computing, pages 307–330. Springer, 2001.
15. S. Tsutsui and A. Ghosh. A study on the eﬀect of multi-parent recombinationin real coded genetic algorithms. In Proceedings of International Conference on
Evolutionary Computation, pages 828–833, 1998.