L'optimisation par essaim de particules (PSO) est une méthode computationnelle en intelligence artificielle et en science computationnelle qui optimise un problème en améliorant itérativement une population de solutions candidates par rapport à une mesure de qualité donnée. Elle résout un problème à travers des interactions entre une population de solutions candidates, appelées particules, en les déplaçant dans l'espace de recherche selon des formules mathématiques simples qui ajustent la position et la vitesse de chaque particule. Le mouvement de chaque particule est influencé par sa propre meilleure position connue jusqu'à présent et par la meilleure position connue dans son voisinage topologique, qui peut inclure l'ensemble de la population si spécifié. Les vecteurs sont mis à jour lorsque de meilleures positions sont trouvées, et cela est censé déplacer l'essaim vers de bonnes solutions.
Le PSO est une métaheuristique car il fait peu ou pas d'hypothèses sur le problème à optimiser et peut rechercher de très grands espaces de solutions candidates. Il n'utilise pas le gradient du problème, donc il ne nécessite pas que le problème d'optimisation soit différentiable, contrairement aux méthodes classiques telles que la descente de gradient ou les méthodes quasi-Newton. Cependant, les métaheuristiques comme le PSO ne garantissent pas qu'une solution optimale sera jamais trouvée.
Origines et développement
Le PSO a été initialement attribué à Kennedy et Eberhart, qui l'ont d'abord conçu pour simuler le comportement social comme une représentation stylisée du mouvement des organismes dans un vol d'oiseaux ou un banc de poissons, ou l'évolution des attitudes dans une population humaine. La simulation des principes du comportement social a été observée comme capable de résoudre des problèmes mathématiques difficiles. Le livre de Kennedy et Eberhart décrit de nombreux aspects philosophiques du PSO et de l'intelligence en essaim. Une enquête extensive sur les applications du PSO a été réalisée par Poli, et en 2017, une revue complète sur les travaux théoriques et expérimentaux du PSO a été publiée par Bonyadi et Michalewicz.
Algorithme
Une variante de base de l'algorithme PSO est initialisée avec une population connectée (appelée essaim) de solutions candidates (appelées particules). Une solution candidate est un vecteur de valeurs numériques qui peut être considéré comme des coordonnées d'un point dans un espace de recherche ; en tant que point se déplaçant itérativement, il peut être conceptualisé comme une particule. Les particules se déplacent dans l'espace de recherche selon quelques formules simples. Chaque particule a des voisins auxquels elle est connectée, où le voisinage peut être quelques membres ou tous les autres membres de la population. La position suivante d'une particule est déterminée stochastiquement par sa propre meilleure position jusqu'à présent dans l'espace de recherche ainsi que par la meilleure position du meilleur voisin de la particule. Lorsqu'une position améliorée est découverte - une qui produit un meilleur résultat dans la fonction objectif - la meilleure position connue de la particule est mise à jour. Le processus est répété, et en faisant cela, il est attendu, mais non garanti, qu'une solution satisfaisante soit finalement découverte.
Formellement, soit \( f: \mathbb{R}^n \to \mathbb{R} \) la fonction de coût à minimiser. La fonction prend une solution candidate comme argument sous la forme d'un vecteur de nombres réels et produit un nombre réel en sortie indiquant la valeur de la fonction objectif. Le gradient de \( f \) n'est pas connu. L'objectif est de trouver une solution \( a \) pour laquelle \( f(a) \le f(b) \) pour tout \( b \) dans l'espace de recherche, ce qui signifie que \( a \) est le minimum global.
Soit \( S \) le nombre de particules dans l'essaim, chacune ayant une position \( x_i \in \mathbb{R}^n \) et une vitesse \( v_i \in \mathbb{R}^n \). Soit \( p_i \) la meilleure position connue de la particule \( i \), et soit \( g \) la meilleure position connue du voisinage de la particule. Un algorithme PSO de base pour minimiser la fonction de coût est :
- Pour chaque particule \( i = 1, \dots, S \) :
- Initialiser la position de la particule avec un vecteur aléatoire uniformément distribué : \( x_i \sim U(b_{lo}, b_{up}) \).
- Initialiser la meilleure position connue de la particule à sa position initiale : \( p_i \leftarrow x_i \).
- Si \( f(p_i) < f(g) \), mettre à jour la meilleure position connue de l'essaim : \( g \leftarrow p_i \).
- Initialiser la vitesse de la particule : \( v_i \sim U(-|b_{up}-b_{lo}|, |b_{up}-b_{lo}|) \).
- Tant qu'un critère de terminaison n'est pas satisfait :
- Pour chaque particule \( i = 1, \dots, S \) :
- Pour chaque dimension \( d = 1, \dots, n \) :
- Choisir des nombres aléatoires \( r_p, r_g \sim U(0,1) \).
- Mettre à jour la vitesse de la particule : \( v_{i,d} \leftarrow w v_{i,d} + \phi_p r_p (p_{i,d} - x_{i,d}) + \phi_g r_g (g_d - x_{i,d}) \).
- Mettre à jour la position de la particule : \( x_i \leftarrow x_i + v_i \).
- Si \( f(x_i) < f(p_i) \), mettre à jour la meilleure position connue de la particule : \( p_i \leftarrow x_i \).
- Si \( f(p_i) < f(g) \), mettre à jour la meilleure position connue de l'essaim : \( g \leftarrow p_i \).
Les valeurs \( b_{lo} \) et \( b_{up} \) représentent les limites inférieure et supérieure de l'espace de recherche. Le paramètre \( w \) est le poids d'inertie. Les paramètres \( \phi_p \) et \( \phi_g \) sont souvent appelés le coefficient cognitif et le coefficient social. Le critère de terminaison peut être le nombre d'itérations effectuées ou une solution où une valeur adéquate de la fonction objectif est trouvée. Les paramètres \( w \), \( \phi_p \) et \( \phi_g \) sont sélectionnés par le praticien et contrôlent le comportement et l'efficacité de la méthode PSO.
Sélection des paramètres
Le choix des paramètres du PSO peut avoir un impact important sur la performance d'optimisation. La sélection de paramètres qui produisent de bonnes performances a fait l'objet de nombreuses recherches. Pour prévenir la divergence (« explosion »), le poids d'inertie doit être inférieur à 1. Les deux autres paramètres peuvent être dérivés en utilisant l'approche de constriction ou sélectionnés librement, mais des analyses suggèrent des domaines de convergence pour les contraindre. Les valeurs typiques sont dans la plage [1, 3]. Les paramètres du PSO peuvent également être réglés en utilisant un autre optimiseur superposé, un concept connu sous le nom de méta-optimisation, ou même affinés pendant l'optimisation, par exemple, au moyen de logique floue. Les paramètres ont également été réglés pour divers scénarios d'optimisation.
Voisinages et topologies
La topologie de l'essaim définit le sous-ensemble de particules avec lequel chaque particule peut échanger des informations. La version de base de l'algorithme utilise la topologie globale comme structure de communication de l'essaim. Cette topologie permet à toutes les particules de communiquer avec toutes les autres particules, donc tout l'essaim partage la même meilleure position \( g \) provenant d'une seule particule. Cependant, cette approche peut conduire l'essaim à être piégé dans un minimum local, donc différentes topologies ont été utilisées pour contrôler le flux d'informations entre les particules. Par exemple, dans les topologies locales, les particules ne partagent des informations qu'avec un sous-ensemble de particules. Ce sous-ensemble peut être géométrique - par exemple « les \( m \) particules les plus proches » - ou, plus souvent, social, c'est-à-dire un ensemble de particules ne dépendant d'aucune distance. Dans de tels cas, la variante du PSO est dite meilleure locale (par opposition à meilleure globale pour le PSO de base). Une topologie d'essaim couramment utilisée est l'anneau, dans laquelle chaque particule a seulement deux voisins, mais il en existe beaucoup d'autres. La topologie n'est pas nécessairement statique ; elle peut changer pendant le processus d'optimisation.
Applications et méthodes connexes
Le PSO a été appliqué à une large gamme de problèmes d'optimisation dans des domaines tels que l'ingénierie, l'économie et l'apprentissage automatique. Il est particulièrement utile lorsque l'espace de recherche est vaste et que la fonction objectif est non différentiable ou bruitée. Le PSO partage des similitudes avec d'autres métaheuristiques basées sur la population, telles que les algorithmes génétiques et l'optimisation par colonies de fourmis, mais il se distingue par son mécanisme de mise à jour de vitesse inspiré du comportement social. Dans le contexte de apprentissage automatique, le PSO peut être utilisé pour le réglage des hyperparamètres ou l'entraînement de réseaux de neurones, bien qu'il soit souvent comparé aux méthodes basées sur le gradient. Sa nature stochastique et son absence d'exigence de gradient en font un outil polyvalent dans le domaine plus large de intelligence artificielle.