Information Technology Reference
In-Depth Information
The DMO is reasonable as long as the assumption of locality is true: the esti-
mated direction of the global optimum can be derived from the local information,
i.e. the descent direction of two successive populations' centers. In the experi-
mental analysis of section 4.5, we will examine the convergence properties of the
DMO on practical problems.
4.4
Success Rate on Monotone Functions
One basic intuition behind biased mutation and in particular behind the DMO
is that a good search direction in the recent past may be beneficial in the next
generation. The precondition of a successful descent direction mutation is a
monotone part of the function. It is probable that the BMO learns the descent
direction, as the self-adaptive process will favor the latter. In the following we
analyze the success rates and the behavior of a simplified DMO model on mono-
tone functions. Let f : IR
IR be the monotone decreasing objective function
to be minimized. A (1+1)-EA with the DMO can be modeled by the Markovian
process ( X t t ) t≥ 0 generated by
X t + σ t Z t + σ t b t if f ( X t + σ t Z t + σ t b t ) <f ( X t )
X t
X t +1 =
(4.43)
otherwise
with X 0 = x 0
IR , σ 0 > 0, and
γ 1 σ t if f ( X t + σ t Z t + σ t b t ) <f ( X t )
γ 2 σ t
σ t +1 =
(4.44)
otherwise
and γ 1 > 1, γ 2
]0 , 1[,aswellas
X t
X t− 1
b t =
(4.45)
|
X t
X t− 1 |
Each Z t ,t
is independent and identically distributed with a marginal density
function. We take the standard Gaussian distribution into account. For monotone
decreasing functions on IR it holds f ( x + k ) ≤ f ( x ) for a positive k .Consequently,
for σ t b t > 0, i.e. self-adaptation has found the bias b t into the descent direction
or the DMO approximates the latter, it holds
f ( X t + σ t Z t + σ t b t )
f ( X t + σ t Z t )
(4.46)
We can compare the success rate of biased mutation to the success rate of
isotropic mutation.
Theorem 4.1. Let ( p s ) ISO and ( p s ) BMO be the success rates of isotropic Gaus-
sian mutation and the BMO and let b t be a bias into the descent direction. On
a monotone function f, it holds ( p s ) ISO < ( p s ) BMO .
 
Search WWH ::




Custom Search