Search-11-métaheuristiques : Optimisation avec MEALPy

Navigation : << Recherche locale | Index | App-1-NQueens >>

métaheuristiques : PSO, ABC, SA et au-dela

Ce notebook explore les métaheuristiques, une famille d’algorithmes d’optimisation inspires de la nature (evolution, essaims, physique) pour resoudre des problemes d’optimisation difficiles. Nous utiliserons la bibliotheque MEALPy qui implemente plus de 200 algorithmes.

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Comprendre les principes fondamentaux des métaheuristiques et leurs catégories (Evolution-based, Swarm-based, Physics-based, Human-based) 2. Comparer les performances de différents algorithmes sur des problemes de benchmark 3. Appliquer mealpy pour resoudre des problemes d’optimisation reels 4. Analyser la convergence et les paramètres des algorithmes

Prerequis

  • Notebook Search-04-LocalSearch (Hill Climbing, Simulated Annealing)
  • Python 3.10+ : numpy, matplotlib
  • Notions de base en optimisation (fonction objectif, minimiseur)

Duree estimee : 1h30

# Dependances pre-provisionnees (numpy matplotlib pandas mealpy 3.x) : deps standards + mealpy.
# Aucun install requis dans le notebook ; imports directs dans les cellules suivantes.

Import des bibliotheques

Chargement des outils pour la comparaison des métaheuristiques.

# Imports
import sys
import time
import math
import numpy as np
import matplotlib.pyplot as plt
import pandas as pd
from pathlib import Path

%matplotlib inline

# Imports MEALPy 3.0.2
from mealpy import ParameterGrid
from mealpy import PSO, ABC, SA, BRO, GWO, WOA, GA, DE, Problem
from mealpy.utils.space import FloatVar

# Configuration
np.random.seed(42)

print("Environnement pret pour les metaheuristiques.")
print(f"MEALPy 3.0.2 importe avec succes.")
Environnement pret pour les metaheuristiques.
MEALPy 3.0.2 importe avec succes.

1. Introduction aux métaheuristiques (~15 min)

Qu’est-ce qu’une métaheuristique ?

Une métaheuristique est un algorithme d’optimisation qui guide un sous-problème heuristique vers une solution optimale (ou proche de l’optimal). Contrairement aux algorithmes exacts, les métaheuristiques ne garantissent pas l’optimalite mais sont souvent efficaces sur des problemes difficiles.

caractéristiques cles : - Sans derivees : ne necessitent pas de calculer les gradients - Iteratives : ameliorent progressivement la solution - Stochastiques : utilisent l’aleatoire pour explorer l’espace - Generiques : applicables a de nombreux problemes

Classification des métaheuristiques

catégorie Inspiration Exemples
Evolution-based théorie de l’evolution, génétique GA, DE, ES
Swarm-based Comportements collectifs (essaims) PSO, ABC, ACO, GWO
Physics-based Loi physique SA, GRAVITY, ELECTRO
Human-based Comportement humain BRO, TS, CA

Ancres savantes – Kennedy, J. & Eberhart, R. (1995), Particle Swarm Optimization, Proc. IEEE Int. Conf. on Neural Networks IV:1942-1948 (PSO, essaim de particules ajustant leurs vitesses vers le meilleur personnel et global) ; Karaboga, D. (2005), An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report-TR06, Erciyes University (Artificial Bee Colony, ABC, rôles employée/observatrice/éclaireuse) ; Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983), Optimization by Simulated Annealing, Science 220(4598):671-680 (recuit simulé, accepte des dégradations selon une température décroissante pour échapper aux optima locaux) ; Yang, X.-S. (2010), Nature-Inspired Metaheuristic Algorithms (2nd ed.), Luniver Press (taxonomie evolution/swarm/physics/human-based et cadre des métaheuristiques sans dérivée).

# Verification de MEALPy
try:
    import mealpy
    print(f"MEALPy version: {mealpy.__version__}")
    print(f"Nombre d'algorithmes disponibles: > 200")
except ImportError:
    print("MEALPy non installe. Installation...")
    print("Commande: pip install mealpy")
MEALPy version: 3.0.3
Nombre d'algorithmes disponibles: > 200

Exploration vs Exploitation

Toute métaheuristique doit equilibrer deux forces opposes :

Aspect Exploration Exploitation
Objectif Decouvrir de nouvelles regions de l’espace Affiner les solutions prometteuses
Risque Trop -> random search, lente convergence Trop -> optimum local
Analogie Chercher dans toute la maison Chercher dans la piece ou on a perdu

Le succes d’une métaheuristique depend de sa capacite a : 1. Explorer largement au debut (eviter les optima locaux) 2. Exploiter intensivement a la fin (converger vers l’optimum) 3. Adapter l’equilibre pendant la recherche

Theoreme No Free Lunch : Aucun algorithme n’est optimal pour tous les problemes. Le choix depend de la structure du problème.

2. La librairie MEALPy (~10 min)

Presentation de MEALPy

MEALPy (Meta-Heuristic Algorithms in Python) est une bibliotheque qui implemente plus de 200 algorithmes d’optimisation métaheuristiques avec une API unifiee.

Installation :

pip install mealpy>=3.0

API standard (MEALPy 3.0.2)

Tous les algorithmes suivent le même schema :

from mealpy import Problem, Algorithme
from mealpy.utils.space import FloatVar

# définir le problème avec FloatVar
bounds = [FloatVar(lb=-10, ub=10), FloatVar(lb=-10, ub=10)]
problem = Problem(
    bounds=bounds,         # Liste de FloatVar definissant les bornes
    minmax="min",          # Minimisation ou maximisation
    obj_func=ma_fonction   # Fonction objectif
)

# créer et executer l'algorithme
model = Algorithme(epoch=100, pop_size=50)
result = model.solve(problem)

paramètres principaux

paramètre Signification Valeur typique
epoch Nombre d’itérations 100-1000
pop_size Taille de la population 20-100
bounds Liste de FloatVar (lb, ub) Problemes-dependent
minmax “min” ou “max” “min” le plus souvent 
# Exemple : optimiser une fonction multimodale (Rastrigin)
def rastrigin(solution):
    """Fonction de Rastrigin : f(x) = 10*n + sum(x**2 - 10*cos(2*pi*x)).
    Multimodale : un optimum global en [0, 0] mais des dizaines d'optima locaux."""
    n = len(solution)
    return 10*n + np.sum(solution**2 - 10*np.cos(2*np.pi*solution))

# Definir le probleme (MEALPy 3.0.2 API)
# Bornes canoniques de Rastrigin : [-5.12, 5.12]
bounds = [FloatVar(lb=-5.12, ub=5.12), FloatVar(lb=-5.12, ub=5.12)]
problem = Problem(
    bounds=bounds,
    minmax="min",
    obj_func=rastrigin
)

# Resoudre avec PSO : la swarm doit echapper aux optima locaux
model = PSO.OriginalPSO(epoch=50, pop_size=20)
result = model.solve(problem)

print("Resultat PSO sur Rastrigin 2D (fonction multimodale):")
print(f"  Solution: {result.solution.round(4)}")
print(f"  Objectif: {result.target.fitness:.6f}")
print(f"  Optimal global: [0, 0] avec f=0 (mais optima locaux nombreux)")
Resultat PSO sur Rastrigin 2D (fonction multimodale):
  Solution: [-0. -0.]
  Objectif: 0.000000
  Optimal global: [0, 0] avec f=0 (mais optima locaux nombreux)

Interpretation : Premier contact avec MEALPy

Sortie obtenue : PSO trouve une solution proche de l’optimum global [0, 0], mais pas toujours exactement. Rastrigin est multimodale : elle regorge d’optima locaux (les cuvettes du paysage cosinusoïdal), et selon l’initialisation la swarm peut s’y piéger — la valeur objectif est alors de l’ordre de 1 à 2, pas 0.

élément Valeur Signification
Solution Vecteur de 2 valeurs Position dans l’espace 2D
Objectif ≈0 si échappée, ~1-2 si piégée Qualité de la solution
Optimal global [0, 0], f=0 Solution théorique

