CMA-ES Ich werde vom letzten und vom letzten Mal an die Einführung von [Python Evolution Calculation Library Deap] fortsetzen (http://qiita.com/neka-nat@github/items/0cb8955bd85027d58c8e). Dieses Mal schauen wir uns [CMA-ES] an (http://en.wikipedia.org/wiki/CMA-ES). Zunächst möchte ich erklären, wie CMA-ES ist. CMA-ES steht für * Covariance Matrix Adaptation Evolution Strategy * und ist eine Optimierungsberechnung für nichtlineare / diskontinuierliche Funktionen. Kurz gesagt wird die Suchpopulation unter Verwendung der multivariaten Normalverteilung erzeugt, und die mittlere und diversifizierte Kovarianzmatrix der multivariaten Normalverteilung wird aus der Bewertung der Population aktualisiert. Unter der Annahme, dass der Suchraum die Dimension $ n $ hat und die Bevölkerungsgenerierung $ \ lambda (> 1) $ im Schritt $ k $ durchgeführt wird, werden die Lösungskandidaten $ x_i \ in {\ aus der folgenden multivariaten Normalverteilung ausgewählt bf R} ^ n (i = 1, ..., \ lambda) $ wird erzeugt.

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

In CMA-ES wird dieses $ m_k, \ sigma_k ^ 2, C_k $ Schritt für Schritt aktualisiert.

Rastrigin-Funktion

Dieses Mal werden wir eine Funktion optimieren, die als Rastrigin-Funktion bezeichnet wird. Die Rastrigin-Funktion wird häufig als Benchmark-Funktion für Optimierungsalgorithmen verwendet und wird durch die folgende Formel ausgedrückt.

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

Hier ist $ A = 10, x_i \ in [-5.12, 5.12] $ und der Mindestpunkt ist $ x = 0 $ und $ f (x) = 0 $. Wenn ich versuche, ein wenig mit matplotlib zu zeichnen ...

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()

Eine Funktion, die so aussieht, wird herauskommen.

Beispielcode

Um zu bestätigen, welche Art von verteilter co-verteilter Matrix in der Mitte von CMA-ES erzeugt wird, versuche ich, die verteilte co-verteilte Matrix bei jedem Schritt zu zeichnen.

# -*- 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  #Problemdimension
NGEN = 50  #Gesamtzahl der Schritte

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):
        #Generieren Sie eine neue Generation von Bevölkerung
        population = toolbox.generate()
        #Bevölkerungsbewertung
        fitnesses = toolbox.map(toolbox.evaluate, population)
        for ind, fit in zip(population, fitnesses):
            ind.fitness.values = fit
        
        #Parameteraktualisierung für die Berechnung der nächsten Generation aus der Bevölkerungsbewertung
        toolbox.update(population)
        
        # hall-of-Update des Ruhmes
        halloffame.update(population)

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

    #Berechnungsergebnis zeichnen
    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):
        #Zeichnen Sie die Varianz der multivariaten Verteilung als 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()

Sie können sehen, dass die grüne Ellipse die Varianz-co-verteilte Matrix jedes Schritts darstellt. Wenn sie sich der optimalen Lösung $ [0,0] $ nähert, wird die Ellipse kleiner und der Suchbereich enger. Wenn Sie das obige Skript tatsächlich ausführen, werden die Ellipsen in den neuen Schritten hinzugefügt und in einer Animation gezeichnet, sodass ich denke, dass die Änderungen in den Ellipsen leichter zu verstehen sind. Die roten Punkte stellen die beste Lösung für jeden Schritt dar, der auch in $ [0,0] $ endet.

Referenz

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

Python-Evolutionsberechnungsbibliothek Deap (3)

Rastrigin-Funktion

Beispielcode

Referenz