Essaim de particules

L’Optimisation par Essaim Particulaire (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 :

  1. 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.
  2. 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 :

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

Algorithme de base

Dans Rn, la particule i de l’essaim est modélisée par son vecteur position xi = (xi1, …, xin) et par son vecteur vitesse vi = (vi1, …, vin).

Cette particule garde en mémoire la meilleure position par laquelle elle est déjà passée, noté pi = (pi1, …, pin). La meilleure position atteinte par toutes les particules de l’essaim est notée pg = (pg1, …, pgn).

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

essaim1

avec c1 et c2 deux constantes, appelées coefficients d’accélération; r1 et r2 sont deux nombres aléatoires tirés uniformément dans [0,1].

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

  • vij(t) correspond à la composante physique du déplacement;
  • le terme d’après correspond à la composante cognitive du déplacement avec c1 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. c2 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 :

essaim2

Pseudo code

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.
essaim3

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
Publicités