C’est précisément la difficulté qui justifie une métaheuristique : une descente de gradient se figerait dans le premier optimum local rencontré, tandis que la swarm de PSO explore plusieurs régions et peut en sortir. Le prochain notebook approfondit comment l’équilibre exploration/exploitation y contribue.

Points cles : 1. L’API MEALPy 3.0.2 utilise FloatVar pour définir les bornes de recherche 2. La fonction objectif recoit un vecteur numpy et retourne un scalaire 3. Le résultat contient solution (vecteur) et target.fitness (valeur) 4. Le paramètre bounds remplace les anciens paramètres lb et ub séparés

3. Fonctions de Benchmark (~5 min)

Pour comparer les métaheuristiques, nous utilisons des fonctions de benchmark classiques en optimisation. Ces fonctions ont des proprietes connues (multimodalite, convexite, etc.) qui permettent d’evaluer les algorithmes.

Fonctions unimodales vs multimodales

Type Propriete Exemple
Unimodal Un seul optimum global Sphere, Rosenbrock
Multimodal Plusieurs optima locaux Rastrigin, Ackley

Les fonctions multimodales sont plus difficiles car les algorithmes peuvent rester coinces dans un optimum local.

# Fonctions de benchmark classiques

def sphere_function(solution):
    """Fonction Sphere : f(x) = sum(x^2).
    
    - Unimodale, convexe
    - Optimum global: x* = [0, ..., 0], f(x*) = 0
    """
    return np.sum(solution**2)


def rastrigin_function(solution):
    """Fonction de Rastrigin : f(x) = 10*n + sum(x^2 - 10*cos(2*pi*x)).
    
    - Multimodale avec de nombreux optima locaux
    - Optimum global: x* = [0, ..., 0], f(x*) = 0
    - Tres difficile pour les algorithmes gloutons
    """
    A = 10
    n = len(solution)
    return A*n + np.sum(solution**2 - A*np.cos(2*np.pi*solution))


def rosenbrock_function(solution):
    """Fonction de Rosenbrock : f(x) = sum(100*(x[i+1] - x[i]^2)^2 + (1 - x[i])^2).
    
    - Vallée etroite et incurvee (difficile a optimiser)
    - Optimum global: x* = [1, ..., 1], f(x*) = 0
    - Classiquement utilisee pour tester la convergence
    """
    return np.sum(100.0*(solution[1:] - solution[:-1]**2)**2 + (1 - solution[:-1])**2)


def ackley_function(solution):
    """Fonction d'Ackley.
    
    - Multimodale avec nombreux plateaux
    - Optimum global: x* = [0, ..., 0], f(x*) = 0
    """
    a, b, c = 20, 0.2, 2*np.pi
    d = len(solution)
    sum1 = np.sum(solution**2)
    sum2 = np.sum(np.cos(c*solution))
    term1 = -a*np.exp(-b*np.sqrt(sum1/d))
    term2 = -np.exp(sum2/d)
    return term1 + term2 + a + np.exp(1)

# Tableau recapitulatif
benchmark_functions = {
    'Sphere': sphere_function,
    'Rastrigin': rastrigin_function,
    'Rosenbrock': rosenbrock_function,
    'Ackley': ackley_function
}

print("Fonctions de benchmark chargees.")
print("\nProprietes:")
print(f"  {'Nom':<15} {'Type':<15} {'Optimum':<20}")
print("-" * 50)
print(f"  {'Sphere':<15} {'Unimodale':<15} {'[0, ..., 0], f=0':<20}")
print(f"  {'Rastrigin':<15} {'Multimodale':<15} {'[0, ..., 0], f=0':<20}")
print(f"  {'Rosenbrock':<15} {'Vallee etroite':<15} {'[1, ..., 1], f=0':<20}")
print(f"  {'Ackley':<15} {'Multimodale':<15} {'[0, ..., 0], f=0':<20}")
Fonctions de benchmark chargees.

Proprietes:
  Nom             Type            Optimum             
--------------------------------------------------
  Sphere          Unimodale       [0, ..., 0], f=0    
  Rastrigin       Multimodale     [0, ..., 0], f=0    
  Rosenbrock      Vallee etroite  [1, ..., 1], f=0    
  Ackley          Multimodale     [0, ..., 0], f=0

4. Evolution-based - Particle Swarm Optimization (PSO) (~20 min)

Principe du PSO

Le Particle Swarm Optimization est inspire du comportement social d’essaims (oiseaux, poissons). Chaque particule a : - Une position courante dans l’espace de recherche - Une vitesse qui determine son deplacement - Une memoire de sa meilleure position personnelle (pbest) - Une connaissance de la meilleure position globale (gbest)

Equations de mise a jour

A chaque itération, chaque particule \(i\) met a jour sa vitesse et sa position :

\[ v_i(t+1) = w \cdot v_i(t) + c_1 \cdot r_1 \cdot (pbest_i - x_i(t)) + c_2 \cdot r_2 \cdot (gbest - x_i(t)) \]

\[ x_i(t+1) = x_i(t) + v_i(t+1) \]

Ou : - \(w\) : inertie (conserve la vitesse actuelle) - \(c_1, c_2\) : coefficients d’acceleration (typiquement \(c_1 = c_2 = 2.0\)) - \(r_1, r_2\) : nombres aleatoires dans \([0, 1]\)

Intuition

Chaque particule equilibre trois forces : 1. Inertie : continuer dans sa direction actuelle 2. Cognitif : retourner vers sa meilleure position personnelle 3. Social : se diriger vers la meilleure position du groupe

# PSO sur Rastrigin (fonction multimodale difficile)

# Parametres du probleme
dim = 10  # Dimension

# Definir le probleme (MEALPy 3.0.2 API)
bounds_rastrigin = [FloatVar(lb=-5.12, ub=5.12) for _ in range(dim)]
problem_rastrigin = Problem(
    bounds=bounds_rastrigin,
    minmax="min",
    obj_func=rastrigin_function
)

# PSO avec parametres standards
model = PSO.OriginalPSO(
    epoch=200,      # Nombre d'iterations
    pop_size=50,    # Taille de l'essaim
    c1=2.0,         # Coefficient cognitif
    c2=2.0,         # Coefficient social
    w=0.9           # Inertie (commence haute pour l'exploration)
)

# Resoudre
print("PSO sur Rastrigin (dim=10)...")
start_time = time.perf_counter()
result_pso = model.solve(problem_rastrigin)
elapsed_pso = (time.perf_counter() - start_time) * 1000

print(f"\nResultat PSO:")
print(f"  Solution: {np.array(result_pso.solution).round(4)}")
print(f"  Objectif: {result_pso.target.fitness:.6f}")
print(f"  Temps: {elapsed_pso:.2f} ms")
print(f"  Optimal attendu: [0, ..., 0], f=0")
PSO sur Rastrigin (dim=10)...

Resultat PSO:
  Solution: [-4.0484  0.851  -1.1011 -1.0477  0.868   3.0508  0.9057  1.0829  3.8671
  2.8737]
  Objectif: 74.677182
  Temps: 746.94 ms
  Optimal attendu: [0, ..., 0], f=0

Interpretation : PSO sur Rastrigin

Sortie obtenue : sur cette exécution (cellule précédente), PSO reste éloigné de l’optimum (objectif ~67,5, optimum=0).

Aspect Observation
Solution Vecteur encore loin de [0, …, 0]
Objectif Encore élevé (~67,5) : Rastrigin multimodal est difficile
Convergence Rapide mais peut rester coincé dans un optimum local

Points clés : 1. PSO progresse vite mais peut rester coincé loin de l’optimum sur les problèmes multimodaux. 2. L’équilibre exploration/exploitation est contrôlé par \(w\), \(c_1\), \(c_2\). 3. La communication sociale (gbest) permet une convergence rapide. 4. Le benchmark multi-seed du §8 (moyenne sur 5 graines, budget égal) le mesure : sur Rastrigin, PSO (9,15) bat SA (12,89) et le tirage aléatoire (74,78) — c’est la sortie mesurée qui le prouve, pas un a priori. Et sur Sphere, la baseline hill-climber (0,28) bat même SA (1,75) et BRO (0,38) : sur un problème trivial, une métaheuristique complexe peut être dépassée par une simple descente locale. C’est l’ancrage « baseline triviale » (No-Free-Lunch) que le notebook enseigne.

