[PYTHON] Informationen zu Parametern der Partikelgruppenoptimierung (PSO)

Einführung

Dies ist der Artikel am 5. Tag von "Adventskalender für Group Intelligence and Optimization 2019". Es ist mein erstes Mal, dass ich einen Artikel über Qiita veröffentliche, daher ist es vielleicht etwas langweilig, aber ich hoffe, Sie werden ihn lesen. Da es sich in diesem Artikel um PSO-Parameter handelt, sollten Sie, wenn Sie überhaupt nichts über PSO wissen, den gestrigen Artikel von Ganariy "[Ich möchte die Methode zur Optimierung von Partikelgruppen (PSO) speichern]](https://qiita.com/ganariya) / items / ae5a38a3537b06bd3842) ”wird besser verstanden, wenn Sie es zuerst lesen.

Informationen zur Partikelgruppenoptimierung (PSO) und zu Parametern

Wie Herr Ganariy im gestrigen Artikel über die Details von PSO erwähnt hat, handelt es sich um einen der meta-heuristischen Algorithmen, die auf der Gewohnheit beruhen, in einem Schwarm von Vögeln und Fischen zu handeln. Seit der Veröffentlichung des Based Paper im Jahr 1995 wurden verschiedene Modelle vorgeschlagen. PSO sucht nach der optimalen Lösung, indem jedes Partikel mit der aktuellen Position $ x $ und der Geschwindigkeit $ v $ aktualisiert wird. Die Geschwindigkeit und Position jedes in Bewegung befindlichen Partikels wird durch die folgende Formel aktualisiert. $ v_{id}(t+1) = w_{id}(t) + c_p × r_p × (pBest_{id} - x_{id}(t)) + c_g × r_g × (gBest_{id} - x_{id}(t)) $ $ x_{id}(t+1) = x_{id}(t) + v_{id}(t+1) $ Hier wird die beste Position, die von jedem gefunden wird, als persönliche Bestleistung (pBest) bezeichnet, und die beste Position der gesamten Gruppe wird als globale Bestleistung (gBest) bezeichnet. Außerdem ist $ v_ {id} $ die Geschwindigkeit des i-ten Teilchens in der d-Dimension, $ x_ {id} $ ist die Position des i-ten Teilchens in der d-Dimension, $ w $ ist das Gewicht, $ c_p $, $ c_g $ ist Konstanten, die als Beschleunigungskoeffizienten $ r_p $ und $ r_g $ bezeichnet werden, sind Zufallszahlen von 0 bis 1. Unter diesen gibt es das Gewicht $ w $ und den Beschleunigungskoeffizienten $ c_p $$ c_g $ als Parameter, die vom Menschen bestimmt werden können, aber insbesondere $ w $ wurde vielfach als Parameter untersucht, der einen großen Einfluss auf die Konvergenz von Partikeln hat. Ich bin.

Gewichtsforschung w

Als Übersichtsartikel zum Gewicht w wurde 2011 ein Artikel mit dem Titel "Ein neuartiger Algorithmus zur Optimierung des Partikelschwarms mit adaptivem Trägheitsgewicht" veröffentlicht. Ich bin. In diesem Artikel werden Gewichte w in drei Haupttypen eingeteilt.

1. Das Gewicht ist konstant oder zufällig In Artikel, der Konstanten angibt, werden Gewichte mit verschiedenen Konstanten getestet, und $ w> 1,2 $ führt zu einer flachen Suche, während $ w < Es wurde gezeigt, dass 0,8 $ dazu neigen, zur lokalen Lösung zu konvergieren. Außerdem ist es in Paper, das einen zufälligen Wert angibt, schwierig, das optimale Gewicht in einer dynamischen Umgebung zu bestimmen, also einen zufälligen Wert wie die folgende Formel Vorschlagen zu geben. $ w = 0.5 + rand()/2 $

