Voir la source de Optimisation par essaims particulaires

{{Infobox Méthode scientifique
| image = PSO-GIF.gif
| légende = Evolution par iteration
}}L'<nowiki/>'''optimisation par essaims particulaires''' (''OEP'' ou ''PSO'' en [[anglais]]) est une [[métaheuristique]] d'[[Optimisation (mathématiques)|optimisation]], inventée par [[Russel Eberhart]] (ingénieur en électricité) et [[James Kennedy (psychologue)|James Kennedy]] (socio-psychologue) en [[1995]].

== Algorithme ==

Cet [[Algorithmique|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 (psychologue)|James Kennedy]] et [[Russel Eberhart]], est la socio-psychologie<ref>{{Article|prénom1=J.|nom1=Kennedy|prénom2=R.|nom2=Eberhart|titre=Particle swarm optimization|périodique=, IEEE International Conference on Neural Networks, 1995. Proceedings|volume=4|date=November 1995|doi=10.1109/icnn.1995.488968|lire en ligne=http://ieeexplore.ieee.org/document/488968/|consulté le=2017-06-06|pages=1942–1948 vol.4}}</ref>.

Cette méthode d'optimisation se base sur la collaboration des individus entre eux. Elle a d'ailleurs des similarités avec les [[algorithme de colonies de fourmis|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 :
# Sa vitesse actuelle <math>V_k</math> ;
# Sa meilleure solution <math>P_i</math> ;
# La meilleure solution obtenue dans son voisinage <math>P_g</math>.

Cela donne l'équation de mouvement suivante :

*<math>V_{k+1} = {\omega}V_k+b_1(P_i-X_k)+b_2(P_g-X_k)</math>.
*<math>X_{k+1} = X_k + V_{k+1}</math>.


Avec :
:<math>X_k</math> sa position actuelle
:<math>{\omega}</math> inertie
:<math>b_1</math> tiré aléatoirement dans [0,φ<sub>1</sub>]
:<math>b_2</math> tiré aléatoirement dans [0,φ<sub>2</sub>]

== Pseudo-code ==
<syntaxhighlight>
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.

</syntaxhighlight>

== Notes et références ==

=== Notes ===

=== Références ===
{{Références}}

== Annexes ==
=== Bibliographie ===
* {{Ouvrage| auteur=Maurice Clerc|nom=Clerc|lien auteur1=Maurice Clerc (mathématicien)| titre=L'optimisation par essaims particulaires| éditeur=Hermès Science| année=2005| pages totales=288| isbn=978-2746209916| présentation en ligne=https://www.lavoisier.fr/livre/mathematiques/l-optimisation-par-essaims-particulaires-versions-parametriques-et-adaptatives/clerc/descriptif-9782746209916}} Avec [http://www.hermes-science.com/clerc/oep.zip codes sources].
* {{Ouvrage| auteur=Abbas El Dor|nom=El Dor| titre=Perfectionnement des algorithmes d’optimisation par essaim particulaire: applications en segmentation d’images et en électronique| année=2013| présentation en ligne=https://tel.archives-ouvertes.fr/tel-00788961| lire en ligne=https://tel.archives-ouvertes.fr/tel-00788961/document}}

=== Articles connexes ===
* [[Boids]]

=== Liens externes ===
* [http://www.particleswarm.info/ Particle Swarm Central]
* [http://www.swarmintelligence.org/ Particle Swarm Optimization]
* [https://www.science-et-vie.com/technos-et-futur/robots-l-union-fait-leur-nouvelle-force-44722 Article Science et Vie - Robots : l'union fait leur nouvelle force]
{{Palette|Apprentissage automatique|Optimisation}}
{{Portail|informatique théorique}}

[[Catégorie:Métaheuristique]]
[[Catégorie:Intelligence artificielle]]