Apprendre Optimisation par Essaim Particulaire | Algorithmes Basés sur l'Essaim

Définition

L'optimisation par essaim particulaire (PSO) est un algorithme bio-inspiré basé sur la population qui s'inspire du comportement collectif des vols d'oiseaux et des bancs de poissons. En PSO, un essaim d'agents simples appelés particules est utilisé. Chaque particule représente une solution potentielle au problème d'optimisation et se déplace dans l'espace de recherche en mettant à jour sa position et sa vitesse.

Concepts fondamentaux

Le mouvement de chaque particule est influencé par deux facteurs principaux :

Meilleur personnel : la meilleure position connue que la particule elle-même a découverte jusqu'à présent ;
Meilleur global : la meilleure position connue trouvée par l'ensemble de l'essaim à tout moment pendant la recherche.

Cette dynamique permet à l'essaim d'explorer efficacement l'espace des solutions, en équilibrant exploration (recherche de nouvelles zones) et exploitation (amélioration des zones déjà connues) à mesure que les particules communiquent et apprennent les unes des autres.

Concepts clés en PSO :

Particules : agents représentant des solutions possibles ;
Position : emplacement actuel d'une particule dans l'espace de recherche ;
Vitesse : direction et rapidité du déplacement de la particule ;
Meilleure position personnelle : meilleure position trouvée par chaque particule jusqu'à présent ;
Meilleure position globale : meilleure position trouvée par n'importe quelle particule de l'essaim.

En mettant à jour de manière itérative les positions et les vitesses selon ces principes, PSO permet de résoudre des problèmes d'optimisation complexes de manière flexible et efficace.

Exemple : Implémentation basique de PSO


              123456789101112131415161718192021222324252627282930313233343536373839404142434445
            
import numpy as np

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Initialize particle positions and velocities
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

# PSO loop
for iteration in range(num_iterations):
    # Evaluate current positions
    scores = objective(positions)
    # Update personal bests
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    # Update global best
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    # Update velocities and positions
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities

print(f"Best position found: {global_best_position:.3f}")
print(f"Objective value: {objective(global_best_position):.3f}")

Étape par étape : Mise à jour des positions et vitesses dans PSO

Évaluer chaque particule : Pour chaque particule, calculer la fonction objectif à sa position actuelle ;
Mettre à jour le meilleur personnel : Si la position actuelle donne un meilleur score que toute position précédente, l’enregistrer comme nouveau meilleur personnel ;
Mettre à jour le meilleur global : Identifier le meilleur score parmi tous les meilleurs personnels et mettre à jour la position globale en conséquence ;
Mettre à jour la vitesse : Pour chaque particule, calculer la nouvelle vitesse en utilisant :
- Le terme d’inertie (w * velocity), qui encourage la particule à continuer dans sa direction actuelle ;
- Le terme cognitif (c1 * r1 * (personal_best - position)), qui attire la particule vers sa propre meilleure expérience ;
- Le terme social (c2 * r2 * (global_best - position)), qui attire la particule vers le meilleur trouvé par l’essaim ;
Mettre à jour la position : Ajouter la nouvelle vitesse à la position actuelle pour obtenir la nouvelle localisation de la particule dans l’espace de recherche.

Les particules répètent ces étapes pendant un nombre défini d’itérations ou jusqu’à ce que les critères de convergence soient atteints.

Exemple : Visualisation des trajectoires des particules


              123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
            
import numpy as np
import matplotlib.pyplot as plt

# Objective function: simple 1D quadratic (minimum at x=3)
def objective(x):
    return (x - 3) ** 2 + 2

# PSO parameters
num_particles = 20
num_iterations = 50
w = 0.5  # Inertia coefficient
c1 = 1.5  # Cognitive (personal) coefficient
c2 = 1.5  # Social (global) coefficient

# Re-run the PSO loop, recording particle trajectories
positions = np.random.uniform(-10, 10, num_particles)
velocities = np.zeros(num_particles)
personal_best_positions = positions.copy()
personal_best_scores = objective(positions)
global_best_idx = np.argmin(personal_best_scores)
global_best_position = personal_best_positions[global_best_idx]

trajectories = [positions.copy()]

for iteration in range(num_iterations):
    scores = objective(positions)
    better_mask = scores < personal_best_scores
    personal_best_scores[better_mask] = scores[better_mask]
    personal_best_positions[better_mask] = positions[better_mask]
    global_best_idx = np.argmin(personal_best_scores)
    global_best_position = personal_best_positions[global_best_idx]
    r1 = np.random.rand(num_particles)
    r2 = np.random.rand(num_particles)
    velocities = (
        w * velocities
        + c1 * r1 * (personal_best_positions - positions)
        + c2 * r2 * (global_best_position - positions)
    )
    positions += velocities
    trajectories.append(positions.copy())

trajectories = np.array(trajectories)

# Plot trajectories
plt.figure(figsize=(10, 6))
for i in range(num_particles):
    plt.plot(trajectories[:, i], label=f"Particle {i+1}", alpha=0.5)
plt.axhline(3, color='red', linestyle='--', label='Optimum (x=3)')
plt.title('Particle Trajectories in PSO')
plt.xlabel('Iteration')
plt.ylabel('Position')
plt.legend(bbox_to_anchor=(1.05, 1), loc='upper left', fontsize='small')
plt.tight_layout()
plt.show()

Analyse des paramètres

Le choix des paramètres PSO a un impact significatif sur le comportement et la performance de l’algorithme :

Coefficient d’inertie (w) : Contrôle la part de la vitesse précédente conservée ;
- Des valeurs élevées favorisent l’exploration et aident les particules à échapper aux minima locaux ;
- Des valeurs faibles privilégient l’exploitation et accélèrent la convergence.
Coefficient cognitif (c1) : Détermine la force d’attraction des particules vers leurs propres meilleures positions ;
- L’augmentation de cette valeur encourage l’exploration indépendante et maintient la diversité de l’essaim.
Coefficient social (c2) : Régit l’attraction vers la meilleure position globale ;
- L’augmentation de cette valeur accélère la convergence en favorisant l’apprentissage collectif ;
- Des valeurs trop élevées peuvent entraîner une stagnation prématurée.

Un réglage minutieux de ces coefficients est essentiel pour obtenir des performances d’optimisation robustes dans différents domaines de problèmes. Ajuster les paramètres pour équilibrer exploration et exploitation, garantissant ainsi une recherche efficace sans blocage ni convergence trop rapide.

Tout était clair ?

Merci pour vos commentaires !

Section 3. Chapitre 2

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Awesome!

Completion rate improved to 6.25

Glissez pour afficher le menu