Construire un moteur génétique générique en Go

Dans l’article précédent, nous avons vu pourquoi les algorithmes génétiques existent : face à un espace de recherche gigantesque, plutôt que de tout calculer, on génère des variantes, on évalue, on sélectionne les meilleures, on recombine, et on recommence. Le principe est simple. Il est temps de le transformer en code.

Mais nous n’allons pas écrire un solveur jetable, taillé pour un seul problème. Nous allons construire un moteur : une brique réutilisable, capable de faire évoluer n’importe quel type de génome. Chaque article suivant s’appuiera dessus sans le modifier. L’implémentation de référence est disponible sur GitHub : le lien vers le dépôt se trouve en fin d’article.

Un moteur qui ne connaît pas le problème

La tentation, quand on implémente un algorithme génétique, est de tout mélanger : la logique d’évolution et les détails du problème à résoudre. Le résultat fonctionne, mais il faut tout réécrire dès qu’on change de problème.

La bonne idée consiste à tracer une frontière nette entre deux mondes :

graph LR
    subgraph M[Le moteur, invariant]
        M1[Initialiser]
        --> M2[Évaluer]
        --> M3[Sélectionner]
        --> M4[Reproduire]
        --> M2
    end

    subgraph P[Le problème, variable]
        P1[Génome]
        P2[Fitness]
        P3[Croisement]
        P4[Mutation]
    end

    M -.s'appuie sur.-> P

    style M1 fill:transparent
    style M2 fill:transparent
    style M3 fill:transparent
    style M4 fill:transparent
    style P1 fill:transparent
    style P2 fill:transparent
    style P3 fill:transparent
    style P4 fill:transparent

D’un côté, la mécanique de l’évolution : produire une population, l’évaluer, sélectionner les meilleurs, les recombiner, recommencer. Cette boucle ne change jamais, quel que soit le problème.

De l’autre, la définition du problème : à quoi ressemble une solution, comment la noter, comment la croiser, comment la muter. Cela change à chaque usage.

C’est exactement cette séparation que les génériques de Go vont nous permettre d’exprimer proprement.

Le génome comme paramètre de type

Depuis Go 1.18, une fonction ou un type peut être paramétré par un type¹. C’est précisément ce qu’il nous faut : le moteur ne doit pas imposer la forme du génome. Une route, une chaîne binaire, un jeu de paramètres : tout doit pouvoir évoluer.

Nous notons ce type G (pour genome), et nous l’introduisons dès la brique la plus élémentaire : l’individu. Un individu, c’est un génome candidat associé au score de fitness qu’on lui a mesuré.

// Individual associe un génome candidat au score de fitness qu'on lui a mesuré.
type Individual[G any] struct {
    Genome  G
    Fitness float64
}

La contrainte any signifie « n’importe quel type ». Le moteur ne fait aucune hypothèse sur G : il se contente de transporter des génomes et de comparer leurs scores. Toute la connaissance du problème sera fournie de l’extérieur.

Décrire un problème : la Config

Voici le cœur de l’architecture. Plutôt que d’imposer au génome d’implémenter une interface, nous décrivons le problème comme un jeu de fonctions regroupées dans une configuration. Le moteur ne reçoit pas un objet intelligent : il reçoit un mode d’emploi.

type Config[G any] struct {
    NewRandom func() G        // produit un génome aléatoire (population initiale)
    Fitness   func(G) float64 // évalue un génome, plus haut = meilleur
    Crossover func(a, b G) G  // combine deux parents en un enfant
    Mutate    func(G) G       // introduit une petite variation

    PopulationSize int         // taille de la population
    MutationRate   float64     // probabilité de muter un enfant [0,1]
    Elitism        int         // nb de meilleurs conservés tels quels
    MaxGen         int         // critère d'arrêt : nombre de générations
    Selector       Selector[G] // stratégie de sélection (défaut : tournoi)
    Seed           int64       // graine aléatoire pour des runs reproductibles
}

On retrouve les quatre concepts de l’article précédent (le génome, la fitness, le croisement, la mutation), mais exprimés comme de simples fonctions. Pour résoudre un nouveau problème, il suffira de fournir ces quatre fonctions et quelques paramètres. Aucune ligne du moteur ne bouge.

