Dieser Artikel ist der 7. Tagesartikel von "Group Intelligence and Optimization 2019 Adventskalender". Ist es nicht cool mit Chaos oder AIWF? Also habe ich es untersucht und umgesetzt.

Überblick

Chaotic Particle Swarm Optimization (CPSO) ist ein Optimierungsalgorithmus, der Chaos in PSO integriert, einem der meta-heuristischen Algorithmen. Wie bei anderen PSO-Algorithmen gibt es viele Varianten, aber das zugrunde liegende Papier (https://www.sciencedirect.com/science/article/abs/pii/S0960077905000330) wurde 2005 veröffentlicht. .. In diesem Artikel habe ich CPSO in Python implementiert und es mit einer Benchmark-Funktion bewertet, sodass ich es zusammenfassen werde.

Algorithmus und Implementierung

CPSO wird grob durch das folgende Verfahren implementiert.

PSO-Ausführung (unter Verwendung von AIWF * in Gewichten)
Extrahieren Sie die oberen 1/5 Partikel
Führen Sie CLS * an den extrahierten Partikeln durch, um die Position zu aktualisieren
Reduzieren Sie den Suchbereich basierend auf den Standortinformationen des Partikels, das CLS durchgeführt hat
Regenerieren Sie die unteren 4/5 Partikel innerhalb des neuen Suchbereichs nach dem Zufallsprinzip
Bewerten Sie jedes Partikel und kehren Sie zu 1 zurück, wenn die Stoppbedingung erfüllt ist.

AIWF (Adaptive Inertia Weight Factor): Adaptive Inertia Weight Factor. Ein vorgeschlagenes Verfahren für den Trägheitskoeffizienten, der einer der Parameter in PSO ist.
CLS (Chaotic Local Search): Chaotische lokale Suche. Vorgeschlagene Methode für die lokale Suche nach der PSO-Ausführung.

Nur der Hauptteil des Artikels enthält den Code. Der gesamte Code ist auf GitHub verfügbar. https://github.com/TatsukiSerizawa/Meta-heuristic/blob/master/cpso.py

1. Führen Sie PSO aus

Führen Sie zunächst PSO aus. 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 jeder gefunden hat, als persönliche Bestleistung (pBest) und die beste Position der gesamten Gruppe 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 der Trägheitskoeffizient, $ c_p $, $ c_g $ Ist eine Konstante, die als Beschleunigungskoeffizient bezeichnet wird, sind $ r_p $ und $ r_g $ Zufallszahlen von 0 bis 1. AIWF wird für den Trägheitskoeffizienten verwendet, der ein Parameter ist, und eine 2,0-Konstante, die üblicherweise verwendet wird, wird für den Beschleunigungskoeffizienten angegeben. Insbesondere soll der Trägheitskoeffizient einen großen Einfluss auf die Ergebnisse haben, und je größer der Wert ist, desto effektiver ist er für die globale Suche, aber es besteht das Problem, dass er nicht für die lokale Suche geeignet ist. Daher reagiert AIWF auf das Problem, indem es den Wert für jedes Partikel ändert. Der Trägheitskoeffizient w in AIWF kann durch die folgende Formel berechnet werden.

w= \left\\{ \begin{array}{} \frac{(w\_{max} - w\_{min})(f-f\_{min})}{(f\_{avg}-f\_{min})}, \( f \leq f\_{avg}) \\\ w\_{max}, \( f > f\_{avg}) \end{array} \right.

AIWF-Code

def aiwf(scores, W):
    for s in range(SWARM_SIZE):
        if scores[s] <= np.mean(scores):
            W[s] = (np.min(W) + (((np.max(W) - np.min(W)) * (scores[s] - np.min(scores))) / 
                    (np.mean(scores) - np.min(scores))))
        else:
            W[s] = np.max(W)
    return W

2. Extrahieren Sie die oberen 1/5 Partikel

Um zu entscheiden, ob das Partikel CLS durchführen soll, wird das Top 1/5 mit der besten Punktzahl als Ergebnis des PSO extrahiert.

3. Führen Sie eine CLS für die extrahierten Partikel durch und aktualisieren Sie die Position

Die lokale Suche wird von CLS durchgeführt. Wenn $ x $ die Position jedes Partikels ist, wird CLS gemäß dem folgenden Verfahren durchgeführt.

Suchen Sie $ cx \ _ {i} ^ {(k)} $ $ \displaystyle cx_i^{(k)}= \frac{x\_{i}-x\_{max,i}}{x\_{max,i}-x\_{min,i}} $
Suchen Sie $ cx \ _ {i} ^ {(k + 1)} $ basierend auf $ cx \ _ {i} ^ {(k)} $ $ cx\_{i}^{(k+1)}= 4cx\_{i}^{(k)}(1-4cx\_{i}^{(k)}) $
Finden und bewerten Sie die Position $ x \ _ {i} ^ {(k + 1)} $ basierend auf $ cx \ _ {i} ^ {(k + 1)} $ $ x\_{i}^{(k+1)}= x\_{min,i}+cx\_{i}^{(k+1)}(x\_{max,i}-x\_{min,i}) $
Wenn das neue Bewertungsergebnis besser ist als $ X ^ {(0)} = [x \ _ {1} ^ {0}, ..., x \ _ {n} ^ {0}] $ oder maximale Iteration Wenn die Nummer erreicht ist, wird das Ergebnis ausgegeben. Andernfalls kehren Sie zu 2 zurück.

CLS-Code

def cls(top_scores, top_positions):
    cx, cy = [], []

    min_x, min_y = min(top["x"] for top in top_positions), min(top["y"] for top in top_positions)
    max_x, max_y = max(top["x"] for top in top_positions), max(top["y"] for top in top_positions)
    
    for i in range(len(top_scores)):
        cx.append((top_positions[i]["x"] - min_x) / (max_x - min_x))
        cy.append((top_positions[i]["y"] - min_y) / (max_y - min_y))

    for i in range(K):
        logistic_x = []
        logistic_y = []
        chaotic_scores = []
        chaotic_positions = []
        for j in range(len(top_scores)):
            logistic_x.append(4 * cx[j] * (1 - cx[j]))
            logistic_y.append(4 * cy[j] * (1 - cy[j]))
            #Position aktualisieren
            chaotic_x, chaotic_y = chaotic_update_position(logistic_x[j], logistic_y[j], min_x, min_y, max_x, max_y)
            chaotic_positions.append({"x": chaotic_x, "y": chaotic_y})
            #Score-Bewertung
            chaotic_scores.append(evaluation(chaotic_x, chaotic_y))
        #Gibt einen Wert zurück, wenn die neue Punktzahl besser als die vorherige ist, andernfalls cx,Aktualisiere cy und wiederhole
        if min(chaotic_scores) < min(top_scores):
            print("Better Chaotic Particle found")
            return chaotic_scores, chaotic_positions
        cx = logistic_x
        cy = logistic_y
    return chaotic_scores, chaotic_positions

#Chaotische Positionsaktualisierung
def chaotic_update_position(x, y, min_x, min_y, max_x, max_y):
    new_x = min_x + x * (max_x - min_x)
    new_y = min_y + y * (max_y - min_y)
    return new_x, new_y

4. Reduzieren Sie den Suchbereich basierend auf den Standortinformationen des Partikels, das CLS durchgeführt hat

Reduzieren Sie den nächsten Suchbereich basierend auf den CLS-Ergebnissen. Geben Sie anhand der Positionsinformationen des Partikels mithilfe von CLS den Suchbereich mithilfe der folgenden Formel erneut an. Wenn jedoch wie in diesem Dokument beschrieben implementiert wird, werden der Minimalwert und der Maximalwert verwendet, wenn der Maximalwert unter mehreren Minimalwerten für den Minimalwert und der Minimalwert unter mehreren Minimalwerten für den Maximalwert verwendet wird Da es umgekehrt wurde, verwendete die Implementierung den Minimalwert für den Minimalwert und den Maximalwert für den Maximalwert, um den Suchbereich zu erweitern.

Code zur Reduzierung des Suchbereichs

def search_space_reduction(top_positions):
    min_x, min_y, max_x, max_y = [], [], [], []

    min_x.append(min(top["x"] for top in top_positions))
    min_y.append(min(top["y"] for top in top_positions))
    max_x.append(max(top["x"] for top in top_positions))
    max_y.append(max(top["y"] for top in top_positions))
    x = [top.get("x") for top in top_positions]
    y = [top.get("y") for top in top_positions]
    
    for i in range(len(top_positions)):
        min_x.append(x[i] - R * (max_x[0] - min_x[0]))
        min_y.append(y[i] - R * (max_y[0] - min_y[0]))
        max_x.append(x[i] + R * (max_x[0] - min_x[0]))
        max_y.append(y[i] + R * (max_y[0] - min_y[0]))
    
    #Wie im Papier neu_min_x = max(min_x)Wenn Sie den Wert auf einstellen, werden der Minimalwert und der Maximalwert umgekehrt. Korrigieren Sie ihn daher.
    new_min_x, new_min_y = min(min_x), min(min_y)
    new_max_x, new_max_y = max(max_x), max(max_y)
    search_space_x = {"min": new_min_x, "max": new_max_x}
    search_space_y = {"min": new_min_y, "max": new_max_y}

    return search_space_x, search_space_y

5. Regenerieren Sie die unteren 4/5 Partikel innerhalb des neuen Suchbereichs nach dem Zufallsprinzip

Da die unteren 4/5-Partikel nicht in den reduzierten neuen Suchbereich passen, erstellen Sie einen neuen, damit er in den Bereich passt. Partikel werden wie in den Grundeinstellungen zufällig generiert.

6. Bewerten Sie jedes Partikel und kehren Sie zu 1 zurück, wenn die Stoppbedingung erfüllt ist.

Bewerten Sie jedes Partikel. Wenn zu diesem Zeitpunkt die Punktzahl besser ist als die zuvor als Schwellenwert festgelegte Punktzahl oder wenn die maximale Anzahl von Suchvorgängen erreicht ist, endet die Suche und das Ergebnis wird ausgegeben. Wenn die Bedingungen nicht erfüllt sind, gehen Sie zurück zu 1. und führen Sie PSO aus, um die Suche fortzusetzen.

Bewertungsergebnis mit Benchmark-Funktion

Es gibt viele Benchmark-Funktionen als Funktionen zur Bewertung des Optimierungsalgorithmus. Artikel von Tomitomi3 enthält eine detaillierte Einführung in die Benchmark-Funktion. Dieses Mal habe ich die hier eingeführte Sphere-Funktion verwendet. Die optimale Lösung für diese Funktion ist $ f \ _ {min} (0, ..., 0) = 0 $.

Diesmal war die Endbedingung Score <1.000e-15 oder 10 Iterationen. Als Ergebnis konnten wir beobachten, wie es konvergierte, wie in der Abbildung gezeigt.

Darüber hinaus sind die Ergebnisse beim Ausführen ohne Zeichnen eines Bildes und beim Ausführen eines einfachen PSO wie folgt. Wenn die Genauigkeit durch CLS verbessert wird, wird auch die Punktzahl aktualisiert, und wenn die Genauigkeit nicht verbessert wird, wird die Punktzahl vor der Übernahme von CLS übernommen. Sie können sehen, dass der Suchbereich jedes Mal verringert und die Punktzahl verbessert wurde. Verglichen mit dem Ergebnis der Ausführung nur des PSO unten ist ersichtlich, dass die Genauigkeit verbessert wird, aber es braucht Zeit.

CPSO log and result

Lap: 1
CLS:
before: 1.856166459555566e-09
after: 1.7476630375799616e-07
Search Area:
before
x: {'min': -5.0, 'max': 5.0}
y: {'min': -5.0, 'max': 5.0}
after
x: {'min': -0.0010838869646188037, 'max': 0.0013954791030881871}
y: {'min': -0.001201690486501598, 'max': 0.0016078160576153975}
Score: 1.856166459555566e-09

Lap: 2
CLS:
before: 2.0926627088682597e-13
Better Chaotic Particle found
after: 7.821496571701076e-14
Search Area:
before
x: {'min': -0.0010838869646188037, 'max': 0.0013954791030881871}
y: {'min': -0.001201690486501598, 'max': 0.0016078160576153975}
after
x: {'min': -7.880347663659637e-06, 'max': 1.5561134225910913e-05}
y: {'min': -1.83517959693168e-05, 'max': 1.853229861175588e-05}
Score:   7.821496571701076e-14

Lap: 3
CLS:
before: 6.562680339774457e-17
Better Chaotic Particle found
after: 5.0984844476716916e-17
Search Area:
before
x: {'min': -7.880347663659637e-06, 'max': 1.5561134225910913e-05}
y: {'min': -1.83517959693168e-05, 'max': 1.853229861175588e-05}
after
x: {'min': -3.794413350751951e-07, 'max': 1.6057623588141383e-07}
y: {'min': -2.7039514283878003e-07, 'max': 8.373690854089289e-08}
Score:   5.0984844476716916e-17

Best Position: {'x': 6.92085226884776e-09, 'y': 1.7568859807915068e-09}
Score: 5.0984844476716916e-17
time: 0.7126889228820801

PSO result

Best Position: {'x': -0.23085945825227583, 'y': -0.13733679597570791}
Score: 4.218973135139706e-06
time: 0.006306886672973633

Zusammenfassung

Durch dieses Experimentieren konnte ich die Genauigkeit und Ausführungszeit von CPSO ermitteln. Dieses Mal habe ich es mit einer einfachen Funktion mit einer optimalen Lösung (monomodal) bewertet, aber ich möchte untersuchen, ob es eine Möglichkeit gibt, es mit einer multimodalen Funktion zu bewerten.

[PYTHON] Bewerten Sie Benchmark-Funktionen mit Chaotic PSO