Optimisation par essaims particulaires

Optimisation par essaims particulaires

Evolution par iteration

Type	Algorithme, optimisation (d), intelligence artificielle

modifier - modifier le code - modifier Wikidata

L'optimisation par essaims particulaires (OEP ou PSO en anglais) est une métaheuristique d'optimisation, inventée par Russel Eberhart (ingénieur en électricité) et James Kennedy (socio-psychologue) en 1995.

Cet algorithme s'inspire à l'origine du monde du vivant. Il s'appuie notamment sur un modèle développé par Craig Reynolds à la fin des années 1980, permettant de simuler le déplacement d'un groupe d'oiseaux. Une autre source d'inspiration, revendiquée par les auteurs, James Kennedy et Russel Eberhart, est la socio-psychologie^[1].

Cette méthode d'optimisation se base sur la collaboration des individus entre eux. Elle a d'ailleurs des similarités avec les algorithmes de colonies de fourmis, qui s'appuient eux aussi sur le concept d'auto-organisation. Cette idée veut qu'un groupe d'individus peu intelligents peut posséder une organisation globale complexe.

Ainsi, grâce à des règles de déplacement très simples (dans l'espace des solutions), les particules peuvent converger progressivement vers un minimum global. Cette métaheuristique semble cependant mieux fonctionner pour des espaces en variables continues.

Au départ de l'algorithme chaque particule est donc positionnée (aléatoirement ou non) dans l'espace de recherche du problème. Chaque itération fait bouger les particules en fonction de trois composantes :

1. Sa vitesse actuelle ${\displaystyle V_{k}}$ ;
2. Sa meilleure solution ${\displaystyle P_{i}}$ ;
3. La meilleure solution obtenue dans son voisinage ${\displaystyle P_{g}}$.

Cela donne l'équation de mouvement suivante :

• ${\displaystyle V_{k+1}={\omega }V_{k}+b_{1}(P_{i}-X_{k})+b_{2}(P_{g}-X_{k})}$.
• ${\displaystyle X_{k+1}=X_{k}+V_{k+1}}$.

Avec :

${\displaystyle X_{k}}$ sa position actuelle

${\displaystyle {\omega }}$ inertie

${\displaystyle b_{1}}$ tiré aléatoirement dans

${\displaystyle b_{2}}$ tiré aléatoirement dans

Algorithme : Optimisation par Essaims Particulaires (PSO)

Entrée : Fonction objectif f(X), Nombre de particules N, Nombre maximum d'itérations MaxIter

Sortie : Meilleure solution Pg et sa valeur f(Pg)

1. Initialisation :
   1.1. Pour chaque particule i = 1 à N :
        - Initialiser la position Xi aléatoirement dans l'espace de recherche
        - Initialiser la vitesse Vi à zéro ou à une petite valeur aléatoire
        - Définir la meilleure solution personnelle Pi à Xi
   1.2. Évaluer la fonction de fitness de chaque particule en utilisant f(Xi)
   1.3. Définir la meilleure solution globale Pg à la position de la meilleure particule

2. Pour chaque itération k = 1 à MaxIter :
   2.1. Pour chaque particule i = 1 à N :
        - Générer b1 et b2, nombres aléatoires dans  et  respectivement
        - Mettre à jour la vitesse Vi selon l'équation :
          Vi(k+1) = ω*Vi(k) + b1*(Pi - Xi(k)) + b2*(Pg - Xi(k))
        - Mettre à jour la position Xi selon l'équation :
          Xi(k+1) = Xi(k) + Vi(k+1)
        - Évaluer la fonction de fitness de la nouvelle position en utilisant f(Xi(k+1))
        - Si f(Xi(k+1)) est meilleure que f(Pi) :
            - Mettre à jour Pi à Xi(k+1)
        - Si f(Xi(k+1)) est meilleure que f(Pg) :
            - Mettre à jour Pg à Xi(k+1)
   2.2. Ajuster éventuellement ω, φ1, et φ2 dynamiquement basé sur le numéro d'itération ou d'autres critères

3. Après avoir complété toutes les itérations, retourner Pg et f(Pg) comme la meilleure solution trouvée.

• Maurice Clerc, L'optimisation par essaims particulaires, Hermès Science, 2005, 288 p. (ISBN 978-2746209916, présentation en ligne) Avec codes sources.
• Abbas El Dor, Perfectionnement des algorithmes d’optimisation par essaim particulaire: applications en segmentation d’images et en électronique, 2013 (présentation en ligne, lire en ligne)

• Boids

• Particle Swarm Central
• Particle Swarm Optimization
• Article Science et Vie - Robots : l'union fait leur nouvelle force

v · m Apprentissage automatique et exploration de données
Paradigmes d'apprentissage	Apprentissage supervisé auto-supervisé semi-supervisé ou non supervisé Apprentissage par renforcement, par transfert ou incrémental
Problèmes	Classement Clustering Détection d'anomalies Optimisation en ligne Modèle génératif Régression Règle d'association Réduction de dimensions Analyse factorielle Sélection de caractéristique Extraction de caractéristique
Apprentissage supervisé	Classement Arbre de décision k-NN U-matrix CRF Régression logistique Régression Modèle linéaire généralisé Régression linéaire Régression de Poisson Modèle probit Analyse discriminante linéaire Machine à vecteurs de support Prédiction structurée Modèle graphique Classification naïve bayésienne Réseau bayésien Modèle de Markov caché Réseau de neurones artificiels récurrents (+ Rétropropagation à travers le temps) Calcul par réservoir à action directe (+ Rétropropagation du gradient) Apprentissage profond Perceptron Perceptron multicouche Réseau neuronal convolutif à impulsions
Apprentissage non supervisé et auto-supervisé	Clustering Regroupement hiérarchique K-moyennes Algorithme espérance-maximisation DBSCAN OPTICS Réduction de dimensions ACP ACP à noyaux Analyse en composantes indépendantes Analyse canonique des corrélations Analyse canonique à noyaux t-SNE Réseau de neurones artificiels Auto-encodeur IA générative et Modèle génératif Réseau de neurones artificiels Réseaux antagonistes génératifs (classique ou de Wasserstein) Auto-encodeur variationnel Réseau de Hopfield Machine de Boltzmann restreinte Cartes de Kohonen Transformeur
Métaheuristique d'optimisation	Stratégie d'évolution et génétique NEAT HyperNEAT Essaims Apprentissage ensembliste Forêts aléatoires Boosting
Théorie	Apprentissage PAC Complexité de Rademacher Dilemme biais-variance Hypothèse de la variété Théorie de Vapnik-Chervonenkis pulvérisation Dimension de Vapnik-Chervonenkis Théorème de Cover
Logiciels	Keras Microsoft Cognitive Toolkit Scikit-learn TensorFlow Theano Weka PyTorch

v · m Optimisation: théorie et algorithmes
Non linéaire	Méthode du nombre d'or Recherche linéaire Méthode de Nelder-Mead Critères de Wolfe Méthode de Broyden-Fletcher-Goldfarb-Shanno Algorithme à régions de confiance Pénalisation Algorithme du gradient Algorithme du gradient stochastique Méthode de Newton Algorithme de Gauss-Newton Algorithme de Levenberg-Marquardt Algorithme du lagrangien augmenté
Convexe	Optimisation complètement positive Optimisation copositive Optimisation SDP Méthode des plans sécants Algorithme de Frank-Wolfe Méthode de l'ellipsoïde Linéaire Optimisation conique Algorithme du simplexe Méthodes de points intérieurs Décomposition de Benders Génération de colonnes Quadratique Optimisation quadratique successive
Combinatoire	Algorithme d'approximation Programmation dynamique Algorithme glouton Optimisation linéaire en nombres entiers
Métaheuristique	Stratégie d'évolution Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l'informatique théorique