Particle Swarm Optimization (PSO) : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le Particle Swarm Optimization (PSO) est un algorithme d’optimisation stochastique inspiré du comportement collectif des essaims biologiques. Proposé par James Kennedy et Russell Eberhart en 1995, le PSO simule un essaim de particules qui explorent conjointement l’espace de recherche pour identifier le minimum (ou maximum) d’une fonction objectif. Chaque particule ajuste sa trajectoire en combinant sa propre expérience individuelle (meilleure position personnelle, pbest) et l’expérience collective du groupe (meilleure position globale, gbest). Cette dualité cognition individuelle — information sociale constitue le cœur de l’algorithme. Contrairement aux algorithmes évolutionnaires, le PSO ne manipule ni croisement ni mutation : le mouvement des particules repose entièrement sur des mises à jour de vitesse et de position. Simple à implémenter, peu paramétrable et efficace sur des problèmes continus non convexes, le PSO s’est imposé comme l’une des métaheuristiques les plus populaires en optimisation et en apprentissage automatique.

Principe mathématique

Le PSO maintient un essaim de N particules dans un espace de recherche de dimension D. Chaque particule i possède :

• Une position x_i(t) ∈ ℝ^D à l’itération t.
• Une vitesse v_i(t) ∈ ℝ^D qui détermine son déplacement.
• Une meilleure position personnelle pbest_i — la position où la particule a obtenu le meilleur score depuis le début.
• Une meilleure position globale gbest — la meilleure position découverte par l’ensemble de l’essaim.

Équations de mise à jour

À chaque itération, la vitesse et la position de chaque particule sont mises à jour selon les formules suivantes :

Mise à jour de la vitesse :

v(t+1) = w · v(t) + c₁ · r₁ · (pbest − x) + c₂ · r₂ · (gbest − x)

Mise à jour de la position :

x(t+1) = x(t) + v(t+1)

Où :

En pratique, on applique souvent un plafond de vitesse |v| ≤ v_max pour éviter que les particules ne quittent brutalement l’espace de recherche. De même, la stratégie d’inertie décroissante (inertia weight decay) est largement utilisée : on commence avec un w élevé (exploration large) et on le réduit progressivement vers un w faible (raffinement local).

Intuition : le banc de poissons

Pour comprendre le PSO sans formules, imaginez un banc de poissons cherchant de la nourriture dans un lac assombri. Chaque poisson :

1. Se souvient de l’endroit où il a déjà trouvé le plus de nourriture (pbest — mémoire personnelle).
2. Observe le groupe et repère la zone où le poisson le mieux loti a trouvé le plus de nourriture (gbest — information collective).
3. Nage en combinant ces deux signaux : il tend vers sa propre zone favorite tout en étant attiré vers le meilleur spot du groupe. Chacun avance en fonction de sa propre mémoire (où j’ai trouvé de la nourriture avant) et de la mémoire collective (où le groupe en a trouvé le plus).

Si un poisson était uniquement guidé par sa mémoire personnelle (c₂ = 0), il tournerait en rond autour de ses propres découvertes passées — aucun apprentissage collectif. Si au contraire il ne suivait que le meilleur du groupe (c₁ = 0), tout l’essaim convergerait immédiatement vers un seul point, au risque de manquer de meilleures solutions ailleurs. L’équilibre entre ces deux forces — cognition individuelle et collaboration sociale — est ce qui rend le PSO efficace.

L’inertie w joue le rôle de l’élan : un poisson à grande vitesse continue dans sa direction malgré les nouvelles informations (exploration), tandis qu’un poisson qui ralentit ajuste finement sa trajectoire (exploitation).

Implémentation Python

Voici une implémentation from scratch du PSO appliquée à la fonction de Rastrigin, un benchmark classique en optimisation :

import numpy as np

def rastrigin(x):
    """Fonction de Rastrigin (minimum global = 0 en x = 0)."""
    A = 10
    D = len(x)
    return A * D + np.sum(x**2 - A * np.cos(2 * np.pi * x))

