Pourquoi les algorithmes génétiques existent

Lorsque l’on découvre les algorithmes génétiques pour la première fois, une question revient presque systématiquement : Pourquoi simuler l’évolution alors qu’un ordinateur est censé calculer la bonne réponse ?

La question est légitime. L’informatique regorge d’algorithmes capables de trouver des solutions exactes : Dijkstra pour les chemins les plus courts, Quicksort pour le tri, A* pour la recherche de chemin, les solveurs SAT pour certains problèmes logiques, ou encore la programmation dynamique pour de nombreux problèmes d’optimisation. Alors pourquoi inventer une famille entière d’algorithmes inspirés de la biologie ?

La réponse tient en une phrase :

C’est précisément dans cet espace que les algorithmes génétiques trouvent leur utilité. Dans cette série, nous allons construire un moteur génétique générique en Go et l’appliquer à différents problèmes d’optimisation et de génération procédurale. Mais avant d’écrire la moindre ligne de code, il est important de comprendre pourquoi cette approche existe.

Une histoire de problèmes impossibles

Imaginons un problème simple. Vous disposez de plusieurs systèmes stellaires et vous souhaitez trouver l’ordre optimal pour les visiter.

Terra
Vega
Sirius
Altair
Tau Ceti
Aldebaran

Avec six destinations, il existe déjà 6! = 720 possibilités. Ce n’est pas énorme : un ordinateur moderne peut toutes les tester en une fraction de seconde. Mais augmentons légèrement le nombre de destinations.

Même en évaluant un milliard de solutions par seconde, il suffit d’une vingtaine de destinations pour basculer dans des temps de calcul absurdes, et d’une trentaine pour dépasser largement l’âge de l’univers. Nous venons de rencontrer un phénomène fondamental de l’informatique :

Le problème n’est plus de savoir calculer une solution, mais de savoir où chercher.

Quand la force brute ne suffit plus

La première idée consiste généralement à tester toutes les possibilités. Cette approche est appelée force brute, et elle possède une propriété très appréciable : la force brute finit toujours par trouver la solution optimale.

Malheureusement, elle souffre d’un défaut majeur : le temps de calcul explose avec la taille du problème. Pour certains problèmes, la croissance est tellement rapide qu’aucune machine existante ne peut explorer l’intégralité de l’espace de recherche¹. Nous devons alors changer de stratégie.

Accepter une idée contre-intuitive

L’un des plus grands changements de perspective en optimisation consiste à abandonner l’idée de perfection. Dans de nombreux cas, la vraie question n’est pas : “quelle est la meilleure solution ?” mais plutôt “Comment trouver une excellente solution rapidement ?”

La nuance est fondamentale. Dans le monde réel, une solution à 99 % de l’optimum trouvée en quelques secondes est souvent plus utile qu’une solution parfaite nécessitant plusieurs années de calcul. C’est précisément le rôle des heuristiques et des métaheuristiques, et les algorithmes génétiques appartiennent à cette famille².

La nature avait déjà trouvé une solution

Pendant des milliards d’années, la nature a dû résoudre un problème similaire : comment produire des organismes capables de survivre, des systèmes biologiques robustes et des comportements adaptés à leur environnement ? La réponse n’a jamais été de calculer directement la meilleure forme de vie possible. L’évolution procède autrement.