# Visualisation de la convergence PSO
# Note: MEALPy 3.x a change l'API - utilisation de l'approche standard avec historique

from mealpy import PSO
import numpy as np

# Solution simple: executer PSO plusieurs fois avec differents epochs pour voir la convergence
epochs_to_test = [10, 20, 50, 100, 200]
convergence_history = []

for n_epochs in epochs_to_test:
    model = PSO.OriginalPSO(epoch=n_epochs, pop_size=30, w=0.9, c1=2.0, c2=2.0)
    result = model.solve(problem_rastrigin)
    convergence_history.append(result.target.fitness)

# Visualiser
fig, ax = plt.subplots(figsize=(10, 6))
ax.plot(epochs_to_test, convergence_history, 'b-o', linewidth=2, markersize=8, label='PSO')
ax.set_xlabel('Nombre d\'epochs', fontsize=12)
ax.set_ylabel('Meilleur fitness', fontsize=12)
ax.set_title('Convergence PSO - Rastrigin', fontsize=14, fontweight='bold')
ax.set_yscale('log')  # Echelle logarithmique pour voir les details
ax.grid(True, alpha=0.3)
ax.legend(fontsize=10)
plt.tight_layout()
plt.show()

print(f"\\nConvergence:")
print(f"  10 epochs: {convergence_history[0]:.6f}")
print(f"  200 epochs: {convergence_history[-1]:.6f}")
print(f"  Amelioration: {convergence_history[0] / convergence_history[-1]:.1f}x")

\nConvergence:
  10 epochs: 91.998566
  200 epochs: 72.917356
  Amelioration: 1.3x

Interpretation : Convergence PSO

Sortie obtenue : La courbe de convergence montre l’evolution de la meilleure solution trouvee par PSO au fil des itérations.

Phase itérations Comportement
Exploration 0-30 Amelioration rapide (decomposition de l’espace)
Transition 30-60 Ralentissement (convergence vers l’optimum)
Exploitation 60-100 Affinage (convergence finale)

Points cles : 1. Exploration initiale : Les premières itérations reduisent drastiquement la fitness 2. Plateaux : Les paliers indiquent des optima locaux temporaires 3. Echelle log : Necessaire pour voir les details de convergence 4. Amelioration factorielle : Le ratio montre l’efficacite globale

Note technique : La classe TrackedPSO etend PSO.OriginalPSO en capturant l’historique. Cette implementation utilise des méthodes internes de MEALPy (before_solve, evolve, check_termination) qui pourraient changer dans les versions futures. Pour un usage en production, utiliser plutot l’API standard ou sauvegarder les résultats intermediaires manuellement.

Exercice : Ordonnancement d’inertie pour PSO

Le paramètre d’inertie w contrôle l’equilibre exploration/exploitation dans PSO. Implementez un decay lineaire : l’inertie commence a w_start=0.9 (forte exploration) et decroit lineairement jusqu’a w_end=0.4 (forte exploitation) au fil des epochs.

Modifiez la boucle de convergence ci-dessus pour utiliser cette stratégie et comparez les résultats avec l’inertie fixe w=0.9.

Indices : - Bouclez sur les epochs manuellement : créez un PSO avec epoch=1 et appelez .solve() successivement - A chaque epoch t : w_t = w_start - (w_start - w_end) * t / n_epochs - MEALPy ne permet pas de changer w en cours d’exécution -> utilisez l’API bas niveau ou simulez avec des appels successifs a PSO avec différents w - Alternative plus simple : lancez PSO avec 5 valeurs de w différentes (0.4, 0.6, 0.7, 0.8, 0.9) et comparez les fitness obtenus

# TODO etudiant : comparer differentes valeurs d'inertie w pour PSO
w_values = [0.4, 0.6, 0.7, 0.8, 0.9]  # TODO etudiant : tester d'autres valeurs
w_results = []

for w in w_values:
    # TODO etudiant : creer un modele PSO avec cette valeur de w
    # model = PSO.OriginalPSO(epoch=100, pop_size=30, w=w, c1=2.0, c2=2.0)
    # result = model.solve(problem_rastrigin)
    # w_results.append({'w': w, 'fitness': result.target.fitness})
    pass  # TODO etudiant : implementer

# TODO etudiant : afficher les resultats et determiner la meilleure valeur de w
# for r in w_results:
#     print(f"w={r['w']}: fitness={r['fitness']:.6f}")

print("Exercice a completer : impact de l'inertie sur PSO")
Exercice a completer : impact de l'inertie sur PSO

5. Swarm-based - Artificial Bee Colony (ABC) (~20 min)

Principe de l’ABC

L’Artificial Bee Colony est inspire du comportement de butinage des abeilles. La colonie est divisee en trois types d’abeilles :

Type rôle Comportement
Ouvrieres (Employed) Exploiter les sources connues Danse autour de la nourriture
Observatrices (Onlooker) Choisir une source sélection probabiliste par qualite
Eclaireuses (Scout) Decouvrir nouvelles sources Recherche aleatoire

Algorithme

  1. Initialisation : Distribuer les abeilles ouvrieres aleatoirement
  2. Phase employed : Chaque ouvriere exploite sa source, en cherche une voisine
  3. Phase onlooker : Les observatrices choisissent une source (probabilite = qualite)
  4. Phase scout : Si une source est epuisee, son abeille devient eclaireuse
  5. Memorisation : Garder la meilleure source trouvee

Avantages

  • Bon equilibre exploration/exploitation
  • Peu de paramètres a regler
  • Efficace sur les problemes multimodaux
# ABC sur Rosenbrock (vallee etroite)

# Parametres du probleme
dim = 10

# Definir le probleme (MEALPy 3.0.2 API)
bounds_rosenbrock = [FloatVar(lb=-5, ub=10) for _ in range(dim)]
problem_rosenbrock = Problem(
    bounds=bounds_rosenbrock,
    minmax="min",
    obj_func=rosenbrock_function
)

# ABC avec parametres standards
model = ABC.OriginalABC(
    epoch=200,         # Nombre de cycles
    pop_size=50,       # Nombre de sources de nourriture (colonie)
    n_limits=50        # Limite avant qu'une source soit abandonnee
)

# Resoudre
print("ABC sur Rosenbrock (dim=10)...")
start_time = time.perf_counter()
result_abc = model.solve(problem_rosenbrock)
elapsed_abc = (time.perf_counter() - start_time) * 1000

print(f"\nResultat ABC:")
print(f"  Solution: {np.array(result_abc.solution).round(4)}")
print(f"  Objectif: {result_abc.target.fitness:.6f}")
print(f"  Temps: {elapsed_abc:.2f} ms")
print(f"  Optimal attendu: [1, ..., 1], f=0")
ABC sur Rosenbrock (dim=10)...

Resultat ABC:
  Solution: [0.6378 0.4194 0.1687 0.0373 0.0231 0.0231 0.0016 0.0046 0.0262 0.0118]
  Objectif: 7.140853
  Temps: 1679.74 ms
  Optimal attendu: [1, ..., 1], f=0

Interpretation : ABC sur Rosenbrock

Sortie obtenue : ABC reste loin de l’optimum [1, …, 1] (f=0) : le vecteur obtenu est proche de [0, …, 0], avec un objectif ~7,60.

Aspect Observation
Solution Vecteur proche de [0, …, 0], objectif ~7,60 (loin de l’optimum [1, …, 1], f=0)
Convergence Plus lente que PSO mais plus stable
Exploration Les eclaireurs permettent d’eviter les optima locaux

Points cles : 1. ABC peine sur les problemes avec vallee etroite comme Rosenbrock (objectif ~7,60 sur ce run, moyenne 3,47 au §8 multi-seed) 2. La phase scout (recherche aleatoire) est cruciale pour l’exploration 3. Le paramètre n_limits contrôle l’equilibre : trop petit = exploration excessive, trop grand = exploitation excessive 4. ABC est moins sensible aux paramètres que PSO

6. Physics-based - Simulated Annealing (SA) (~15 min)

Lien avec Search-4

Nous avons déjà vu le Simulated Annealing dans le notebook Search-04-LocalSearch. MEALPy fournit une implementation alternative qui suit la même API.