Cette approche est délibérément la plus simple possible. Pas d’héritage, pas de hiérarchie de types : des fonctions que l’on branche. C’est ce qui rend le moteur à la fois lisible et trivial à réutiliser.

La boucle d’évolution

Le moteur lui-même n’est qu’une traduction directe de la boucle évolutive. On part d’une population aléatoire, on l’évalue, puis on enchaîne les générations : sélectionner, reproduire, muter, recommencer.

graph LR
    A[Population<br/>initiale]
    --> B[Évaluer<br/>la fitness]
    --> C[Sélectionner<br/>les parents]
    --> D[Croiser<br/>et muter]
    --> E[Nouvelle<br/>génération]
    --> B

    style A fill:transparent
    style B fill:transparent
    style C fill:transparent
    style D fill:transparent
    style E fill:transparent

En Go, cela donne un type Engine[G] et une méthode Run. On conserve à chaque instant le meilleur individu rencontré, et on s’arrête après un nombre fixé de générations, ou plus tôt si l’appelant le demande.

type Engine[G any] struct {
    cfg Config[G]
    rng *rand.Rand
}

func New[G any](cfg Config[G]) *Engine[G] {
    // applique les valeurs par défaut et valide la configuration
    cfg = withDefaults(cfg)
    return &Engine[G]{cfg: cfg, rng: rand.New(rand.NewSource(cfg.Seed))}
}

func (e *Engine[G]) Run(ctx context.Context) Individual[G] {
    pop := e.initPopulation()
    e.evaluate(pop)
    best := top(pop)

    for range e.cfg.MaxGen {
        select {
        case <-ctx.Done():
            return best // arrêt propre : on renvoie le meilleur trouvé jusqu'ici
        default:
        }

        pop = e.nextGeneration(pop)
        e.evaluate(pop)
        if c := top(pop); c.Fitness > best.Fitness {
            best = c
        }
    }

    return best
}

Run ne mentionne aucun détail de problème. Il orchestre des fonctions fournies par la Config : c’est ce qui le rend générique. Le context.Context permet, lui, d’interrompre proprement une recherche trop longue ; nous y revenons plus bas.

Produire une génération

Le passage d’une génération à la suivante condense toute l’idée de l’algorithme génétique. On commence par conserver intacts les meilleurs individus, c’est l’élitisme, qui garantit qu’une bonne solution n’est jamais perdue. Puis on remplit le reste de la population en sélectionnant des parents, en les croisant, et en mutant parfois l’enfant obtenu.

func (e *Engine[G]) nextGeneration(pop []Individual[G]) []Individual[G] {
    next := make([]Individual[G], 0, len(pop))
    next = append(next, elites(pop, e.cfg.Elitism)...) // on garde les meilleurs intacts

    for len(next) < e.cfg.PopulationSize {
        a := e.cfg.Selector.Select(pop, e.rng)
        b := e.cfg.Selector.Select(pop, e.rng)

        child := e.cfg.Crossover(a.Genome, b.Genome)
        if e.rng.Float64() < e.cfg.MutationRate {
            child = e.cfg.Mutate(child)
        }

        next = append(next, Individual[G]{Genome: child})
    }

    return next
}

C’est ici que se joue la différence avec le hasard pur évoquée dans l’article précédent. Chaque nouvelle génération hérite du passé : les meilleurs individus sont préservés, leurs caractéristiques se transmettent par croisement, et la mutation se contente d’explorer prudemment leurs alentours. Le système n’oublie jamais ce qui fonctionne ; il accumule.

Rendre la sélection interchangeable

Reste une question : comment choisir les parents ? Il existe plusieurs stratégies (tournoi, roulette proportionnelle à la fitness, sélection par rang) et aucune n’est universellement meilleure. Plutôt que de figer un choix dans le moteur, nous en faisons un point d’extension.

type Selector[G any] interface {
    Select(pop []Individual[G], rng *rand.Rand) Individual[G]
}

// TournamentSelector tire au hasard quelques individus et renvoie le meilleur.
type TournamentSelector[G any] struct{ Size int }

