Optimisation par essaims particulaires

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Algorithme[modifier | modifier le code]

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[Qui ?], est la socio-psychologie[réf. nécessaire].

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 local. 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 3 composantes :

  1. Sa vitesse actuelle,
  2. Sa meilleure solution P_i,
  3. La meilleure solution obtenue dans son voisinage P_g.

Cela donne l'équation de mouvement suivante :

  • V_{k+1} = {\omega}V_k+b_1(P_i-X_k)+b_2(P_g-X_k).
  • X_{k+1} = X_k + V_{k+1}.


Avec :

{\omega} inertie
b_1 tiré aléatoirement dans [0,φ1]
b_2 tiré aléatoirement dans [0,φ2]

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]