Stratégie d'évolution naturelle - Natural evolution strategy

Partie d' une série sur le
Algorithme évolutif
Développement artificiel Algorithme évolutif cellulaire Algorithme culturel Évolution différentielle Fitness efficace Stratégie d'évolution Adaptation gaussienne Optimisation multimodale évolutive Évolution grammaticale Optimisation de l'essaim de particules Algorithme mémétique Stratégie d'évolution naturelle Algorithme génétique basé sur le promoteur Algorithme d'optimisation en spirale
Algorithme génétique
Chromosome Algorithme de sélection clonale Crossover Mutation Mémoire génétique Systèmes génétiques flous Sélection Algorithme de vol
Programmation génétique
Programmation génétique cartésienne Programmation génétique linéaire Programmation multi-expressions Schéma Eurisko Référence de parité
v t e

Les stratégies d'évolution naturelle ( NES ) sont une famille d' algorithmes d' optimisation numérique pour les problèmes de boîte noire . Semblables dans l'esprit des stratégies d'évolution , ils mettent à jour de manière itérative les paramètres (continus) d'une distribution de recherche en suivant le gradient naturel vers une plus grande aptitude attendue.

Méthode

La procédure générale est la suivante: la distribution de recherche paramétrée est utilisée pour produire un lot de points de recherche, et la fonction d'aptitude est évaluée à chacun de ces points. Les paramètres de la distribution (qui incluent les paramètres de stratégie ) permettent à l'algorithme de capturer de manière adaptative la structure (locale) de la fonction de fitness. Par exemple, dans le cas d'une distribution gaussienne , celle-ci comprend la moyenne et la matrice de covariance . À partir des échantillons, NES estime un gradient de recherche sur les paramètres vers une plus grande aptitude attendue. NES effectue ensuite une étape d'ascension du gradient le long du gradient naturel , une méthode du second ordre qui, contrairement au gradient simple, renormalise la mise à jour par rapport à l'incertitude. Cette étape est cruciale, car elle évite les oscillations, la convergence prématurée et les effets indésirables provenant d'une paramétrisation donnée. L'ensemble du processus se répète jusqu'à ce qu'un critère d'arrêt soit satisfait.

Tous les membres de la famille NES fonctionnent selon les mêmes principes. Ils diffèrent par le type de distribution de probabilité et la méthode d' approximation du gradient utilisée. Différents espaces de recherche nécessitent des distributions de recherche différentes; par exemple, en faible dimensionnalité, il peut être très avantageux de modéliser la matrice de covariance complète. Dans les dimensions élevées, en revanche, une alternative plus évolutive consiste à limiter la covariance à la diagonale uniquement. De plus, les espaces de recherche hautement multimodaux peuvent bénéficier de distributions plus lourdes (comme Cauchy , par opposition à la Gaussienne). Une dernière distinction apparaît entre les distributions où nous pouvons calculer analytiquement le gradient naturel et les distributions plus générales où nous devons l'estimer à partir d'échantillons.

Rechercher des dégradés

Laissez désigner les paramètres de la distribution de la recherche et la fonction de fitness évaluée à . NES poursuit alors l'objectif de maximiser l' adéquation attendue sous la distribution de recherche${\ displaystyle \ theta}$${\ displaystyle \ pi (x \, | \, \ theta)}$${\ displaystyle f (x)}$${\ displaystyle x}$

${\ displaystyle J (\ theta) = \ operatorname {E} _ {\ theta} [f (x)] = \ int f (x) \; \ pi (x \, | \, \ theta) \; dx}$

par ascension de gradient . Le dégradé peut être réécrit comme

${\ displaystyle \ nabla _ {\ theta} J (\ theta) = \ nabla _ {\ theta} \ int f (x) \; \ pi (x \, | \, \ theta) \; dx}$

${\ displaystyle = \ int f (x) \; \ nabla _ {\ theta} \ pi (x \, | \, \ theta) \; dx}$

${\ displaystyle = \ int f (x) \; \ nabla _ {\ theta} \ pi (x \, | \, \ theta) \; {\ frac {\ pi (x \, | \, \ theta)} {\ pi (x \, | \, \ theta)}} \; dx}$

${\ displaystyle = \ int {\ Big [} f (x) \; \ nabla _ {\ theta} \ log \ pi (x \, | \, \ theta) {\ Big]} \; \ pi (x \ , | \, \ theta) \; dx}$

${\ displaystyle = \ operatorname {E} _ {\ theta} \ left [f (x) \; \ nabla _ {\ theta} \ log \ pi (x \, | \, \ theta) \ right]}$

