Exercices — Les métaheuristiques (recuit simulé)

Pr. EL HADIQ Zouhair

5 exercices Python progressifs sur la recherche locale et le recuit simulé. Une solution modèle et un commentaire sont donnés pour chaque exercice.

Conseil. Cherchez d'abord la solution seul(e), puis comparez. Pour les fonctions aléatoires, fixez une graine avec random.seed(0) afin de pouvoir reproduire vos résultats.

Écrire longueur(tour, D) qui renvoie la longueur du circuit fermé visitant les villes dans l'ordre de tour, où D[i][j] est la distance de la ville i à la ville j. Ne pas oublier l'arête de retour.

D = [[0,2,9,10],[2,0,6,4],[9,6,0,3],[10,4,3,0]]
longueur([0,1,2,3], D) → 21
longueur([0,1,3,2], D) → 18

Solution :

def longueur(tour, D):
    n = len(tour)
    s = 0
    for i in range(n):
        s += D[tour[i]][tour[(i + 1) % n]]
    return s

Clé : le modulo (i+1) % n referme le circuit (la dernière ville revient à la première). Coût O(n).

Écrire proba_acceptation(dE, T) qui renvoie la probabilité d'accepter un voisin : 1 si dE ≤ 0, sinon e^−dE/T.

proba_acceptation(0, 10)  → 1.0
proba_acceptation(10, 10) → 0.3679...
proba_acceptation(20, 10) → 0.1353...

Solution :

import math

def proba_acceptation(dE, T):
    if dE <= 0:
        return 1.0
    return math.exp(-dE / T)

À observer : plus dE est grand ou plus T est petit, plus la probabilité d'accepter une dégradation est faible.

Pour rendre la décision reproductible, le tirage u ∈ [0, 1[ est passé en argument. Écrire accepte(dE, T, u) renvoyant un booléen : accepter si dE ≤ 0, ou si u < e−dE/T.

accepte(-3, 10, 0.9) → True
accepte(50, 1, 0.5)  → False
accepte(5, 100, 0.5) → True

Solution :

import math

def accepte(dE, T, u):
    return dE <= 0 or u < math.exp(-dE / T)

Clé : grâce au court-circuit du or, l'exponentielle n'est même pas évaluée quand dE ≤ 0.

On minimise une fonction f sur les entiers ; le voisinage de x est {x−1, x+1}. Écrire descente(f, x0) qui se déplace tant qu'un voisin est strictement meilleur, puis renvoie l'entier où elle se bloque.

descente(lambda x:(x-3)**2, 0)  → 3
descente(lambda x:(x+5)**2, 0)  → -5

Solution :

def descente(f, x0):
    x = x0
    while True:
        m = min([x - 1, x + 1], key=f)
        if f(m) < f(x):
            x = m
        else:
            return x

Limite : la descente renvoie un optimum local. Sur une fonction à plusieurs creux, elle peut manquer le minimum global : c'est précisément ce que corrige le recuit simulé.

Minimiser f sur les entiers (voisin : x + random.choice([-1, 1])). Écrire recuit_simule(f, x0, T0, alpha, n_iter) renvoyant le meilleur coût rencontré. Démarrer par random.seed(0).

recuit_simule(lambda x:(x-7)**2, 0, 10, 0.99, 2000)  → 0
recuit_simule(lambda x:(x-20)**2, 0, 50, 0.995, 5000) → 0

Solution :

import math, random

def recuit_simule(f, x0, T0, alpha, n_iter):
    random.seed(0)
    x = x0
    c = f(x)
    best, cbest = x, c
    T = T0
    for _ in range(n_iter):
        x2 = x + random.choice([-1, 1])
        c2 = f(x2)
        dE = c2 - c
        if dE <= 0 or random.random() < math.exp(-dE / T):
            x, c = x2, c2
            if c < cbest:
                best, cbest = x, c
        T = alpha * T
    return cbest

Clé : on accepte parfois une dégradation (remontée) pour s'échapper des optima locaux, et on conserve à part le meilleur coût car la solution courante peut empirer.