Algorithme génétique en Python : mesurer l’écart à un optimum connu

Pour savoir ce que vaut un algorithme génétique, comparez-le d’abord à une solution exacte sur un problème assez petit. Une courbe qui monte ne dit pas quelle qualité reste à gagner. Une exécution réussie ne dit pas non plus ce qui se passe avec une autre graine aléatoire.

Nous allons sélectionner des objets sous une contrainte de capacité, calculer les 4 096 possibilités, puis tester une heuristique génétique et une recherche aléatoire. Ce cas complète le guide des algorithmes génétiques : son sujet est l’évaluation de l’heuristique, plutôt que la résolution générale du sac à dos.

Un petit problème dont on peut connaître la réponse

Douze objets ont chacun une charge et une valeur pédagogique. On choisit chaque objet zéro ou une fois, avec une charge totale au plus égale à 26. Les chiffres sont sans unité monétaire ; ils ne décrivent aucun achat réel.

L’énumération de toutes les sélections donne un optimum de 70. L’une des solutions retenues choisit les objets 5, 8, 9 et 10, pour une charge de 8 + 9 + 5 + 4 = 26 et une valeur de 22 + 24 + 13 + 11 = 70. Il peut exister d’autres sélections ex æquo ; notre fonction conserve la première rencontrée.

Un protocole explicite pour l’heuristique

Un individu est un tuple de douze bits. Les solutions hors capacité reçoivent le score −1 ; la sélection vide, de score zéro, fait partie de la population initiale. Le meilleur individu est conservé à chaque génération. Les parents sont choisis par tournoi de trois candidats, croisés en un point, puis chaque bit peut muter avec une probabilité de 1 / 12.

Nous utilisons vingt individus et les graines 0 à 19, sans choisir seulement les meilleures exécutions. Trois générations après la population initiale représentent 80 évaluations ; vingt-cinq générations représentent 520 évaluations. Les candidats répétés sont recomptés, sans cache. La recherche aléatoire reçoit exactement le même nombre d’évaluations, dont une pour la sélection vide.

Ces choix définissent notre variante d’algorithme génétique. D’autres sélections, mutations, réparations ou tailles de population peuvent changer le résultat. La documentation DEAP sur les algorithmes évolutionnaires illustre cette diversité. Le script ci-dessous est autonome et n’utilise pas DEAP.

Résultats sur vingt graines

L’écart d’une solution de valeur v est calculé par 100 × (70 − v) / 70. La valeur moyenne seule masquerait les échecs : même avec 520 évaluations, l’algorithme génétique manque l’optimum pour cinq graines. La recherche aléatoire est proche sur ce petit problème et son pire résultat à ce budget est même meilleur.

Le budget plus élevé aide ici les deux méthodes. Ce tableau ne démontre aucune supériorité générale : nous n’avons qu’un problème fixé, vingt graines et aucun test statistique de généralisation à d’autres instances. L’égalité du nombre d’évaluations ne garantit pas non plus l’égalité des durées d’exécution.

Code et résultats CSV à télécharger

Télécharger le script, les 80 résultats CSV et les cinq tests — ZIP gratuit. Python 3.12.14 a été utilisé. Matplotlib sert à la figure ; la recherche elle-même utilise la bibliothèque standard. Installez les dépendances, lancez python genetique_optimum.py, puis python test_exemple.py.

"""Une heuristique évaluée contre les 4096 sélections d'un petit problème fixé."""
import csv, itertools, json, random
from pathlib import Path
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

OUT = Path(__file__).resolve().parent
POIDS = (3, 5, 7, 4, 8, 6, 2, 9, 5, 4, 7, 3)
VALEURS = (8, 12, 19, 9, 22, 16, 5, 24, 13, 11, 18, 7)
BUDGET = 26


def score(bits, poids=POIDS, valeurs=VALEURS, budget=BUDGET):
    charge = sum(b * w for b, w in zip(bits, poids))
    return sum(b * v for b, v in zip(bits, valeurs)) if charge <= budget else -1


def exact(poids=POIDS, valeurs=VALEURS, budget=BUDGET):
    candidats = itertools.product((0, 1), repeat=len(poids))
    return max(candidats, key=lambda b: score(b, poids, valeurs, budget))