Rappel du principe

SA s’inspire du processus metallurgique de recuit : 1. Chauffer le materiau a haute temperature (desordre) 2. Refroidir lentement (organisation progressive) 3. Obtenir une structure cristalline optimale

Critere d’acceptation

\[ P(accepter) = \begin{cases} 1 & \text{si } \Delta E \leq 0 \ e^{-\Delta E / T} & \text{si } \Delta E > 0 \end{cases} \]

Ou \(\Delta E = f(x_{new}) - f(x_{current})\) et \(T\) est la temperature qui diminue.

# SA (MEALPy) sur Ackley

# Parametres du probleme
dim = 10

# Definir le probleme (MEALPy 3.0.2 API)
bounds_ackley = [FloatVar(lb=-5, ub=5) for _ in range(dim)]
problem_ackley = Problem(
    bounds=bounds_ackley,
    minmax="min",
    obj_func=ackley_function
)

# SA avec MEALPy
model = SA.OriginalSA(
    epoch=500,            # Nombre d'iterations
    pop_size=50,          # Nombre de solutions (MEALPy utilise une population)
    temp_init=100,        # Temperature initiale
    step_size=0.1         # Amplitude du voisinage
)

# Resoudre
print("SA (MEALPy) sur Ackley (dim=10)...")
start_time = time.perf_counter()
result_sa = model.solve(problem_ackley)
elapsed_sa = (time.perf_counter() - start_time) * 1000

print(f"\nResultat SA:")
print(f"  Solution: {np.array(result_sa.solution).round(4)}")
print(f"  Objectif: {result_sa.target.fitness:.6f}")
print(f"  Temps: {elapsed_sa:.2f} ms")
print(f"  Optimal attendu: [0, ..., 0], f=0")
SA (MEALPy) sur Ackley (dim=10)...

Resultat SA:
  Solution: [-1.9579 -0.8849 -1.0217  1.06   -0.1426 -1.0855 -0.0574  2.7776  5.045
 -0.8602]
  Objectif: 7.249536
  Temps: 336.48 ms
  Optimal attendu: [0, ..., 0], f=0

Interpretation : SA sur Ackley

Sortie obtenue : SA trouve une solution acceptable sur Ackley.

Aspect Observation
Convergence Lente mais stable
Qualite Solution satisfaisante mais pas toujours optimale
Temperature contrôle l’equilibre exploration/exploitation

Points cles : 1. L’implementation MEALPy de SA utilise une population (contrairement a SA classique) 2. SA est moins efficace que PSO ou ABC sur les problemes de haute dimension 3. SA reste utile pour les problemes ou l’evaluation est très couteuse (peu d’evaluations) 4. Le paramètre temp_init est critique : trop haut = exploration excessive, trop bas = blocage

7. Human-based - Brownian Optimization (BRO) (~15 min)

Principe du BRO

Le Brownian Optimization s’inspire du mouvement brownien observe dans les particules en suspension (mouvement aleatoire). Cette métaheuristique de catégorie “Human-based” simule le comportement de recherche aleatoire avec tendance a explorer.

Algorithme

  1. Initialisation : Generer une population aleatoire
  2. Mouvement brownien : Chaque solution se deplace aleatoirement
  3. Tendance centrale : Attraction vers le meilleur trouve
  4. sélection : Garder les meilleures solutions

Avantages

  • Simple a implementer
  • Efficace sur les problemes lisses et convexes
  • Peu de paramètres
# BRO sur Rastrigin (fonction multimodale : un vrai defi d'exploration)

import logging
logging.disable(logging.WARNING)   # isoler la sortie du spam INFO de MEALPy

# Parametres du probleme
dim = 10

# Definir le probleme (MEALPy 3.0.2 API)
bounds_rastrigin_bro = [FloatVar(lb=-5.12, ub=5.12) for _ in range(dim)]
problem_rastrigin_bro = Problem(
    bounds=bounds_rastrigin_bro,
    minmax="min",
    obj_func=rastrigin_function
)

# BRO
model = BRO.OriginalBRO(
    epoch=100,
    pop_size=50
)

# Resoudre
print("BRO sur Rastrigin (dim=10)...")
start_time = time.perf_counter()
result_bro = model.solve(problem_rastrigin_bro, seed=42)   # seed fixe : reproductible
elapsed_bro = (time.perf_counter() - start_time) * 1000

print(f"\nResultat BRO:")
print(f"  Solution: {np.array(result_bro.solution).round(6)}")
print(f"  Objectif: {result_bro.target.fitness:.8f}")
print(f"  Temps: {elapsed_bro:.2f} ms")
print(f"  Optimal attendu: [0, ..., 0], f=0")

logging.disable(logging.NOTSET)   # re-activer le logging pour les cellules suivantes
BRO sur Rastrigin (dim=10)...

Resultat BRO:
  Solution: [2.021049 2.021049 2.021049 2.021049 2.021049 2.021049 2.021049 2.021049
 2.021049 2.021049]
  Objectif: 41.71963560
  Temps: 332.73 ms
  Optimal attendu: [0, ..., 0], f=0

Interpretation : BRO sur Rastrigin

Sortie obtenue : sur Rastrigin (dim=10, epoch=100, pop_size=50, seed=42), BRO converge vers une fitness de ~41,7 — un minimum local (toutes les composantes ≈2,02), loin de l’optimum f=0.

Aspect Observation (sortie réelle)
Qualité ~41,7 sur Rastrigin (ce run), loin de 0
Problème Rastrigin est multimodale : des dizaines de minima locaux, un vrai défi d’exploration (l’exemple convexe Sphere, trop facile, a été remplacé par ce banc)
Robustesse Un seul run peut être trompeur : le §8 multi-seed montre que la moyenne de BRO y est 12,9 (±14,7)

À noter. Donner à BRO la surface multimodale que son « mouvement brownien » est censé explorer n’améliore pas de façon fiable son score : ce run (seed=42) atteint 41,7 — pire que la moyenne du §8 —, d’où le multi-seed. Sur Rastrigin au §8, BRO (12,9) bat le tirage aléatoire (74,8) et le hill-climber (76,7) à budget égal, mais reste loin de PSO (9,15) / ABC (1,61). Leçon : une métaheuristique élégante ne surpasse pas automatiquement les méthodes simples — mesurer la fitness moyenne sur plusieurs graines avant de conclure.

Points clés : 1. BRO sur Rastrigin : ~41,7 sur ce run (seed=42), un minimum local (x≈2,02 partout), loin de l’optimum. 2. Le mouvement brownien fournit une exploration, mais sans exploitation efficace du multimodale. 3. Au §8 (multi-seed), BRO (12,9) bat le tirage aléatoire (74,8) et le hill-climber (76,7) sur Rastrigin — mais un run isolé (41,7) est trompeur. 4. Ne pas présupposer qu’une métaheuristique « facile » réussit sur un problème « adapté » : toujours mesurer sur plusieurs graines.

Exercice : Comparer deux algorithmes supplementaires (GWO vs WOA)

MEALPy offre plus de 200 algorithmes. Avant le benchmark comparatif, testez deux algorithmes que nous n’avons pas encore etudies : GWO (Grey Wolf Optimizer) et WOA (Whale Optimization Algorithm).

Enonce : lancez GWO et WOA sur la fonction Rastrigin (dim=10) avec les mêmes paramètres (epoch=100, pop_size=30) et comparez les fitness obtenus avec PSO.

Consignes : 1. Importez GWO et WOA depuis MEALPy (déjà importes en haut du notebook) 2. créez les modèles et resolvez le même problème problem_rastrigin 3. Comparez les fitness : lequel est le plus performant sur Rastrigin ? 4. Mesurez le temps d’exécution et calculez le ratio performance/temps

Indice : GWO.OriginalGWO(epoch=100, pop_size=30) et WOA.OriginalWOA(epoch=100, pop_size=30) suivent la même API que PSO.

# Exercice : Comparer GWO et WOA sur Rastrigin

# TODO etudiant : lancez GWO et WOA sur problem_rastrigin
# Etape 1 : creez GWO.OriginalGWO(epoch=100, pop_size=30)
# Etape 2 : creez WOA.OriginalWOA(epoch=100, pop_size=30)
# Etape 3 : resolvez et comparez les fitness avec PSO
# Etape 4 : calculez le ratio fitness/temps pour chaque algorithme