func (t TournamentSelector[G]) Select(pop []Individual[G], rng *rand.Rand) Individual[G] {
    best := pop[rng.Intn(len(pop))]
    for range t.Size - 1 {
        if c := pop[rng.Intn(len(pop))]; c.Fitness > best.Fitness {
            best = c
        }
    }
    return best
}

La sélection par tournoi² est notre stratégie par défaut : simple, robuste, et facile à régler via la taille du tournoi. Mais le moteur ne dépend que de l’interface Selector. Brancher une roulette ou une sélection par rang plus tard ne demandera pas de toucher une seule ligne de la boucle d’évolution.

La robustesse, concrètement

Un moteur « simple » ne doit pas être un moteur fragile. Trois garde-fous le rendent sûr à utiliser sans en compliquer le cœur.

Des valeurs par défaut raisonnables. Un appelant ne devrait pas avoir à renseigner chaque paramètre pour obtenir un comportement correct. withDefaults comble les champs laissés à zéro (taille de population, élitisme, nombre de générations, stratégie de sélection) et signale clairement par une panique si une fonction obligatoire manque, plutôt que de planter mystérieusement plus loin.

func withDefaults[G any](c Config[G]) Config[G] {
    if c.NewRandom == nil || c.Fitness == nil || c.Crossover == nil {
        panic("genetic: NewRandom, Fitness et Crossover sont obligatoires")
    }
    if c.PopulationSize <= 0 {
        c.PopulationSize = 100
    }
    if c.MaxGen <= 0 {
        c.MaxGen = 200
    }
    if c.Selector == nil {
        c.Selector = TournamentSelector[G]{Size: 3}
    }
    return c
}

Un arrêt coopératif. Une recherche peut être longue. Grâce au context.Context accepté par Run, l’appelant peut imposer un délai maximal ou annuler à tout moment, et récupérer malgré tout le meilleur individu trouvé. Le moteur ne s’emballe jamais sans issue.

Des exécutions reproductibles. Tout algorithme génétique repose sur l’aléatoire, mais un aléatoire incontrôlable rend le code impossible à tester et à comparer. En initialisant le générateur avec une graine (Seed), deux exécutions identiques produisent exactement le même résultat, indispensable pour déboguer et mesurer.

Pourquoi ce design est évolutif

Faisons le bilan. Le moteur que nous avons construit ne contient aucune trace d’un problème particulier. Pour l’appliquer à un nouveau cas, on ne change que la Config.

graph TD
    A[Engine&#91;G&#93;<br/>inchangé]

    A --> B[Config&#91;string&#93;<br/>évolution de texte]
    A --> C[Config&#91;Tuning&#93;<br/>équilibrage d'arbre 4X]
    A --> D[Config&#91;Planet&#93;<br/>planètes habitables]
    A --> E[Config&#91;...&#93;<br/>tout autre génome]

    style A fill:transparent
    style B fill:transparent
    style C fill:transparent
    style D fill:transparent
    style E fill:transparent

C’est exactement la promesse du schéma « moteur génétique générique » de l’article précédent : un seul moteur, et seule la définition du génome change. À cela s’ajoute une seconde dimension d’évolutivité, celle des stratégies internes, comme la sélection, que l’on remplace sans rien casser.

Conclusion

Nous avons transformé le principe évolutif en un moteur générique en Go. Sa force tient à une seule décision d’architecture : séparer la mécanique de l’évolution, qui ne change jamais, de la définition du problème, fournie de l’extérieur sous forme de fonctions. Les génériques expriment cette séparation, le context et la graine aléatoire la rendent sûre, et l’interface Selector la rend extensible.

Le moteur est volontairement abstrait : il ne sait toujours rien du moindre problème concret. C’est précisément ce que nous allons changer dans le prochain article, en lui confiant son premier vrai problème, tiré de l’univers du jeu : l’équilibrage d’un arbre technologique de 4X, où il faut régler les déblocages et les coûts pour obtenir la difficulté voulue. Nous n’écrirons alors qu’un génome et ses quatre fonctions, et nous regarderons le moteur converger.

Le dépôt

L’implémentation de base du moteur décrit dans cet article est disponible en open source. N’hésitez pas à l’explorer, le cloner et l’adapter à vos propres problèmes.