On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization
Dirk Sudholt, Carsten Witt · Algorithmica · 2018
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.