Information Technology Reference
In-Depth Information
2.
σ>s
, i.e. the circle cuts its contour line beyond the constraint boundary.
The angle
α
is
π
−
(
ξ
+
ϑ
). In the triangle of
β
and
ξ
it holds
ξ
=
π/
2
−
β
,
we get
α
=
β
+
π/
2
−
arccos(
d/σ
). Hence, the success probability is
(
p
s
)
σ>d,σ>s
=
α/
(2
π
)=
β/
(2
π
)+(
π/
2
−
arccos(
d/σ
))
/
(2
π
)
(7.12)
Again, for 0
<d/σ<
1, it holds 0
<
arccos(
d/σ
)
<π/
2 and as we postulated
β
=
π/
2, we get
(
p
s
)
σ>d,σ>s
<
1
/
2
.
(7.13)
As (
p
s
)
σ>d,σ<s
≥
(
p
s
)
σ>d,σ>s
for a small distance
d
or a big step size
σ
,we
can assert the asymptotic behavior
(
p
s
)
σ>d
→
β/
(2
π
)for
d/σ
→
0
(7.14)
Furthermore, (
p
s
)
σ>d
decreases for smaller
β
.
Example 7.2.
We give an example to illustrate the success rate situation. We
assume that
β
=
π/
4and
d/σ
=1
/
2. As 2
d>
(
d/
sin
β
), we have to consider the
case
σ>s
. The success rate becomes (
p
s
)
σ>d,σ>s
=5
/
24. As the probability for
a small step size (
p
s
)
σ<d
=1
/
2 is much bigger, it will in particular be preferred
by a self-adaptive mechanism.
We continue to prove the step size reduction for our (1+1)-EA. As the optimum
lies at the constraint boundary, the EA will
encounter
the latter,
σ>d
.Theorem
7.3 describes the behavior of the (1+1)-EA at the constraint boundary by stating
the expected mutation change
E
(
γ
) in each iteration, lemma 7.1 provides a
quantitative analysis stating the success rate (
p
s
)
σ>d
, in the following denoted
as
p
.
Theorem 7.3 (Premature Step Size Reduction).
Let f be a linear fitness
function and g a linear constraint boundary with angle β<π/
2
between f and
g. In the vicinity of the constraint boundary σ>d, the above modeled (1+1)-
EA with γ>
1 + (tan
β
)
reduces its step size σ in each iteration by E
(
γ
)=
γ
1
1
p
p
)
−
<
1
with p<
1
/
2
.
(1
−
Proof.
We distinguish two states
Γ
1
and
Γ
2
for an individual
X
t
in the neigh-
borhood of the constraint boundary,
σ>d
.
1.
Γ
1
denotes the situation that a successful mutation was produced, i.e.
f
(
X
t
+
σ
t
Z
t
)
<f
(
X
t
)
g
(
X
t
+
σ
t
Z
t
)=0.
2.
Γ
2
denotes the failure
f
(
X
t
+
σ
t
Z
t
)
>f
(
X
t
)
∧
g
(
X
t
+
σ
t
Z
t
)
>
0. Lemma 7.1
shows that the probability for a success is small, at most smaller than 1
/
2
and converges to
β/
(2
π
)for
d/σ
∨
→
0.
Search WWH ::
Custom Search