Contenus

Optimisation par Essaim de Particules

L’Optimisation par Essaim de Particules (OEP, ou PSO en anglais) a été proposée par Kennedy et Eberhart. Cette méthode est inspirée du comportement social des animaux évoluant en essaim.

Au départ, ils cherchaient à simuler la capacité des oiseaux à voler de façon synchrone et leur aptitude à changer brusquement de direction tout en restant en une formation optimale.

Les particules sont les individus et elles se déplacent dans l’hyperespace de recherche en se basant sur des informations limitées :

Chaque particule est dotée d’une mémoire qui lui permet de mémoriser le meilleur point par lequel elle est déjà passée et elle a tendance à retourner vers ce point.
Chaque particule est informée du meilleur point connu au sein de son voisinage et elle va tendre à aller vers ce point.

Chaque individu utilise donc, non seulement, sa propre mémoire, mais aussi l’information locale sur ses plus proches voisins pour décider de son propre déplacement. Des règles simples, telles que : aller à la même vitesse que les autres, se déplacer dans la même direction ou encore rester proche de ses voisins sont des exemples de comportements qui suffisent à maintenir la cohésion de l’essaim.

Le déplacement d’une particule est influencé par les trois types de comportement :

Une composante physique : la particule tend à suivre sa suivre sa propre voie ;
Une composante cognitive : la particule tend à revenir vers le meilleur site par lequel elle est déjà passée ;
Une composante sociale : la particule tend à se diriger vers le meilleur site déjà atteint par ses voisins.

Algorithme d’Optimisation par Essaim de Particules

Dans Rⁿ, la particule i de l’essaim est modélisée par son vecteur position x_i = (x_i1, …, x_in) et par son vecteur vitesse v_i = (v_i1, …, v_in).

Cette particule garde en mémoire la meilleure position par laquelle elle est déjà passée, noté p_i = (p_i1, …, p_in). La meilleure position atteinte par toutes les particules de l’essaim est notée p_g = (p_g1, …, p_gn).

Au temps t+1, le vecteur vitesse est calculé à partir de la formule A :

avec c₁ et c₂ deux constantes, appelées coefficients d’accélération; r₁ et r₂ sont deux nombres aléatoires tirés uniformément dans [0,1].

Les trois termes additionnés de la formule s’explique ainsi :

v_ij(t) correspond à la composante physique du déplacement;
le terme d’après correspond à la composante cognitive du déplacement avec c₁ qui pondère les tendances de la particule à vouloir suivre son instinct de conservation et à aller vers sa meilleure position connue;
le dernier terme correspond à la composante sociale du déplacement. c₂ contrôle l’aptitude sociale de la particule en se rapprochant plus de la meilleure position de ses informatrices.

La position de la particule i est alors définie par la formule B :

Pseudo code de l’Optimisation par Essaim de Particules

Le critère d’arrêt peut être différent suivant le problème posé et les exigences de l’utilisateur. Si l’optimum global est connu a priori, on peut définir une erreur acceptable comme critère d’arrêt. Sinon, on peut fixer nombre maximum d’itérations ou un nombre maximum d’évaluations de la fonction objectif.

Variantes

Imposer une vitesse max positive et négative
Appliquer un coefficient d’inertie au premier terme de la formule A -> Shi et Eberhart 1998
Appliquer un facteur de constriction dans la formule A à la place des constantes -> Clerc et Kennedy 2002
Appliquer d’une topologie de voisinage pour savoir avec quelle particule une particule i va communiquer -> Kennedy 1999