def genetique(seed, generations, taille=20):
    rng = random.Random(seed)
    n = len(POIDS)
    population = [tuple(0 for _ in range(n))]
    population += [tuple(rng.randrange(2) for _ in range(n)) for _ in range(taille - 1)]
    historique = []
    for generation in range(generations + 1):
        notes = [score(b) for b in population]
        elite = population[max(range(taille), key=lambda i: notes[i])]
        historique.append(max(notes))
        if generation == generations:
            return elite, historique, taille * (generations + 1)
        def parent():
            indices = rng.sample(range(taille), 3)
            return population[max(indices, key=lambda i: notes[i])]
        nouvelle = [elite]  # Élitisme : le meilleur candidat est conservé.
        while len(nouvelle) < taille:
            a, b = parent(), parent()
            coupure = rng.randrange(1, n)
            enfant = a[:coupure] + b[coupure:]
            enfant = tuple(1-x if rng.random() < 1/n else x for x in enfant)
            nouvelle.append(enfant)
        population = nouvelle


def aleatoire(seed, evaluations):
    rng = random.Random(seed)
    candidats = [tuple(0 for _ in POIDS)]
    candidats += [tuple(rng.randrange(2) for _ in POIDS) for _ in range(evaluations - 1)]
    return max(candidats, key=score)


def experience():
    optimum = exact()
    valeur_optimale = score(optimum)
    lignes = []
    for generations in [3, 25]:
        for seed in range(20):
            meilleur, historique, evaluations = genetique(seed, generations)
            hasard = aleatoire(seed, evaluations)
            for methode, solution in [("genetique", meilleur), ("aleatoire", hasard)]:
                v = score(solution)
                lignes.append({"methode": methode, "generations_GA": generations,
                               "seed": seed, "evaluations": evaluations, "valeur": v,
                               "ecart_pct": 100 * (valeur_optimale - v) / valeur_optimale})
    with (OUT / "comparaisons.csv").open("w", newline="", encoding="utf-8") as f:
        w = csv.DictWriter(f, fieldnames=list(lignes[0]))
        w.writeheader()
        w.writerows(lignes)
    resume = []
    for generations in [3, 25]:
        for methode in ["genetique", "aleatoire"]:
            groupe = [r for r in lignes if r["generations_GA"] == generations and r["methode"] == methode]
            resume.append({"methode": methode, "generations_GA": generations,
                           "evaluations": groupe[0]["evaluations"],
                           "optimum_atteint": sum(r["valeur"] == valeur_optimale for r in groupe),
                           "valeur_min": min(r["valeur"] for r in groupe),
                           "valeur_max": max(r["valeur"] for r in groupe),
                           "ecart_moyen_pct": sum(r["ecart_pct"] for r in groupe) / len(groupe)})
    fig, ax = plt.subplots(figsize=(10, 5), layout="constrained")
    for i, r in enumerate(resume):
        ys = [x["ecart_pct"] for x in lignes if x["methode"] == r["methode"] and x["generations_GA"] == r["generations_GA"]]
        ax.scatter([i + (j-9.5)*.012 for j in range(20)], ys, color="#167c80", alpha=.7)
    ax.set(xticks=range(4), xticklabels=[f'{r["methode"]}\n{r["evaluations"]} évaluations' for r in resume],
           ylabel="Écart à l’optimum (%)", title="Vingt graines sur un seul problème : la variabilité compte")
    ax.axhline(0, color="#e0a13b", linestyle="--")
    fig.savefig(OUT / "figure.png", dpi=160)
    plt.close(fig)
    return {"optimum": valeur_optimale, "selection": list(optimum),
            "charge": sum(b*w for b, w in zip(optimum, POIDS)),
            "candidats_exacts": 2**len(POIDS), "graines": 20, "resume": resume}


if __name__ == "__main__":
    resultats = experience()
    (OUT / "resultats.json").write_text(json.dumps(resultats, indent=2), encoding="utf-8")
    print(json.dumps(resultats, indent=2))

Ce que les tests contrôlent

Un petit sac à dos dont la réponse se calcule à la main vérifie le témoin exact. Les autres tests contrôlent la pénalité d’infaisabilité, le respect de la capacité, l’absence de score supérieur à l’optimum, la conservation du meilleur score et la répétabilité avec une même graine. Ils ne prouvent pas que l’heuristique trouve toujours l’optimum.

Passer à un problème plus grand

Sur douze objets, l’énumération est simple ; lorsque le nombre d’objets augmente, ses 2ⁿ sélections deviennent coûteuses. Cela ne rend pas automatiquement l’algorithme génétique meilleur que toute méthode exacte : la structure du problème peut permettre programmation dynamique, solveur spécialisé ou bornes plus efficaces.

Avant de transposer cette expérience, fixez une famille d’instances, les contraintes de validité et le budget. Comparez plusieurs graines, conservez les candidats infaisables dans le décompte des essais et distinguez meilleure solution trouvée et optimum prouvé. Quand l’optimum devient inconnu, annoncez cette limite au lieu de fabriquer un pourcentage d’écart.

Pour d’autres décisions à vérifier par le code, consultez le catalogue Python gratuit ou l’assistant de choix d’algorithme.