Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler

La (1+1)-ES et la règle du cinquième, population et auto-adaptation sur la fonction de Rastrigin, CMA-ES, programmes sous forme d’arbres, régression symbolique qui retrouve la troisième loi de Kepler dans les données des planètes, et gonflement des programmes.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 28 sur 52

Programme complet de la série 52 sur 83 sujets publiés

Ce que vous retiendrez

Comment les stratégies d’évolution ajustent des nombres réels et règlent elles-mêmes leur pas.
Pourquoi, sur un terrain accidenté, une population l’emporte sur un individu seul.
Comment la programmation génétique fait pousser des formules entières — et pourquoi elles ont tendance à gonfler.

Utile à connaître avant : Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée

Dans les années soixante, deux étudiants de l’Université technique de Berlin, Ingo Rechenberg et Hans-Paul Schwefel, se tenaient dans une soufflerie au-dessus d’une plaque articulée. Ils voulaient trouver la forme offrant la plus faible résistance, mais pour la calculer il leur manquait à la fois les équations et les ordinateurs. Alors ils ont tiré au sort : ils tournaient les articulations au hasard, mesuraient la résistance et, si elle était plus faible, gardaient la nouvelle forme. De cette expérience est née la stratégie d’évolution — une évolution qui, au lieu de uns et de zéros, ajuste des nombres. Un quart de siècle plus tard, John Koza a montré que l’évolution permet aussi de faire pousser des programmes entiers.

Cet épisode fait suite à l’article Algorithmes génétiques. Là, un individu était une chaîne de bits ; ici, ce sera un vecteur de nombres réels et un arbre de programme.

1. Faire évoluer des nombres : la (1+1)-ES

Algorithme — (1+1)-ES

On minimise f : ℝⁿ → ℝ. Un individu est un point x ∈ ℝⁿ, σ > 0 est le pas de mutation. À chaque génération :

crée un descendant y = x + σ · z, où z ~ N(0, I) est un vecteur de nombres indépendants de loi normale ;
si f(y) ≤ f(x), remplace x ← y.

En termes simples

Un parent, un enfant. L’enfant, c’est le parent avec un peu de bruit aléatoire dans chaque nombre ; s’il est meilleur, il prend sa place. Le pas σ dit quelle est l’ampleur de ce bruit — s’il fait de petites retouches ou de grands sauts.

y = x + σ · z, z ~ N(0, I)

y: descendant — le nouveau candidat que l’on va évaluer
x: parent — le meilleur point trouvé jusqu’ici ; le descendant naît dans son voisinage, car près d’un bon point se trouvent souvent d’autres bons points
σ: pas de mutation — un seul nombre qui fixe à quelle distance du parent on cherche ; le bruit z a une variance de 1, seul σ lui donne l’échelle du problème
z ~ N(0, I): direction et longueur de l’essai — la moyenne 0 signifie qu’aucune direction n’est favorisée d’avance ; la matrice identité I, que toutes les coordonnées changent indépendamment et avec la même force

Mutation dans une stratégie d’évolution : le parent plus un pas aléatoire dont la longueur est réglée par σ.

Définition — loi normale N(0, 1) et N(0, I)

Une variable aléatoire Z suit la loi normale centrée réduite N(0, 1) si elle a pour densité φ(z) = e^−z²/2 / √(2π) ; son espérance vaut 0 et sa variance 1. Environ 68 % des valeurs se trouvent dans l’intervalle [−1, 1] et 95 % dans [−1,96 ; 1,96].

Un vecteur z ~ N(0, I) de ℝⁿ a n composantes indépendantes de loi N(0, 1). Sa longueur tourne typiquement autour de √n (environ 3,2 pour n = 10), car E‖z‖² = n.

Notre programme produit des nombres normaux par la méthode de Box-Muller à partir de deux nombres uniformes u₁, u₂ ∈ (0, 1) : z = √(−2 ln u₁) · cos(2πu₂).

Essayons sur la fonction la plus simple possible, la sphère f(x) = x₁² + … + x₁₀² en dix dimensions. Le minimum est évidemment en zéro ; on part du point (3, …, 3), où f = 90. Comment choisir σ ? Une grande valeur sait descendre vite, mais près du minimum elle dépasse sans cesse la cible. Une petite est précise, mais met une éternité à atteindre le fond.

2. La règle du cinquième

Définition — règle du cinquième (Rechenberg, 1973)