soit la valeur attendue de fois les dérivés de log- à . En pratique, il est possible d'utiliser l' approximation de Monte Carlo basée sur un nombre fini d' échantillons ${\ displaystyle f (x)}$${\ displaystyle x}$${\ displaystyle \ lambda}$

${\ displaystyle \ nabla _ {\ theta} J (\ theta) \ approx {\ frac {1} {\ lambda}} \ sum _ {k = 1} ^ {\ lambda} f (x_ {k}) \; \ nabla _ {\ theta} \ log \ pi (x_ {k} \, | \, \ theta)}$.

Enfin, les paramètres de la distribution de recherche peuvent être mis à jour de manière itérative

${\ displaystyle \ theta \ leftarrow \ theta + \ eta \ nabla _ {\ theta} J (\ theta)}$

Ascension de gradient naturel

Au lieu d'utiliser le gradient stochastique simple pour les mises à jour, NES suit le gradient naturel , dont il a été démontré qu'il possède de nombreux avantages par rapport au gradient simple ( vanille ), par exemple:

• la direction du gradient est indépendante du paramétrage de la distribution de recherche
• les amplitudes des mises à jour sont automatiquement ajustées en fonction de l'incertitude, accélérant à leur tour la convergence sur les plateaux et les crêtes.

La mise à jour NES est donc

${\ displaystyle \ theta \ leftarrow \ theta + \ eta \ mathbf {F} ^ {- 1} \ nabla _ {\ theta} J (\ theta)}$,

où est la matrice d'information de Fisher . La matrice de Fisher peut parfois être calculée exactement, sinon elle est estimée à partir d'échantillons, en réutilisant les log-dérivés . ${\ displaystyle \ mathbf {F}}$${\ displaystyle \ nabla _ {\ theta} \ log \ pi (x | \ theta)}$

Mise en forme du fitness

NES utilise la mise en forme de la forme physique basée sur le rang afin de rendre l'algorithme plus robuste et invariant sous des transformations monotones croissantes de la fonction de fitness. À cette fin, la forme physique de la population est transformée en un ensemble de valeurs d' utilité . Soit le i ^ème meilleur individu. En remplaçant la forme physique par l'utilité, l'estimation du gradient devient ${\ displaystyle u_ {1} \ geq \ dots \ geq u _ {\ lambda}}$${\ displaystyle x_ {i}}$

${\ displaystyle \ nabla _ {\ theta} J (\ theta) = \ sum _ {k = 1} ^ {\ lambda} u_ {k} \; \ nabla _ {\ theta} \ log \ pi (x_ {k } \, | \, \ theta)}$.

Le choix de la fonction d'utilité est un paramètre libre de l'algorithme.

Pseudocode

input: ${\displaystyle f,\;\;\theta _{init}}$

1  repeat
   
2     for  ${\displaystyle k=1\ldots \lambda }$ do                                              // λ is the population size
       
3         draw sample ${\displaystyle x_{k}\sim \pi (\cdot |\theta )}$
       
4         evaluate fitness ${\displaystyle f(x_{k})}$
       
5         calculate log-derivatives ${\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )}$
       
6     end
   
7     assign the utilities ${\displaystyle u_{k}}$                                          // based on rank
   
8     estimate the gradient ${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )}$
   
9     estimate ${\displaystyle \mathbf {F} \leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k}|\theta )\nabla _{\theta }\log \pi (x_{k}|\theta )^{\top }}$           // or compute it exactly 
   
10    update parameters ${\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}$                        // η is the learning rate

11 until stopping criterion is met

Voir également

• Calcul évolutif
• Stratégie d'évolution de l'adaptation de la matrice de covariance (CMA-ES)

Bibliographie

• D. Wierstra, T. Schaul, J. Peters et J. Schmidhuber (2008). Stratégies d'évolution naturelle . Congrès IEEE sur le calcul évolutif (CEC).
• Y. Sun, D. Wierstra, T. Schaul et J. Schmidhuber (2009). Recherche stochastique à l'aide du dégradé naturel . Conférence internationale sur l'apprentissage automatique (ICML).
• T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra et J. Schmidhuber (2010). Stratégies d'évolution naturelle exponentielle . Conférence sur le calcul génétique et évolutif (GECCO).
• T. Schaul, T. Glasmachers et J. Schmidhuber (2011). Dimensions élevées et queues lourdes pour les stratégies d'évolution naturelle . Conférence sur le calcul génétique et évolutif (GECCO).
• T. Schaul (2012). Les stratégies d'évolution naturelle convergent vers les fonctions de sphère . Conférence sur le calcul génétique et évolutif (GECCO).

Liens externes

• Collection d'implémentations NES dans différentes langues