Optimisation par essaims particulaires

Evolution par iteration

Type	Algorithme, optimisation (d)

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 [0,φ₁]

${\displaystyle b_{2))$ tiré aléatoirement dans [0,φ₂]

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 [0,φ1] et [0,φ2] 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 Calcul par réservoir à action directe Apprentissage profond Perceptron Perceptron multicouche Réseau neuronal convolutif à impulsions
Apprentissage non supervisé et auto-supervisé	Clustering Regroupement hiérarchique K-means Algorithme espérance-maximisation DBSCAN OPTICS Réduction de dimensions ACP Analyse en composantes indépendantes Analyse canonique des corrélations 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 Réseau de Hopfield Machine de Boltzmann restreinte Cartes de Kohonen Transformeur
Métaheuristique d'optimisation	Algorithme évolutionniste et génétique NEAT HyperNEAT Essaims Apprentissage ensembliste Forêts aléatoires Boosting
Théorie	Dilemme biais-variance Apprentissage PAC Théorie de Vapnik-Chervonenkis pulvérisation Dimension de Vapnik-Chervonenkis Théorème de Cover Complexité de Rademacher
Logiciels	Keras Microsoft Cognitive Toolkit Scikit-learn TensorFlow Theano Weka PyTorch

v · m Optimisation mathématiques et algorithmiques
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	Algorithme évolutionniste Algorithme génétique Essaims Forêts aléatoires Boosting
Liste

• Portail de l'informatique théorique