Information Technology Reference
In-Depth Information
=
r
1
N
(
N
δ
m
(INV)
=
P
{
i
1
=
x, j
1
=
x
−
1
,...,i
r
=
y
+1
,j
r
=
y
}
−
1)
(5.7)
with the difference of ranks
r
=
x
−
y
. The order of the other cities is not changed
by the neighbored INV-operations.
If a sequence of mutations can move every city
c
q
with rank
x
to every rank
y
as
proven with lemma 5.6, there must exist a sequence of mutations that transfers
tour
π
x
into
π
y
with probability
r
max
·
(
N−
1)
1
N
(
N −
1)
δ
m
(INV)
=
P
{
π
x
→
π
y
}≥
(5.8)
with
r
max
=max
1
cities have to be moved by at most
r
max
. Hence, the probability for a finite
path of pairwise distinct permutations
P
{
r
i
|
x
i
−
y
i
,
1
≤
i
≤
N
}≤
N
−
1andintheworstcase
N
−
δ
m
(INV)
>
0and
assumption (A
2
) is valid. Assumption (A
3
) is valid with
δ
s
=1
/λ >
0. We had
to modify the comma selection in this kind of way to ensure convergence and
are convinced that the modification will not influence our experimental results.
3
Hence, the EA using the INV operator converges with probability 1 to the global
optimum after a finite number of iterations. Assumption (A
4
) would be valid for
a 1-elitist strategy, i.e. the best individual is always kept in the population.
In particular it is valid for plus selection and guarantees that the EA converges
completely and in mean to the global optimum after a finite number of iterations.
But this is not the case for comma selection.
{
π
x
i
+1
=
mut
(
π
x
i
)
}≥
Theorem 5.7
The EA with self-adaptive inversion mutation (SA-INV) con-
verges with probability 1 to the optimum after a finite number of iterations.
Proof.
Assumptions (A
1
)and(A
3
) are valid analog to the proof of theorem 5.5.
Let
P
k
=1
be the probability for
k
= 1. As SA-INV uses Gaussian mutation with
rounding procedures to mutate strategy parameter
k
,itholds
P
{
k
=1
}
>
0
and according to the argumentation of theorem 5.5's proof with
k
=1,
r
max
(
N
−
1)
δ
m
(SA-INV)
=
P
{
k
=1
}
·
δ
m
(INV)
>
0
(5.9)
Hence, it holds
P
{
π
x
i
+1
=
mut
(
π
x
i
)
}≥
δ
m
(SA-INV)
>
0and(A
2
) is valid.
5.4
Experimental Analysis
In this section we analyze the SA-INV operator empirically. The analysis con-
tains a comparison with the standard inversion mutation (INV) with constant
number of edge swaps in each generation. We conduct the experiments on three
3
Assumption (A
3
) is also valid for fitness proportional and tournament selection.
Search WWH ::
Custom Search