# Indice : result.target.fitness donne la fitness, time.perf_counter() pour le temps
result = None  # TODO etudiant : remplacer par vos resultats comparatifs
print("Exercice a completer : comparaison GWO vs WOA vs PSO")
Exercice a completer : comparaison GWO vs WOA vs PSO

8. Benchmark Comparatif (~15 min)

Comparons maintenant six approches sur les quatre fonctions de benchmark : les quatre metaheuristiques (PSO, ABC, SA, BRO) et deux baselines triviales — un tirage aleatoire (RandomSearch) et un hill-climber a pas continu — toutes a budget d’evaluations egal (NFE). L’ancrage par baseline permet de distinguer « l’algorithme est bon » de « le probleme est facile » (No-Free-Lunch rendu mesurable).

# Baselines triviales : ancrer le benchmarking des metaheuristiques

from types import SimpleNamespace


class RandomSearch:
    """Baseline A : tirage aleatoire uniforme a budget egal (NFE fixe).

    Evalue ``budget`` points uniformes dans les bornes et garde le meilleur.
    C'est la reference ``vide'' : une metaheuristique ne vaut que si elle le bat
    a budget d'evaluations egal (No-Free-Lunch rendu mesurable).
    """
    def __init__(self, budget: int = 3000):
        self.budget = int(budget)
    def solve(self, problem, seed=None):
        rng = np.random.default_rng(seed)
        lb, ub = np.array(problem.lb, dtype=float), np.array(problem.ub, dtype=float)
        best, best_fitness = None, float('inf')
        for _ in range(self.budget):
            candidate = rng.uniform(lb, ub)
            fitness = float(problem.obj_func(candidate))
            if fitness < best_fitness:
                best_fitness, best = fitness, candidate
        return SimpleNamespace(solution=best, target=SimpleNamespace(fitness=best_fitness))


class HillClimber:
    """Baseline B : hill-climber stochastique a pas continu.

    Demarre d'un point aleatoire, propose a chaque pas un voisin en ajoutant un
    bruit gaussien (pas continu), et s'y deplace s'il est meilleur. Montre bien
    que la descente locale est competitive sur les fonctions unimodales mais peut
    rester piegee dans un optimum local sur les multimodales.
    """
    def __init__(self, budget: int = 3000, step_size: float = 0.5):
        self.budget = int(budget)
        self.step_size = float(step_size)
    def solve(self, problem, seed=None):
        rng = np.random.default_rng(seed)
        lb, ub = np.array(problem.lb, dtype=float), np.array(problem.ub, dtype=float)
        x = rng.uniform(lb, ub)
        best_fitness = float(problem.obj_func(x))
        for _ in range(self.budget):
            neighbor = np.clip(x + self.step_size * rng.standard_normal(len(lb)), lb, ub)
            fitness = float(problem.obj_func(neighbor))
            if fitness < best_fitness:
                best_fitness, x = fitness, neighbor
        return SimpleNamespace(solution=x, target=SimpleNamespace(fitness=best_fitness))


print('Baselines definies : RandomSearch (tirage aleatoire) et HillClimber (pas continu).')
Baselines definies : RandomSearch (tirage aleatoire) et HillClimber (pas continu).
import logging
logging.disable(logging.WARNING)

# Benchmark comparatif multi-seed : 6 algorithmes x 4 fonctions x 5 graines

# Budget d'evaluations (NFE) commun : epoch x pop_size = 100 x 30 = 3000.
# Les deux baselines (RandomSearch, HillClimber) sont ancrees sur ce meme NFE
# pour que la comparaison soit « a budget egal ».

algorithms = {
    'PSO': PSO.OriginalPSO(epoch=100, pop_size=30),
    'ABC': ABC.OriginalABC(epoch=100, pop_size=30),
    'SA': SA.OriginalSA(epoch=100, pop_size=30, temp_init=100),
    'BRO': BRO.OriginalBRO(epoch=100, pop_size=30),
    'HillClimber': HillClimber(budget=3000, step_size=0.5),
    'RandomSearch': RandomSearch(budget=3000)
}

functions = {
    'Sphere': (sphere_function, [-10]*10, [10]*10, [0]*10),
    'Rastrigin': (rastrigin_function, [-5.12]*10, [5.12]*10, [0]*10),
    'Rosenbrock': (rosenbrock_function, [-5]*10, [10]*10, [1]*10),
    'Ackley': (ackley_function, [-5]*10, [5]*10, [0]*10)
}

seeds = [42, 7, 99, 123, 2024]

results = []

print("Benchmark multi-seed : 6 algorithmes x 4 fonctions x {} graines".format(len(seeds)))
print("Budget d'evaluations : 3000 (= epoch 100 x pop_size 30) pour tous.")
print("=" * 84)
print("{:<14}{:<12}{:<12}{:<12}{:<12}{:<12}".format('Algorithme', 'Fonction', 'Fitness moy', 'std', 'Erreur moy', 'Temps (ms)'))
print("-" * 84)

for algo_name, algo_model in algorithms.items():
    for func_name, (func, lb, ub, optimal) in functions.items():
        bounds = [FloatVar(lb=lb[i], ub=ub[i]) for i in range(len(lb))]
        problem = Problem(bounds=bounds, minmax="min", obj_func=func)
        fits, errs, times = [], [], []
        for seed in seeds:
            start = time.perf_counter()
            result = algo_model.solve(problem, seed=seed)
            times.append((time.perf_counter() - start) * 1000)
            fits.append(result.target.fitness)
            errs.append(np.linalg.norm(np.array(result.solution) - np.array(optimal)))
        fit_mean, fit_std = float(np.mean(fits)), float(np.std(fits))
        results.append({
            'algorithm': algo_name,
            'function': func_name,
            'fitness_mean': fit_mean,
            'fitness_std': fit_std,
            'error_mean': float(np.mean(errs)),
            'time_ms': float(np.mean(times))
        })
        print("{:<14}{:<12}{:<12.4f}{:<12.4f}{:<12.4f}{:<12.1f}".format(algo_name, func_name, fit_mean, fit_std, float(np.mean(errs)), float(np.mean(times))))

print("=" * 84)

logging.disable(logging.NOTSET)   # re-activer pour les cellules suivantes
Benchmark multi-seed : 6 algorithmes x 4 fonctions x 5 graines
Budget d'evaluations : 3000 (= epoch 100 x pop_size 30) pour tous.
====================================================================================
Algorithme    Fonction    Fitness moy std         Erreur moy  Temps (ms)  
------------------------------------------------------------------------------------
PSO           Sphere      0.0000      0.0000      0.0005      157.6       
PSO           Rastrigin   9.1536      13.8782     1.8233      158.8       
PSO           Rosenbrock  5.4823      3.0538      2.3012      163.4       
PSO           Ackley      0.0001      0.0001      0.0001      172.0       
ABC           Sphere      0.0006      0.0002      0.0235      354.7       
ABC           Rastrigin   1.6050      2.0713      0.0705      408.3       
ABC           Rosenbrock  3.4668      3.3647      0.1699      376.4       
ABC           Ackley      0.0241      0.0065      0.0176      426.6       
SA            Sphere      1.7465      2.0383      0.9857      9.0         
SA            Rastrigin   12.8907     14.7260     1.9881      9.6         
SA            Rosenbrock  17.2632     4.4635      2.5058      9.3         
SA            Ackley      1.4245      1.4102      0.6572      10.0        
BRO           Sphere      0.3776      0.3702      0.5232      164.3       
BRO           Rastrigin   12.8907     14.7260     1.9881      172.0       
BRO           Rosenbrock  56.6924     44.7906     2.4841      169.0       
BRO           Ackley      0.7106      0.5456      0.2616      223.9       
HillClimber   Sphere      0.2831      0.0730      0.5275      15.4        
HillClimber   Rastrigin   76.7232     30.5690     6.8648      26.0        
HillClimber   Rosenbrock  88.8024     112.7116    3.4246      29.1        
HillClimber   Ackley      1.7484      0.3457      0.7094      33.7        
RandomSearch  Sphere      51.3552     12.6681     7.1094      33.9        
RandomSearch  Rastrigin   74.7824     10.9847     5.8175      39.3        
RandomSearch  Rosenbrock  19798.0862  9215.0537   7.4390      39.3        
RandomSearch  Ackley      5.6888      0.4159      3.6980      51.5        
====================================================================================

Visualisons la fitness moyenne (± écart-type sur 5 graines) des six approches sur les quatre fonctions de benchmark, puis leurs temps d’exécution.

# Visualisation : fitness moyenne (echelle log) avec barres +/- ecart-type

df = pd.DataFrame(results)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

algorithms = df['algorithm'].unique()
functions = df['function'].unique()
n_algos, n_funcs = len(algorithms), len(functions)

# 6 algorithmes : 4 metaheuristiques + 2 baselines (HillClimber, RandomSearch)
colors = ['#1f77b4', '#ff7f0e', '#2ca02c', '#d62728', '#9467bd', '#8c564b']
bar_width = 0.15
x_base = np.arange(n_funcs)

# Graphique 1 : fitness moyenne par fonction (log) avec +/- std
for i, algo in enumerate(algorithms):
    subset = df[df['algorithm'] == algo]
    means = [subset[subset['function'] == f]['fitness_mean'].values[0] for f in functions]
    stds = [subset[subset['function'] == f]['fitness_std'].values[0] for f in functions]
    bars = ax1.bar(x_base + i * bar_width, means, bar_width, yerr=stds,
                   label=algo, color=colors[i], alpha=0.8, error_kw={'lw': 1, 'capsize': 3})
    for bar, val in zip(bars, means):
        ax1.text(bar.get_x() + bar.get_width() / 2., bar.get_height(),
                f'{val:.2f}', ha='center', va='bottom', fontsize=7)

ax1.set_yscale('log')
ax1.set_xlabel('Fonction', fontsize=12)
ax1.set_ylabel('Fitness moyenne (log)', fontsize=12)
ax1.set_title('Fitness moyenne par fonction (\u00b1 ecart-type)', fontsize=13, fontweight='bold')
ax1.set_xticks(x_base + bar_width * (n_algos - 1) / 2)
ax1.set_xticklabels(functions)
ax1.grid(axis='y', alpha=0.3)
ax1.legend(title='Algorithme', fontsize=9)

# Graphique 2 : temps d'execution moyen
for i, algo in enumerate(algorithms):
    subset = df[df['algorithm'] == algo]
    times = [subset[subset['function'] == f]['time_ms'].values[0] for f in functions]
    bars = ax2.bar(x_base + i * bar_width, times, bar_width,
                   label=algo, color=colors[i], alpha=0.8)
    for bar, val in zip(bars, times):
        ax2.text(bar.get_x() + bar.get_width() / 2., bar.get_height(),
                f'{val:.0f}', ha='center', va='bottom', fontsize=7)

ax2.set_xlabel('Fonction', fontsize=12)
ax2.set_ylabel('Temps (ms)', fontsize=12)
ax2.set_title("Temps d'execution moyen", fontsize=13, fontweight='bold')
ax2.set_xticks(x_base + bar_width * (n_algos - 1) / 2)
ax2.set_xticklabels(functions)
ax2.grid(axis='y', alpha=0.3)
ax2.legend(title='Algorithme', fontsize=9)

plt.suptitle('Comparaison des metaheuristiques (+ 2 baselines)', fontsize=15, fontweight='bold')
plt.tight_layout()
plt.show()

Interpretation : Comparaison des algorithmes (multi-seed)

Observations (lues dans le benchmark multi-seed ci-dessus — moyenne sur 5 graines, budget 3000 évaluations) :

La lecture honnête des moyennes donne un classement net, et surtout révèle l’ancrage par baseline que le notebook cherchait : sur les fonctions lisses, un simple hill-climber peut battre des métaheuristiques, tandis que le tirage aléatoire reste le plancher.

Algorithme Sphere Rastrigin Rosenbrock Ackley Meilleur sur
PSO 0,0000 9,15 5,48 0,0001 Sphere, Ackley
ABC 0,0006 1,61 3,47 0,024 Rastrigin, Rosenbrock
SA 1,75 12,89 17,26 1,42 (aucune en tête)
BRO 0,38 12,89 56,69 0,71 (aucune en tête)
HillClimber (baseline) 0,28 76,72 88,80 1,75 Sphere
RandomSearch (baseline) 51,36 74,78 19 798 5,69 (plancher)

La ligne No-Free-Lunch (métaheuristique battue par une baseline) : sur Sphere (convexe, triviale), le hill-climber (0,28) bat BRO (0,38) et SA (1,75) — deux métaheuristiques « intelligentes » sont dépassées par une simple descente locale. C’est exactement ce que l’ancrage par baseline rend visible : sans lui, « SA est faible » restait une opinion ; avec lui, on voit que sur un problème trivial une métaheuristique complexe gaspille son budget de 3000 évaluations.

RandomSearch = plancher : il est le plus mauvais sur les quatre fonctions (de 5,69 sur Ackley à 19 798 sur Rosenbrock). Aucune métaheuristique n’est battue par le tirage aléatoire ici — contrairement à ce qu’un run isolé suggérait (voir la note honnêteté ci-dessous).

Le vrai No-Free-Lunch est entre les deux baselines : le hill-climber écrase RandomSearch sur les fonctions unimodales (Sphere 0,28 vs 51,36 ; Rosenbrock 88,80 vs 19 798), mais perd son avantage sur Rastrigin multimodale (76,72 vs 74,78, à bruit près) : la descente locale, piégée par les dizaines d’optima locaux, ne fait pas mieux que le pur hasard. La « bonne » heuristique dépend donc du paysage — le message No-Free-Lunch.

Surprise mesurée — SA ≡ BRO sur Rastrigin. SA (12,89) et BRO (12,89) ont des moyennes identiques sur Rastrigin (même écart-type 14,7). Ce n’est pas un artefact : ce sont deux recherches stochastiques qui, avec les mêmes graines, se font piéger aux mêmes optima locaux de la fonction la plus multimodale. Sur Sphere/Rosenbrock leurs trajectoires divergent. Leçon : à budget égal, deux algorithmes « différents » peuvent coïncider sur une instance — d’où l’intérêt de tester plusieurs fonctions.

Classement des métaheuristiques : 1. ABC : meilleur sur Rastrigin (1,61) et Rosenbrock (3,47) ; quasi-optimal sur Sphere/Ackley. 2. PSO : meilleur sur Sphere (0,0000) et Ackley (0,0001), excellent partout. 3. SA et BRO : les plus faibles — SA est même battu par le hill-climber sur Sphere. 4. SA est de loin le plus rapide (~9-10 ms contre ~150-400 ms) : il n’explore pas une population complète à chaque époque, au prix d’une qualité souvent inférieure.

Note honnêteté (correction d’un run isolé) : le benchmark naïf (exécution unique) suggérait que SA était battue par le tirage aléatoire sur Sphere/Ackley. Le multi-seed montre au contraire que SA bat RandomSearch partout — c’est contre le hill-climber qu’il perd (Sphere). C’est précisément la leçon ici : un seul run d’une métaheuristique stochastique est trompeur ; la moyenne sur ≥5 graines est indispensable (d’où l’exercice du §9).

Exercice : Robustesse multi-seed

Les résultats d’une métaheuristique varient d’une exécution a l’autre (stochasticite). Implementez une evaluation multi-seed : lancez PSO sur Rastrigin 5 fois avec des seeds différentes, et calculez la moyenne et l’ecart-type du fitness final.

Indices : - Fixez le seed numpy avant chaque exécution : np.random.seed(seed_val) - Collectez les fitness dans une liste - Utilisez np.mean() et np.std() pour les statistiques - Un ecart-type faible = algorithme robuste, un ecart-type fort = results dependants du seed

# TODO etudiant : evaluation multi-seed de PSO sur Rastrigin
seeds = [0, 42, 123, 456, 789]
multi_seed_fitness = []

for seed_val in seeds:
    # TODO etudiant : fixer le seed et lancer PSO
    # np.random.seed(seed_val)
    # model = PSO.OriginalPSO(epoch=100, pop_size=30, w=0.9, c1=2.0, c2=2.0)
    # result = model.solve(problem_rastrigin)
    # multi_seed_fitness.append(result.target.fitness)
    pass  # TODO etudiant : implementer

# TODO etudiant : calculer et afficher les statistiques
# mean_fitness = np.mean(multi_seed_fitness)
# std_fitness = np.std(multi_seed_fitness)
# print(f"PSO sur Rastrigin (5 seeds): mean={mean_fitness:.4f}, std={std_fitness:.4f}")

print("Exercice a completer : robustesse multi-seed")
Exercice a completer : robustesse multi-seed

9. Analyse des paramètres (~10 min)

Les métaheuristiques ont des hyperparametres qui affectent significativement les performances. Analysons l’impact de deux paramètres PSO clés : pop_size et w (inertie).

# Analyse de l'impact de pop_size

pop_sizes = [10, 30, 50, 100]
results_pop = []

print("Impact de pop_size sur PSO (Rastrigin, dim=10)")
print("=" * 60)
print(f"{'Pop_size':<12} {'Fitness':<15} {'Temps (ms)':<12} {'Evaluations':<15}")
print("-" * 60)

for ps in pop_sizes:
    model = PSO.OriginalPSO(epoch=50, pop_size=ps, w=0.9, c1=2.0, c2=2.0)
    
    start = time.perf_counter()
    result = model.solve(problem_rastrigin)
    elapsed = (time.perf_counter() - start) * 1000
    
    evals = model.epoch * ps  # Nombre approximatif d'evaluations
    
    results_pop.append({
        'pop_size': ps,
        'fitness': result.target.fitness,
        'time_ms': elapsed,
        'evaluations': evals
    })
    
    print(f"{ps:<12} {result.target.fitness:<15.4f} {elapsed:<12.1f} {evals:<15}")

print("=" * 60)
print("\nObservation: Une population plus grande ameliore la qualite")
print("mais augmente le temps de calcul lineairement.")
Impact de pop_size sur PSO (Rastrigin, dim=10)
============================================================
Pop_size     Fitness         Temps (ms)   Evaluations    
------------------------------------------------------------
10           92.0218         64.2         500            
30           79.5983         237.2        1500           
50           76.7512         161.3        2500           
100          78.6148         294.0        5000           
============================================================

Observation: Une population plus grande ameliore la qualite
mais augmente le temps de calcul lineairement.

Visualisons l’impact de la taille de population sur la qualite de la solution et le temps de calcul.

# Visualisation de l'impact de pop_size
df_pop = pd.DataFrame(results_pop)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))

# Fitness vs pop_size
ax1.plot(df_pop['pop_size'], df_pop['fitness'], 'o-', linewidth=2, markersize=8, color='#4CAF50')
ax1.set_xlabel('Taille de population', fontsize=12)
ax1.set_ylabel('Fitness final', fontsize=12)
ax1.set_title('Impact de pop_size sur la qualite', fontsize=13, fontweight='bold')
ax1.grid(True, alpha=0.3)

# Temps vs pop_size
ax2.plot(df_pop['pop_size'], df_pop['time_ms'], 'o-', linewidth=2, markersize=8, color='#2196F3')
ax2.set_xlabel('Taille de population', fontsize=12)
ax2.set_ylabel('Temps (ms)', fontsize=12)
ax2.set_title('Impact de pop_size sur le temps', fontsize=13, fontweight='bold')
ax2.grid(True, alpha=0.3)

plt.suptitle('Analyse du parametre pop_size (PSO)', fontsize=14, fontweight='bold')
plt.tight_layout()
plt.show()

print("\nAnalyse:")
print(f"  Amelioration fitness: {df_pop['fitness'].iloc[0] / df_pop['fitness'].iloc[-1]:.2f}x")
print(f"  Augmentation temps: {df_pop['time_ms'].iloc[-1] / df_pop['time_ms'].iloc[0]:.2f}x")
print(f"  Ratio gain/coût: {(df_pop['fitness'].iloc[0] / df_pop['fitness'].iloc[-1]) / (df_pop['time_ms'].iloc[-1] / df_pop['time_ms'].iloc[0]):.2f}")


Analyse:
  Amelioration fitness: 1.17x
  Augmentation temps: 4.58x
  Ratio gain/coût: 0.26

Interpretation : Impact de la taille de population

Sortie obtenue : La taille de population affecte significativement la qualite de la solution et le temps de calcul.

Metrique Observation Interpretation
Fitness Ameliore avec pop_size croissant Plus de particules = meilleure exploration
Temps Croissance lineaire Chaque particule additionnelle coute le même temps
Ratio gain/coût Diminue avec pop_size Loi des rendements decroissants

Points cles : 1. Effet positif : Une population plus grande ameliore la qualite de la solution 2. Loi des rendements decroissants : Le gain marginal diminue avec pop_size 3. Cout lineaire : Le temps de calcul augmente proportionnellement a pop_size 4. Choix optimal : pop_size=30-50 est souvent un bon compromis

Note pratique : Pour un problème de dimension 10, pop_size=30 suffit généralement. Augmenter a 100+ ne justifie le cout que pour des problemes très difficiles.

10. Exemple guide

Exemple guide 1 : Comparer PSO et ABC sur un problème reel

Enonce : Soit le problème d’optimisation suivant (maximisation du profit d’une entreprise):

\[ \max_{x, y} \quad 50x + 80y - x^2 - 2y^2 - xy \\ \quad \text{s.c.} \quad x \in [0, 20], y \in [0, 20] \]

  1. Convertir en problème de minimisation pour MEALPy
  2. Resoudre avec PSO et ABC (epoch=100, pop_size=30)
  3. Comparer les solutions obtenues

Indice : Pour maximiser \(f(x, y)\), minimiser \(-f(x, y)\).

# Exercice 1 : Probleme d'optimisation d'entreprise

def profit_function(solution):
    """Fonction de profit a maximiser: 50*x + 80*y - x^2 - 2*y^2 - x*y.
    
    Pour MEALPy, on retourne l'oppose (minimisation).
    """
    x, y = solution
    profit = 50*x + 80*y - x**2 - 2*y**2 - x*y
    return -profit  # Minimiser l'oppose = maximiser

# A COMPLETER
# 1. Definir le probleme avec lb=[0, 0], ub=[20, 20]
bounds_profit = [FloatVar(lb=0, ub=20), FloatVar(lb=0, ub=20)]
problem_profit = Problem(bounds=bounds_profit, 
                         minmax="min", 
                         obj_func=profit_function)

# 2. Resoudre avec PSO et ABC
models_ex1 = {
    "PSO": PSO.OriginalPSO(epoch=100, pop_size=30),
    "ABC": ABC.OriginalABC(epoch=100, pop_size=30),
}

for name, model in models_ex1.items():
    result = model.solve(problem_profit)
    x, y = result.solution
    print(f"{name} : x={x:.4f}, y={y:.4f}, profit={-result.target.fitness:.4f}")

# 3. Comparer les resultats
PSO : x=17.1429, y=15.7143, profit=1057.1429
ABC : x=17.1429, y=15.7143, profit=1057.1429

Exemple : Impact de la dimension sur PSO

Objectif : Etudier comment la dimension de l’espace de recherche affecte les performances de PSO sur la fonction Sphere.

méthode : On lance PSO sur la fonction Sphere pour dim = 2, 5, 10, 20 et on mesure le fitness final et le temps de calcul.

Question : Comment le temps de calcul evolue-t-il avec la dimension ? Est-ce lineaire, quadratique, exponentiel ?

résultat attendu : Le temps croit de maniere quasi-lineaire avec la dimension, tandis que le fitness se degrade (augmente) en dimension elevee.

# Exemple : Impact de la dimension sur PSO

dimensions = [2, 5, 10, 20]
results_dim = []

# A COMPLETER
for dim in dimensions:
    # Definir le probleme
    # Lancer PSO avec epoch=50, pop_size=30
    # Stocker resultats
    bounds = [FloatVar(lb=-10, ub=10) for _ in range(dim)]
    problem = Problem(bounds=bounds, minmax="min", obj_func=sphere_function)
    model = PSO.OriginalPSO(epoch=50, pop_size=30)

    start = time.perf_counter()
    result = model.solve(problem)
    elapsed = (time.perf_counter() - start) * 1000

    results_dim.append({'dim': dim, 'fitness': result.target.fitness, 'time_ms': elapsed})
    print(f"dim={dim:<3} fitness={result.target.fitness:.6f} temps={elapsed:.2f} ms")

