eldorado.tu-dortmund.de/server/api/core/bitstreams/037298d5-be78-4f2e-9f95-0a70a3044f8d/content
better individual of SP2 fail is lower bounded by (1 − 1/n2)n2−1 ≥ 1/e. As at most n1/2 bits flip per mutation, the algorithm is at least
n/4 − 2n1/2 + 2
n1/2 =
n1/2
4 − 2 +
2
n1/2 ≥ n1/2
8
times in the above [...] √
n/2-path
P n/2√
n/2 = (p1, . . . , pℓ)
of dimension n/2, the short path
Qn/2 = (q1, . . . , qℓ′)
of dimension n/2, and a weighted ZeroMax function
z(x) := n3 − n2
√ n/2
∑
i=1
xi − n/2 ∑
i= √
n/2+1
xi [...] within 2en(ln n + 2) steps is at least 1/2. Dividing (1/4)n3/2 steps into (1/(8en(ln n+2)))n3/2 = Ω(n1/3) phases of length 2en(ln n+2)
the decision vector 0n is reached with probability at least 1 − 2−Ω(n1/3) …