Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules

Optimisation des groupes de particules

L'optimisation des essaims de particules (PSO) est un type d'intelligence de groupe et est utilisée pour les problèmes d'optimisation combinée comme méthode de recherche de solution. C'est un flux pour procéder à la recherche en répétant la mise à jour de deux informations, la vitesse et la position de la particule. La figure ci-dessous est une image de l'optimisation des groupes de particules. pso2.png

algorithme

L'algorithme d'optimisation des groupes de particules est le suivant. スクリーンショット 2019-11-25 15.33.15.png

Formule de renouvellement

La vitesse et la position des particules sont mises à jour par la formule de mise à jour suivante. En termes simples, la vitesse représente la direction dans laquelle la particule évolue et la position représente les paramètres de la particule elle-même. スクリーンショット 2019-11-25 15.35.13.png

Expérience

Résolvons réellement le problème d'optimisation. Cette fois

x^2 + y^2

Résolvons le problème de minimisation. Par conséquent, (x, y) = (0,0) est la solution optimale. Le code utilisé est le suivant.

# -*- coding: utf-8 -*-
import numpy as np
import random

#Fonction d'évaluation
def evaluate(particle):
    z = 0
    for i in range(len(particle)):
        z += particle[i] ** 2
    return z

#Mise à jour de la position
def update_position(particle, velocity):
    new_particle = particle + velocity
    return new_particle

#Mise à jour de la vitesse
def update_velocity(particle, velocity, pbest, gbest, w=0.5, max=0.15):
    new_velocity = np.array([0.0 for i in range(len(particle))])
    #new_velocity = [0.0 for i in range(len(particle))]
    r1 = random.uniform(0, max)
    r2 = random.uniform(0, max)
    for i in range(len(particle)):
        new_velocity[i] = (w * float(velocity[i]) + r1 * (float(pbest[i]) - float(particle[i])) + r2 * (float(gbest[0]) - float(particle[i])))

    return new_velocity

def main():
    N = 100 #Nombre de particules
    length = 2  #Nombre de dimensions
    para_max = 100  #Valeur maximale du paramètre
    #Initialisation de la position des particules
    ps = [[random.uniform(-para_max, para_max) for j in range(length)] for i in range(N)]
    vs = [[0.0 for j in range(length)] for i in range(N)]
    #Record personnel
    personal_best_position = ps
    #Meilleure note personnelle
    personal_best_scores = [evaluate(p) for p in ps]
    #Index de la particule avec la valeur d'évaluation la plus basse
    best_particle = np.argmin(personal_best_scores)
    #Meilleur mondial
    global_best_position = personal_best_position[best_particle]

    generation = 30 #Nombre maximum de générations
    #Boucle depuis plusieurs générations
    for t in range(generation):
        file = open("data/pso/pso" + str(t+1) + ".txt", "w")
        #Boucle pendant quelques minutes
        for n in range(N):
            #Écriture de fichier
            file.write(str(ps[n][0]) + " " + str(ps[n][1]) + "\n")
            #Mise à jour de la vitesse des particules
            vs[n] = update_velocity(ps[n], vs[n], personal_best_position[n], global_best_position)
            #Mettre à jour la position des particules
            ps[n] = update_position(ps[n], vs[n])

            #Calculez la valeur d'évaluation et trouvez le record personnel
            score = evaluate(ps[n])
            if score < personal_best_scores[n]:
                personal_best_scores[n] = score
                personal_best_position[n] = ps[n]
        #Mettez à jour le meilleur du monde
        best_particle = np.argmin(personal_best_scores)
        global_best_position = personal_best_position[best_particle]
        file.close()

    print(global_best_position)
    print(min(personal_best_scores))

if __name__ == '__main__':
    main()

Résultat expérimental

Les individus des générations 1, 10, 20 et 30 sont codés par couleur et représentés sur la figure. Vous pouvez voir que les particules convergent vers (0,0) à mesure que la génération progresse. PSO.png

Recommended Posts

Essayez de résoudre le problème de minimisation des fonctions en utilisant l'optimisation des groupes de particules
Essayez de résoudre le problème de l'héritage de classe Python
Essayez l'optimisation des fonctions à l'aide d'Hyperopt
Essayez de résoudre le problème d'affectation du médecin de formation avec Python
Essayez de résoudre le problème N Queen avec SA de PyQUBO
Comment résoudre le problème d'emballage du bac
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (théorie)
Trouvez la valeur minimale de la fonction par la méthode d'optimisation du groupe de particules (PSO)
Résoudre les problèmes de sac à dos à l'aide de pyomo et glpk
Essayez de résoudre le diagramme homme-machine avec Python
Essayez de résoudre le problème du voyageur de commerce avec un algorithme génétique (résultat de l'exécution)
Essayez de résoudre le livre des défis de programmation avec python3
[Python] Essayez de lire la bonne réponse au problème FizzBuzz
Essayez de résoudre les problèmes / problèmes du "programmeur matriciel" (Chapitre 1)
Comment résoudre la fonction récursive qui a résolu abc115-D
J'ai essayé d'approcher la fonction sin en utilisant le chainer
J'ai essayé de résoudre le problème avec Python Vol.1
Essayez de résoudre le Sudoku à une vitesse explosive en utilisant Numpy
Essayez d'obtenir la liste des fonctions du paquet Python> os
J'ai essayé de simuler l'optimisation des publicités à l'aide de l'algorithme Bandit
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
Essayez de résoudre les problèmes / problèmes du "programmeur matriciel" (fonction du chapitre 0)
Résolvez le problème japonais lors de l'utilisation du module CSV en Python.
Le problème devient plus facile à résoudre en fonction de la méthode de formulation
J'ai essayé d'approcher la fonction sin en utilisant chainer (re-challenge)
Essayez l'optimisation des fonctions avec Optuna
Résolvez le problème de Monty Hall
Essayez d'utiliser l'API Twitter
Essayez d'utiliser l'API Twitter
À propos des paramètres d'optimisation des groupes de particules (PSO)
J'ai essayé d'obtenir l'index de la liste en utilisant la fonction énumérer
Essayez de modifier une nouvelle image à l'aide du modèle StyleGAN2 entraîné
Essayez de faire fonctionner la base de données en utilisant Peewee de ORM de Python (version août 2019)
Je voulais résoudre le problème ABC164 A ~ D avec Python
J'ai essayé de résoudre le problème de planification des équipes par diverses méthodes
Essayez de résoudre l'itinéraire le plus court avec les données sociales Python + NetworkX +
Résolvez des problèmes d'optimisation multivariée à l'aide de sagemath
Comment utiliser la fonction zip
Essayez d'utiliser pynag pour configurer Nagios
Précautions lors de l'utilisation de la fonction urllib.parse.quote
Essayez d'obtenir des statistiques en utilisant e-Stat
Essayez d'utiliser le module Python Cmd
Essayez Cython dans les plus brefs délais
Le moyen le plus rapide d'essayer EfficientNet
La façon la plus simple d'essayer PyQtGraph
Comment diviser et traiter une trame de données à l'aide de la fonction groupby
Le 16ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Essayez d'utiliser le framework web de Python Django (1) - De l'installation au démarrage du serveur
Essayez d'obtenir l'état de la surface de la route en utilisant de grandes données de gestion de la surface de la route
Essayez d'utiliser n pour rétrograder la version de Node.js que vous avez installée
Le 19ème comment écrire un problème de référence en temps réel hors ligne à résoudre avec Python
Essayez de résoudre un problème défini de mathématiques au lycée avec Python