Si la proportion de mutations réussies (descendant meilleur que le parent) dépasse 1/5, augmente σ ; si elle est plus faible, diminue-le. Une forme possible : après un succès σ ← σ · e^1/3, après un échec σ ← σ · e^−1/12. Le pas reste en moyenne inchangé exactement quand un cinquième des mutations réussit : (1/5) · (1/3) = (4/5) · (1/12).

En termes simples

Si presque chaque essai réussit, vous êtes prudent pour rien — augmentez. Si presque aucun ne réussit, vous sautez trop loin — réduisez. Rechenberg a montré qu’on progresse le plus vite quand environ un essai sur cinq réussit. L’algorithme règle ainsi son pas tout seul.

Les deux branches de la règle s’écrivent en une seule formule ; s = 1 après un succès et 0 après un échec :

σ ← σ · exp( 5/12 · ( s − 1/5 ) )

σ: pas de mutation — il change par multiplication, pas par addition : il reste positif et le pas peut diminuer de nombreux ordres de grandeur (de 1 jusqu’aux millièmes), comme l’exige la proximité du minimum
5/12: vitesse d’adaptation — après un succès exp(5/12 · 4/5) = e^1/3 ≈ 1,40, après un échec exp(−5/12 · 1/5) = e^−1/12 ≈ 0,92 ; un nombre plus grand réagirait plus vite, mais σ fluctuerait davantage
s: résultat du dernier essai (1 = le descendant n’était pas pire) — la seule information dont la règle a besoin
1/5: taux de succès visé — quand exactement un cinquième des essais réussit, la moyenne de s − 1/5 est nulle et σ reste en moyenne inchangé

Après N essais avec S succès, le pas est multiplié par exp(5/12 · (S − N/5)) : sur dix essais, deux succès laissent le pas inchangé, quatre le multiplient par 2,30, un seul le réduit à 0,66.

(1+1)-ES sur la sphère en dix dimensions fixe σ = 1σ = 0,1σ = 0,01règle du 1/5

La règle du cinquième passe sous 10⁻⁶ en 587 évaluations — et la courbe du graphique descend régulièrement, car le pas diminue aussi vite que le minimum se rapproche. Avec un σ = 1 fixe, l’algorithme bute vite sur un « plancher » autour de un, sous lequel on ne peut pas descendre avec de si grands sauts. Avec σ = 0,01, il descend, mais lentement : même après 5 000 évaluations, il n’est pas sous 10⁻⁴.

import math, random

def es_1_plus_1(f, x, sigma=1.0, kroku=1000):
    fx = f(x)
    for _ in range(kroku):
        y = [xi + sigma * random.gauss(0, 1) for xi in x]
        fy = f(y)
        if fy <= fx:
            x, fx = y, fy
            sigma *= math.exp(1 / 3)     # succès : augmente
        else:
            sigma *= math.exp(-1 / 12)   # échec : réduis
    return x, fx

Exemple — les douze premiers pas de l’exécution du graphique

Départ x = (3, …, 3), f(x) = 90, σ = 1. La colonne σ donne le pas après la mise à jour :

pas	`f`(`y`)	succès ?	`f`(`x`)	`σ`
1	115,31	non	90,00	0,920
2	95,78	non	90,00	0,846
3	123,94	non	90,00	0,779
4	107,86	non	90,00	0,717
5	101,54	non	90,00	0,659
6	113,11	non	90,00	0,607
7	94,03	non	90,00	0,558
8	95,09	non	90,00	0,513
9	86,27	oui	86,27	0,717
10	114,52	non	86,27	0,659
11	97,72	non	86,27	0,607
12	102,44	non	86,27	0,558

après 8 échecs : σ = e^−8/12 ≈ 0,513

le pas 9 réussit (86,27 < 90) : σ = 0,513 · e^1/3 ≈ 0,513 · 1,396 ≈ 0,717

Avec σ = 1, un pas en dix dimensions mesure environ √10 ≈ 3,2 et les huit premiers descendants sont pires que le départ, donc la règle resserre le pas. Les succès deviennent ensuite plus fréquents et σ se stabilise là où environ un essai sur cinq réussit — sur toute l’exécution, 99 essais sur 587 ont réussi, soit 17 %. À mesure que le point s’approche du minimum, le pas diminue avec lui : à la fin de l’exécution, après 580 évaluations, σ ≈ 0,00055.

