Particle Swarm Optimization

Particle Swarm Optimization (PSO) : L’optimisation par essaims particulaires (Particle Swarm Optimization) est une méthode qui s’inspire de la biologie pour résoudre des problèmes d’optimisation.

Comme les réseaux de neurones artificiels, les algorithmes génétiques ou les algorithmes de colonies de fourmis, le Particle Swarm Optimization (PSO) est un  algorithme bio-inspiré. Il repose sur les principes d’auto-organisation qui permettent à un groupe d’organismes vivants d’agir ensemble de manière complexe, à partir de “règles” simples. Le PSO s’inspire du modèle développé par Craig Reynolds pour simuler le déplacement grégaire de certains animaux (troupeaux de bovins, volées d’oiseaux…). Dans ce modèle, chaque oiseau artificiel ou “boid” (bird-oid object), se déplace aléatoirement en suivant trois règles simples :

– La cohésion : les boids sont attirés vers la position moyenne du groupe ;
– L’alignement : les boids suivent le même chemin que leurs voisins ;
– La séparation : pour éviter les collisions, les boids gardent une certaine distance entre eux.

Le PSO introduit un autre principe : les boids ne se déplacent pas aléatoirement, ils ont un objectif à atteindre. Celui-ci est déterminé par une fonction à optimiser ou “fonction objectif” qui est fournie par l’utilisateur, et qui dépend de l’application concernée.

Comment fonctionne cet algorithme ? PSO explore l’espace de recherche grâce à des essais successifs de positions de boids, leurs mouvements étant gérés par des équations simples. Ainsi, la localisation de chaque boid dans l’espace de recherche représente une solution potentielle au problème d’optimisation. Et la “qualité” associée à chacune de ces solutions est quantifiée par la fonction objectif, optimisée petit à petit selon les positions, plus ou moins optimales.

Concrètement, le plus souvent, les localisations et les vitesses des boids sont représentées comme des vecteurs de nombres à D-dimensions, les positions et les vitesses initiales étant souvent définies aléatoirement. Puis, on réitère l’exploration en mettant à jour la position de chaque boid puis son vecteur vitesse jusqu’à atteindre une solution satisfaisante. On évalue le niveau de qualité associé à la position de chaque boid grâce à la fonction objectif. On détermine ainsi le meilleur boid et la meilleure position que chaque boid a pu rencontrer jusqu’à ce moment. Ensuite, le vecteur vitesse de chaque boid X est mis à jour (flèche en pointillé sur le schéma ci-dessous) en faisant une somme pondérée des trois vecteurs suivants.

– Un vecteur vitesse partant de X et allant vers le meilleur boid de l’essai (flèche rouge sur le schéma) ;
– Un vecteur vitesse allant vers la meilleure position que le boid a visité (flèche verte) ;
– Le vecteur vitesse précédent (flèche bleue).

Intuitivement, les actions des différents boids de l’essai permettent simultanément d’explorer l’espace de recherche et d’exploiter les zones les plus prometteuses. Un grand nombre de variantes de cet algorithme ont été développés et sont utilisés dans divers cadres d’application.

La vidéo et le schéma suivants illustrent l’utilisation d’une variante de cet algorithme dans le cadre d’une installation artistique interactive appelée “portrait on the fly”, développée par Laurent Mignonneau et Christa Sommerer. Dans cette installation, une caméra filme des spectateurs qui font face à un écran. Ces images sont “traitées” via  un essaim de mouches artificielles (des boids) visibles sur l’écran. Ces mouches se déplacent de telle sorte à optimiser un critère de détection de contours d’objets, en l’occurrence le contour des spectateurs faisant face à l’écran. Ainsi, le spectateur assiste, en direct, à la construction de sa silhouette, un genre de selfie créé par un essaim de mouches artificielles !