2. Zeitlich veränderliche Gewichte Viele PSO-basierte Methoden verwenden eine Methode, die den Gewichtswert basierend auf der Anzahl der Iterationen bestimmt. Unter diesen ist die in vielen Veröffentlichungen verwendete Methode das linear abnehmende Gewicht [Referenz: 1, [2](https: // ieeexplore) .ieee.org / document / 785511), 3]. Dies wird durch die folgende Formel ausgedrückt, wobei die maximale Anzahl von Iterationen $ iter_ {max} $ und die Anzahl von Iterationen $ iter $, das Anfangsgewicht $ w_ {max} $ und der Endwert $ w_ {min} $ verwendet werden. $ w(iter) = ((iter_{max} - iter)/iter_{max})(w_{max} - w_{min}) + w_{min} $ Für die zeitlich variierenden Gewichte wurden verschiedene Gewichte vorgeschlagen, wie beispielsweise ein Verfahren unter Verwendung eines Chaosmodells und ein nichtlinear abnehmendes Gewicht.

3. Adaptives Gewicht Es überwacht von Zeit zu Zeit die Situation und ermittelt die Gewichte anhand der Rückkopplungsparameter. Es wurde eine Vielzahl von Methoden vorgeschlagen. Wenn Sie interessiert sind, lesen Sie bitte das Übersichtsartikel.

LDWPSO-Implementierung

Von den oben genannten möchte ich das bekannteste und am häufigsten verwendete PSO mit linearem Dekrementgewicht (LDWPSO) implementieren. Die Kugelfunktion wird als Bewertungsfunktion verwendet. Das Programm sieht folgendermaßen aus: Bei der Ausführung wird die 4. Schleife visualisiert und angezeigt.

import numpy as np
import random
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import time

SWARM_SIZE = 100 #Anzahl der Partikel
ITERATION = 30 #Anzahl der PSO-Schleifen
C1 = C2 = 2.0 #Beschleunigungskoeffizient
MIN_X, MIN_Y = -5.0, -5.0 #Mindestreichweite zu Beginn der Suche
MAX_X, MAX_Y = 5.0, 5.0 #Maximale Reichweite zu Beginn der Suche
W_MAX, W_MIN = 0.9, 0.4

#Bewertungsfunktion(z = x^2+y^2)
def evaluation(x, y):
    return x**2 + y**2 # Sphere function

# PSO
def pso(position, velocity, personal_best_scores, personal_best_positions, best_position, search_space_x, search_space_y):
    #Verschieben Sie die Partikel um die Anzahl der Schleifen
    for i in range(ITERATION):
        for s in range(SWARM_SIZE):
            #Ersetzung von Informationen vor Änderung
            x, y = position[s]["x"], position[s]["y"]
            vx, vy = velocity[s]["x"], velocity[s]["y"]
            p = personal_best_positions[s]
            
            #Aktualisierung der Partikelposition
            new_x, new_y = update_position(x, y, vx, vy, search_space_x, search_space_y)
            position[s] = {"x": new_x, "y": new_y}
            #Aktualisierung der Partikelgeschwindigkeit
            new_vx, new_vy = update_velocity(new_x, new_y, vx, vy, p, best_position, i)
            velocity[s] = {"x": new_vx, "y": new_vy}

            #Finden Sie den Bewertungswert
            score = evaluation(new_x, new_y)
            # update personal best
            if score < personal_best_scores[s]:
                personal_best_scores[s] = score
                personal_best_positions[s] = {"x": new_x, "y": new_y}
        # update global best
        best_particle = np.argmin(personal_best_scores)
        best_position = personal_best_positions[best_particle]

        # PSO Visualization
        
        if i == 0 or i == 1 or i == 2 or i == 3:
            print("ITERATION = " + str(i+1))
            visualization(personal_best_positions)
        

#Funktion zur Aktualisierung der Partikelposition
def update_position(x, y, vx, vy, search_space_x, search_space_y):
    new_x = x + vx
    new_y = y + vy
    #Überprüfen Sie, ob es innerhalb des Suchbereichs liegt
    if new_x < search_space_x["min"] or new_y < search_space_y["min"]:
        new_x, new_y = search_space_x["min"], search_space_y["min"]
    elif new_x > search_space_x["max"] or new_y > search_space_y["max"]:
        new_x, new_y = search_space_x["max"], search_space_y["max"]
    return new_x, new_y

#Funktion zur Aktualisierung der Partikelgeschwindigkeit
def update_velocity(x, y, vx, vy, p, g, i):
    #random parameter (0~1)
    r1 = random.random()
    r2 = random.random()

    #Linear abnehmendes Gewicht
    L = (ITERATION - i) / ITERATION
    D = W_MAX - W_MIN
    w = L * D + W_MIN
    print(w)

    #Geschwindigkeitsaktualisierung
    new_vx = w * vx + C1 * (g["x"] - x) * r1 + C2 * (p["x"] - x) * r2
    new_vy = w * vy + C1 * (g["y"] - y) * r1 + C2 * (p["y"] - y) * r2
    return new_vx, new_vy

#Visualisierungsfunktion
def visualization(positions):
    fig = plt.figure()
    ax = Axes3D(fig)
    # Mesh
    #mesh_x = np.arange(-0.5e-3, 0.5e-3, 0.1e-4)
    #mesh_y = np.arange(-0.5e-3, 0.5e-3, 0.1e-4)
    mesh_x = np.arange(-5.0, 5.0, 0.5)
    mesh_y = np.arange(-5.0, 5.0, 0.5)
    mesh_X, mesh_Y = np.meshgrid(mesh_x, mesh_y)
    mesh_Z = evaluation(mesh_X, mesh_Y)
    ax.plot_wireframe(mesh_X, mesh_Y, mesh_Z)
    # Particle
    for j in range(SWARM_SIZE):
        z = evaluation(positions[j]["x"], positions[j]["y"])
        ax.scatter(positions[j]["x"], positions[j]["y"], z)
    ax.set_xlim([-5.0, 5.0])
    ax.set_ylim([-5.0, 5.0])
    ax.set_zlim([-1.0, 30.0])
    ax.set_xlabel("x")
    ax.set_ylabel("y")
    ax.set_zlabel("f(x, y)")
    plt.show()

def run(position, velocity, personal_best_scores, personal_best_positions, best_position, search_space_x, search_space_y):
    pso(position, velocity, personal_best_scores, personal_best_positions, best_position, search_space_x, search_space_y)
    return best_position, personal_best_scores

def main():
    #Startzeitmessung
    start = time.time()

    #Anfangsposition jedes Partikels,Geschwindigkeit, personal best,globale Best- und Suchraumeinstellungen
    position = []
    velocity = []
    personal_best_scores = []
    #Ausgangsposition,Anfangsgeschwindigkeit
    for s in range(SWARM_SIZE):
        position.append({"x": random.uniform(MIN_X, MAX_X), "y": random.uniform(MIN_Y, MAX_Y)})
        velocity.append({"x": random.uniform(0, 1), "y": random.uniform(0, 1)})
    # personal best
    personal_best_positions = list(position)
    for p in position:
        personal_best_scores.append(evaluation(p["x"], p["y"]))
    # global best
    best_particle = np.argmin(personal_best_scores)
    best_position = personal_best_positions[best_particle]
    # search space
    search_space_x, search_space_y = {'min': MIN_X, "max": MAX_X}, {"min": MIN_Y, "max": MAX_Y}

    # run
    best_position, personal_best_scores = run(position, velocity, personal_best_scores, personal_best_positions, best_position, search_space_x, search_space_y)

    #Zeitmessung beendet
    process_time = time.time() - start

    # Optimal solution
    print("Best Position:", best_position)
    print("Score:", min(personal_best_scores))
    print("time:", process_time)

if __name__ == '__main__':
    main()

Eigentlich wäre es schön, wenn ich es mit einem einfachen PSO vergleichen könnte, aber da ich erschöpft bin, bin ich interessiert, weil es ein einfaches PSO wird, indem ich einfach den Wert von $ w_ {min} $ auf 0,9 ändere. Bitte probieren Sie es aus.

Zusammenfassung

Es ist ein ziemlich akademischer Artikel geworden, aber zusammenfassend: ・ Das PSO-Gewicht $ w $ hat einen großen Einfluss auf die Konvergenz zur optimalen Lösung. ・ Es gibt drei Haupttypen von Gewichten -Das am häufigsten verwendete Gewicht ist das linear abnehmende Gewicht, das eines der zeitlich variierenden Gewichte ist. Es wird sein. Auf diese Weise wäre ich dankbar, wenn Sie wissen könnten, dass verschiedene Studien auch mit nur einem Parameter durchgeführt werden.