3. Population et auto-adaptation

La sphère n’a qu’un seul minimum. Les vrais problèmes en ont souvent des quantités — et là, un seul individu ne suffit pas. Une fonction de test typique est la fonction de Rastrigin : f(x) = 10n + ∑ (x_i² − 10 cos 2πx_i). C’est une sphère dans laquelle on aurait creusé une grille régulière de cuvettes ; le minimum global 0 est à l’origine et, autour de lui, il y en a des centaines de locaux.

f(x) = 10n + ∑_i=1ⁿ ( x_i² − 10 cos 2πx_i )

10n: décalage vers le haut — à l’origine, le cosinus retire au plus 10 par coordonnée ; la constante les rend pour que le minimum global vaille exactement 0
x_i²: sphère — la pente générale vers l’origine ; sans elle, toutes les cuvettes seraient aussi profondes et aucun minimum ne serait global
10 cos 2πx_i: ondulations de période 1 et d’amplitude 10 — elles creusent une cuvette à chaque entier ; l’amplitude est bien plus grande que la pente de la sphère entre deux cuvettes voisines, si bien qu’une recherche locale reste coincée dans la cuvette la plus proche

La fonction de Rastrigin : une sphère lisse à la surface régulièrement ondulée.

Exemple — le départ et les cuvettes voisines (n = 2)

départ (4,2 ; −3,8) : x₁² = 17,64, 10 cos(2π · 4,2) = 10 cos(0,4π) ≈ 3,09

x₂² = 14,44, 10 cos(2π · (−3,8)) = 10 cos(0,4π) ≈ 3,09

f = 20 + (17,64 − 3,09) + (14,44 − 3,09) ≈ 45,90

fond des cuvettes voisines de l’origine, en (±1 ; 0) et (0 ; ±1) : f ≈ 0,99 (au point 0,995, pas exactement 1 — la sphère le tire vers l’origine)

fond des cuvettes diagonales en (±1 ; ±1) : f ≈ 1,99

La valeur 1,49 à la génération 8 (voir plus bas) signifie donc une population dans une cuvette voisine, pas encore au fond.

Définition — (μ, λ)-ES et (μ + λ)-ES avec auto-adaptation

La population compte μ parents ; chaque génération crée λ > μ descendants. Dans (μ, λ), les μ meilleurs descendants survivent et les parents meurent ; dans (μ + λ), on sélectionne parmi les parents et les descendants réunis.

Auto-adaptation : chaque individu porte son propre pas σ. Le descendant le mute d’abord, σ′ = σ · e^{τ · N(0, 1)} avec τ ≈ 1/√(2n), et ne déplace qu’ensuite sa position avec lui : y = x + σ′ · N(0, I).

En termes simples

Le pas se transmet comme n’importe quel autre caractère. Qui a un pas bien réglé a de meilleurs enfants — et ainsi son pas s’impose aussi. Personne n’a besoin de compter les succès : l’évolution se règle elle-même. La variante (μ, λ), où les parents ne survivent pas, ne se laisse en outre pas bloquer par un seul individu chanceux : chaque génération repart à neuf.

σ′ = σ · e^{τ · N(0, 1)}, τ = 1/√(2n)

σ′: pas du descendant — la position est aussitôt déplacée avec lui, donc la valeur sélective du descendant révèle si le pas était bon
σ: pas du parent — il se transmet ; le descendant part de ce qui a réussi au parent
τ: taux d’apprentissage du pas — de combien le pas peut changer d’une génération à l’autre ; il diminue quand le nombre de dimensions n augmente, car une seule valeur sélective renseigne alors moins sur la qualité du pas
N(0, 1): changement aléatoire — symétrique autour de zéro, donc agrandir et réduire sont également probables ; c’est la sélection seule qui décide du sens

Le pas change par multiplication avec une exponentielle : il reste positif et doubler est aussi probable que diminuer de moitié.

Exemple — mutation du pas pour n = 2

τ = 1/√(2 · 2) = 1/2

N(0, 1) = +1 : σ′ = σ · e^0,5 ≈ 1,65 σ ; N(0, 1) = −1 : σ′ = σ · e^−0,5 ≈ 0,61 σ

Un descendant typique essaie donc un pas d’environ 40 % plus petit à 65 % plus grand que celui du parent. Dans notre exécution, le pas du meilleur individu est tombé en 15 générations de 2 à 0,011 — presque deux cents fois moins.

