À propos des paramètres d'optimisation des groupes de particules (PSO)

introduction

Ceci est l'article sur le 5ème jour du "Calendrier de l'Avent de Group Intelligence and Optimization 2019". C'est la première fois que je publie un article sur Qiita, donc c'est peut-être un peu ennuyeux, mais j'espère que vous le lirez. De plus, comme cet article concerne les paramètres PSO, si vous ne connaissez pas PSO en premier lieu, l'article de Ganariy d'hier "Je veux enregistrer la méthode d'optimisation des groupes de particules (PSO) / items / ae5a38a3537b06bd3842) »sera plus compréhensible si vous le lisez d'abord.

À propos de l'optimisation des groupes de particules (PSO) et des paramètres

Comme M. Ganariy l'a mentionné dans l'article d'hier sur les détails de PSO, il s'agit de l'un des algorithmes méta-heuristiques basés sur l'habitude d'agir dans un troupeau d'oiseaux et de poissons. Depuis la publication du Based Paper en 1995, divers modèles ont été proposés. PSO recherche la solution optimale en mettant à jour chaque particule avec la position actuelle $ x $ et la vitesse $ v . La vitesse et la position de chaque particule en mouvement sont mises à jour par la formule suivante. $ 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) $$ Ici, la meilleure position trouvée par chacun est appelée le record personnel (pBest), et la meilleure position de l'ensemble du groupe est appelée le meilleur global (gBest). De plus, $ v_ {id} $ est la vitesse de la i-ème particule dans la d-dimension, $ x_ {id} $ est la position de la i-ème particule dans la d-dimension, $ w $ est le poids, $ c_p $, $ c_g $ est Les constantes appelées coefficients d'accélération, $ r_p $ et $ r_g $, sont des nombres aléatoires de 0 à 1. Parmi ceux-ci, il y a le poids $ w $ et le coefficient d'accélération $ c_p $$ c_g $ comme paramètres qui peuvent être déterminés par l'homme, mais en particulier $ w $ a été beaucoup étudié comme paramètre qui a une grande influence sur la convergence des particules. Je suis.

Recherche effectuée sur le poids w

En tant qu'article de synthèse sur le poids w, un article intitulé "Un nouvel algorithme d'optimisation des essaims de particules avec poids d'inertie adaptative" a été publié en 2011. Je suis. Dans cet article, les poids w sont classés en trois types principaux.

  1. Le poids est constant ou aléatoire Dans Article donnant des constantes, des poids avec différentes constantes sont testés, et $ w> 1,2 $ entraîne une recherche superficielle, tandis que $ w < Il a été montré que 0.8 $ a tendance à converger vers la solution locale. De plus, dans Paper qui donne une valeur aléatoire, il est difficile de déterminer le poids optimal dans un environnement dynamique, donc une valeur aléatoire comme la formule suivante Proposez de donner. $ w = 0.5 + rand()/2 $

  2. Pondérations variant dans le temps De nombreuses méthodes basées sur PSO utilisent une méthode qui détermine la valeur de pondération en fonction du nombre d'itérations. L'une des méthodes utilisées dans de nombreux articles est le poids décroissant linéaire [Référence: 1, [2](https: // ieeexplore). .ieee.org / document / 785511), 3]. Ceci est exprimé par la formule suivante utilisant le nombre maximum d'itérations $ iter_ {max} $ et le nombre d'itérations $ iter $, le poids initial $ w_ {max} $ et la valeur finale $ w_ {min} . $ w(iter) = ((iter_{max} - iter)/iter_{max})(w_{max} - w_{min}) + w_{min} $$ En ce qui concerne les poids variant dans le temps, divers poids tels qu'une méthode utilisant un modèle de chaos et un poids décroissant non linéaire ont été proposés.

  3. Poids adaptatif Il surveille la situation de temps en temps et détermine les pondérations en fonction des paramètres de rétroaction. Une grande variété de méthodes a été proposée, donc si vous êtes intéressé, veuillez lire l'article de synthèse.

Implémentation LDWPSO

Parmi ce qui précède, je voudrais implémenter le PSO (LDWPSO) de poids de décrémentation linéaire le plus célèbre et le plus couramment utilisé. La fonction Sphère est utilisée comme fonction d'évaluation. Le programme ressemble à ceci: Lors de l'exécution, la 4ème boucle est visualisée et affichée.

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

SWARM_SIZE = 100 #Nombre de particules
ITERATION = 30 #Nombre de boucles PSO
C1 = C2 = 2.0 #Coefficient d'accélération
MIN_X, MIN_Y = -5.0, -5.0 #Portée minimale au début de la recherche
MAX_X, MAX_Y = 5.0, 5.0 #Portée maximale au début de la recherche
W_MAX, W_MIN = 0.9, 0.4

#Fonction d'évaluation(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):
    #Déplacer les particules par le nombre de boucles
    for i in range(ITERATION):
        for s in range(SWARM_SIZE):
            #Substitution d'informations avant le changement
            x, y = position[s]["x"], position[s]["y"]
            vx, vy = velocity[s]["x"], velocity[s]["y"]
            p = personal_best_positions[s]
            
            #Mise à jour de la position des particules
            new_x, new_y = update_position(x, y, vx, vy, search_space_x, search_space_y)
            position[s] = {"x": new_x, "y": new_y}
            #Mise à jour de la vitesse des particules
            new_vx, new_vy = update_velocity(new_x, new_y, vx, vy, p, best_position, i)
            velocity[s] = {"x": new_vx, "y": new_vy}

            #Trouvez la valeur d'évaluation
            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)
        

#Fonction de mise à jour de la position des particules
def update_position(x, y, vx, vy, search_space_x, search_space_y):
    new_x = x + vx
    new_y = y + vy
    #Vérifiez s'il se trouve dans la plage de recherche
    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

#Fonction de mise à jour de la vitesse des particules
def update_velocity(x, y, vx, vy, p, g, i):
    #random parameter (0~1)
    r1 = random.random()
    r2 = random.random()

    #Diminution linéaire du poids
    L = (ITERATION - i) / ITERATION
    D = W_MAX - W_MIN
    w = L * D + W_MIN
    print(w)

    #Mise à jour de la vitesse
    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

#Fonction de visualisation
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():
    #Mesure de l'heure de début
    start = time.time()

    #Position initiale de chaque particule,la vitesse, personal best,meilleurs paramètres globaux et espace de recherche
    position = []
    velocity = []
    personal_best_scores = []
    #Position initiale,Vitesse initiale
    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)

    #Mesure du temps terminée
    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()

En fait, ce serait bien si je pouvais le comparer à un simple PSO, mais comme je suis épuisé, cela m'intéresse car il devient un simple PSO simplement en changeant la valeur de $ w_ {min} $ en 0.9. Veuillez essayer.

Résumé

C'est devenu un article assez académique, mais en résumé, ・ Le poids PSO $ w $ a une grande influence sur la convergence vers la solution optimale. ・ Il existe trois principaux types de poids -Le poids le plus couramment utilisé est le poids linéaire décroissant, qui est l'un des poids variant dans le temps. Ce sera. De cette façon, je vous serais reconnaissant de bien vouloir savoir que diverses études sont en cours, même avec un seul paramètre.

Recommended Posts

À propos des paramètres d'optimisation des groupes de particules (PSO)
Trouvez la valeur minimale de la fonction par la méthode d'optimisation du groupe de particules (PSO)
Implémentation de la régression logistique avec la méthode d'optimisation des groupes de particules
Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules