Name
Title | ||
|---|---|---|
On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization |
Abstract | ||
|---|---|---|
Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor \(\rho \) in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of \({\varOmega }(K\sqrt{n} + n \log n)\) and \({\varOmega }(\sqrt{n}/\rho + n \log n)\), respectively, suggesting that the update strength should be limited to \(1/K, \rho = O(1/(\sqrt{n} \log n))\). In fact, choosing \(1/K, \rho \sim 1/(\sqrt{n}\log n)\) both algorithms efficiently optimize OneMax in expected time \({\varTheta }(n \log n)\). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00453-018-0480-z | Algorithmica |
Keywords | Field | DocType |
Ant colony optimization,Estimation-of-distribution algorithms,Genetic Algorithms,Probabilistic model-building Genetic Algorithms,Runtime analysis,Theory of randomized search heuristics | Ant colony optimization algorithms,Binary logarithm,Discrete mathematics,Combinatorics,Stochastic behavior,Global optimization,Estimation of distribution algorithm,Probability distribution,Mathematics,Metaheuristic | Journal |
Volume | Issue | ISSN |
81.0 | 4 | 1432-0541 |
Citations | PageRank | References |
2 | 0.37 | 24 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dirk Sudholt | 1 | 1063 | 64.62 |
| Carsten Witt | 2 | 987 | 59.83 |