import math, random

def es_mi_lambda(f, start, mi=15, lam=100, sigma=2.0, generaci=80):
    n = len(start)
    tau = 1 / math.sqrt(2 * n)
    rodice = [(start, sigma)] * mi
    for _ in range(generaci):
        deti = []
        for _ in range(lam):
            x, s = random.choice(rodice)                    # parent au hasard
            s = s * math.exp(tau * random.gauss(0, 1))      # d’abord muter le pas
            y = [xi + s * random.gauss(0, 1) for xi in x]   # puis la position avec lui
            deti.append((y, s))
        deti.sort(key=lambda d: f(d[0]))
        rodice = deti[:mi]          # (μ, λ) : seuls les meilleurs descendants survivent
    return rodice[0]

(15, 100)-ES sur la fonction de Rastrigin ; la croix est le minimum global

La population part autour du point (4,2 ; −3,8), où f ≈ 45,9. Au début, elle est répartie sur plusieurs cuvettes à la fois et se resserre vers les plus profondes. À la génération 8, le meilleur individu est encore dans une cuvette voisine (f ≈ 1,49), mais le pas est déjà tombé de 2 à 0,27. À la génération 15, la population est au minimum global et le pas a diminué au centième pour pouvoir l’affiner.

Sur cent exécutions avec des graines différentes, la (15, 100)-ES a trouvé le minimum global dans 32 cas. À titre de comparaison, la (1+1)-ES avec la règle du cinquième et le même budget de 8 000 évaluations : dans un seul. Sur les sphères, un individu seul est le plus rapide ; sur un terrain accidenté, c’est la population qui l’emporte — et même elle finit souvent dans l’une des cuvettes voisines.

4. CMA-ES

L’auto-adaptation ne règle que la longueur du pas. Et si le minimum se trouve dans une vallée étroite et oblique, où il vaut mieux faire de longs pas dans une direction et de courts dans une autre ? CMA-ES (Hansen et Ostermeier, 2001) apprend à partir des pas réussis toute la matrice de covariance de la mutation — la forme du nuage dans lequel elle tire les descendants. Pendant la recherche, le nuage tourne et s’allonge le long de la vallée. Pour optimiser des fonctions continues dont on ne connaît pas le gradient, CMA-ES est aujourd’hui l’une des méthodes les plus fiables.

Définition — mutation avec matrice de covariance

Pour une matrice symétrique définie positive C ∈ ℝ^n×n, z ~ N(0, C) est un vecteur d’espérance 0 et de covariances E[z_iz_j] = C_ij. On l’obtient à partir d’un bruit ordinaire : z = Au, où u ~ N(0, I) et AA^T = C. Le descendant est y = m + σ · z, où m est le centre de la population.

Les points de même densité se trouvent sur un ellipsoïde ; ses axes sont les vecteurs propres de C et les longueurs des axes sont proportionnelles aux racines des valeurs propres. Pour C = I, c’est une sphère et l’on retrouve une stratégie d’évolution ordinaire.

En simplifiant (la vraie CMA-ES ajoute encore les chemins d’évolution et son propre réglage de σ, voir N. Hansen, The CMA Evolution Strategy: A Tutorial, 2016), la matrice se déplace après chaque génération vers les pas réussis :

C ← (1 − c) C + c ∑_i=1^μ w_i z_iz_i^T

C: matrice de covariance de la mutation — la forme du nuage dans lequel on tire les descendants
1 − c: mémoire — l’ancienne matrice ne se rapproche qu’un peu de la nouvelle information, car une génération est un échantillon petit et aléatoire
c: taux d’apprentissage de la matrice, un nombre entre 0 et 1 — le poids accordé aux pas de la dernière génération
∑ w_i: moyenne pondérée sur les μ meilleurs descendants ; les poids sont positifs, leur somme vaut 1 et un meilleur descendant a un poids plus grand — on n’apprend que des pas qui ont payé
z_iz_i^T: le pas réussi z_i = (y_i − m)/σ sous forme de matrice — il allonge le nuage précisément dans sa direction

Les directions qui ont réussi reçoivent une plus grande variance à la génération suivante.

Exemple — un pas réussi le long de la diagonale

C = I (nuage circulaire), un seul pas réussi z = (1, 1), c = 0,2 :

zz^T = [[1, 1], [1, 1]]

