The Complex Parameter Landscape of the Compact Genetic Algorithm

摘要: The compact Genetic Algorithm (cGA) evolves a probability distribution favoring optimal solutions in the underlying search space by repeatedly sampling from and updating it according to promising samples. We study intricate dynamics of cGA on test function OneMax, how its performance depends hypothetical population size K, which determines quickly decisions about bit values are fixated probabilistic model. It is known that Univariate Marginal Distribution (UMDA), related algorithm whose called  $$\lambda$$ , run expected time $$O(n \log n)$$ when just large enough ( $$K = \varTheta (\sqrt{n}\log $$\lambda respectively) avoid wrong being fixated. UMDA also shows same very different regime =\varTheta (\log equivalent cGA) with much smaller size, but for reasons: many initially, then reverted efficiently. If even $$o(\log ), exponential. show sizes between two regimes worse as they yield larger runtimes: we prove lower bound $$\varOmega (K^{1/3}n + n OneMax O(\sqrt{n}/\log ^2 . For \varOmega ^3 runtime increases growing K before dropping again $$O(K\sqrt{n} (\sqrt{n} This suggests bimodal in K regions between.