Log-linear Convergence of the Scale-invariant $(\mu/\mu_w,\lambda)$-{ES} and Optimal mu for Intermediate Recombination for Large Population Sizes

Mohamed Jebalia (1) , Anne Auger (1)

1 TAO - Machine Learning and Optimisation

Evolution Strategies (ESs) are population-based methods well suited for parallelization. In this report, we study the convergence of the (mu/mu_w,lambda)-ES, an ES with weighted recombination, and derive its optimal convergence rate and optimal mu especially for large population sizes. First, we theoretically prove the log-linear convergence of the algorithm using a scale-invariant adaptation rule for the step-size and minimizing spherical objective functions and identify its convergence rate as the expectation of an underlying random variable. Then, using Monte-Carlo computations of the convergence rate in the case of equal weights, we derive optimal values for mu that we compare with previously proposed rules. Our numerical computations show also a dependency of the optimal convergence rate in ln(lambda) in agreement with previous theoretical results.

Les Stratégies d'Évolution (SE) sont des méthodes à base de populations adaptées à la parallélisation. Dans ce rapport, on étudie le SE avec recombinaison, (mu/mu_w,lambda)-ES, particulièrement dans le cas de grandes tailles de population. Nous prouvous théroriquement le comportement log-linéaire de l'algorithme lors de la minimization d'une fonction sphérique et identifions la vitesse de convergence relative à cet algorithme comme étant l'espérance d'une certaine variable aléatoire. En utilisant des échantillonnages de Monte-Carlo pour calculer les vitesses de convergence dans le cas de poids égaux, nous déterminons les valeurs optimales de mu et proposons une nouvelle formule pour choisir mu pour de très grandes valeurs de lambda. Cette règle est comparée avec des règles proposées précédemment dans d'autres études. Les calculs numériques montrent aussi une dépendence de la vitesse de convergence en ln(lambda) ce qui rejoint des résultats théroriques précédents.

Domaines: Optimisation et contrôle [math.OC]

Mohamed Jebalia, Anne Auger. Log-linear Convergence of the Scale-invariant $(\mu/\mu_w,\lambda)$-{ES} and Optimal mu for Intermediate Recombination for Large Population Sizes. [Research Report] RR-7275, INRIA. 2010. ⟨inria-00495401⟩