Information Technology Reference
In-Depth Information
Intuitively, as for nearly every optimization problem bigger mutations seem to
be advantageous at the beginning of the search in order to explore the search
domain. Later smaller steps make sense in order to optimize locally and to avoid
the destruction of close-to-optimum solutions. Hence, it seems useful to adapt
the number
k
of successive applications of inversion mutation. For the strategy
variable mutation of
k
we use meta-EP mutation, see section 4.1.8,
k
:=
k
+
γ
·N
(0
,
1)
.
(5.3)
Figure 5.2 shows the pseudocode of SA-INV.
1
utate
k
2
For
i=0
to
k
3
Randomly choose points
p
1
and
p
2
4
Inverse part between
p
1
and
p
2
of tour
π
5
Next
Fig. 5.2.
Pseudocode of the SA-INV operator. The strategy variable
k
determines the
number of edge swaps. An edge swap is the inversion of the part between the randomly
chosen pairs, i.e. edges (
p
1
−
1
,p
1
)and(
p
2
,p
2
+1).
5.3
Convergence Properties
In the following we prove that an EA using the INV-Operator finds the global
optimum in finite time. As stated by Rudolph [125] and Eiben [36] it is not
necessary to build an quantitatively exact Markov model for each EA vari-
ant. Instead, we can use a qualitative model. Let
X
be the search space and
n
denote the population of parents. Parent selection is abbrevi-
ated with
mat
, recombination with
reco
, mutation with
mut
and selection with
sel
. Our convergence proof is based on theorem 5.4. So, we have to ensure the
following assumptions (A
1
)to(A
4
) [125]:
(
x
1
,...,x
n
)
∈X
•
(A
1
)
∀
x
∈
(
x
1
,...,x
n
):
P
{
x
∈
reco
(
mat
(
x
1
,...,x
n
))
}≥
δ
r
>
0.
•
(A
2
) For every pair
x, y
there exists a finite path
x
1
,x
2
,...,x
l
of pairwise
distinct points with
x
1
=
x
and
x
l
=
y
such that
P
∈X
{
x
i
+1
=
mut
(
x
i
)
}≥
δ
m
>
0 for all
i
=1
,...,l
−
1.
•
(A
2
') For every pair
x, y
∈X
holds
P
{
y
=
mut
(
x
)
}≥
δ
m
>
0.
•
∀
x
∈
(
x
1
,...,x
l
):
P
{
x
∈
sel
(
x
1
,...,x
l
)
}≥
δ
s
>
0.
(A
3
)
(A
4
)Let
v
l
(
x
1
,...,x
l
)=max
•
{
f
(
x
i
):
i
=1
,...,l
}
denote the best fitness
value within a population of
l
individuals (
l
≥
n
). The selection method
fulfills the condition
v
n
(
sel
(
x
1
,...,x
l
)) =
v
l
(
x
1
,...,x
l
)
P
{
}
=1
.
(5.4)
Search WWH ::
Custom Search