🔭 astrophysics

The Inefficiency of Genetic Programming for Symbolic Regression

En analysant le comportement de recherche de la programmation génétique pour la régression symbolique sur des ensembles de données réels grâce à de nouveaux algorithmes d'égalité de saturation, cette étude démontre que cette méthode est inefficace car elle explore une fraction négligeable des expressions sémantiquement uniques et évalue de manière redondante des expressions équivalentes.

Auteurs originaux : Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Publié 2026-03-30

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🕵️‍♂️ Le Grand Détective des Formules Mathématiques

Imaginez que vous êtes un détective privé. Votre mission ? Trouver la formule mathématique parfaite qui explique un phénomène du monde réel (par exemple, comment l'eau coule dans un tuyau rouillé, ou comment les étoiles tournent autour des galaxies).

C'est ce qu'on appelle la Régression Symbolique. Le but est de trouver l'équation exacte (comme $y = 2x + 5$ ) plutôt que de juste prédire des chiffres.

Pour trouver cette formule, on utilise souvent un outil appelé Programmation Génétique (PG). C'est un peu comme un jardinier qui fait évoluer des plantes : il crée des milliers de formules, garde les meilleures, les mélange (comme on croise deux plantes) et les modifie légèrement pour voir si ça s'améliore.

🐢 Le Problème : Le Jardinier qui tourne en rond

Les auteurs de ce papier se sont demandé : "Est-ce que ce jardinier (la PG) est vraiment efficace ?"

Pour répondre, ils ont fait une expérience très particulière. Au lieu de laisser le jardinier chercher au hasard dans un océan infini, ils ont créé un petit jardin clos (un espace de recherche limité) où ils connaissaient toutes les plantes possibles. Ils ont même fait une liste complète de toutes les formules uniques qui existent dans ce jardin.

Ensuite, ils ont laissé le jardinier (la PG) chercher la meilleure plante, et ils ont comparé son travail à celui d'un touriste qui marche au hasard (une recherche aléatoire) dans le même petit jardin.

🎭 Les Découvertes Surprenantes

Voici ce qu'ils ont découvert, avec des analogies pour illustrer :

1. Le Jardinier visite les mêmes endroits encore et encore

C'est le problème principal. Le jardinier (la PG) passe beaucoup de temps à créer des formules qui, en apparence, sont différentes, mais qui font exactement la même chose.

L'analogie : Imaginez que vous cherchez un trésor. Le jardinier trouve un chemin qui mène au trésor, puis il en trouve un autre qui est juste le premier chemin écrit à l'envers, puis un troisième qui est le même chemin mais avec des arbres dessinés dessus. Pour lui, ce sont trois aventures différentes. Pour nous (et pour les mathématiques), c'est le même chemin.
Le résultat : La PG passe environ 90 % de son temps à réévaluer des formules qu'elle a déjà vues (mais déguisées). C'est comme si vous cherchiez vos clés dans votre poche gauche, puis dans votre poche droite, puis dans votre poche gauche encore, sans jamais réaliser qu'elles sont dans votre poche intérieure !

2. Le Touriste est plus rapide que le Jardinier

Quand on compare le jardinier (PG) au touriste qui marche au hasard (Recherche Aléatoire) dans ce petit jardin :

Le touriste trouve la meilleure formule beaucoup plus vite.
Pourquoi ? Parce que le touriste ne perd pas de temps à faire des détours inutiles ou à redécouvrir les mêmes formules. Il essaie une nouvelle formule à chaque pas.
Le jardinier, lui, essaie d'être "intelligent" en croisant ses formules, mais il finit par tourner en rond dans les mêmes zones du jardin.

3. La "Magie" de la Simplification

Pour prouver que le jardinier perd son temps, les chercheurs ont utilisé un outil magique appelé saturation d'égalité.

L'analogie : Imaginez que le jardinier vous montre une formule compliquée : (x + 1) * 2 - 2. L'outil magique dit : "Attends, c'est juste 2x !".
Grâce à cet outil, ils ont pu voir que beaucoup de formules complexes que le jardinier créait étaient en réalité des versions déguisées de formules très simples (comme une constante, ou un chiffre tout seul). Le jardinier passait donc 50 % de son temps à créer des formules qui ne servaient à rien de plus que de dire "42".

🌍 Pourquoi c'est important ?

Les chercheurs ont testé cela sur deux vrais problèmes scientifiques :

L'écoulement de l'eau dans les tuyaux (un problème d'ingénierie vieux de 80 ans).
Le mouvement des galaxies (un problème d'astrophysique sur la matière noire).

Dans les deux cas, la Programmation Génétique n'a jamais trouvé la meilleure formule possible, même après des milliers d'essais. Elle s'est contentée de trouver des solutions "correctes", mais pas optimales, tout en gaspillant énormément de temps et d'énergie de calcul.

💡 La Conclusion en une phrase

La Programmation Génétique, telle qu'elle est utilisée aujourd'hui, est un peu comme un chasseur qui tire dans tous les sens : il finit peut-être par toucher la cible, mais il gaspille 90 % de ses balles à tirer sur des cibles fantômes ou sur des cibles qu'il a déjà touchées.

Leçon à retenir : Pour trouver les meilleures formules mathématiques, il faut peut-être arrêter de laisser l'algorithme "évoluer" au hasard et commencer à lui apprendre à simplifier ce qu'il crée, pour éviter de tourner en rond dans le même jardin.

1. Problématique

La régression symbolique (SR) vise à trouver une expression mathématique explicite qui modélise parfaitement un ensemble de données. La Programmation Génétique (PG) est l'algorithme d'évolution le plus couramment utilisé pour cette tâche. Cependant, l'espace de recherche en PG est vaste et contient une redondance massive : de nombreuses structures d'arbres génétiques différentes (génotypes) représentent la même fonction mathématique (phénotype) ou sont isomorphes après simplification.

Le problème central abordé par les auteurs est l'inefficacité de la PG dans des contextes réalistes mais limités. La question est de savoir si la PG explore efficacement l'espace des solutions uniques ou si elle gaspille des ressources computationnelles à réévaluer des expressions sémantiquement identiques (duplicates) ou à explorer des régions non prometteuses, par rapport à une recherche aléatoire idéale.

2. Méthodologie

Pour répondre à cette question, les auteurs ont conçu une méthodologie rigoureuse permettant une comparaison exhaustive entre la PG et une recherche aléatoire sur un espace de solutions sémantiquement unique.

A. Exhaustive Symbolic Regression (ESR) améliorée

Les auteurs ont utilisé et amélioré l'algorithme ESR pour énumérer exhaustivement tout l'espace de recherche possible pour des expressions de longueur limitée (jusqu'à 12 nœuds).

Génération : Ils génèrent tous les arbres d'expressions valides selon une grammaire formelle.
Déduplication sémantique (Innovation clé) : Au lieu de se fier uniquement aux valeurs de fitness (qui dépendent des paramètres optimisés), ils utilisent l'équilibration d'égalité (equality saturation - eq-sat). Cette technique, implémentée via la bibliothèque MetaTheory.jl en Julia, applique un ensemble de règles de réécriture (commutativité, associativité, distributivité, etc.) pour réduire chaque expression à une forme canonique.
Résultat : Cela permet d'identifier et de supprimer les expressions redondantes, ne gardant que les structures mathématiquement uniques. L'espace de recherche réduit est ainsi plusieurs ordres de grandeur plus petit que l'espace brut des arbres.

B. Benchmark : Recherche Aléatoire (RS)

Une fois l'espace des expressions uniques énuméré, les auteurs ont simulé une recherche aléatoire (RS) idéale. Cet algorithme parcourt les expressions uniques dans un ordre aléatoire, optimise leurs paramètres et les évalue. Cela sert de référence théorique pour mesurer l'efficacité de la PG, car la RS ne réévalue jamais deux fois la même expression unique.

C. Expérimentation avec la Programmation Génétique

Algorithmes : Ils ont utilisé deux implémentations de PG : TinyGP (une version simple et modifiable) et Operon (un système de pointe).
Données : Deux jeux de données réels de physique ont été utilisés :
1. Données de Nikuradse : Écoulement dans des tuyaux rugueux (relation entre frottement turbulent et rugosité).
2. Relation d'Accélération Radiale (RAR) : Dynamique galactique (lien entre accélération baryonique et dynamique totale).
Protocole : 50 exécutions indépendantes pour chaque configuration, avec des limites de longueur d'expression de 10, 12 et 20 nœuds.

3. Contributions Clés

Quantification de la redondance : Première étude permettant de mesurer précisément combien d'expressions évaluées par la PG sont des "duplicates" sémantiques (isomorphes) grâce à l'utilisation de l'équilibration d'égalité.
Comparaison PG vs Recherche Aléatoire sur espace unique : Démonstration que, dans des espaces limités, la PG est moins efficace qu'une simple recherche aléatoire parcourant uniquement les expressions uniques.
Analyse de l'exploration : Mise en évidence du fait que la PG explore une fraction infime de l'espace des solutions uniques et réévalue massivement des expressions déjà visitées.

4. Résultats

Les résultats obtenus sont alarmants pour l'efficacité de la PG dans ces contextes :

Faible taux de solutions uniques : La PG réévalue constamment des expressions sémantiquement identiques.
- Pour les limites de longueur 10 et 12, seulement 10 % à 20 % des expressions évaluées par la PG sont uniques après simplification.
- Environ 50 % des expressions générées pour les longueurs 10 et 12 se simplifient en un modèle constant trivial ( $p_1$ ), ce qui indique une exploration inefficace de régions non informatives.
Probabilité de succès inférieure à la recherche aléatoire :
- Pour atteindre un seuil de qualité donné (ex: MSE < 0.005 sur Nikuradse), la PG doit visiter un ordre de grandeur plus d'expressions que la recherche aléatoire idéale.
- La PG n'a jamais trouvé la solution globale optimale (la meilleure expression possible dans l'espace énuméré) sur aucun des jeux de données, même après 50 exécutions.
- La recherche aléatoire, elle, trouve systématiquement les meilleures solutions car elle ne gaspille pas de temps sur les redondances.
Échec à trouver les meilleurs modèles : Même en augmentant la limite de longueur à 20 nœuds (pour permettre à la PG de trouver des solutions plus complexes qui pourraient se simplifier), elle échoue toujours à trouver la solution optimale de longueur 12, alors que la recherche aléatoire sur l'espace de longueur 12 y parvient facilement.
Consistance des résultats : Les résultats sont similaires entre TinyGP et Operon, suggérant que ce n'est pas un artefact d'implémentation mais une propriété intrinsèque de la PG dans ces espaces.

5. Signification et Conclusion

L'article conclut que la Programmation Génétique est inefficace pour la régression symbolique dans des espaces de recherche limités, principalement à cause de deux facteurs :

La redondance massive : La PG génère et réévalue constamment des expressions qui sont mathématiquement équivalentes à celles déjà visitées.
L'exploration aveugle : Contrairement à une recherche aléatoire sur l'espace des formes uniques, la PG ne parvient pas à se concentrer efficacement sur les régions prometteuses de l'espace sémantique.

Implications :

Les chercheurs doivent reconsidérer l'efficacité de la PG standard pour la SR.
L'utilisation de mécanismes de déduplication sémantique (comme l'équilibration d'égalité) en temps réel ou la recherche directe dans l'espace des formes canoniques pourrait être cruciale pour améliorer les performances.
La question de savoir si la redondance aide à traverser des "plateaux neutres" pour atteindre des optima globaux reste ouverte, mais les résultats montrent que, dans les espaces restreints étudiés, le coût de cette redondance dépasse largement ses bénéfices potentiels.

En résumé, cette étude fournit une preuve empirique solide que, sans mécanismes avancés de gestion de la redondance sémantique, la PG gaspille une grande partie de son effort computationnel à réévaluer le même contenu mathématique sous différentes formes syntaxiques.