1
Y n(k) x R(k)= 1 n(k) x R(k) x a"1'k)
keS (1 +c)LjeSkeS
Thus, P2(i I n) can be expressed as
Sn(j) x R(j) x a0',j)
P2(i I n) j= Eq. 4.14
Y YS n(k)x R(k)x ax(,k)1
je Ske S
n n(j) x R(j) x a"Oj)
je S
(1 + a)L n(k) x R(k)'
k S
and P2(m I n) is multinomially distributed as follows
M!
Vm, ne S' : P2(m I n)=x F P(i I nm()
1 m(i)! ies
ie S
= M1 xI P2(i I )m(i) Eq. 4.15
0mm ie S
(M) 1 Y n(j)x R(j)ax"('"j) m
m ( + +(X)"is n(k)xR(k)
keS
The transition probability matrix of the Markov chain representing the two-operator algo-
rithm is composed of the array of conditional probabilities defined by Eq. 4.15, i.e.
P= [P2(m I n)]. Eq. 4.16
Since the elements of P depend on a (and hence by Eq. 4.12 on pm(k)), the two-operator
Markov chain is generally not time-homogeneous. It is time-homogeneous if the mutation
probability is fixed.
Eq. 4.14-4.16 for the two-operator simple genetic algorithm are analogous to Eq.
4.2-4.6 for the one-operator variant except that P2(i I n) is strictly greater than zero for all
n e S'. Thus, the two-operator analog of Eq. 4.5 is not required. Also