graph LR
    A[Variations<br/>aléatoires]
    --> B[Sélection<br/>par l'environnement]
    --> C[Reproduction<br/>des survivants]
    --> D[Nouvelle<br/>génération]
    --> A

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

Le principe est remarquablement simple : produire de nombreuses variantes, évaluer lesquelles fonctionnent le mieux, conserver les plus adaptées, puis recommencer. Après suffisamment d’itérations, des structures extrêmement complexes peuvent émerger. Les algorithmes génétiques reprennent exactement cette idée.

Le principe d’un algorithme génétique

Un algorithme génétique repose généralement sur quatre concepts.

Le génome

Le génome représente une solution candidate. Selon le problème, il peut prendre des formes très différentes :

Terra -> Vega -> Sirius -> Altair      (un trajet)
101001100101                           (une suite binaire)
Masse = 1.1, Température = 22, Eau = 65%   (des paramètres)

Le génome n’est rien de plus qu’une représentation manipulable par l’algorithme.

La population

Au lieu de travailler sur une seule solution, nous en manipulons plusieurs simultanément. Chaque solution est appelée un individu, et l’ensemble constitue la population. Faire évoluer une population entière permet d’explorer plusieurs régions de l’espace de recherche en parallèle.

La fitness

Pour comparer les individus, il faut une métrique. Cette métrique est appelée fonction de fitness.

func Fitness(distance float64) float64 {
    if distance <= 0 {
        return 0
    }

    return 1 / distance
}

Ici, plus la distance est faible, plus la fitness est élevée. L’algorithme cherche alors naturellement les individus ayant le meilleur score.

La reproduction

Les meilleurs individus sont utilisés pour produire de nouveaux individus, généralement par croisement puis mutation.

Parent A : 11110000
Parent B : 00001111
Enfant   : 11111111   (croisement)
Mutation : 11110111   (un bit basculé)

Le croisement combine les informations des parents ; la mutation introduit une petite variation qui permet d’explorer continuellement de nouvelles zones de l’espace de recherche.

Pourquoi ne pas simplement utiliser du hasard ?

C’est probablement l’objection la plus fréquente : si nous générons suffisamment de solutions aléatoires, nous finirons bien par tomber sur une bonne. Le problème est que le hasard pur ne retient aucune information.

graph TD
    subgraph H[Hasard pur]
        H1[Solution aléatoire] --> H2[Évaluation] --> H3[Suppression]
        H3 -.repart de zéro.-> H1
    end

    subgraph G[Algorithme génétique]
        G1[Bonne solution] --> G2[Sélection] --> G3[Transmission] --> G4[Amélioration]
        G4 -.hérite du passé.-> G1
    end

À chaque tentative, le hasard oublie tout. Un algorithme génétique, lui, conserve ce qui fonctionne : chaque génération hérite des découvertes précédentes, et le système apprend progressivement où chercher. C’est cette accumulation de petites améliorations qui rend l’approche efficace.

Ce que les algorithmes génétiques ne sont pas

Les algorithmes génétiques souffrent parfois d’une réputation exagérée. Ils ne sont ni magiques, ni intelligents, ni universellement meilleurs, ni garantis optimaux. Dans de nombreux cas, un algorithme spécialisé sera plus rapide et plus efficace.

graph TD
    A[Problème à résoudre]

    A --> B{Solution exacte<br/>connue ?}
    B -->|Oui| C[Algorithme spécialisé<br/>Dijkstra, DP, SAT...]

    B -->|Non| D{Espace de recherche<br/>gigantesque ?}
    D -->|Non| F[Méthode plus simple<br/>recherche locale, gloutonne]
    D -->|Oui| E{Une bonne solution<br/>suffit ?}

    E -->|Oui| G[Métaheuristique<br/>algorithme génétique, recuit simulé...]
    E -->|Non| H[Impasse pratique]

Un algorithme génétique devient intéressant lorsque l’espace de recherche est immense, que les contraintes sont nombreuses, que plusieurs objectifs entrent en conflit, qu’une bonne solution suffit, et que l’optimum exact est difficile à calculer.

Quelques exemples concrets

Les algorithmes génétiques sont utilisés dans de nombreux domaines³ : optimisation de trajectoires pour trouver des itinéraires ou des séquences d’actions efficaces, planification industrielle pour orchestrer des ressources limitées, conception de circuits pour explorer automatiquement des architectures matérielles, robotique pour faire émerger des comportements adaptés à un environnement, et génération procédurale pour construire automatiquement systèmes stellaires, planètes, écosystèmes, arbres technologiques ou règles d’équilibrage.

Dans tous ces cas, il est souvent plus simple d’évaluer une solution que de calculer directement la meilleure.

Pourquoi cette approche est intéressante pour nous

Dans cette série, nous allons utiliser les algorithmes génétiques comme un outil généraliste. L’idée n’est pas de construire un solveur spécialisé, mais un moteur capable de faire évoluer n’importe quel type de génome.

graph TD
    A[Moteur génétique générique]

    A --> B[Arbre<br/>technologique 4X]
    A --> C[Systèmes<br/>stellaires]
    A --> D[Planètes<br/>habitables]
    A --> E[Espèces<br/>simulées]
    A --> F[Équilibrage<br/>de règles]
    A --> G[NEAT<br/>réseaux évolués]

À chaque nouvel article, nous conserverons le même moteur. Seule la définition du génome changera.

Conclusion

Les algorithmes génétiques existent parce que certains problèmes deviennent rapidement impossibles à résoudre de manière exhaustive. Face à ces espaces de recherche gigantesques, ils proposent une approche différente : générer, évaluer, sélectionner, reproduire, recommencer. Inspirés par les mécanismes de l’évolution naturelle, ils permettent d’explorer efficacement un grand nombre de solutions potentielles sans avoir à toutes les tester.

Dans le prochain article, nous quitterons la théorie pour passer à la pratique : nous concevrons un moteur génétique générique en Go capable de faire évoluer n’importe quel type de génome.