C ← 0,8 · [[1, 0], [0, 1]] + 0,2 · [[1, 1], [1, 1]] = [[1 ; 0,2], [0,2 ; 1]]

valeurs propres : 1 + 0,2 = 1,2 dans la direction (1, 1) et 1 − 0,2 = 0,8 dans la direction (1, −1)

Le nuage s’est allongé le long de la direction réussie et rétréci en travers — après quelques générations de ce genre, il s’étend le long de la vallée.

5. Programmation génétique

Définition — un programme comme arbre

On se donne un ensemble de fonctions F (avec leurs arités) et un ensemble de terminaux T (variables et constantes). Un programme est un arbre enraciné dont les nœuds internes sont des fonctions de F ayant autant d’enfants que leur arité, et dont les feuilles sont des terminaux de T. La valeur du programme se calcule des feuilles vers la racine.

Clôture : chaque fonction doit accepter la sortie de n’importe quelle autre. C’est pourquoi on utilise la division protégée (la division par zéro renvoie 1) et la racine de la valeur absolue.

En termes simples

La formule (a ÷ 5) × √a est un arbre : en haut la multiplication, en dessous la division et la racine, tout en bas a et un cinq. La programmation génétique croise des programmes en coupant une branche à l’un et en greffant à sa place une branche de l’autre. La mutation remplace une branche par une nouvelle poussée au hasard. Les opérations protégées garantissent qu’aucun programme ne plante ; il peut seulement produire des absurdités — et la sélection les élimine.

John Koza, de l’université Stanford, a décrit la méthode en 1992 dans le livre Genetic Programming et l’a montrée sur des dizaines de problèmes, du pilotage d’un robot à la recherche de formules.

Exemple — évaluation de l’arbre (a ÷ 5) × √a pour la Terre

Des feuilles vers la racine, a = 149,6 (millions de km) :

branche gauche : a ÷ 5 = 149,6 / 5 = 29,92

branche droite : √a = √149,6 ≈ 12,231

racine : 29,92 × 12,231 ≈ 365,95 jours (valeur réelle 365,26, écart +0,19 %)

def gp(populace, generaci, p_krizeni=0.9, max_hloubka=7):
    for _ in range(generaci):
        dalsi = [nejlepsi(populace)]                  # élitisme : le meilleur
        while len(dalsi) < len(populace):
            if random.random() < p_krizeni:           # croisement par échange de sous-arbres
                a, b = turnaj(populace), turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), podstrom(b, nahodny_uzel(b)))
            else:                                     # mutation : branche → nouvelle au hasard
                a = turnaj(populace)
                dite = nahrad(a, nahodny_uzel(a), nahodny_strom(hloubka=2))
            if hloubka(dite) <= max_hloubka:         # on jette les enfants trop profonds
                dalsi.append(dite)
        populace = dalsi
    return nejlepsi(populace)        # plus petite erreur ; à égalité, le plus petit arbre

6. Régression symbolique : la loi de Kepler

Johannes Kepler a cherché pendant dix ans la relation entre la distance d’une planète au Soleil et sa période de révolution ; il a publié la troisième loi en 1619. Donnons la même tâche à la programmation génétique. Elle dispose de huit planètes — le demi-grand axe a en millions de kilomètres et la période de révolution T en jours —, des opérations +, −, ×, ÷ et √, de la variable a et des chiffres de 1 à 9. L’erreur d’un programme est l’écart relatif moyen par rapport aux périodes de révolution réelles. La population compte 300 programmes et 40 générations.

Définition — régression symbolique

Pour des données (x_i, y_i), la régression symbolique cherche une expression g d’une grammaire donnée (fonctions et terminaux) qui minimise l’erreur ∑ ℓ(g(x_i), y_i). Contrairement à la régression ordinaire, la forme du modèle n’est pas donnée d’avance, seulement les briques.

En termes simples

La régression linéaire de l’article sur les statistiques cherche la meilleure droite. La régression symbolique ne cherche pas des nombres dans une formule connue, mais la formule elle-même — et le résultat, un humain peut le lire.

Précisément, l’erreur d’un programme g est la moyenne des différences absolues des logarithmes :

E(g) = (1/8) ∑_i=1⁸ | ln g(a_i) − ln T_i |

