Information Technology Reference
In-Depth Information
constraint boundary
infeasible search space
direction
to optimum
3
s
s
2
lines of constant fitness
s
1
feasible search space
Fig. 7.1.
Success rates at the boundary of the feasible search space. Three cases have
to be considered, i.e. 1.
σ<d
,2.
σ>d
,
σ<s
and 3.
σ>d
,
σ>s
. The bold circular
arcs are the regions where successful mutations are produced.
and
σ
t
+1
=
γσ
t
if
f
(
X
t
+
σ
t
Z
t
)
<f
(
X
t
)
∧
g
(
X
t
+
σ
t
Z
t
)=0
(7.5)
γ
−
1
σ
t
otherwise
with step size
σ
t
and mutation parameter
γ>
1. The function
g
measures the
constraint violation. Each random vector
Z
t
,t
0 is independent and identically
distributed in the following way: We assume that mutations
σ
t
Z
t
are produced
on the edge of the circle around
X
t
with radius
σ
t
. When a successful mutation
is produced, the step length
σ
t
is increased and decreased otherwise. We are
interested in the development of the step size
σ
t
and the distance
d
t
to the
constraint boundary. For the sake of better readability we write
σ
instead of
σ
t
and
d
instead of
d
t
where possible. In the following lemma 7.1 we analyze the
success probabilities for the three cases.
≥
Lemma 7.1.
Let
(
p
s
)
be the success probability for individual X
t
of the (1+1)-
EA, with step size σ and distance d to the constraint boundary. Then it holds
(
p
s
)
σ<d
=1
/
2
and
(
p
s
)
σ>d
<
1
/
2
.Ford/σ
→
0
it holds
(
p
s
)
σ>d
→
β/
(2
π
)
.
Search WWH ::
Custom Search