Information Technology Reference
In-Depth Information
Theorem 5.4
(Rudolph [125]). If the assumptions (A
1
), (A
2
)and(A
3
)are
valid, then the EA visits the global optimum after a finite number of iterations
with probability one, regardless of the initialization. If assumption (A
4
)isvalid
additionally and the selection method chooses from parents as well as offspring,
then the EA converges completely and in mean to the global optimum regardless
of the initialization.
For the definitions of the terms
converges completely
and
converges in mean
,see
section 2.1.2. We prove the global convergence of the following EA using INV as
mutation operator:
1. recombination: no recombination is used, i.e. individuals for mutation are
selected with uniform distribution,
2. mutation: INV/SA-INV see definitions 5.2 and 5.3,
3. selection: comma-selection with modification, i.e. comma-selection selects the
μ
1 best parents from the
λ
descendants and one parent randomly with
uniform distribution and probability
p
∗
≥
−
1
/λ
.
Theorem 5.5
The EA with inversion mutation (INV) as defined above con-
verges with probability 1 to the global optimum after a finite number of iterations.
Proof.
We make use of theorem 5.4 and have to ensure that assumptions (A
1
)
to (A
3
) are valid. Assumption (A
1
) is valid, because
mat
(
x
1
,...,x
n
)=
x
i
,0
≤
i
n
with
P
(
X
=
i
)=1
/n >
0. Since no recombination is used
reco
(
x
i
)=
x
i
with probability 1. So,
≤
∀
x
∈
(
x
1
,...,x
n
):
P
{
x
∈
reco
(
mat
(
x
1
,...,x
n
))
}
=1
/n
=
δ
r
>
0
(5.5)
To prove assumption (A
2
) we have to show that for every tour
π
x
and tour
π
y
:
∃
a finite sequence INV
1
,...,
INV
r
of INV-operations such that INV
r
(
...
INV
1
(
π
x
)) =
π
y
. We use the following lemma 5.6.
Lemma 5.6
Let π be a tour with cities c
q
with rank x and c
s
with rank y, x>y.
∀
a finite sequence INV
1
,...,INV
r
of INV-operations with π
c
q
,c
s
∃
=
INV
r
(
...INV
1
(
π
))
such that π
(
q
)=
y,withprobabilityδ
m
(
INV
)
>
0
.
Proof.
It holds
x
=
π
(
q
)and
y
=
π
(
s
). For
x>y
, a sequence of
r
=
x
y
successive INV(
π, i, j
)-operations
2
on neighbored cities moves city
c
q
from rank
x
to rank
y
, i.e.
−
INV(
π, x, x −
1)
,
INV(
π
2
,x−
1
,x−
2)
,...,
INV(
π
r
,y
+1
,y
)
(5.6)
Since parameters
i
and
j
of the INV-operator are chosen randomly with uniform
distribution, the probability to choose them is
P
{
i
=
x, j
=
x
−
1
}
=1
/
(
N
(
N
−
1)). Hence, the probability of the successive INV-operations is
2
INV(
π,i, j
) is inversion mutation of tour
π
with
inversion points
p
1
=
i
and
p
2
=
j
.
Search WWH ::
Custom Search