(1/8) ∑: moyenne sur huit planètes — l’erreur ne dépend pas de la quantité de données et se lit comme un « écart typique par planète »
| … |: valeur absolue — une prédiction trop grande de 1 % est aussi mauvaise qu’une trop petite de 1 %, et les erreurs de signes opposés ne s’annulent pas
ln g(a_i) − ln T_i: la différence des logarithmes vaut ln(g/T), c’est-à-dire l’écart relatif : pour de petits écarts, ln(1 + r) ≈ r. Les périodes de révolution diffèrent d’un facteur presque mille (88 jours pour Mercure, 60 190 pour Neptune) ; avec une différence ordinaire, seul Neptune déciderait de l’erreur

L’écart relatif moyen, dans lequel Mercure pèse autant que Neptune. Un programme au résultat négatif ou infini reçoit une erreur ∞.

Le meilleur programme de la population initiale, aléatoire, s’écarte des périodes de révolution réelles de 32 % en moyenne. Dès la troisième génération, il a un écart de 8 % et la bonne forme a^1,5, avec seulement une constante de 0,22. À la quinzième génération arrive ceci :

Meilleur programme à la génération 15 ((a ÷ 5) × √(a))

T = a · √a / 5 — donc T proportionnel à a^3/2, autrement dit T² proportionnel à a³. C’est la troisième loi de Kepler. L’écart moyen est de 0,30 % et la constante 1/5 est très proche de la vraie valeur 0,1996 pour ces unités. Sur vingt exécutions avec des graines différentes, dix-huit ont trouvé l’exposant 1,5.

D’où vient 0,1996 ? De la loi de la gravitation de Newton découle, pour une orbite circulaire (et pour une ellipse de demi-grand axe a, quand la masse de la planète est négligeable devant celle du Soleil), la forme de la loi avec sa constante :

T = 2π / √(GM_☉) · a^3/2

T: période de révolution — la durée d’un tour
2π: un tour correspond à un angle de 2π ; la formule vient de la vitesse angulaire ω via T = 2π/ω
√(GM_☉): la force de la gravité du Soleil (G la constante gravitationnelle, M_☉ la masse du Soleil) — une attraction plus forte signifie une révolution plus rapide, d’où sa place au dénominateur
a^3/2: distance — la gravité s’affaiblit en a² et le trajet s’allonge proportionnellement à a ; l’égalité de la force centripète et de la force gravitationnelle, ω²a = GM_☉/a², donne ω ∝ a^−3/2

La troisième loi de Kepler déduite de la gravitation newtonienne ; la programmation génétique a trouvé la forme a^3/2 et la constante à partir de huit paires de nombres seulement.

Exemple — la constante en millions de km et en jours

Le paramètre gravitationnel du Soleil vaut GM_☉ = 1,327 124 · 10²⁰ m³/s² (valeur nominale de l’Union astronomique internationale, résolution B3 de 2015). L’unité de longueur est 10⁹ m, donc a^3/2 en mètres est (10⁹)^3/2 = √(10²⁷) fois plus grand :

√(10²⁷ / 1,327 124 · 10²⁰) = √(7,535 · 10⁶) ≈ 2 745,0 s

2π · 2 745,0 s ≈ 17 247 s

17 247 s / 86 400 s/jour ≈ 0,1996 jour

Le programme avec la constante 1/5 = 0,2 s’écarte donc de 0,19 % — exactement l’écart obtenu plus haut pour la Terre.

7. Le gonflement

Mais l’évolution ne s’en est pas tenue à la belle formule. D’ici la génération 40, elle a « amélioré » l’écart à 0,23 % avec ceci :

Meilleur programme à la génération 40 (((a + ((((2 × 8) − a) ÷ 5) ÷ a)) ÷ 5) × √(a))

L’arbre a seize nœuds au lieu de six, et les branches ajoutées ne font rien d’autre que retoucher la constante et contourner l’arrondi des données. Physiquement, c’est une formule moins bonne — surajustée à huit planètes. La taille moyenne des programmes dans la population est d’ailleurs passée de 9,8 nœuds au départ à 23,8 à la vingtième génération.

Définition — gonflement et pression de parcimonie

Le gonflement (bloat) est une croissance de la taille des programmes de la population qui ne correspond à aucune amélioration de leur valeur sélective. La pression de parcimonie (parsimony pressure) pénalise la taille : soit elle l’ajoute à l’erreur, F′(g) = F(g) + c · |g|, soit elle l’utilise comme second critère à erreur égale.

En termes simples

