Page 47 - Read Online

Page 140 Ortiz et al. Intell Robot 2021;1(2):131-50 I http://dx.doi.org/10.20517/ir.2021.09

r 1 , 1 1 1 r 1 n 1 , n
f 1 f 2 f 3 f n = f *
r Q 1 1 Q 1 2 Q 1 3 Q 1 n
m , 1 1 1 r m n 1 , n
r r 2 , 1 1 1 r r
( m - 1 ) 1 ( m 1 - ) n 1 , n 2 n 1 , n
, 1 1 r 2 , 1 2 1 r r
r 3 , 1 1 1 3 n 1 , n 2 n 2 , n
Q 2 1 Q 2 2 Q 2 3 Q 2 n
r m , 1 2 1 r 3 , 1 2 1 r m n 2 , n r
r r 3 , 1 3 1 r ( m 1 - ) n 2 , n 3 n 2 , n
( m - 1 ) 1 r 3 n 3 , n
, 2 1
Q Q Q Q 3
3 1 3 2 3 3 n
r ( m - 1 ) 1 r ( m 1 ) n
-
, 3 1 r m n 3 , n 3 , n
r m , 1 3 1 r ( m - 1 ) 1 r ( m 1 - ) n
( , m - 1 ) 1 ( , m 1 - ) n
Q ( m - 1 ) 1 Q ( m - 2 ) 1 Q ( m - 3 ) 1 Q ( m - n ) 1
r m ( , 1 m - 1 ) 1 r m n ( , m 1 - ) n
r m , 1 m 1 r m n , m n
Q Q Q Q
m 1 m 2 m 3 m n
Figure 2. Roadmap genetic algorithm model as a finite Markov chain.

Í
Euclidean distance. The total fitness is = ( ). Therefore, the probability of selection of a
=1
chromosome for = 1, 2, . . . , is
( )
= (37)

An optimal solution in is mutated by

© ( ) ª
­
= lim (1 − ) = lim ­1 − ® ® = 1 (38)

→∞ →∞ ­ Í ®
( )

« =1 ¬
In the mutation operation, an optimal solution with = 1 is a global solution if → ∞. To prove the
convergence, we use a Markov chain, as shown in Figure 2. Each chromosome can move from to the state
( +1). The moving probability is , > 0, = 1, 2, . . . , , , = 1, 2, . . . , .
The operators, selection, crossing, and mutation create ( ) with . It preserves the best chromosomes of

( − 1). ( + 1) in the population ( ) can be regarded as the Markov transition:

{ +1 = +1 | = } = ( +1 , ) (39)
Theorem 2 If GA for the roadmap is an elitist process, then the probability of in is exponential.
∗
Proof 2 The iteration 1 is changed with the chromosomes when genetic process is elitist,

Õ − 1
∗
( 1 = ∀0 < ≤ ) = 1,11 = (40)

=2

where is the size of the population. If for all , ∈ , there is 0 < ≤ such that ( , ) ≥ > 0, then

= min { ( , )∀0 < ≤ } ≤ 1 (41)
This implies that, given certain state , the probability of transition in time between and + is at least ,

∗
( ≠ ∀ < ≤ + ) ≥ 1 − (42)

Without loss of generality, the transition in the iteration + 1 is

∗
( +1 ) = ( ≠ ∀0 < ≤ ( + 1) )
∗ ∗
( ≠ ∀0 < ≤ ) ( ≠ ∀ < ≤ ( + 1) )