Update Strength in EDAs and ACO: How to Avoid Genetic Drift
share
We provide a rigorous runtime analysis concerning the update strength, a vital parameter in probabilistic model-building GAs such as the step size 1/K in the compact Genetic Algorithm (cGA) and the evaporation factor ρ in ACO. While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to genetic drift and poor performance. We demonstrate this trade-off for the cGA and a simple MMAS ACO algorithm on the OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(K√(n) + n n) and Ω(√(n)/ρ + n n), respectively, showing that the update strength should be limited to 1/K, ρ = O(1/(√(n) n)). In fact, choosing 1/K, ρ∼ 1/(√(n) n) both algorithms efficiently optimize OneMax in expected time O(n n). Our analyses provide new insights into the stochastic behavior of probabilistic model-building GAs and propose new guidelines for setting the update strength in global optimization.
READ FULL TEXT