The Complex Parameter Landscape of the Compact Genetic Algorithm

Abstract

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

Topics & Concepts