class ParticleSwarmOptimizer:
    def __init__(self, n_particles, dim, bounds, w=0.7, c1=1.5, c2=1.5,
                 max_iter=200, v_max=None):
        self.n_particles = n_particles
        self.dim = dim
        self.bounds = bounds
        self.w = w
        self.c1 = c1
        self.c2 = c2
        self.max_iter = max_iter
        self.v_max = v_max if v_max else (bounds[0][1] - bounds[0][0]) * 0.2

        # Initialisation aléatoire
        lows = np.array([b[0] for b in bounds])
        highs = np.array([b[1] for b in bounds])
        self.positions = np.random.uniform(lows, highs, (n_particles, dim))
        self.velocities = np.random.uniform(-self.v_max, self.v_max,
                                            (n_particles, dim))
        self.pbest_pos = self.positions.copy()
        self.pbest_val = np.array([self._evaluate(p) for p in self.positions])

        gbest_idx = np.argmin(self.pbest_val)
        self.gbest_pos = self.pbest_pos[gbest_idx].copy()
        self.gbest_val = self.pbest_val[gbest_idx]

        self.convergence_history = []

    def _evaluate(self, x):
        return rastrigin(x)

    def optimize(self):
        for t in range(self.max_iter):
            # Inertie décroissante linéaire
            w_current = self.w - (self.w - 0.3) * (t / self.max_iter)

            for i in range(self.n_particles):
                r1 = np.random.rand(self.dim)
                r2 = np.random.rand(self.dim)

                # Mise à jour de la vitesse
                cognitive = self.c1 * r1 * (self.pbest_pos[i] - self.positions[i])
                social = self.c2 * r2 * (self.gbest_pos - self.positions[i])
                self.velocities[i] = (w_current * self.velocities[i]
                                      + cognitive + social)

                # Plafond de vitesse
                self.velocities[i] = np.clip(self.velocities[i],
                                             -self.v_max, self.v_max)

                # Mise à jour de la position
                self.positions[i] += self.velocities[i]

                # Respect des bornes
                for d in range(self.dim):
                    self.positions[i, d] = np.clip(
                        self.positions[i, d], self.bounds[d][0], self.bounds[d][1])

                # Évaluation
                val = self._evaluate(self.positions[i])

                # Mise à jour du pbest
                if val < self.pbest_val[i]:
                    self.pbest_val[i] = val
                    self.pbest_pos[i] = self.positions[i].copy()

                    # Mise à jour du gbest
                    if val < self.gbest_val:
                        self.gbest_val = val
                        self.gbest_pos = self.positions[i].copy()

            self.convergence_history.append(self.gbest_val)

        return self.gbest_pos, self.gbest_val

# Exécution
if __name__ == "__main__":
    dim = 2
    bounds = [(-5.12, 5.12)] * dim

    pso = ParticleSwarmOptimizer(
        n_particles=30, dim=dim, bounds=bounds,
        w=0.9, c1=2.0, c2=2.0, max_iter=100
    )

    best_pos, best_val = pso.optimize()

    print(f"Meilleure position : {best_pos}")
    print(f"Meilleure valeur    : {best_val:.6f}")
    print(f"Valeur théorique     : 0.000000 (en x = 0)")
    print(f"Historique (5 derniers) : {pso.convergence_history[-5:]}")

Visualisation de la trajectoire et de la convergence

Pour visualiser la convergence de l’essaim, on trace l’historique du gbest au fil des itérations :

import matplotlib.pyplot as plt

plt.figure(figsize=(10, 5))
plt.plot(pso.convergence_history, linewidth=2, color="steelblue")
plt.xlabel("Itération")
plt.ylabel("Meilleure valeur (gbest)")
plt.title("Convergence du PSO sur la fonction de Rastrigin")
plt.grid(True, alpha=0.3)
plt.yscale("log")
plt.show()

Sur la fonction de Rastrigin en 2D, on observe généralement une convergence rapide en quelques dizaines d’itérations, avec le gbest approchant la valeur théorique de 0 avec une précision allant de 10⁻³ à 10⁻⁵ selon les paramètres choisis. Pour visualiser la trajectoire individuelle des particules, on peut superposer au contour de la fonction de Rastrigin les chemins parcourus par quelques particules représentatives, révélant comment l’essaim se densifie progressivement autour de l’optimum global.

Hyperparamètres

Le PSO est remarquablement économe en paramètres. Voici les six hyperparamètres principaux et leurs valeurs typiques :

Valeurs de référence

