Algorithmes génétiques : exploration, diversité et convergence

Les algorithmes génétiques s'inspirent de certains mécanismes de l'évolution pour chercher de bonnes solutions à un problème. Une solution candidate est codée comme un génome, une fonction d'évaluation attribue une performance, puis une nouvelle génération est produite par sélection, croisement et mutation.

La sélection favorise les candidats performants, mais une pression excessive peut éliminer trop vite la diversité. La mutation introduit des variations; le croisement combine des fragments. L'efficacité dépend du codage et de la manière dont ces opérateurs respectent la structure du problème.

Il est tentant de décrire l'évolution de la population comme une spirale vers l'optimum. Cette image n'est pas générale. L'espace des solutions peut être discontinu, trompeur ou composé de nombreux bassins. La population peut stagner, perdre sa diversité, osciller entre régions ou converger vers une solution locale médiocre.

Les meilleurs algorithmes surveillent donc plusieurs indicateurs : meilleure performance, performance moyenne, diversité génétique et stabilité. Des méthodes de maintien de diversité, de nichage ou d'élitisme contrôlé peuvent préserver plusieurs pistes. Dans l'optimisation multiobjectif, on cherche un front de Pareto plutôt qu'un unique optimum.

Les algorithmes génétiques sont particulièrement utiles lorsque les dérivées sont indisponibles, lorsque les variables sont mixtes ou lorsque la structure du problème permet des opérateurs spécialisés. Ils peuvent toutefois exiger beaucoup d'évaluations. Une comparaison honnête avec des méthodes plus simples est indispensable.

La métaphore biologique a aussi ses limites. L'évolution naturelle n'optimise pas une fonction globale fixe; les environnements changent, les organismes interagissent et la reproduction est beaucoup plus complexe. L'algorithme emprunte une idée de variation et sélection, puis la transforme en outil d'ingénierie.

Le lien avec le projet est la convergence adaptative. Une population explore, se diversifie puis concentre progressivement ses efforts. Cette dynamique peut être représentée de multiples façons, mais aucune spirale caractéristique n'est attendue sans choix de projection particulier.

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.

Pour comprendre les opérateurs, choisissons un problème volontairement élémentaire : maximiser le nombre de 1 dans un mot binaire. Le mot est le génome ; son nombre de 1 est sa performance. Cette fonction, souvent appelée OneMax, rend chaque calcul vérifiable à la main. Elle ne représente ni un organisme réel ni un problème industriel complet. Le codage, l’évaluation et les règles de reproduction sont trois choix distincts ; la famille des algorithmes génétiques les organise dans une recherche sur des populations. ^[1]

Les parents 10110100 et 01101011 ont respectivement quatre et cinq bits à 1. Une coupure après la quatrième position échange leurs dernières moitiés : les enfants deviennent 10111011, de performance six, et 01100100, de performance trois. Le croisement n’améliore donc pas nécessairement chaque enfant. Une mutation qui change le dernier bit du meilleur enfant en 0 fait redescendre son score à cinq. La variation produit des possibilités ; seule l’évaluation permet de savoir lesquelles sont favorables pour la fonction choisie.

Le laboratoire suit 32 génomes de 16 bits pendant 40 générations. Deux candidats tirés au hasard participent à chaque tournoi de sélection ; le meilleur fournit un parent. Les enfants subissent un croisement et des mutations indépendantes. Un exemplaire du meilleur génome est conservé intact : c’est l’élitisme utilisé ici. La graine 37 rend l’expérience reproductible. La courbe du meilleur score ne peut pas baisser avec cette règle, alors que la moyenne peut temporairement diminuer.

La seconde courbe mesure la diversité : pⱼ est la proportion de 1 à la position j. Une position fixée à 0 ou à 1 contribue zéro ; un partage moitié-moitié contribue 0,5. Ainsi, une population presque identique peut avoir un excellent score moyen tout en explorant très peu. Augmenter la mutation entretient des variations, mais peut aussi défaire de bons génomes. Le curseur montre ce compromis sur un seul problème simple ; une trajectoire favorable ne prouve ni la rapidité sur d’autres problèmes ni une garantie générale d’atteindre l’optimum.

Construisons maintenant une fonction-piège sur trois bits. Le score vaut trois pour 000, deux avec un seul 1, un avec deux 1, et quatre pour 111. Partir de 000 et n’accepter que les changements d’un bit qui améliorent le score bloque immédiatement la recherche : tous les voisins ont un score inférieur. Pourtant, 111 est meilleur. Il faut franchir une baisse intermédiaire ou produire un saut plus grand. Le dessin ne représente pas un terrain physique : ses abscisses regroupent les génomes par leur nombre de 1.

Cette petite table explique pourquoi diversité, mutation et recombinaison peuvent être utiles sans devenir des solutions magiques. Si tous les parents valent déjà 000, leur croisement produit encore 000 : recombiner n’invente pas un allèle absent. Une mutation peut l’introduire, mais la sélection peut aussitôt l’éliminer. Pour diagnostiquer une stagnation, on examine donc ensemble les scores, les génomes et les opérateurs, au lieu de qualifier de convergence toute courbe qui cesse de monter. L’arrêt observé peut correspondre à une réussite, à un optimum local ou à une exploration épuisée.