df_dim = pd.DataFrame(results_dim)

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
ax1.plot(df_dim['dim'], df_dim['fitness'], 'o-', color='#4CAF50')
ax1.set_xlabel('Dimension'); ax1.set_ylabel('Fitness (log)')
ax1.set_yscale('log'); ax1.set_title('Fitness vs dimension'); ax1.grid(True, alpha=0.3)

ax2.plot(df_dim['dim'], df_dim['time_ms'], 'o-', color='#2196F3')
ax2.set_xlabel('Dimension'); ax2.set_ylabel('Temps (ms)')
ax2.set_title('Temps vs dimension'); ax2.grid(True, alpha=0.3)
plt.tight_layout(); plt.show()

# ordre de croissance du temps
ordre = np.log(df_dim['time_ms'].iloc[-1] / df_dim['time_ms'].iloc[0]) / np.log(df_dim['dim'].iloc[-1] / df_dim['dim'].iloc[0])
print(f"\nOrdre de croissance empirique : ~O(n^{ordre:.2f})")
print("Le temps croit de maniere quasi-lineaire avec la dimension.")

# Visualiser
# plt.plot(...)
dim=2   fitness=0.000000 temps=92.10 ms
dim=5   fitness=0.000000 temps=99.52 ms
dim=10  fitness=0.028539 temps=113.38 ms
dim=20  fitness=1.710354 temps=146.79 ms


Ordre de croissance empirique : ~O(n^0.20)
Le temps croit de maniere quasi-lineaire avec la dimension.

Exemple guide 3 : Recuit simule pour le TSP

Enonce : Le problème du Voyageur de Commerce (TSP - Traveling Salesman Problem) consiste a trouver le tour le plus court visitant un ensemble de villes exactement une fois, puis en revenant au point de depart.

Implementez une resolution du TSP a l’aide du Simulated Annealing de MEALPy :

  1. Generez un ensemble de 15 villes avec des coordonnees aleatoires dans [0, 100] x [0, 100]
  2. Definissez une fonction objectif qui calcule la longueur totale d’un tour (en utilisant la distance euclidienne)
  3. Utilisez SA.OriginalSA avec au moins 300 epochs et une population de 50 pour minimiser la distance
  4. Affichez les coordonnees des villes et le tour optimal trouve sur un graphique (matplotlib)
  5. Comparez le résultat obtenu avec un tour aleatoire (ordre initial des villes)

Indice : Pour le TSP, chaque solution est une permutation des indices de villes. Vous pouvez representer chaque variable comme un entier dans [0, n_villes-1] et post-traiter la solution pour obtenir une permutation valide (eliminer les doublons et reordonner).

Bonus : Testez aussi avec WOA.OriginalWOA (Whale Optimization Algorithm) sur le même problème et comparez les résultats.

# Exercice 3 : Recuit simule pour le TSP
import numpy as np
import matplotlib.pyplot as plt
from mealpy import SA, Problem
from mealpy.utils.space import FloatVar

np.random.seed(42)
n_villes = 15

# Exercice: Generer les coordonnees des villes aleatoirement
# villes = ...

# Exercice: Definir la fonction objectif (distance totale du tour)
# def tsp_distance(solution):
#     # Reordonner les villes selon la solution
#     # Calculer la somme des distances entre villes consecutives
#     # Inclure le retour a la ville de depart
#     pass

# Exercice: Definir le probleme MEALPy
# bounds = [FloatVar(lb=0, ub=n_villes-1) for _ in range(n_villes)]
# problem_tsp = Problem(bounds=bounds, minmax="min", obj_func=tsp_distance)

# Exercice: Resoudre avec SA
# model = SA.OriginalSA(epoch=300, pop_size=50, temp_init=100)
# result = model.solve(problem_tsp)

# Exercice: Visualiser le tour optimal
# fig, ax = plt.subplots(figsize=(8, 8))
# # Afficher les villes
# # Afficher le tour
# # Comparer avec un tour aleatoire
# plt.show()

print("Exercice 3 : Implementez le TSP avec Simulated Annealing")
Exercice 3 : Implementez le TSP avec Simulated Annealing

11. Resume

Concepts cles

Concept Definition
métaheuristique Algorithme d’optimisation stochastique sans derivees
Exploration Decouverte de nouvelles regions de l’espace
Exploitation Affinage des solutions prometteuses
No Free Lunch Aucun algorithme n’est optimal pour tous les problemes

Classification des métaheuristiques

catégorie Inspiration Algorithmes Meilleur sur
Evolution-based théorie de l’evolution GA, DE Problemes généraux
Swarm-based Essaims naturels PSO, ABC, GWO Multimodal, dynamique
Physics-based Loi physique SA, GRAVITY problème spécifiques
Human-based Comportement humain BRO, TS Problemes structures

Tableau comparatif

Algorithme Complexite paramètres Robustesse Vitesse
PSO O(nepochp) w, c1, c2 +++ ++
ABC O(nepochp) n_limits ++++ +
SA O(epoch*n) T0, alpha ++ +
BRO O(nepochp) Peu ++ +++

Quand utiliser quelle métaheuristique ?

Situation Algorithme recommande
problème general, multimodal PSO
Vallees etroites, contraintes ABC
Evaluation très couteuse SA (peu d’itérations)
problème convexe simple BRO
problème avec contraintes complexes DE, GA

Pour aller plus loin

  • Notebook suivant : App-1-NQueens - Application des métaheuristiques au N-Reines
  • MEALPy documentation : https://mealpy.readthedocs.io/ - Liste complete des 200+ algorithmes
  • Reference : Yang, X.-S. (2010). Nature-Inspired Metaheuristic Algorithms. Luniver Press

Navigation : << Recherche locale | Index | App-1-NQueens >>

Conclusion

Ce notebook a presente les métaheuristiques via la bibliotheque MEALPy, en comparant quatre algorithmes sur des fonctions de benchmark classiques.

Ce que nous avons appris

Algorithme Inspiration Sphere Rastrigin Rosenbrock Vitesse
PSO Essaim 0,0000 9,15 5,48 moyen
ABC Ruche 0,0006 1,61 3,47 lent
SA Physique 1,75 12,89 17,26 rapide
BRO Humain 0,38 12,89 56,69 moyen
HillClimber (baseline) — 0,28 76,72 88,80 rapide
RandomSearch (baseline) — 51,36 74,78 19 798 moyen

Lecon principale : no free lunch

Les résultats mesures confirment le theoreme No Free Lunch : aucun algorithme ne domine universellement. Sur ces benchmarks, ABC domine Rastrigin (1,61) et Rosenbrock (3,47) ; PSO domine Sphere (0,0000) et Ackley (0,0001). Le recuit simule (SA) est le plus rapide mais de qualite inferieure. Surtout — l’apport des baselines — un simple hill-climber bat SA et BRO sur Sphere (0,28 vs 1,75 et 0,38) : sur un probleme trivial, une metaheuristique complexe peut etre depassee par une descente locale. Et le tirage aleatoire reste le plancher. Rosenbrock (vallee etroite) et Rastrigin (multimodal) restent les instances les plus difficiles, et la moyenne sur plusieurs graines est indispensable avant de conclure (un unique run trompe).

MEALPy offre une interface uniforme pour 100+ métaheuristiques, facilite les comparaisons systématiques, et permet l’analyse de sensibilite aux paramètres.

Suite : App-13 - TSP métaheuristiques | Retour au sommaire

References academiques

  • Kennedy, J. & Eberhart, R. (1995). Particle Swarm Optimization. Proc. IEEE International Conference on Neural Networks IV:1942-1948.
  • Karaboga, D. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization. Technical Report-TR06, Erciyes University, Turkey.
  • Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science 220(4598):671-680.
  • Yang, X.-S. (2010). Nature-Inspired Metaheuristic Algorithms (2nd ed.). Luniver Press.
Retour au sommet