Les valeurs proposées par Shi et Eberhart (1998) — w = 0,729, c₁ = c₂ = 1,494 — sont considérées comme un point de départ robuste pour la plupart des problèmes. Le nombre de particules est souvent fixé à 30 comme compromis par défaut. Une règle empirique courante pour le nombre de particules est : n_particles ≈ 10 + 2 × √D, où D est la dimensionnalité du problème.

Avantages et limites

Avantages

• Simplicité d’implémentation : quelques dizaines de lignes de code suffisent. Aucun opérateur complexe (pas de croisement, pas de mutation, pas de sélection).
• Peu de paramètres : seulement 5 à 6 hyperparamètres à régler, contre des dizaines pour certains algorithmes évolutionnaires.
• Convergence rapide : sur des fonctions continues et lisses, le PSO converge généralement plus vite qu’un algorithme génétique classique.
• Parallélisation naturelle : l’évaluation de chaque particule est indépendante, ce qui permet une accélération massive sur GPU ou sur cluster distribué.
• Flexibilité : adaptable aux problèmes discrets (PSO binaire), aux espaces contraints, et aux fonctions objectif non différentiables.

Limites

• Convergence prématurée : sur des fonctions multimodales à nombreux minima locaux (comme Rastrigin en haute dimension), l’essaim peut se piéger dans un optimum local si le gbest converge trop vite.
• Sensibilité aux paramètres : bien que peu nombreux, les hyperparamètres influencent fortement les performances. De mauvais choix mènent à une stagnation ou une divergence.
• Dimensionnalité : les performances se dégradent au-delà de ~50 dimensions (problème de la malédiction de la dimensionnalité).
• Pas de garantie théorique : contrairement à certaines méthodes d’optimisation convexe, le PSO n’offre aucune garantie de convergence vers l’optimum global.
• Problèmes discrets : la version originale est conçue pour l’espace continu. Les adaptations binaires ou combinatoires nécessitent des modifications significatives.

4 cas d’usage concrets

1. Entraînement de réseaux de neurones

Le PSO peut optimiser directement les poids d’un réseau de neurones en traitant l’ensemble des poids comme la position d’une particule. Bien que la rétropropagation du gradient reste dominante pour l’entraînement, le PSO est précieux pour initialiser les poids avant un affinage par gradient descent, ou pour optimiser des réseaux non différentiables. Des travaux de recherche ont montré que le PSO peut surpasser la rétropropagation sur des fonctions d’activation irrégulières ou discontinues.

2. Optimisation d’hyperparamètres de modèles

Tout comme la Bayesian Optimization, le PSO peut rechercher les meilleurs hyperparamètres d’un modèle de machine learning (taux d’apprentissage, nombre de couches, régularisation, fonctions d’activation, etc.). Chaque particule encode une combinaison d’hyperparamètres et sa fitness correspond à la validation croisée du modèle entraîné avec ces paramètres. Cette approche est particulièrement efficace quand le nombre d’hyperparamètres est élevé et que les évaluations sont rapides.

3. Ingénierie et conception structurelle

En génie civil et aéronautique, le PSO est utilisé pour optimiser la forme de pièces mécaniques, la répartition de matériaux composites, ou les paramètres de contrôle de vol. La capacité à gérer des fonctions objectif coûteuses à évaluer (simulations par éléments finis, essais en soufflerie virtuelle) en fait un choix pertinent. Par exemple, la conception d’une aile d’avion peut être formulée comme la minimisation de la traînée sous contraintes de portance et de résistance structurelle — un problème idéal pour le PSO.

4. Planification de trajectoires et robotique

En robotique mobile, le PSO planifie des trajectoires optimales en évitant des obstacles. Chaque particule représente une trajectoire candidate, encodée comme une séquence de points de passage (waypoints). La fonction objectif pénalise la longueur du chemin, les collisions potentielles et les accélérations brusques. Cette approche est particulièrement efficace pour les robots autonomes en environnement dynamique, où l’essaim peut être réinitialisé à chaque changement de configuration de l’environnement pour recalculer en temps réel la trajectoire optimale.

Voir aussi

• Title: Maîtriser la question d’entretien Python : Calculer la racine carrée de x
• Vérifiez l’appartenance des points à un polygone convexe en O(log N) avec Python