Supposons que l’on minimise à la fois coût et durée. Une solution domine une autre si elle n’est moins bonne sur aucun objectif et est strictement meilleure sur au moins un. Dans notre échantillon fictif, le point (1,8) domine (5,8) : même durée, coût plus faible. En revanche, (1,8) et (2,6) sont incomparables, car gagner en durée coûte davantage. Les points non dominés constituent le front de cet échantillon, pas nécessairement celui de toutes les solutions possibles. Les algorithmes multiobjectifs comme NSGA-II cherchent à maintenir un ensemble de compromis. ^[2]

La question finale appartient au problème posé : quel compromis est acceptable, quelles contraintes sont impératives, et quelle incertitude affecte l’évaluation ? Dessiner la suite des solutions en spirale dans ce plan ne répond à aucune de ces questions. Un front peut être courbe, fragmenté ou discontinu sans suivre une spirale. La convergence algorithmique concerne le comportement d’une recherche et sa qualité relativement à un objectif ; la forme du dessin ne constitue pas un critère d’optimalité.

Le point de départ est concret: une recherche par population où variation et sélection déplacent progressivement les solutions. Un algorithme génétique maintient une population de candidats, évalue leur aptitude, puis applique sélection, croisement et mutation. La convergence vers une bonne solution dépend du paysage d’aptitude, de la diversité et de la pression de sélection. Une trajectoire en spirale dans l’espace des paramètres est une visualisation possible, pas une loi de l’évolution. Cette première distinction est importante, car une forme enroulée peut être une trajectoire, une structure, une projection ou une simple convention graphique.

Le modèle doit préciser la représentation des chromosomes, la fonction d’aptitude et la règle de variation. Une population peut se rapprocher d’un optimum local puis perdre sa diversité; une mutation plus forte peut explorer mais ralentir la stabilisation. « Converger » exige donc un critère explicite et une comparaison avec d’autres méthodes. Le modèle n’est pas l’objet: c’est une description dont les hypothèses doivent rester visibles.

Sur une fonction à deux paramètres, on peut tracer tous les individus à chaque génération. Certains nuages tournent autour d’une vallée d’aptitude, mais cette spirale peut venir de la projection, de la corrélation des variables ou du choix de l’échelle. La dynamique réelle se lit aussi dans diversité et fitness. Le contre-exemple est aussi instructif que l’exemple: il montre quelle variable manque lorsqu’on passe d’un domaine à l’autre.

Un test honnête répète les runs avec plusieurs graines et compare meilleur score, score moyen, diversité et coût de calcul. Une seule exécution réussie ne démontre pas la robustesse. Les graphiques doivent distinguer données simulées, solution connue et hypothèse de modèle. Une figure quantitative doit distinguer données publiées, calcul théorique, simulation et schéma conceptuel.

Pour comprendre une recherche par population où variation et sélection déplacent progressivement les solutions, il faut séparer au moins la variable qui tourne, celle qui change d’échelle et celle qui transporte l’information ou la matière. Un algorithme génétique maintient une population de candidats, évalue leur aptitude, puis applique sélection, croisement et mutation. La convergence vers une bonne solution dépend du paysage d’aptitude, de la diversité et de la pression de sélection. Une trajectoire en spirale dans l’espace des paramètres est une visualisation possible, pas une loi de l’évolution. Une forme globale peut rester stable alors que les éléments qui la composent se remplacent; à l’inverse, une trajectoire peut changer de forme sans que le mécanisme local soit nouveau.

La métaphore spirale est utile pour parler d’exploration puis de resserrement, mais la sélection génétique n’est pas un mouvement angulaire. Le mécanisme est stochastique et populationnel. La convergence peut être fonctionnelle sans prendre une forme géométrique. On ne peut donc pas conclure à partir d’une image seule. Il faut demander quelle observation ferait échouer l’hypothèse, puis conserver les résultats négatifs dans la comparaison. Cette discipline est particulièrement importante lorsque plusieurs modèles produisent une silhouette voisine.

Un test honnête répète les runs avec plusieurs graines et compare meilleur score, score moyen, diversité et coût de calcul. Une seule exécution réussie ne démontre pas la robustesse. Les graphiques doivent distinguer données simulées, solution connue et hypothèse de modèle. Pour rendre le résultat contrôlable, il faut conserver les paramètres, les unités, la résolution, les conditions initiales et la méthode de calcul. Une visualisation interactive doit aussi offrir un état initial lisible et un bouton de réinitialisation; sinon le lecteur voit un résultat sans pouvoir en comprendre la dépendance.

Le modèle présenté explique le modèle doit préciser la représentation des chromosomes, la fonction d’aptitude et la règle de variation. une population peut se rapprocher d’un optimum local puis perdre sa diversité; une mutation plus forte peut explorer mais ralentir la stabilisation. « converger » exige donc un critère explicite et une comparaison avec d’autres méthodes. mais il ne répond pas à toutes les échelles. Il reste à préciser comment les conditions initiales, les perturbations et les limites du système modifient le motif. C’est là que commence la recherche: non pas en ajoutant une analogie, mais en formulant une prédiction qui pourrait être mesurée.

La métaphore spirale est utile pour parler d’exploration puis de resserrement, mais la sélection génétique n’est pas un mouvement angulaire. Le mécanisme est stochastique et populationnel. La convergence peut être fonctionnelle sans prendre une forme géométrique. ^[3]

La relation avec la thèse du site est précise: une recherche par population où variation et sélection déplacent progressivement les solutions peut partager une géométrie, une dynamique ou une représentation avec une autre famille de phénomènes, mais ces niveaux ne sont pas identiques. La comparaison devient scientifique lorsqu’elle nomme le mécanisme commun supposé, les variables qui diffèrent et le test qui permettrait de les départager.