CMA-ES Dans la continuité de la dernière et de la dernière fois, je vais continuer l'introduction de la bibliothèque de calcul d'évolution Python Deap. Cette fois, nous examinerons CMA-ES. Tout d'abord, je voudrais expliquer à quoi ressemble le CMA-ES. CMA-ES signifie * Covariance Matrix Adaptation Evolution Strategy * et est un calcul d'optimisation pour les fonctions non linéaires / discontinues. En bref, la population de recherche est générée en utilisant la distribution normale multivariée, et la matrice de covariance moyenne et diversifiée de la distribution normale multivariée est mise à jour à partir de l'évaluation de la population. Maintenant, en supposant que l'espace de recherche est de dimension $ n $ et que la génération de population $ \ lambda (> 1) $ est effectuée à l'étape $ k $, les solutions candidates $ x_i \ in {\ de la distribution normale multivariée suivante bf R} ^ n (i = 1, ..., \ lambda) $ est généré.

x_i ~ \sim N(m_k, \sigma_k^2 C_k)

Dans CMA-ES, ce $ m_k, \ sigma_k ^ 2, C_k $ sera mis à jour à chaque étape.

Fonction rastrigine

Cette fois, nous optimiserons une fonction appelée fonction Rastrigin. La fonction Rastrigin est souvent utilisée comme fonction de référence pour les algorithmes d'optimisation et s'exprime par la formule suivante.

f(x) = An + \sum_{i=1}^n [ x_i^2 - A\cos(2\pi x_i ) ]

Ici, $ A = 10, x_i \ in [-5.12, 5.12] $, et le point minimum est $ x = 0 $ et $ f (x) = 0 $. Quand j'essaye de dessiner un peu avec matplotlib ...

from mpl_toolkits.mplot3d import Axes3D
from matplotlib import cm
import matplotlib.pyplot as plt

from deap import benchmarks
import numpy as np

fig = plt.figure()
ax = fig.gca(projection='3d')
X = np.arange(-5.12, 5.12, 0.1)
Y = np.arange(-5.12, 5.12, 0.1)
X, Y = np.meshgrid(X, Y)
Z = [[benchmarks.rastrigin((x, y))[0] for x, y in zip(xx, yy)] for xx, yy in zip(X, Y)]
surf = ax.plot_surface(X, Y, Z, rstride=1, cstride=1, cmap=cm.coolwarm, linewidth=0, antialiased=False)
plt.show()

Une fonction qui ressemble à ceci sortira.

Exemple de code

Afin de confirmer quel type de matrice co-distribuée distribuée est générée au milieu de CMA-ES, j'essaie de dessiner la matrice co-distribuée distribuée à chaque étape.

# -*- coding: utf-8 -*-
import numpy

from deap import algorithms
from deap import base
from deap import benchmarks
from deap import cma
from deap import creator
from deap import tools

import matplotlib.pyplot as plt

N = 2  #Dimension du problème
NGEN = 50  #Nombre total d'étapes

creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("evaluate", benchmarks.rastrigin)

def main():
    numpy.random.seed(64)

    # The CMA-ES algorithm 
    strategy = cma.Strategy(centroid=[5.0]*N, sigma=3.0, lambda_=20*N)
    toolbox.register("generate", strategy.generate, creator.Individual)
    toolbox.register("update", strategy.update)

    halloffame = tools.HallOfFame(1)

    halloffame_array = []
    C_array = []
    centroid_array = []
    for gen in range(NGEN):
        #Générer une nouvelle génération de population
        population = toolbox.generate()
        #Évaluation de la population
        fitnesses = toolbox.map(toolbox.evaluate, population)
        for ind, fit in zip(population, fitnesses):
            ind.fitness.values = fit
        
        #Mise à jour des paramètres pour le calcul de nouvelle génération à partir de l'évaluation de la population
        toolbox.update(population)
        
        # hall-of-mise à jour de la renommée
        halloffame.update(population)

        halloffame_array.append(halloffame[0])
        C_array.append(strategy.C)
        centroid_array.append(strategy.centroid)

    #Dessiner le résultat du calcul
    import matplotlib.pyplot as plt
    import matplotlib.cm as cm
    from matplotlib.patches import Ellipse
    plt.ion()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    X = numpy.arange(-5.12, 5.12, 0.1)
    Y = numpy.arange(-5.12, 5.12, 0.1)
    X, Y = numpy.meshgrid(X, Y)
    Z = [[benchmarks.rastrigin((x, y))[0] for x, y in zip(xx, yy)]
         for xx, yy in zip(X, Y)]
    ax.imshow(Z, cmap=cm.jet, extent=[-5.12, 5.12, -5.12, 5.12])
    for x, sigma, xmean in zip(halloffame_array, C_array, centroid_array):
        #Dessinez la variance de la distribution multivariée sous forme d'ellipse
        Darray, Bmat = numpy.linalg.eigh(sigma)
        ax.add_artist(Ellipse((xmean[0], xmean[1]),
                              numpy.sqrt(Darray[0]),
                              numpy.sqrt(Darray[1]),
                              numpy.arctan2(Bmat[1, 0], Bmat[0, 0]) * 180 / numpy.pi,
                              color="g",
                              alpha=0.7))
        ax.plot([x[0]], [x[1]], c='r', marker='o')
        ax.axis([-5.12, 5.12, -5.12, 5.12])
        plt.draw()
    plt.show(block=True)

if __name__ == "__main__":
    main()

Vous pouvez voir que l'ellipse verte représente la matrice de variance-co-dispersion de chaque étape, et à mesure qu'elle s'approche de la solution optimale $ [0,0] $, l'ellipse devient plus petite et la plage de recherche se rétrécit. Lorsque vous exécutez réellement le script ci-dessus, les ellipses dans les nouvelles étapes seront ajoutées et dessinées dans une animation, donc je pense que les changements dans les ellipses seront plus faciles à comprendre. Les points rouges représentent la meilleure solution pour chaque étape, qui se termine également par $ [0,0] $.

référence

Exemple CMA-ES: http://deap.gel.ulaval.ca/doc/default/examples/cmaes_plotting.html

Bibliothèque de calcul d'évolution Python Deap (3)

Fonction rastrigine

Exemple de code

référence