Les programmes se couvrent de code qui ne fait rien ou apporte une correction infime — un peu comme s’accumulent dans les génomes des êtres vivants des séquences sans fonction. Un grand arbre est en outre plus difficile à casser par le croisement, il se multiplie donc plus facilement. Notre algorithme préfère, à erreur égale, le plus petit arbre, mais quand un arbre plus grand réduit l’erreur d’un cheveu, il gagne. Le même dilemme qu’avec le surapprentissage d’un modèle : précision sur les données, ou simplicité qui généralise ?

F′(g) = F(g) + c · |g|

F′(g): erreur corrigée selon laquelle on sélectionne — plus petite, c’est mieux
F(g): erreur du programme sur les données — toujours l’essentiel de ce qu’on veut réduire
c: prix d’un nœud — indique de combien l’erreur doit s’améliorer pour qu’un nœud de plus soit rentable ; on le choisit pour qu’il ne tranche que pour des améliorations négligeables
|g|: taille du programme, le nombre de nœuds de l’arbre — une mesure de complexité que l’on peut calculer sans comprendre le programme

Un nœud de plus doit se payer en réduisant l’erreur d’au moins c.

Exemple — quel c aurait sauvé la loi de Kepler

Arbre de la génération 15 : erreur 0,2986 %, 6 nœuds. Arbre de la génération 40 : erreur 0,2312 %, 16 nœuds. Le plus petit arbre gagne quand

0,002 986 + 6c < 0,002 312 + 16c

10c > 0,000 674 ⇒ c > 6,7 · 10⁻⁵

Dix nœuds de plus ont amélioré l’erreur de moins d’un centième de point de pourcentage. Avec un prix supérieur à 0,007 % par nœud, l’arbre de la génération 40 aurait perdu la sélection face à la loi lisible de la génération 15.

8. Stratégies d’évolution et programmes aujourd’hui

Des stratégies d’évolution à la place de l’apprentissage par renforcement. En 2017, OpenAI a montré qu’une simple stratégie d’évolution sait entraîner des réseaux de neurones à piloter des robots simulés et à jouer à des jeux Atari presque aussi bien que l’apprentissage par renforcement — et qu’on peut la répartir sur des milliers de processeurs qui ne s’échangent que quelques nombres.
Découvrir des lois à partir de données. En 2009, Schmidt et Lipson ont fait déduire par régression symbolique des lois du mouvement et des lois de conservation à partir de mesures de pendules. Des bibliothèques actuelles comme PySR servent en physique et en astronomie, où une formule lisible vaut plus qu’une boîte noire.
Évolution d’algorithmes d’apprentissage automatique. Le projet AutoML-Zero (Google, 2020) a laissé l’évolution assembler des algorithmes d’apprentissage à partir d’opérations mathématiques élémentaires et a ainsi redécouvert, par exemple, la rétropropagation du gradient.
Des programmes avec des modèles de langage. Les systèmes FunSearch et AlphaEvolve de l’épisode précédent sont de la programmation génétique dans laquelle la mutation est confiée à un modèle de langage au lieu d’une branche aléatoire.

9. Résumé

Les stratégies d’évolution mutent des nombres réels avec un bruit normal de pas σ.
La règle du cinquième et l’auto-adaptation règlent σ automatiquement ; CMA-ES apprend aussi la forme des mutations.
Sur les sphères, un seul individu suffit ; sur un terrain accidenté, une population aide : sur la fonction de Rastrigin, 32 succès sur 100 contre un seul.
La programmation génétique fait pousser des programmes sous forme d’arbres ; la régression symbolique a retrouvé dans les données sur les planètes la troisième loi de Kepler.
Les programmes ont tendance à gonfler et à surapprendre — la pression de parcimonie y remédie.

Envie de mettre la main à la pâte ? Demandez à un agent d’IA d’écrire une régression symbolique et donnez-lui vos propres données — par exemple la période d’un pendule selon la longueur de la ficelle — et voyez s’il trouve √L.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.

Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler

1. Faire évoluer des nombres : la (1+1)-ES

2. La règle du cinquième

3. Population et auto-adaptation

4. CMA-ES

5. Programmation génétique

6. Régression symbolique : la loi de Kepler

7. Le gonflement

8. Stratégies d’évolution et programmes aujourd’hui

9. Résumé

Un Agent sur votre ordinateur, piloté depuis votre téléphone