[PYTHON] Trouvez la valeur minimale de la fonction par la méthode d'optimisation du groupe de particules (PSO)

Aperçu

L'optimisation des essaims de particules (PSO) est un type d'intelligence de groupe inspirée du comportement d'un groupe d'animaux. Dans cet article, je présenterai un exemple simple de la méthode d'optimisation des groupes de particules.

Spécimen

L'équation parabolique est donnée sous la forme suivante.

\begin{aligned}
z = x^2+y^2
\end{aligned}

Évidemment, la valeur minimale est $ z = 0 $ lorsque $ (x, y) = (0, 0) $. Ceci est obtenu en utilisant la méthode d'optimisation des groupes de particules.

Explication de la méthode d'optimisation des groupes de particules

Voir l'article ci-dessous. (L'indice du §2 est-il en partie incorrect?) Optimisation des groupes de particules et système non linéaire

Implémentons le §2 de cet article.

Code source

main.py

# -*- coding: utf-8 -*-

import numpy as np
import random

#Fonction d'évaluation: z = x^2 + y^2
def criterion(x, y):
    z = x * x + y * y
    return z

#Une fonction qui met à jour la position des particules
def update_position(x, y, vx, vy):
    new_x = x + vx
    new_y = y + vy
    return new_x, new_y

#Une fonction qui met à jour la vitesse des particules
def update_velocity(x, y, vx, vy, p, g, w=0.5, ro_max=0.14):
    #Le paramètre ro est donné au hasard
    ro1 = random.uniform(0, ro_max)
    ro2 = random.uniform(0, ro_max)
    #Mettre à jour la vitesse des particules
    new_vx = w * vx + ro1 * (p["x"] - x) + ro2 * (g["x"] - x)
    new_vy = w * vy + ro1 * (p["y"] - y) + ro2 * (g["y"] - y)
    return new_vx, new_vy


def main():
    N = 100  #Nombre de particules
    x_min, x_max = -5, 5
    y_min, y_max = -5, 5
    #Position des particules,la vitesse,Record personnel,Initialisez le meilleur du monde
    ps = [{"x": random.uniform(x_min, x_max), 
        "y": random.uniform(y_min, y_max)} for i in range(N)]
    vs = [{"x": 0.0, "y": 0.0} for i in range(N)]
    personal_best_positions = list(ps)
    personal_best_scores = [criterion(p["x"], p["y"]) for p in ps]
    best_particle = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[best_particle]
    
    T = 30  #Limite de temps(Nombre de boucles)
    for t in range(T):
        for n in range(N):
            x, y = ps[n]["x"], ps[n]["y"]
            vx, vy = vs[n]["x"], vs[n]["y"]
            p = personal_best_positions[n]
            #Mettre à jour la position des particules
            new_x, new_y = update_position(x, y, vx, vy)
            ps[n] = {"x": new_x, "y": new_y}
            #Mettre à jour la vitesse des particules
            new_vx, new_vy = update_velocity(
                new_x, new_y, vx, vy, p, global_best_position)
            vs[n] = {"x": new_vx, "y": new_vy}
            #Trouvez la valeur d'évaluation,Mettez à jour votre record personnel
            score = criterion(new_x, new_y)
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_positions[n] = {"x": new_x, "y": new_y}
        #Mettez à jour le meilleur du monde
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_positions[best_particle]
    #Solution optimale
    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

résultat

résultat

{'y': 0.00390598718159734, 'x': -0.0018420875049243782}
1.86500222386e-05

Visualisation

Il semble que les particules $ N (= 100) $ sont concentrées sur $ (x, y) = (0, 0) $.

Autre

Comment déterminez-vous certains paramètres tels que le nombre de particules? (Essai et erreur?)

L'ordre de mise à jour de position, de mise à jour de vitesse, de record personnel, de meilleur global est hors de propos selon la littérature ... Dans cet article, nous mettrons à jour la position ⇒ mettre à jour la vitesse ⇒ mettre à jour le record personnel ⇒ mettre à jour le meilleur mondial.

Modifier l'historique

• (2014/11/18) Correction du code source