Name
Abstract | ||
|---|---|---|
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 log n) and Ω(√n/ρ + n log n), respectively, showing that the update strength should be limited to 1/K, ρ = O(1/(√n log n)). In fact, choosing 1/K, ρ sim 1/(√n log n) both algorithms efficiently optimize OneMax in expected time O(n log 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1145/2908812.2908867 | GECCO |
Keywords | DocType | Volume |
Ant Colony Optimization, Estimation-of-Distribution Algorithms, Iteration-Best Update, Genetic Drift, Runtime Analysis, Theory | Conference | abs/1607.04063 |
Citations | PageRank | References |
14 | 0.70 | 12 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dirk Sudholt | 1 | 1063 | 64.62 |
| Carsten Witt | 2 | 987 | 59.83 |