Algorithmes génétiques et calcul évolutionniste

• Introduction
• Qu'est-ce qu'un algorithme génétique ?
• Un bref historique des algorithmes génétiques
• Quelles sont les forces des algorithmes génétiques ?
• Quelles sont les limites des algorithmes génétiques ?
• Quelques exemples spécifiques d'algorithmes génétiques
• Arguments créationnistes
• Conclusion
• Références et ressources

Introduction

Sommaire

Les créationnistes affirment parfois que l'évolution est inutile en tant que théorie scientifique car elle ne produit aucun avantage pratique et n'a aucune pertinence pour la vie quotidienne. Cependant, les seules preuves de la biologie montrent que cette affirmation est fausse. Il existe de nombreux phénomènes naturels pour lesquels l'évolution nous fournit un fondement théorique solide. Pour ne citer qu'un exemple, le développement observé de la résistance - aux insecticides chez les ravageurs des cultures, aux antibiotiques chez les bactéries, à la chimiothérapie chez les cellules cancéreuses, et aux médicaments anti-rétroviraux chez des virus tels que le VIH - est une conséquence directe des lois de la mutation et de la sélection, et la compréhension de ces principes nous a aidés à élaborer des stratégies pour faire face à ces organismes nuisibles. Le postulat évolutionniste de la descendance commune a contribué au développement de nouveaux médicaments et techniques médicaux en donnant aux chercheurs une bonne idée des organismes sur lesquels ils devraient expérimenter pour obtenir des résultats les plus susceptibles d'être pertinents pour les humains. Enfin, le principe de l'élevage sélectif a été utilisé avec grand succès par les humains pour créer des organismes personnalisés, sans équivalent dans la nature, à leur propre avantage. L'exemple canonique, bien sûr, est la multitude de variétés de chiens domestiqués (des races aussi diverses que les bulldogs, les chihuahuas et les dachshunds ont été produites à partir de loups en seulement quelques milliers d'années), mais des exemples moins connus incluent le maïs cultivé (très différent de ses parents sauvages, aucun desquels ne possède les « épis » familiers du maïs cultivé par l'homme), les poissons rouges (comme les chiens, nous avons élevé des variétés qui ressemblent de manière spectaculaire différente du type sauvage), et les vaches laitières (avec des mamelles immenses bien plus grandes que ce qui serait nécessaire uniquement pour nourrir la progéniture).

Les critiques pourraient affirmer que les créationnistes peuvent expliquer ces choses sans avoir recours à l'évolution. Par exemple, les créationnistes expliquent souvent le développement de la résistance aux agents antibiotiques chez les bactéries, ou les changements apportés aux animaux domestiques par la sélection artificielle, en supposant que Dieu a décidé de créer des organismes en groupes fixes, appelés « genres » ou baramin. Bien que la microévolution naturelle ou la sélection artificielle guidée par l'homme puisse engendrer différentes variétés au sein de l'« espèce-chien » originellement créée, ou de l'« espèce-vache », ou de l'« espèce-bactérie » (!), aucune quantité de temps ou de changement génétique ne peut transformer un « genre » en un autre. Cependant, la manière exacte dont les créationnistes déterminent ce qu'est un « genre », ou le mécanisme qui empêche les êtres vivants d'évoluer au-delà de ses limites, n'est jamais expliquée.

Mais au cours des dernières décennies, les progrès continus de la technologie moderne ont apporté quelque chose de nouveau. L'évolution produit désormais des avantages pratiques dans un domaine très différent, et cette fois, les créationnistes ne peuvent pas affirmer que leur explication s'accorde aussi bien avec les faits. Ce domaine est l'informatique, et les avantages proviennent d'une stratégie de programmation appelée algorithmes génétiques. Cet essai expliquera ce que sont les algorithmes génétiques et montrera comment ils sont pertinents pour le débat sur l'évolution/le créationnisme.

Qu'est-ce qu'un algorithme génétique ?

Haut

• Méthodes de représentation
• Méthodes de sélection
• Méthodes de changement
• Autres techniques de résolution de problèmes

De manière concise, un algorithme génétique (ou AG pour abrégé) est une technique de programmation qui imite l'évolution biologique en tant que stratégie de résolution de problèmes. Étant donné un problème spécifique à résoudre, l'entrée de l'AG est un ensemble de solutions potentielles à ce problème, encodées d'une certaine manière, et une mesure appelée une fonction d'aptitude qui permet à chaque candidat d'être évalué quantitativement. Ces candidats peuvent être des solutions déjà connues pour fonctionner, l'objectif de l'AG étant de les améliorer, mais plus souvent ils sont générés au hasard.

Le GA évalue ensuite chaque candidat selon la fonction de fitness. Dans un pool de candidats générés aléatoirement, bien sûr, la plupart ne fonctionneront pas du tout et seront supprimés. Cependant, purement par hasard, quelques-uns peuvent promettre quelque chose - ils peuvent montrer une activité, même si elle est faible et imparfaite, en vue de résoudre le problème.

Ces candidats prometteurs sont conservés et autorisés à se reproduire. De multiples copies en sont faites, mais ces copies ne sont pas parfaites ; des changements aléatoires sont introduits lors du processus de copie. Ces descendants numériques passent ensuite à la génération suivante, formant un nouveau pool de solutions candidates, et sont soumis à une seconde évaluation de leur aptitude. Les solutions candidates qui ont été dégradées, ou qui ne se sont pas améliorées, par les modifications apportées à leur code sont à nouveau supprimées ; mais là encore, purement par hasard, les variations aléatoires introduites dans la population peuvent avoir amélioré certains individus, les transformant en meilleures, plus complètes ou plus efficaces solutions au problème en jeu. Encore une fois, ces individus gagnants sont sélectionnés et copiés dans la génération suivante avec des changements aléatoires, et le processus se répète. L'attente est que l'aptitude moyenne de la population augmente à chaque tour, et donc en répétant ce processus pour des centaines ou des milliers de tours, de très bonnes solutions au problème peuvent être découvertes.

Qu'il puisse paraître étonnant et contre-intuitif à certains, les algorithmes génétiques se sont révélés être une stratégie de résolution de problèmes extrêmement puissante et efficace, démontrant de manière spectaculaire la puissance des principes évolutifs. Les algorithmes génétiques ont été utilisés dans une grande variété de domaines pour faire évoluer des solutions à des problèmes aussi difficiles, voire plus difficiles, que ceux auxquels font face les concepteurs humains. De plus, les solutions qu'ils produisent sont souvent plus efficaces, plus élégantes ou plus complexes que tout ce qu'un ingénieur humain pourrait produire de comparable. Dans certains cas, les algorithmes génétiques ont trouvé des solutions qui déroutent même les programmeurs qui ont écrit les algorithmes en premier lieu !

Méthodes de représentation

Avant qu'un algorithme génétique ne puisse être appliqué à un problème, une méthode est nécessaire pour encoder les solutions potentielles à ce problème sous une forme qu'un ordinateur peut traiter. Une approche courante consiste à encoder les solutions sous forme de chaînes binaires : des suites de 1 et de 0, où le chiffre à chaque position représente la valeur d'un certain aspect de la solution. Une autre approche, similaire, consiste à encoder les solutions sous forme de tableaux d'entiers ou de nombres décimaux, chaque position représentant à nouveau un aspect particulier de la solution. Cette approche permet une plus grande précision et complexité que la méthode relativement restreinte utilisant uniquement des nombres binaires et est souvent « plus intuitivement proche de l'espace du problème » (Fleming et Purshouse 2002, p. 1228).

Cette technique a été utilisée, par exemple, dans le travail de Steffen Schulze-Kremer, qui a écrit un algorithme génétique pour prédire la structure tridimensionnelle d'une protéine en fonction de la séquence d'acides aminés qui la composent (Mitchell 1996, p. 62). L'AG de Schulze-Kremer utilisait des nombres à virgule flottante pour représenter les si-dits « angles de torsion » entre les liaisons peptidiques qui relient les acides aminés. (Une protéine est constituée d'une séquence de blocs de base appelés acides aminés, qui sont joints les uns aux autres comme les maillons d'une chaîne. Une fois tous les acides aminés liés, la protéine se replie en une forme tridimensionnelle complexe en fonction des acides aminés qui s'attirent entre eux et de ceux qui se repoussent. La forme d'une protéine détermine sa fonction.) Les algorithmes génétiques pour l'entraînement de réseaux de neurones utilisent souvent cette méthode d'encodage également.

Une troisième approche consiste à représenter les individus dans un AG comme des chaînes de lettres, où chaque lettre représente à nouveau un aspect spécifique de la solution. Un exemple de cette technique est l'approche de « codage grammatical » de Hiroaki Kitano, où un AG a été chargé d'évoluer un ensemble simple de règles appelé une grammaire hors contexte, qui a ensuite été utilisé pour générer des réseaux de neurones pour divers problèmes (Mitchell 1996, p. 74).

Le mérite de ces trois méthodes est qu'elles permettent de définir facilement des opérateurs qui provoquent les changements aléatoires chez les candidats sélectionnés : inverser un 0 en un 1 ou vice versa, ajouter ou soustraire à la valeur d'un nombre une quantité choisie au hasard, ou remplacer une lettre par une autre. (Voir la section sur Méthodes de changement pour plus de détails sur les opérateurs génétiques.) Une autre stratégie, développée principalement par John Koza de l'Université de Stanford et appelée programmation génétique, représente les programmes sous forme de structures de données arborescentes appelées arbres (Koza et al. 2003, p. 35). Dans cette approche, des changements aléatoires peuvent être réalisés en modifiant l'opérateur ou en altérant la valeur d'un nœud donné dans l'arbre, ou en remplaçant un sous-arbre par un autre.

Figure 1 : Trois arbres de programmes simples du genre normalement utilisé en programmation génétique. L'expression mathématique que chacun représente est donnée en dessous.

Il est important de noter que les algorithmes évolutionnaires n'ont pas besoin de représenter les solutions candidates sous forme de chaînes de données de longueur fixe. Certains le font, mais d'autres non ; par exemple, l'encodage grammatical de Kitano, discuté ci-dessus, peut être efficacement mis à l'échelle pour créer de grands réseaux de neurones complexes, et les arbres de programmation génétique de Koza peuvent grandir arbitrairement tant que nécessaire pour résoudre le problème auquel ils sont appliqués.

Méthodes de sélection

Il existe de nombreuses techniques différentes qu'un algorithme génétique peut utiliser pour sélectionner les individus à copier dans la génération suivante, mais les méthodes les plus courantes sont listées ci-dessous. Certaines de ces méthodes sont mutuellement exclusives, tandis que d'autres peuvent et sont souvent utilisées en combinaison.

Sélection élitiste : Les membres les plus aptes de chaque génération sont garantis d'être sélectionnés. (La plupart des AG ne utilisent pas l'élitisme pur, mais plutôt une forme modifiée où le meilleur individu, ou quelques-uns des meilleurs, de chaque génération sont copiés dans la génération suivante au cas où rien de mieux ne se présenterait.)

Sélection proportionnelle à l'aptitude : Les individus plus aptes ont plus de chances, mais pas de certitude, d'être sélectionnés.

Sélection à la roue : Une forme de sélection proportionnelle à la fitness dans laquelle la probabilité qu'un individu soit sélectionné est proportionnelle à l'ampleur par laquelle sa fitness est supérieure ou inférieure à celle de ses concurrents. (Conceptuellement, cela peut être représenté comme un jeu de roulette : chaque individu obtient une tranche de la roue, mais ceux qui sont plus aptes obtiennent des tranches plus grandes que ceux qui le sont moins. La roue est ensuite lancée, et l'individu qui « possède » la section sur laquelle elle atterrit à chaque fois est choisi.)

Échelle de sélection : À mesure que la fitness moyenne de la population augmente, l'intensité de la pression de sélection augmente également et la fonction de fitness devient plus discriminante. Cette méthode peut être utile pour effectuer la meilleure sélection plus tard lorsque tous les individus ont une fitness relativement élevée et que seules de petites différences de fitness distinguent les uns des autres.

Sélection par tournoi : Des sous-groupes d'individus sont choisis parmi la population plus large, et les membres de chaque sous-groupe s'affrontent entre eux. Seule une personne issue de chaque sous-groupe est choisie pour se reproduire.

Sélection par rang : Chaque individu de la population est attribué un rang numérique en fonction de sa fitness, et la sélection est basée sur ce classement plutôt que sur les différences absolues de fitness. L'avantage de cette méthode est qu'elle peut empêcher les individus très aptes de gagner la dominance tôt au détriment des moins aptes, ce qui réduirait la diversité génétique de la population et pourrait entraver les tentatives de trouver une solution acceptable.

Sélection générationnelle : La descendance des individus sélectionnés à chaque génération constitue l'intégralité de la génération suivante. Aucun individu n'est conservé entre les générations.

Sélection à l'état stationnaire : La descendance des individus sélectionnés à chaque génération retourne dans le pool génétique préexistant, remplaçant certains membres moins aptes de la génération précédente. Certains individus sont conservés d'une génération à l'autre.

Sélection hiérarchique : Les individus passent par plusieurs tours de sélection à chaque génération. Les évaluations de niveau inférieur sont plus rapides et moins discriminantes, tandis que celles qui survivent aux niveaux supérieurs sont évaluées plus rigoureusement. L'avantage de cette méthode est qu'elle réduit le temps de calcul global en utilisant une évaluation plus rapide et moins sélective pour éliminer la majorité des individus qui ne montrent aucun ou peu de promesses, et en ne soumettant que ceux qui survivent à ce test initial à une évaluation de fitness plus rigoureuse et plus coûteuse en termes de calcul.

Méthodes de changement

Une fois que la sélection a choisi les individus aptes, ceux-ci doivent être modifiés aléatoirement dans l'espoir d'améliorer leur aptitude pour la génération suivante. Il existe deux stratégies de base pour accomplir cela. La première et la plus simple est appelée mutation. Tout comme la mutation chez les êtres vivants change un gène en un autre, la mutation dans un algorithme génétique provoque de petites altérations à des points uniques du code d'un individu.

La deuxième méthode s'appelle crossover et consiste à choisir deux individus pour échanger des segments de leur code, produisant des « descendants » artificiels qui sont des combinaisons de leurs parents. Ce processus vise à simuler le processus analogue de recombination qui se produit chez les chromosomes lors de la reproduction sexuée. Les formes courantes de crossover incluent le crossover à point unique, dans lequel un point d'échange est défini à une position aléatoire dans les génomes des deux individus, et un individu contribue à l'ensemble de son code avant ce point tandis que l'autre contribue à l'ensemble de son code après ce point pour produire un descendant, et le crossover uniforme, dans lequel la valeur à une position donnée dans le génome du descendant est soit la valeur du génome d'un parent à cette position, soit la valeur du génome de l'autre parent à cette position, choisie avec une probabilité de 50/50.

Figure 2 : Recombination et mutation. Les diagrammes ci-dessus illustrent l'effet de chacun de ces opérateurs génétiques sur des individus d'une population de chaînes de 8 bits. Le diagramme supérieur montre deux individus soumis à une recombination à un seul point ; le point d'échange est fixé entre la cinquième et la sixième positions du génome, produisant un nouvel individu qui est un hybride de ses ancêtres. Le deuxième diagramme montre un individu soumis à une mutation à la position 4, changeant le 0 à cette position dans son génome en un 1.

Autres techniques de résolution de problèmes

Avec l'émergence de l'informatique de vie artificielle et le développement de méthodes heuristiques, d'autres techniques de résolution de problèmes informatisées sont apparues qui présentent, à certains égards, des similitudes avec les algorithmes génétiques. Cette section explique certaines de ces techniques, les points dans lesquels elles ressemblent aux AG et les points dans lesquels elles diffèrent.

• Les réseaux de neurones
  Un réseau de neurones, ou « réseau neuronal » pour faire court, est une méthode de résolution de problèmes basée sur un modèle informatique de la façon dont les neurones sont connectés dans le cerveau. Un réseau de neurones est constitué de couches d'unités de traitement appelées nœuds reliés par des liens directionnels : une couche d'entrée, une couche de sortie, et zéro ou plusieurs couches cachées entre les deux. Un motif initial d'entrée est présenté à la couche d'entrée du réseau de neurones, et les nœuds stimulés transmettent ensuite un signal aux nœuds de la couche suivante à laquelle ils sont connectés. Si la somme de toutes les entrées entrant dans l'un de ces neurones virtuels est supérieure au seuil d'activation de ce neurone, celui-ci s'active lui-même et transmet son propre signal aux neurones de la couche suivante. Le motif d'activation se propage donc vers l'avant jusqu'à atteindre la couche de sortie, où il est renvoyé en tant que solution à l'entrée présentée. Tout comme dans le système nerveux des organismes biologiques, les réseaux de neurones apprennent et affinent leurs performances au fil du temps via des cycles répétés d'ajustement de leurs seuils jusqu'à ce que la sortie réelle corresponde à la sortie souhaitée pour toute entrée donnée. Ce processus peut être supervisé par un expérimentateur humain ou peut fonctionner automatiquement en utilisant un algorithme d'apprentissage (Mitchell 1996, p. 52). Des algorithmes génétiques ont été utilisés à la fois pour construire et pour entraîner les réseaux de neurones.

Figure 3 : Un réseau de neurones simple en avant, avec une couche d'entrée composée de quatre neurones, une couche cachée composée de trois neurones, et une couche de sortie composée de quatre neurones. Le nombre sur chaque neurone représente son seuil d'activation : il ne se déclenchera que s'il reçoit au moins ce nombre d'entrées. Le schéma montre le réseau de neurones recevant une chaîne d'entrée et illustre comment l'activation se propage en avant à travers le réseau pour produire une sortie.

• Escalade
  Similaire aux algorithmes génétiques, bien que plus systématique et moins aléatoire, un algorithme d'escalade commence par une solution initiale au problème en jeu, généralement choisie au hasard. La chaîne est ensuite mutée, et si la mutation entraîne une meilleure aptitude pour la nouvelle solution que pour la précédente, la nouvelle solution est conservée ; sinon, la solution actuelle est maintenue. L'algorithme est ensuite répété jusqu'à ce qu'aucune mutation ne puisse être trouvée qui entraîne une augmentation de l'aptitude de la solution actuelle, et cette solution est retournée comme résultat (Koza et al. 2003, p. 59). (Pour comprendre d'où vient le nom de cette technique, imaginez que l'espace de toutes les solutions possibles à un problème donné est représenté comme un paysage de contours en trois dimensions. Un ensemble de coordonnées donné sur ce paysage représente une solution particulière. Les solutions qui sont meilleures sont plus élevées en altitude, formant des collines et des sommets ; celles qui sont moins bonnes sont plus basses en altitude, formant des vallées. Un « escaladeur » est alors un algorithme qui commence à un point donné sur le paysage et monte inexorablement vers le haut.) L'escalade est ce qu'on appelle un algorithme glouton, ce qui signifie qu'il fait toujours le meilleur choix disponible à chaque étape dans l'espoir que le meilleur résultat global puisse être atteint de cette manière. Par contraste, des méthodes telles que les algorithmes génétiques et le recuit simulé, discutées ci-dessous, ne sont pas gloutons ; ces méthodes font parfois des choix sous-optimaux dans l'espoir qu'ils mènent à de meilleures solutions plus tard.
  
  
• Recuit simulé
  Une autre technique d'optimisation similaire aux algorithmes évolutifs est connue sous le nom de recuit simulé. L'idée emprunte son nom au processus industriel de recuit dans lequel un matériau est chauffé au-dessus d'un point critique pour le ramollir, puis refroidi progressivement afin d'effacer les défauts de sa structure cristalline, produisant une disposition de réseau atomique plus stable et régulière (Haupt et Haupt 1998, p. 16). Dans le recuit simulé, comme dans les algorithmes génétiques, il existe une fonction d'aptitude qui définit un paysage d'aptitude ; cependant, plutôt qu'une population de candidats comme dans les AG, il n'y a qu'une seule solution candidate. Le recuit simulé ajoute également le concept de « température », une quantité numérique globale qui diminue progressivement au fil du temps. À chaque étape de l'algorithme, la solution mute (ce qui équivaut à se déplacer vers un point adjacent du paysage d'aptitude). L'aptitude de la nouvelle solution est ensuite comparée à l'aptitude de la solution précédente ; si elle est plus élevée, la nouvelle solution est conservée. Sinon, l'algorithme prend une décision de conserver ou de rejeter la solution en fonction de la température. Si la température est élevée, comme c'est le cas initialement, même les changements qui entraînent des diminutions significatives de l'aptitude peuvent être conservés et utilisés comme base pour le prochain tour de l'algorithme, mais à mesure que la température diminue, l'algorithme devient de plus en plus enclin à n'accepter que les changements augmentant l'aptitude. Finalement, la température atteint zéro et le système « se fige » ; quelle que soit la configuration dans laquelle il se trouve à ce moment-là, elle devient la solution. Le recuit simulé est souvent utilisé pour des applications de conception en ingénierie, telles que la détermination de la disposition physique des composants sur une puce informatique (Kirkpatrick, Gelatt et Vecchi 1983).

Une brève histoire des AG

Haut

Les premiers exemples de ce qui pourrait aujourd'hui être appelé des algorithmes génétiques sont apparus à la fin des années 1950 et au début des années 1960, programmés sur ordinateur par des biologistes de l'évolution qui cherchaient explicitement à modéliser des aspects de l'évolution naturelle. Aucun d'eux ne se rendit compte que cette stratégie pourrait être plus généralement applicable à des problèmes artificiels, mais cette reconnaissance ne tarda pas à venir : « Le calcul évolutionniste était définitivement dans l'air dans les jours formateurs de l'ordinateur électronique » (Mitchell 1996, p.2). En 1962, des chercheurs tels que G.E.P. Box, G.J. Friedman, W.W. Bledsoe et H.J. Bremermann avaient tous indépendamment développé des algorithmes inspirés de l'évolution pour l'optimisation de fonctions et l'apprentissage automatique, mais leur travail n'a attiré peu de suivi. Un développement plus réussi dans ce domaine est venu en 1965, lorsque Ingo Rechenberg, alors de l'Université technique de Berlin, a introduit une technique qu'il a appelée stratégie d'évolution, bien qu'elle soit plus similaire aux montées de cote qu'aux algorithmes génétiques. Dans cette technique, il n'y avait pas de population ou de croisement ; un parent était muté pour produire un seul descendant, et le meilleur des deux était conservé et devenait le parent pour le prochain tour de mutation (Haupt et Haupt 1998, p.146). Des versions ultérieures ont introduit l'idée d'une population. Les stratégies d'évolution sont toujours employées aujourd'hui par des ingénieurs et des scientifiques, en particulier en Allemagne.

Le prochain développement important dans ce domaine est survenu en 1966, lorsque L.J. Fogel, A.J. Owens et M.J. Walsh ont introduit aux États-Unis une technique qu'ils ont appelée programmation évolutive. Dans cette méthode, les solutions candidates aux problèmes étaient représentées comme des machines à états finis simples ; comme la stratégie évolutive de Rechenberg, leur algorithme fonctionnait en mutant aléatoirement l'une de ces machines simulées et en conservant la meilleure des deux (Mitchell 1996, p.2 ; Goldberg 1989, p.105). Comme les stratégies évolutives, une formulation plus large de la technique de programmation évolutive reste aujourd'hui un domaine de recherche en cours. Cependant, ce qui manquait encore à ces deux méthodologies était la reconnaissance de l'importance du croisement.

Dès 1962, les travaux de John Holland sur les systèmes adaptatifs ont posé les bases des développements ultérieurs ; notamment, Holland a été le premier à proposer explicitement l'opérateur de croisement et d'autres opérateurs de recombinaison. Cependant, les travaux fondateurs dans le domaine des algorithmes génétiques sont apparus en 1975 avec la publication du livre Adaptation in Natural and Artificial Systems. S'appuyant sur des recherches et des articles antérieurs tant de la part de Holland lui-même que de collègues de l'Université du Michigan, ce livre fut le premier à présenter de manière systématique et rigoureuse le concept de systèmes numériques adaptatifs utilisant la mutation, la sélection et le croisement, simulant ainsi les processus de l'évolution biologique, en tant que stratégie de résolution de problèmes. Le livre a également tenté de poser les algorithmes génétiques sur des bases théoriques solides en introduisant la notion de schémas (Mitchell 1996, p.3 ; Haupt et Haupt 1998, p.147). La même année, la thèse importante de Kenneth De Jong a établi le potentiel des AG en démontrant qu'ils pouvaient performer bien sur une grande variété de fonctions de test, y compris des paysages de recherche bruyants, discontinus et multimodaux (Goldberg 1989, p.107).

Ces œuvres fondatrices ont suscité un intérêt plus large pour l'informatique évolutionniste. Au début et au milieu des années 1980, les algorithmes génétiques étaient appliqués à une vaste gamme de sujets, allant de problèmes mathématiques abstraits comme le bin-packing et la coloration de graphes à des problèmes d'ingénierie concrets tels que la régulation du flux dans les pipelines, la reconnaissance et la classification de motifs, ainsi que l'optimisation structurelle (Goldberg 1989, p. 128).

À première vue, ces applications étaient principalement théoriques. Cependant, à mesure que la recherche continuait à se multiplier, les algorithmes génétiques se sont répandus dans le secteur commercial, leur essor étant alimenté par la croissance exponentielle de la puissance de calcul et le développement d'Internet. Aujourd'hui, le calcul évolutionniste est un domaine florissant, et les algorithmes génétiques « résolvent des problèmes d'intérêt quotidien » (Haupt et Haupt 1998, p. 147) dans des domaines d'étude aussi divers que la prédiction des marchés boursiers et la planification de portefeuilles, l'ingénierie aérospatiale, la conception de microprocesseurs, la biochimie et la biologie moléculaire, ainsi que la planification des horaires dans les aéroports et les chaînes d'assemblage. La puissance de l'évolution a touché pratiquement tous les domaines que l'on peut nommer, façonnant le monde qui nous entoure de manière invisible à des milliers de façons, et de nouveaux usages continuent d'être découverts à mesure que la recherche progresse. Et au cœur de tout cela se trouve rien de plus que la simple et puissante intuition de Charles Darwin : que le hasard aléatoire des variations, couplé à la loi de la sélection, est une technique de résolution de problèmes d'une puissance immense et d'une application presque illimitée.

Quelles sont les forces des AG ?

Haut

• Le premier et le plus important point est que les algorithmes génétiques sont intrinsèquement parallèles. La plupart des autres algorithmes sont sériels et ne peuvent explorer l'espace des solutions d'un problème que dans une seule direction à la fois ; et si la solution qu'ils découvrent s'avère sous-optimale, il n'y a rien à faire d'autre qu'abandonner tout le travail précédemment accompli et recommencer. Cependant, puisque les AG ont plusieurs descendants, ils peuvent explorer l'espace des solutions dans plusieurs directions en même temps. Si un chemin s'avère être une impasse, ils peuvent facilement l'éliminer et continuer leur travail sur des pistes plus prometteuses, leur offrant ainsi une plus grande chance à chaque exécution de trouver la solution optimale.
  
  Cependant, l'avantage du parallélisme va au-delà de cela. Considérez ce qui suit : toutes les chaînes binaires de 8 chiffres (chaînes de 0 et de 1) forment un espace de recherche, qui peut être représenté par ******** (où le * représente "soit 0 soit 1"). La chaîne 01101010 est un membre de cet espace. Cependant, elle est également un membre de l'espace 0*******, de l'espace 01******, de l'espace 0******0, de l'espace 0*1*1*1*, de l'espace 01*01**0, et ainsi de suite. En évaluant la fitness de cette chaîne particulière, un algorithme génétique échantillonnerait chacun de ces nombreux espaces auxquels elle appartient. Au fil de nombreuses telles évaluations, il construirait une valeur de plus en plus précise pour la moyenne de la fitness de chacun de ces espaces, chacun ayant de nombreux membres. Par conséquent, un AG qui évalue explicitement un petit nombre d'individus évalue implicitement un groupe beaucoup plus grand d'individus - tout comme un sondage qui pose des questions à un certain membre d'un groupe ethnique, religieux ou social espère apprendre quelque chose sur les opinions de tous les membres de ce groupe, et peut donc prédire de manière fiable l'opinion nationale en échantillonnant seulement un petit pourcentage de la population. De la même manière, l'AG peut "se concentrer" sur l'espace contenant les individus de plus haute fitness et trouver le meilleur d'entre eux dans ce groupe. Dans le contexte des algorithmes évolutionnistes, cela est connu sous le nom de Théorème du Schéma, et constitue l'"avantage central" d'un AG par rapport à d'autres méthodes de résolution de problèmes (Holland 1992, p. 68 ; Mitchell 1996, p. 28-29 ; Goldberg 1989, p. 20).
  
  
• En raison du parallélisme qui leur permet d'évaluer implicitement de nombreux schémas en même temps, les algorithmes génétiques sont particulièrement adaptés pour résoudre des problèmes où l'espace de toutes les solutions potentielles est vraiment immense - trop vaste pour être exploré exhaustivement en un temps raisonnable. La plupart des problèmes relevant de cette catégorie sont connus sous le nom de « problèmes non linéaires ». Dans un problème linéaire, l'aptitude de chaque composant est indépendante, de sorte que toute amélioration apportée à une partie quelconque entraînera une amélioration du système dans son ensemble. Inutile de le dire, peu de problèmes du monde réel sont de cette nature. La non-linéarité est la norme, où modifier un composant peut avoir des effets en cascade sur l'ensemble du système, et où plusieurs modifications qui, individuellement, sont préjudiciables peuvent conduire à des améliorations bien plus importantes de l'aptitude lorsqu'elles sont combinées. La non-linéarité entraîne une explosion combinatoire : l'espace des chaînes binaires de 1 000 chiffres peut être exploré exhaustivement en évaluant seulement 2 000 possibilités si le problème est linéaire, alors que s'il est non linéaire, une exploration exhaustive nécessite d'évaluer 2¹⁰⁰⁰ possibilités - un nombre qui prendrait plus de 300 chiffres pour être écrit en entier.
  
  Heureusement, le parallélisme implicite d'un AG lui permet de surmonter même ce nombre énorme de possibilités, trouvant avec succès des résultats optimaux ou très bons en un court laps de temps après avoir échantillonné directement de petites régions du vaste paysage d'aptitude (Forrest 1993, p. 877). Par exemple, un algorithme génétique développé conjointement par des ingénieurs de General Electric et de l'Institut polytechnique de Rensselaer a produit une conception de turbine de moteur à réaction à haute performance qui était trois fois meilleure qu'une configuration conçue par un humain et 50 % meilleure qu'une configuration conçue par un système expert, en naviguant avec succès dans un espace de solutions contenant plus de 10³⁸⁷ possibilités. Les méthodes conventionnelles pour concevoir de telles turbines font partie intégrante de projets d'ingénierie qui peuvent prendre jusqu'à cinq ans et coûter plus de 2 milliards de dollars ; l'algorithme génétique a découvert cette solution après deux jours sur un poste de travail de bureau d'ingénierie typique (Holland 1992, p. 72).
  
  
• Un autre atout notable des algorithmes génétiques est leur bonne performance sur des problèmes pour lesquels le paysage de fitness est complexe — ceux où la fonction de fitness est discontinue, bruitée, évolue dans le temps ou présente de nombreux optima locaux. La plupart des problèmes pratiques ont un vaste espace de solutions, impossible à explorer exhaustivement ; le défi devient alors comment éviter les optima locaux — des solutions qui sont meilleures que toutes les autres similaires à elles, mais qui ne sont pas aussi bonnes que d'autres ailleurs dans l'espace de solutions. De nombreux algorithmes de recherche peuvent se faire piéger par des optima locaux : si ils atteignent le sommet d'une colline sur le paysage de fitness, ils découvriront qu'aucune meilleure solution n'existe à proximité et concluront qu'ils ont atteint la meilleure, même si des sommets plus élevés existent ailleurs sur la carte.
  
  Les algorithmes évolutionnaires, en revanche, se sont révélés efficaces pour échapper aux optima locaux et découvrir l'optimum global, même dans un paysage de fitness très accidenté et complexe. (Il convient de noter qu'en réalité, il n'y a généralement aucun moyen de savoir si une solution donnée à un problème est l'optimum global ou simplement un optimum local très élevé. Cependant, même si un AG ne livre pas toujours une solution parfaitement prouvée à un problème, il peut presque toujours fournir au moins une très bonne solution.) Les quatre composants majeurs d'un AG — le parallélisme, la sélection, la mutation et le croisement — travaillent ensemble pour accomplir cela. Au début, l'AG génère une population initiale diverse, jetant un « filet » sur le paysage de fitness. (Koza (2003, p. 506) compare cela à une armée de parachutistes atterrissant sur le paysage de l'espace de recherche d'un problème, chacun recevant l'ordre de trouver le sommet le plus élevé.) De petites mutations permettent à chaque individu d'explorer son voisinage immédiat, tandis que la sélection oriente les progrès, guidant la progéniture de l'algorithme vers des parties plus prometteuses de l'espace de solutions (Holland 1992, p. 68).
  
  Cependant, le croisement est l'élément clé qui distingue les algorithmes génétiques d'autres méthodes telles que les montées de cote et le recuit simulé. Sans croisement, chaque solution individuelle est seule, explorant l'espace de recherche dans son voisinage immédiat sans référence à ce que d'autres individus peuvent avoir découvert. En revanche, avec le croisement en place, il y a un transfert d'information entre les candidats réussis — les individus peuvent bénéficier de ce que les autres ont appris, et les schémas peuvent être mélangés et combinés, avec le potentiel de produire une progéniture qui possède les forces de ses deux parents et aucune de leurs faiblesses. Ce point est illustré dans Koza et al. 1999, p. 486, où les auteurs discutent d'un problème de synthèse d'un filtre passe-bas en utilisant la programmation génétique. Dans une génération, deux circuits parents ont été sélectionnés pour subir un croisement ; un parent avait une bonne topologie (composants tels que des inductances et des condensateurs aux bons endroits) mais une mauvaise dimensionnement (valeurs d'inductance et de capacité pour ses composants qui étaient beaucoup trop faibles). L'autre parent avait une mauvaise topologie, mais un bon dimensionnement. Le résultat de l'accouplement des deux par croisement a été une progéniture avec la bonne topologie d'un parent et le bon dimensionnement de l'autre, résultant en une amélioration substantielle de la fitness par rapport à ses deux parents.
  
  Le problème de trouver l'optimum global dans un espace avec de nombreux optima locaux est également connu sous le nom de dilemme de l'exploration vs. l'exploitation, « un problème classique pour tous les systèmes qui peuvent s'adapter et apprendre » (Holland 1992, p. 69). Une fois qu'un algorithme (ou un concepteur humain) a trouvé une stratégie de résolution de problèmes qui semble fonctionner de manière satisfaisante, devrait-il se concentrer sur l'utilisation optimale de cette stratégie, ou devrait-il chercher d'autres ? Abandonner une stratégie éprouvée pour en chercher de nouvelles est presque garanti d'impliquer des pertes et une dégradation des performances, du moins à court terme. Mais si l'on s'en tient à une stratégie particulière à l'exclusion de toutes les autres, on risque de ne pas découvrir de meilleures stratégies qui existent mais n'ont pas encore été trouvées. Encore une fois, les algorithmes génétiques se sont montrés très bons pour trouver cet équilibre et découvrir de bonnes solutions avec un temps et un effort de calcul raisonnables.
  
  
• Un autre domaine où les algorithmes génétiques excellent est leur capacité à manipuler plusieurs paramètres simultanément (Forrest 1993, p. 874). De nombreux problèmes du monde réel ne peuvent pas être énoncés en termes d'une seule valeur à minimiser ou maximiser, mais doivent être exprimés en termes de plusieurs objectifs, généralement avec des compromis impliqués : on ne peut améliorer l'un qu'au détriment de l'autre. Les AG sont très bons pour résoudre de tels problèmes : en particulier, leur utilisation du parallélisme leur permet de produire plusieurs solutions également bonnes au même problème, peut-être avec une solution candidate optimisant un paramètre et une autre candidate optimisant un paramètre différent (Haupt et Haupt 1998, p. 17), et un superviseur humain peut ensuite sélectionner l'un de ces candidats à utiliser. Si une solution particulière à un problème multiobjectif optimise un paramètre à un tel degré que ce paramètre ne peut être davantage amélioré sans causer une diminution correspondante de la qualité d'un autre paramètre, cette solution est appelée Pareto optimale ou non dominée (Coello 2000, p. 112).
  
  
• Enfin, l'une des qualités des algorithmes génétiques qui pourrait à première vue sembler être une faiblesse s'avère être l'une de leurs forces : à savoir, que les AG ne savent rien des problèmes auxquels ils sont déployés pour les résoudre. Au lieu d'utiliser des informations spécifiques au domaine déjà connues pour guider chaque étape et apporter des modifications avec un œil spécifique sur l'amélioration, comme le font les concepteurs humains, ils sont des « horlogers aveugles » (Dawkins 1996) ; ils apportent des modifications aléatoires à leurs solutions candidates et utilisent ensuite la fonction d'aptitude pour déterminer si ces modifications produisent une amélioration.
  
  La vertu de cette technique est qu'elle permet aux algorithmes génétiques de commencer avec un esprit ouvert, pour ainsi dire. Puisque leurs décisions sont basées sur le hasard, tous les chemins de recherche possibles sont théoriquement ouverts à un AG ; par contraste, toute stratégie de résolution de problèmes qui repose sur des connaissances antérieures doit inévitablement commencer par écarter de nombreux chemins a priori, manquant ainsi de toute solution nouvelle qui pourrait y exister (Koza et al. 1999, p. 547). Dépourvus de préconceptions basées sur des croyances établies sur « la façon dont les choses devraient être faites » ou sur ce qui « ne pourrait pas fonctionner », les AG ne rencontrent pas ce problème. De même, toute technique qui repose sur des connaissances antérieures s'effondrera lorsque ces connaissances ne seront pas disponibles, mais encore une fois, les AG ne sont pas affectés négativement par l'ignorance (Goldberg 1989, p. 23). Grâce à leurs composants de parallélisme, de croisement et de mutation, ils peuvent parcourir largement le paysage d'aptitude, explorant des régions que des algorithmes produits intelligemment auraient pu négliger, et potentiellement découvrir des solutions d'une créativité saisissante et inattendue qui n'aurait jamais pu venir à l'esprit des concepteurs humains. Une illustration vivante de cela est la redécouverte, par la programmation génétique, du concept de rétroaction négative - un principe crucial pour de nombreux composants électroniques importants d'aujourd'hui, mais qui, lorsqu'il a été découvert pour la première fois, a été refusé un brevet pendant neuf années parce que le concept était si contraire aux croyances établies (Koza et al. 2003, p. 413). Les algorithmes évolutionnaires, bien sûr, ne sont ni conscients ni préoccupés par le fait qu'une solution va à l'encontre des croyances établies - seulement par le fait qu'elle fonctionne.

Quelles sont les limites des AG ?

Haut

Même si les algorithmes génétiques se sont révélés être une stratégie de résolution de problèmes efficace et puissante, ils ne sont pas une panacée. Les AG présentent certaines limites ; cependant, il sera démontré que toutes ces limites peuvent être surmontées et qu'aucune d'elles ne porte atteinte à la validité de l'évolution biologique.

• La première, et la plus importante, considération dans la création d'un algorithme génétique est de définir une représentation pour le problème. Le langage utilisé pour spécifier les solutions candidates doit être robuste ; c'est-à-dire, il doit être capable de tolérer des changements aléatoires de telle sorte que des erreurs fatales ou des non-sens ne résultent pas systématiquement.
  
  Il existe deux façons principales d'atteindre cela. La première, qui est utilisée par la plupart des algorithmes génétiques, est de définir les individus comme des listes de nombres - à valeurs binaires, entières ou réelles - où chaque nombre représente un certain aspect d'une solution candidate. Si les individus sont des chaînes binaires, 0 ou 1 pourraient signifier l'absence ou la présence d'une caractéristique donnée. S'ils sont des listes de nombres, ces nombres pourraient représenter beaucoup de choses différentes : les poids des liens dans un réseau de neurones, l'ordre des villes visitées dans un tour donné, l'emplacement spatial des composants électroniques, les valeurs fournies à un contrôleur, les angles de torsion des liaisons peptidiques dans une protéine, et ainsi de suite. La mutation implique alors de changer ces nombres, d'inverser des bits ou d'ajouter ou de soustraire des valeurs aléatoires. Dans ce cas, le code du programme réel ne change pas ; c'est le code qui gère la simulation et suit les individus, évaluant leur fitness et s'assurant peut-être que seuls des résultats réalistes et possibles pour le problème donné résultent.
  
  Dans une autre méthode, la programmation génétique, le code du programme réel change. Comme discuté dans la section Méthodes de représentation, la PG représente les individus comme des arbres de code exécutables qui peuvent être mutés en changeant ou en échangeant des sous-arbres. Les deux de ces méthodes produisent des représentations qui sont robustes contre la mutation et peuvent représenter beaucoup de différents types de problèmes, et comme discuté dans la section Quelques exemples spécifiques, les deux ont connu un succès considérable.
  
  Cette question de représenter les solutions candidates d'une manière robuste ne se pose pas dans la nature, car la méthode de représentation utilisée par l'évolution, à savoir le code génétique, est intrinsèquement robuste : avec seulement très peu d'exceptions, comme une chaîne de codons stop, il n'existe pas de séquence de bases d'ADN qui ne puisse pas être traduite en une protéine. Par conséquent, pratiquement tout changement aux gènes d'un individu produira toujours un résultat intelligible, et donc les mutations dans l'évolution ont une plus grande chance de produire une amélioration. C'est en contraste avec les langues créées par l'homme telles que l'anglais, où le nombre de mots significatifs est petit comparé au nombre total de façons dont on peut combiner les lettres de l'alphabet, et donc les changements aléatoires à une phrase en anglais sont susceptibles de produire des non-sens.
  
  
• Le problème de la manière d'écrire la fonction d'aptitude doit être soigneusement examiné afin que l'aptitude plus élevée soit atteignable et corresponde réellement à une meilleure solution pour le problème donné. Si la fonction d'aptitude est choisie de manière inadéquate ou définie de manière imprécise, l'algorithme génétique peut être incapable de trouver une solution au problème, ou peut finir par résoudre le mauvais problème. (Cette dernière situation est parfois décrite comme la tendance d'un AG à « tricher », bien qu'en réalité, tout ce qui se passe est que l'AG fait ce à quoi il a été programmé, et non ce que ses créateurs avaient l'intention qu'il fasse.) Un exemple de cela peut être trouvé dans Graham-Rowe 2002, dans lequel des chercheurs ont utilisé un algorithme évolutionniste en conjonction avec un tableau matériel reprogrammable, en définissant la fonction d'aptitude pour récompenser le circuit en évolution pour qu'il produise un signal oscillant. À la fin de l'expérience, un signal oscillant était en effet produit - mais au lieu que le circuit lui-même agisse comme un oscillateur, comme les chercheurs l'avaient prévu, ils ont découvert qu'il était devenu un récepteur radio qui captait et relayait un signal oscillant provenant d'un équipement électronique voisin !
  
  Ce n'est pas un problème dans la nature, cependant. Dans le laboratoire de l'évolution biologique, il n'y a qu'une seule fonction d'aptitude, qui est la même pour tous les êtres vivants - le désir de survivre et de se reproduire, peu importe quelles adaptations rendent cela possible. Les organismes qui se reproduisent plus abondamment par rapport à leurs concurrents sont plus aptes ; ceux qui ne parviennent pas à se reproduire sont inadaptés.
  
  
• En plus de faire un bon choix de la fonction d'aptitude, les autres paramètres d'un algorithme génétique (GA) — la taille de la population, le taux de mutation et de croisement, le type et l'intensité de la sélection — doivent également être choisis avec soin. Si la taille de la population est trop petite, l'algorithme génétique peut ne pas explorer suffisamment l'espace des solutions pour trouver de manière cohérente de bonnes solutions. Si le taux de changement génétique est trop élevé ou si le schéma de sélection est mal choisi, des schémas bénéfiques peuvent être perturbés et la population peut entrer dans une catastrophe d'erreurs, changeant trop vite pour que la sélection puisse jamais amener une convergence.
  
  Les êtres vivants doivent faire face à des difficultés similaires, et l'évolution y a fait face. Il est vrai que si la taille d'une population tombe trop bas, si les taux de mutation sont trop élevés, ou si la pression de sélection est trop forte (une telle situation pourrait être causée par un changement environnemental drastique), alors l'espèce peut s'éteindre. La solution a été « l'évolution de l'évolvabilité » — des adaptations qui modifient la capacité d'une espèce à s'adapter. Par exemple, la plupart des êtres vivants ont évolué des machines moléculaires élaborées qui vérifient et corrigent les erreurs pendant le processus de réplication de l'ADN, maintenant leur taux de mutation à des niveaux acceptablement bas ; à l'inverse, en cas de stress environnemental sévère, certaines espèces bactériennes entrent dans un état de hypermutation où le taux d'erreurs de réplication de l'ADN augmente considérablement, augmentant la chance qu'une mutation compensatoire soit découverte. Bien sûr, toutes les catastrophes ne peuvent pas être évitées, mais la diversité énorme et les adaptations hautement complexes des êtres vivants d'aujourd'hui montrent que, en général, l'évolution est une stratégie réussie. De même, les diverses applications et les résultats impressionnants produits par les algorithmes génétiques montrent qu'ils constituent un domaine d'étude puissant et worthwhile.
  
  
• Un type de problème avec lequel les algorithmes génétiques ont du mal à faire face sont les problèmes de fonctions de fitness « trompeuses » (Mitchell 1996, p.125), celles où les emplacements des points améliorés donnent des informations trompeuses sur l'endroit où l'optimum global est susceptible d'être trouvé. Par exemple, imaginez un problème où l'espace de recherche consistait en toutes les chaînes binaires de huit caractères, et où la fitness d'un individu était directement proportionnelle au nombre de 1s qu'il contenait - c'est-à-dire que 00000001 serait moins adapté que 00000011, lequel serait moins adapté que 00000111, et ainsi de suite - avec deux exceptions : la chaîne 11111111 s'est avérée avoir une très faible fitness, et la chaîne 00000000 s'est avérée avoir une très haute fitness. Dans un tel problème, un AG (ainsi que la plupart des autres algorithmes) n'aurait pas plus de chances de trouver l'optimum global qu'une recherche aléatoire.
  
  La résolution de ce problème est la même pour les algorithmes génétiques et l'évolution biologique : l'évolution n'est pas un processus qui doit trouver l'optimum global unique à chaque fois. Elle peut presque aussi bien faire en atteignant le sommet d'un optimum local élevé, et pour la plupart des situations, cela suffira, même si l'optimum global ne peut pas facilement être atteint à partir de ce point. L'évolution est très clairement un « satisficer » - un algorithme qui délivre une solution « suffisante », bien que pas nécessairement la meilleure solution possible, compte tenu du temps et des efforts raisonnables investis dans la recherche. La FAQ Evidence for Jury-Rigged Design in Nature donne des exemples de ce résultat apparaissant dans la nature. (Il est également worth noting que peu, si ce n'est aucun, des problèmes du monde réel sont aussi pleinement trompeurs que l'exemple quelque peu artificiel donné ci-dessus. Habituellement, l'emplacement des améliorations locales donne au moins quelques informations sur l'emplacement de l'optimum global.)
  
  
• Un problème bien connu qui peut survenir avec un AG est appelé la convergence prématurée. Si un individu plus apte que la plupart de ses concurrents émerge tôt dans le déroulement de l'exécution, il peut se reproduire si abondamment qu'il réduit trop tôt la diversité de la population, conduisant l'algorithme à converger vers l'optimum local que cet individu représente, plutôt que d'explorer suffisamment le paysage d'aptitude pour trouver l'optimum global (Forrest 1993, p. 876 ; Mitchell 1996, p. 167). C'est un problème particulièrement fréquent dans les petites populations, où même des variations aléatoires du taux de reproduction peuvent faire qu'un génotype devienne dominant par rapport aux autres.
  
  Les méthodes les plus courantes mises en œuvre par les chercheurs en AG pour résoudre ce problème consistent toutes à contrôler l'intensité de la sélection, afin de ne pas accorder aux individus excessivement aptes un avantage trop important. Le classement, l'échelle et la sélection par tournoi, évoqués précédemment, sont trois moyens majeurs pour accomplir cela ; certaines méthodes d'échelle de la sélection incluent l'échelle sigma, dans laquelle la reproduction est basée sur une comparaison statistique à l'aptitude moyenne de la population, et la sélection de Boltzmann, dans laquelle l'intensité de la sélection augmente au cours d'une exécution d'une manière similaire à la variable « température » dans le recuit simulé (Mitchell 1996, p. 168).
  
  La convergence prématurée se produit en nature (où elle est appelée dérive génétique par les biologistes). Cela ne devrait pas surprendre ; comme discuté ci-dessus, l'évolution en tant que stratégie de résolution de problèmes n'est pas tenue de trouver la seule meilleure solution, mais simplement une qui soit suffisante. Cependant, la convergence prématurée en nature est moins fréquente car la plupart des mutations bénéfiques chez les êtres vivants ne produisent que de petites améliorations incrémentales de l'aptitude ; les mutations qui produisent un tel gain d'aptitude important à donner à leurs porteurs un avantage reproductif dramatique sont rares.
  
  
• Enfin, plusieurs chercheurs (Holland 1992, p.72; Forrest 1993, p.875; Haupt et Haupt 1998, p.18) déconseillent l'utilisation d'algorithmes génétiques sur des problèmes analytiquement solubles. Ce n'est pas que les algorithmes génétiques ne puissent pas trouver de bonnes solutions à de tels problèmes ; c'est simplement que les méthodes analytiques traditionnelles prennent beaucoup moins de temps et d'efforts de calcul que les AG et, contrairement aux AG, sont généralement garanties mathématiquement pour fournir la solution exacte unique. Bien sûr, comme il n'existe pas de solution mathématiquement parfaite à tout problème d'adaptation biologique, cette question ne se pose pas dans la nature.

Quelques exemples spécifiques des AG

Haut

À mesure que le pouvoir de l'évolution gagne une reconnaissance de plus en plus généralisée, les algorithmes génétiques ont été utilisés pour résoudre une large variété de problèmes dans un ensemble extrêmement divers de domaines, démontrant clairement leur puissance et leur potentiel. Cette section abordera certains des usages les plus remarquables auxquels ils ont été mis.

• Acoustique
• Ingénierie aérospatiale
• Astronomie et astrophysique
• Chimie
• Ingénierie électrique
• Marchés financiers
• Jeux
• Géophysique
• Ingénierie des matériaux
• Mathématiques et algorithmique
• Armée et forces de l'ordre
• Biologie moléculaire
• Reconnaissance de motifs et fouille de données
• Robotique
• Routage et planification
• Ingénierie des systèmes

• Acoustique
  Sato et al. 2002 ont utilisé des algorithmes génétiques pour concevoir une salle de concert aux propriétés acoustiques optimales, maximisant la qualité sonore pour le public, le chef d'orchestre et les musiciens sur scène. Cette tâche implique l'optimisation simultanée de plusieurs variables. Partant d'une salle de forme de boîte à chaussures, l'AG des auteurs a produit deux solutions non dominées, toutes deux décrites comme « en forme de feuille » (p.526). Les auteurs indiquent que ces solutions ont des proportions similaires à celles du Grosser Musikvereinsaal de Vienne, qui est largement considéré comme l'une des meilleures – sinon la meilleure – salle de concert du monde en termes de propriétés acoustiques.
  
  Porto, Fogel et Fogel 1995 ont utilisé la programmation évolutive pour entraîner des réseaux de neurones à distinguer les réflexions sonar provenant de différents types d'objets : sphères métalliques artificielles, monts sous-marins, poissons et vie végétale, ainsi que le bruit de fond aléatoire. Après 500 générations, le meilleur réseau de neurones évolué avait une probabilité de classification correcte comprise entre 94 % et 98 % et une probabilité de mauvaise classification comprise entre 7,4 % et 1,5 %, ce qui correspond à des « probabilités raisonnables de détection et de fausse alarme » (p.21). Le réseau évolué a égalé les performances d'un autre réseau développé par recuit simulé et a constamment surpassé les réseaux entraînés par rétropropagation, qui « se sont répétemment bloqués à des ensembles de poids sous-optimaux qui ne donnaient pas de résultats satisfaisants » (p.21). Par contraste, les deux méthodes stochastiques ont montré leur capacité à surmonter ces optima locaux et à produire des réseaux plus petits, efficaces et plus robustes ; mais les auteurs suggèrent que l'algorithme évolutif, contrairement au recuit simulé, opère sur une population et tire donc parti des informations globales sur l'espace de recherche, ce qui pourrait conduire à de meilleures performances à long terme.
  
  Tang et al. 1996 recensent les utilisations des algorithmes génétiques dans le domaine de l'acoustique et du traitement du signal. Un domaine d'intérêt particulier concerne l'utilisation des AG pour concevoir des systèmes de contrôle actif du bruit (ANC), qui annulent les sons indésirables en produisant des ondes sonores qui interfèrent destructivement avec le bruit indésirable. Il s'agit d'un problème à multiples objectifs nécessitant le positionnement précis et le contrôle de plusieurs haut-parleurs ; les AG ont été utilisés à la fois pour concevoir les contrôleurs et trouver le positionnement optimal des haut-parleurs pour de tels systèmes, aboutissant à une « atténuation efficace du bruit » (p.33) lors de tests expérimentaux.
  
  
• Ingénierie aérospatiale
  Obayashi et al. 2000 used a multiple-objective genetic algorithm to design the wing shape for a supersonic aircraft. Three major considerations govern the wing's configuration - minimizing aerodynamic drag at supersonic cruising speeds, minimizing drag at subsonic speeds, and minimizing aerodynamic load (the bending force on the wing). These objectives are mutually exclusive, and optimizing them all simultaneously requires tradeoffs to be made.
  
  The chromosome in this problem is a string of 66 real-valued numbers, each of which corresponds to a specific aspect of the wing: its shape, its thickness, its twist, and so on. Evolution with elitist rank selection was simulated for 70 generations, with a population size of 64 individuals. At the termination of this process, there were several Pareto-optimal individuals, each one representing a single non-dominated solution to the problem. The paper notes that these best-of-run individuals have "physically reasonable" characteristics, indicating the validity of the optimization technique (p.186). To further evaluate the quality of the solutions, six of the best were compared to a supersonic wing design produced by the SST Design Team of Japan's National Aerospace Laboratory. All six were competitive, having drag and load values approximately equal to or less than the human-designed wing; one of the evolved solutions in particular outperformed the NAL's design in all three objectives. The authors note that the GA's solutions are similar to a design called the "arrow wing" which was first suggested in the late 1950s, but ultimately abandoned in favor of the more conventional delta-wing design.
  
  In a follow-up paper (Sasaki et al. 2001), the authors repeat their experiment while adding a quatrième objective, namely minimizing the twisting moment of the wing (a known potential problem for arrow-wing SST designs). Additional control points for thickness are also added to the array of design variables. After 75 generations of evolution, two of the best Pareto-optimal solutions were again compared to the Japanese National Aerospace Laboratory's wing design for the NEXST-1 experimental supersonic airplane. It was found that both of these designs (as well as one optimal design from the previous simulation, discussed above) were physically reasonable and superior to the NAL's design in all four objectives.
  
  Williams, Crossley et Lang 2001 applied genetic algorithms to the task of spacing satellite orbits to minimize coverage blackouts. As telecommunications technology continues to improve, humans are increasingly dependent on Earth-orbiting satellites to perform many vital functions, and one of the problems engineers face is designing their orbital trajectories. Satellites in high Earth orbit, around 22,000 miles up, can see large sections of the planet at once and be in constant contact with ground stations, but these are far more expensive to launch and more vulnerable to cosmic radiation. It is more economical to put satellites in low orbits, as low as a few hundred miles in some cases, but because of the curvature of the Earth it is inevitable that these satellites will at times lose line-of-sight access to surface receivers and thus be useless. Even constellations of several satellites experience unavoidable blackouts and losses of coverage for this reason. The challenge is to arrange the satellites' orbits to minimize this downtime. This is a multi-objective problem, involving the minimization of both the average blackout time for all locations and the maximum blackout time for any one location; in practice, these goals turn out to be mutually exclusive.
  
  When the GA was applied to this problem, the evolved results for three, four and five-satellite constellations were unusual, highly asymmetric orbit configurations, with the satellites spaced by alternating large and small gaps rather than equal-sized gaps as conventional techniques would produce. However, this solution significantly reduced both average and maximum revisit times, in some cases by up to 90 minutes. In a news article about the results, Dr. William Crossley noted that "engineers with years of aerospace experience were surprised by the higher performance offered by the unconventional design".
  
  

  Keane et Brown 1996 ont utilisé un AG pour faire évoluer un nouveau design pour une poutre ou un bras de levier porteur de charge qui pourrait être assemblé en orbite et utilisé pour des satellites, des stations spatiales et d'autres projets de construction aérospatiale. Le résultat, une structure tordue et ressemblant à de l'organique qui a été comparée à un os de jambe humain, n'utilise pas plus de matériau que le design de poutre standard, mais est légère, robuste et bien supérieure pour amortir les vibrations dommageables, comme l'ont confirmé des tests réels du produit final. Et pourtant "Aucune intelligence n'a conçu ces designs. Ils ont simplement évolué" (Petit 1998). Les auteurs du papier ajoutent également que leur AG n'a fonctionné que pendant 10 générations en raison de la nature intensivement computationnelle de la simulation, et que la population n'était pas encore stagnée. Poursuivre l'exécution pendant plus de générations aurait incontestablement produit d'autres améliorations des performances.

  Figure 4 : Une poutre tridimensionnelle optimisée génétiquement avec une réponse fréquentielle améliorée. (Adapté de [1].)

  
  
  Finally, as reported in Gibbs 1996, Lockheed Martin has used a genetic algorithm to evolve a series of maneuvers to shift a spacecraft from one orientation to another within 2% of the theoretical minimum time for such maneuvers. The evolved solution was 10% faster than a solution hand-crafted by an expert for the same problem.
  
  
• Astronomie et astrophysique
  Charbonneau 1995 suggère l'utilité des algorithmes génétiques (AG) pour les problèmes d'astrophysique en les appliquant à trois exemples : ajuster la courbe de rotation d'une galaxie en se basant sur les vitesses de rotation observées de ses composants, déterminer la période de pulsation d'une étoile variable à partir de données en série temporelle, et résoudre les paramètres critiques dans un modèle magnétohydrodynamique du vent solaire. Les trois sont des problèmes multidimensionnels non linéaires difficiles.
  
  L'algorithme génétique de Charbonneau, PIKAIA, utilise une sélection par classement proportionnelle à la fitness par générations couplée à l'élitisme, garantissant que le meilleur individu unique est copié une fois dans la génération suivante sans modification. PIKAIA a un taux de croisement de 0,65 et un taux de mutation variable qui est fixé à 0,003 initialement et augmente progressivement plus tard, lorsque la population approche de la convergence, pour maintenir la variabilité dans le pool génique.
  
  Dans le problème de la courbe de rotation galactique, l'AG a produit deux courbes, toutes deux de très bons ajustements aux données (un résultat courant dans ce type de problème, où il y a peu de contraste entre les sommets voisins) ; des observations ultérieures peuvent alors distinguer laquelle doit être préférée. Dans le problème de la série temporelle, l'AG a été impressionnément réussi à générer de manière autonome un ajustement de haute qualité pour les données, mais les problèmes plus difficiles n'ont pas été ajustés aussi bien (bien que, Charbonneau le souligne, ces problèmes soient tout aussi difficiles à résoudre avec des techniques conventionnelles). Le papier suggère qu'un AG hybride employant à la fois l'évolution artificielle et des techniques analytiques standard pourrait mieux performer. Enfin, en résolvant pour les six paramètres critiques du vent solaire, l'AG a déterminé avec succès la valeur de trois d'entre eux avec une précision de moins de 0,1 % et les trois restants avec des précisions de moins de 1 à 10 %. (Bien qu'une erreur expérimentale plus faible pour ces trois serait toujours préférable, Charbonneau note qu'il n'existe aucune autre méthode robuste et efficace pour résoudre expérimentalement un problème non linéaire de six dimensions de ce type ; une méthode de gradient conjugué fonctionne « tant qu'une très bonne estimation de départ peut être fournie » (p. 323). Par contraste, les AG ne nécessitent pas de telles connaissances spécifiques au domaine finement ajustées.)
  
  Sur la base des résultats obtenus jusqu'à présent, Charbonneau suggère que les AG peuvent et devraient trouver une utilité dans d'autres problèmes difficiles d'astrophysique, en particulier les problèmes inverses tels que l'imagerie Doppler et les inversions héliosismiques. En conclusion, Charbonneau soutient que les AG sont un « concurrent fort et prometteur » (p. 324) dans ce domaine, qui peut être attendu pour compléter plutôt que remplacer les techniques d'optimisation traditionnelles, et conclut que « la conclusion, s'il y en a une, est que les algorithmes génétiques fonctionnent, et souvent de manière effrayante bien » (p. 325).
  
  
• Chimie
  Des impulsions laser à haute puissance et ultra-courtes peuvent dissocier des molécules complexes en molécules plus simples, un processus ayant des applications importantes en chimie organique et en microélectronique. Les produits finaux spécifiques d'une telle réaction peuvent être contrôlés en modulant la phase de l'impulsion laser. Cependant, pour les grandes molécules, la résolution analytique de la forme d'impulsion souhaitée est trop difficile : les calculs sont trop complexes et les caractéristiques pertinentes (les surfaces d'énergie potentielle des molécules) ne sont pas connues avec une précision suffisante.
  
  Assion et al. 1998 ont résolu ce problème en utilisant un algorithme évolutionnaire pour concevoir la forme de l'impulsion. Au lieu d'entrer des connaissances complexes et spécifiques au problème concernant les caractéristiques quantiques des molécules d'entrée pour concevoir l'impulsion selon des spécifications, l'AE (algorithme évolutionnaire) lance une impulsion, mesure les proportions des molécules de produit résultantes, mute aléatoirement les caractéristiques du faisceau dans l'espoir d'obtenir ces proportions plus proches de la sortie souhaitée, et le processus se répète. (Plutôt que d'ajuster finement directement n'importe quelle caractéristique du faisceau laser, l'AG (algorithme génétique) des auteurs représente les individus comme un ensemble de 128 nombres, chacun étant une valeur de tension qui contrôle l'indice de réfraction d'un des pixels du modulateur de lumière laser. Encore une fois, aucune connaissance spécifique au problème concernant les propriétés du laser ou des produits de réaction n'est nécessaire.) Les auteurs indiquent que leur algorithme, lorsqu'il est appliqué à deux substances d'échantillon, « trouve automatiquement la meilleure configuration... peu importe à quel point la réponse moléculaire peut être compliquée » (p. 920), démontrant un « contrôle cohérent automatisé sur des produits qui sont chimiquement différents les uns des autres et de la molécule parente » (p. 921).
  
  Au début et au milieu des années 1990, l'adoption généralisée d'une nouvelle technique de conception de médicaments appelée chimie combinatoire a révolutionné l'industrie pharmaceutique. Dans cette méthode, plutôt que la synthèse laborieuse et précise d'un seul composé à la fois, les biochimistes mélangent délibérément une grande variété de réactifs pour produire une variété encore plus large de produits - des centaines, des milliers ou des millions de composés différents par lot - qui peuvent ensuite être rapidement criblés pour leur activité biochimique. Dans la conception de bibliothèques de réactifs pour cette technique, il existe deux approches principales : la conception basée sur les réactifs, qui choisit des groupes optimisés de réactifs sans tenir compte des produits qui en résulteront, et la conception basée sur les produits, qui sélectionne les réactifs les plus susceptibles de produire des produits ayant les propriétés souhaitées. La conception basée sur les produits est plus difficile et complexe, mais il a été démontré qu'elle aboutit à de meilleures et plus diverses bibliothèques combinatoires et à une plus grande probabilité d'obtenir un résultat utilisable.
  
  Dans un article financé par le département de recherche et développement de GlaxoSmithKline, Gillet 2002 discute de l'utilisation d'un algorithme génétique multiobjectif pour la conception basée sur les produits de bibliothèques combinatoires. Lors du choix des composés qui entrent dans une bibliothèque particulière, des qualités telles que la diversité moléculaire et le poids, le coût des fournitures, la toxicité, l'absorption, la distribution et le métabolisme doivent tous être pris en compte. Si l'objectif est de trouver des molécules similaires à une molécule existante de fonction connue (une méthode courante de conception de nouveaux médicaments), la similarité structurale peut également être prise en compte. Cet article présente une approche multiobjectif où un ensemble de résultats Pareto-optimaux qui maximisent ou minimisent chacun de ces objectifs peut être développé. L'auteur conclut que l'AG a été capable de satisfaire simultanément les critères de diversité moléculaire et d'efficacité synthétique maximale, et a été capable de trouver des molécules qui ressemblent à des médicaments ainsi que « très similaires aux molécules cibles données après avoir exploré une très petite fraction de l'espace de recherche total » (p. 378).
  
  Dans un article connexe, Glen et Payne 1995 discutent de l'utilisation d'algorithmes génétiques pour concevoir automatiquement de nouvelles molécules à partir de zéro afin de correspondre à un ensemble donné de spécifications. Étant donné une population initiale soit générée aléatoirement soit en utilisant la simple molécule d'éthane comme graine, l'AG ajoute, retire et modifie aléatoirement des atomes et des fragments moléculaires dans le but de générer des molécules qui correspondent aux contraintes données. L'AG peut simultanément optimiser un grand nombre d'objectifs, y compris le poids moléculaire, le volume moléculaire, le nombre de liaisons, le nombre de centres chiraux, le nombre d'atomes, le nombre de liaisons rotatable, la polarisabilité, le moment dipolaire, et plus encore afin de produire des molécules candidates ayant les propriétés souhaitées. Sur la base de tests expérimentaux, y compris un problème d'optimisation difficile impliquant la génération de molécules ayant des propriétés similaires au ribose (un composé sucré fréquemment mimé dans les médicaments antiviraux), les auteurs concluent que l'AG est un « excellent générateur d'idées » (p. 199) qui offre des « propriétés d'optimisation rapides et puissantes » et peut générer « un ensemble diversifié de structures possibles » (p. 182). Ils vont plus loin en affirmant : « Particulièrement notable est la puissante capacité d'optimisation de l'algorithme génétique, même avec des tailles de population relativement petites » (p. 200). En signe que ces résultats ne sont pas seulement théoriques, Lemley 2001 rapporte que la société Unilever a utilisé des algorithmes génétiques pour concevoir de nouveaux composés antimicrobiens pour leur utilisation dans les nettoyants, lesquels elle a brevetés.
  
  
• Génie électrique
  Un tableau de portes à programmation par champ, ou FPGA pour abréger, est un type spécial de carte de circuits imprimés comportant une matrice de cellules logiques, chacune pouvant agir comme n'importe quel type de porte logique, reliées par des interconnexions flexibles qui peuvent connecter les cellules. Ces deux fonctions sont contrôlées par un logiciel, de sorte qu'en chargeant simplement un programme spécial dans la carte, elle peut être modifiée en temps réel pour effectuer les fonctions de l'un des nombreux dispositifs matériels.
  
  Le Dr Adrian Thompson a exploité cet appareil, en conjonction avec les principes de l'évolution, pour produire un prototype de circuit de reconnaissance vocale capable de distinguer et de répondre à des commandes vocales en utilisant seulement 37 portes logiques — une tâche qui aurait été considérée comme impossible pour n'importe quel ingénieur humain. Il a généré des chaînes de bits aléatoires de 0 et 1 et les a utilisés comme configurations pour le FPGA, sélectionnant les individus les plus aptes de chaque génération, les reproduisant et les mutuant aléatoirement, échangeant des sections de leur code et les transmettant à un autre tour de sélection. Son objectif était d'évoluer un dispositif capable, au début, de discriminer entre des tons de fréquences différentes (1 et 10 kilohertz), puis de distinguer entre les mots prononcés « go » et « stop ».
  
  Cet objectif a été atteint en 3000 générations, mais le succès a été encore plus grand que prévu. Le système évolué utilise beaucoup moins de cellules que tout ce qu'un ingénieur humain aurait pu concevoir, et il n'a même pas besoin du composant le plus critique des systèmes construits par l'homme — une horloge. Comment cela fonctionne-t-il ? Thompson n'a aucune idée, bien qu'il ait tracé le signal d'entrée à travers un arrangement complexe de boucles de rétroaction au sein du circuit évolué. En fait, parmi les 37 portes logiques que le produit final utilise, cinq d'entre elles ne sont même reliées au reste du circuit d'aucune manière — pourtant, si leur alimentation est coupée, le circuit cesse de fonctionner. Il semble que l'évolution ait exploité un effet électromagnétique subtil de ces cellules pour trouver sa solution, mais le fonctionnement exact de la structure évolutive complexe et élaborée reste un mystère (Davidson 1997).
  
  Altshuler et Linden 1997 ont utilisé un algorithme génétique pour évoluer des antennes filaires avec des propriétés prédéfinies. Les auteurs notent que la conception de telles antennes est un processus imprécis, commençant par les propriétés désirées et déterminant ensuite la forme de l'antenne par des « suppositions... intuition, expérience, équations approximatives ou études empiriques » (p.50). Cette technique est chronophage, ne produit souvent pas des résultats optimaux et tend à fonctionner bien seulement pour des conceptions relativement simples et symétriques. Par contraste, dans l'approche par algorithme génétique, l'ingénieur spécifie les propriétés électromagnétiques de l'antenne, et l'AG synthétise automatiquement une configuration correspondante.
  
  

  Figure 5 : Une antenne génétique filaire courbée (d'après Altshuler et Linden 1997, figure 1).

  Altshuler et Linden ont utilisé leur AG pour concevoir une antenne à polarisation circulaire à sept segments avec une couverture hémisphérique ; le résultat est montré à gauche. Chaque individu dans l'AG consistait en un chromosome binaire spécifiant les coordonnées tridimensionnelles de chaque extrémité de chaque fil. L'aptitude a été évaluée en simulant chaque candidat selon un code de câblage électromagnétique, et l'individu le meilleur de la série a ensuite été construit et testé. Les auteurs décrivent la forme de cette antenne, qui ne ressemble pas aux antennes traditionnelles et n'a aucune symétrie évidente, comme « inhabituellement étrange » et « contre-intuitive » (p.52), mais elle présentait un diagramme de rayonnement presque uniforme avec une large bande passante à la fois en simulation et lors des tests expérimentaux, correspondant parfaitement à la spécification préalable. Les auteurs concluent qu'une méthode de conception d'antenne basée sur un algorithme génétique montre une « promesse remarquable ». « ...cette nouvelle procédure de conception est capable de trouver des antennes génétiques capables de résoudre efficacement des problèmes d'antennes difficiles, et elle sera particulièrement utile dans des situations où les conceptions existantes ne sont pas adéquates » (p.52).

• Marchés financiers
  Mahfoud et Mani 1996 ont utilisé un algorithme génétique pour prédire les performances futures de 1600 actions cotées en bourse. Plus précisément, l'AG a été chargé de prévoir le rendement relatif de chaque action, défini comme le rendement de cette action moins le rendement moyen de l'ensemble des 1600 actions sur la période concernée, soit 12 semaines (un trimestre civil) à l'avenir. En entrée, l'AG a reçu des données historiques sur chaque action sous la forme d'une liste de 15 attributs, tels que le ratio cours/bénéfice et le taux de croissance, mesurés à divers points dans le passé ; l'AG a été chargé d'évoluer un ensemble de règles si/alors pour classer chaque action et de fournir, en sortie, à la fois une recommandation sur quoi faire concernant cette action (acheter, vendre ou aucune prédiction) et une prévision numérique du rendement relatif. Les résultats de l'AG ont été comparés à ceux d'un système établi basé sur les réseaux de neurones que les auteurs utilisaient depuis trois ans pour prévoir les cours boursiers et gérer des portefeuilles. Bien sûr, le marché des actions est un système extrêmement bruité et non linéaire, et aucun mécanisme prédictif ne peut être correct 100 % du temps ; le défi consiste à trouver un prédicteur qui soit plus souvent que non correct.
  
  Dans l'expérience, l'AG et le réseau de neurones ont chacun effectué des prévisions à la fin de chaque semaine pour chacune des 1600 actions, pendant douze semaines consécutives. Douze semaines après chaque prédiction, la performance réelle a été comparée au rendement relatif prédit. Dans l'ensemble, l'AG a nettement surpassé le réseau de neurones : lors d'une exécution d'essai, l'AG a correctement prédit la direction d'une action 47,6 % du temps, n'a fait aucune prédiction 45,8 % du temps, et a fait une prédiction incorrecte seulement 6,6 % du temps, pour une précision prédictive globale de 87,8 %. Bien que le réseau de neurones ait fait plus souvent des prévisions définitives, il s'est également trompé plus souvent dans ses prévisions (en fait, les auteurs spéculent que la plus grande capacité de l'AG à ne pas faire de prédiction lorsque les données étaient incertaines a été un facteur de son succès ; le réseau de neurones produit toujours une prédiction sauf si explicitement restreint par le programmeur). Dans l'expérience sur 1600 actions, l'AG a produit un rendement relatif de +5,47 %, contre +4,40 % pour le réseau de neurones – une différence statistiquement significative. En fait, l'AG a également nettement surpassé trois principaux indices boursiers – le S&P 500, le S&P 400 et le Russell 2000 – sur cette période ; la chance a été exclue comme cause de ce résultat au niveau de confiance de 95 %. Les auteurs attribuent ce succès convaincant à la capacité de l'algorithme génétique d'apprendre des relations non linéaires qui ne sont pas facilement apparentes aux observateurs humains, ainsi qu'au fait qu'il ne possède pas le « biais a priori de l'expert humain contre les règles contre-intuitives ou contraires » (p. 562).
  
  Un succès similaire a été obtenu par Andreou, Georgopoulos et Likothanassis 2002, qui ont utilisé des algorithmes génétiques hybrides pour faire évoluer des réseaux de neurones prédisant les taux de change des devises étrangères jusqu'à un mois à l'avance. Contrairement à l'exemple précédent, où les AG et les réseaux de neurones étaient en compétition, ici les deux ont travaillé en concert, l'AG faisant évoluer l'architecture (nombre d'unités d'entrée, nombre d'unités cachées et l'agencement des liens entre elles) du réseau, qui a ensuite été entraîné par un algorithme de filtrage.
  
  En tant qu'informations historiques, l'algorithme a reçu 1300 valeurs brutes journalières précédentes de cinq devises – le dollar américain, le mark allemand, le franc français, la livre sterling et le drachme grec – et a été chargé de prédire leurs valeurs futures 1, 2, 5 et 20 jours à l'avance. Les performances de l'AG hybride ont, dans l'ensemble, montré un « niveau remarquable de précision » (p. 200) dans tous les cas testés, surpassant plusieurs autres méthodes, y compris les réseaux de neurones seuls. Les corrélations pour le cas d'un jour variaient de 92 à 99 %, et bien que la précision ait diminué avec des délais temporels de plus en plus grands, l'AG est resté « assez réussi » (p. 206) et a clairement surpassé les autres méthodes. Les auteurs concluent que « un succès prédictif remarquable a été atteint à la fois à l'horizon d'une étape et à l'horizon de prédiction multistep » (p. 208) – en fait, ils affirment que leurs résultats sont bien meilleurs que toute stratégie prédictive connexe tentée sur cette série de données ou d'autres devises.
  
  Les utilisations des AG sur les marchés financiers ont commencé à se répandre dans les sociétés de courtage du monde réel. Naik 1996 rapporte que LBS Capital Management, une société américaine dont le siège est en Floride, utilise des algorithmes génétiques pour sélectionner des actions pour un fonds de pension qu'elle gère. Coale 1997 et Begley et Beals 1995 rapportent que First Quadrant, une société d'investissement en Californie qui gère plus de 2,2 milliards de dollars, utilise des AG pour prendre des décisions d'investissement pour l'ensemble de ses services financiers. Leur modèle évolué rapporte, en moyenne, 255 $ pour chaque 100 $ investis sur six ans, contre 205 $ pour d'autres types de systèmes de modélisation.
  
  
• Jeu de rôle
  One of the most novel and compelling demonstrations of the power of genetic algorithms was presented by Chellapilla et Fogel 2001, who used a GA to evolve neural networks that could play the game of checkers. The authors state that one of the major difficulties in these sorts of strategy-related problems is the problème d'attribution de crédit - in other words, how does one write a fitness function? It has been widely believed that the mere criterion of win, lose or draw does not provide sufficient information for an evolutionary algorithm to figure out what constitutes good play.
  
  In this paper, Chellapilla and Fogel overturn that assumption. Given only the spatial positions of pieces on the checkerboard and the total number of pieces possessed by each side, they were able to evolve a checkers program that plays at a level competitive with human experts, without any intelligent input as to what constitutes good play - indeed, the individuals in the evolutionary algorithm were not even told what the criteria for a win were, nor were they told the result of any one game.
  
  In Chellapilla and Fogel's representation, the game state was represented by a numeric list of 32 elements, with each position in the list corresponding to an available position on the board. The value at each position was either 0 for an unoccupied square, -1 if that square was occupied by an enemy checker, +1 if that square was occupied by one of the program's checkers, and -K or +K for a square occupied by an enemy or friendly king. (The value of K was not pre-specified, but again was determined by evolution over the course of the algorithm.) Accompanying this was a neural network with multiple processing layers and one input layer with a node for each of the possible 4x4, 5x5, 6x6, 7x7 and 8x8 squares on the board. The output of the neural net for any given arrangement of pieces was a value from -1 to +1 indicating how good it felt that position was for it. For each move, the neural network was presented with a game tree listing all possible moves up to four turns into the future, and a move decision was made based on which branch of the tree produced the best results for it.
  
  The evolutionary algorithm began with a population of 15 neural networks with randomly generated weights and biases assigned to each node and link; each individual then reproduced once, generating an offspring with variations in the values of the network. These 30 individuals then competed for survival by playing against each other, with each individual competing against 5 randomly chosen opponents per turn. 1 point was awarded for each win and 2 points were deducted for each loss. The 15 best performers, based on total score, were selected to produce offspring for the next generation, and the process repeated. Evolution was continued for 840 generations (approximately six months of computer time).
  
  

  Classe Échecs Maître Senior 2400+ Maître 2200-2399 Expert 2000-2199 Classe A 1800-1999 Classe B 1600-1799 Classe C 1400-1599 Classe J < 200

  Le meilleur individu qui a émergé de cette sélection a été inscrit comme concurrent sur le site de jeu www.zone.com. Sur une période de deux mois, il a affronté 165 adversaires humains composant une gamme de niveaux de compétence élevés, de la classe C au maître, selon le système de classement de la Fédération d'échecs des États-Unis (affiché à gauche, certains rangs omis pour la clarté). Parmi ces parties, le réseau neuronal a gagné 94, perdu 39 et fait match nul 32 ; basé sur les classements des adversaires dans ces parties, le réseau neuronal évolué était équivalent à un joueur avec une échecs moyenne de 2045,85, le plaçant au niveau expert - un classement supérieur à 99,61 % des plus de 80 000 joueurs enregistrés sur le site. L'une des victoires les plus significatives du réseau neuronal était lorsqu'il a vaincu un joueur classé 98e sur tous les joueurs enregistrés, dont l'échecs était juste de 27 points en dessous du niveau maître.

  
  
  Tests conducted with a simple piece-differential program (which bases moves solely on the difference between the number of checkers remaining to each side) with an eight-move look-ahead showed the neural net to be significantly superior, with a rating over 400 points higher. "A program that relies only on the piece count and an eight-ply search will defeat a lot of people, but it is not an expert. The best evolved neural network is" (p.425). Even when it was searching positions two further moves ahead than the neural net, the piece-differential program lost decisively in eight out of ten games. This conclusively demonstrates that the evolved neural net is not merely counting pieces, but is somehow processing spatial characteristics of the board to decide its moves. The authors point out that opponents on zone.com often commented that the neural net's moves were "strange", but its overall level of play was described as "very tough" or with similar complimentary terms.
  
  To further test the evolved neural network (which the authors named "Anaconda" since it often won by restricting its opponents' mobility), it was played against a commercial checkers program, Hoyle's Classic Games, distributed by Sierra Online (Chellapilla et Fogel 2000). This program comes with a variety of built-in characters, each of whom plays at a different skill level. Anaconda was tested against three characters ("Beatrice", "Natasha" and "Leopold") designated as expert-level players, playing one game as red and one game as white against each of them with a six-ply look-ahead. Though the authors doubted that this depth of look-ahead would give Anaconda the ability to play at the expert skill level it had previously shown, it won six straight victories out of all six games played. Based on this outcome, the authors expressed skepticism over whether the Hoyle software played at the skill level advertised, though it should be noted that they reached this conclusion based uniquement on the ease with which Anaconda defeated it!
  
  The ultimate test of Anaconda was given in Chellapilla et Fogel 2002, where the evolved neural net was matched against the best checkers player in the world: Chinook, a program designed principally by Dr. Jonathan Schaeffer of the University of Alberta. Rated at 2814 in 1996 (with its closest human competitors rated in the 2600s), Chinook incorporates a book of opening moves provided by human grandmasters, a sophisticated set of middle-game algorithms, and a complete database of all possible moves with ten pieces on the board or less, so it never makes a mistake in the endgame. An enormous amount of human intelligence and expertise went into the design of this program.
  
  Chellapilla and Fogel pitted Anaconda against Chinook in a 10-game tournament, with Chinook playing at a 5-ply skill level, making it roughly approximate to master level. Chinook won this contest, four wins to two with four draws. (Interestingly, the authors note, in two of the games that ended as draws, Anaconda held the lead with four kings to Chinook's three. Furthermore, one of Chinook's wins came from a 10-ply series of movies drawn from its endgame database, which Anaconda with an 8-ply look-ahead could not have anticipated. If Anaconda had had access to an endgame database of the same quality as Chinook's, the outcome of the tournament might well have been a victory for Anaconda, four wins to three.) These results "provide good support for the expert-level rating that Anaconda earned on www.zone.com" (p.76), with an overall rating of 2030-2055, comparable to the 2045 rating it earned by playing against humans. While Anaconda is not an invulnerable player, it is able to play competitively at the expert level and hold its own against a variety of extremely skilled human checkers players. When one considers the very simple fitness criterion under which these results were obtained, the emergence of Anaconda provides dramatic corroboration of the power of evolution.
  
  
• Géophysique
  Sambridge et Gallagher 1993 ont utilisé un algorithme génétique pour localiser les hypocentres de séismes sur la base de données sismologiques. (L'hypocentre est le point situé sous la surface de la Terre où un séisme commence. L'épicentre est le point à la surface directement au-dessus de l'hypocentre.) Il s'agit d'une tâche extrêmement complexe, car les propriétés des ondes sismiques dépendent des propriétés des couches rocheuses à travers lesquelles elles se propagent. La méthode traditionnelle pour localiser l'hypocentre repose sur ce qui est connu sous le nom d'algorithme d'inversion sismique, qui commence par une meilleure estimation de l'emplacement, calcule les dérivées du temps de parcours des ondes par rapport à la position de la source, et effectue une opération matricielle pour fournir une localisation mise à jour. Ce processus est répété jusqu'à ce qu'une solution acceptable soit atteinte. (Ce Post of the Month, de novembre 2003, fournit plus d'informations.) Cependant, cette méthode nécessite des informations sur les dérivées et est sujette à se retrouver piégée dans des optima locaux.
  
  Un algorithme de localisation qui ne dépend pas des informations sur les dérivées ou des modèles de vitesse peut éviter ces lacunes en ne calculant que le problème direct - la différence entre les temps d'arrivée des ondes observés et prédits pour différents emplacements d'hypocentres. Cependant, une recherche exhaustive basée sur cette méthode serait beaucoup trop coûteuse en termes de calcul. C'est, bien sûr, précisément le type de problème d'optimisation auquel les algorithmes génétiques excellent. Comme tous les AG, celui proposé par le document cité est de nature parallèle - plutôt que de perturber progressivement un seul hypocentre pour le rapprocher de la solution, il commence avec un nuage d'hypocentres potentiels qui se rétrécit au fil du temps pour converger vers une seule solution. Les auteurs indiquent que leur approche « peut rapidement localiser des solutions quasi optimales sans une recherche exhaustive de l'espace des paramètres » (p. 1467), affiche un « comportement hautement organisé résultant en une recherche efficace » et constitue un « compromis entre l'efficacité des méthodes basées sur les dérivées et la robustesse d'une recherche exhaustive entièrement non linéaire » (p. 1469). Les auteurs concluent que leur algorithme génétique est « efficace pour une optimisation véritablement globale » (p. 1488) et « un nouvel outil puissant pour effectuer une localisation robuste des hypocentres » (p. 1489).
  
  
• Ingénierie des matériaux
  Giro, Cyrillo et Galvão 2002 ont utilisé des algorithmes génétiques pour concevoir des polymères à base de carbone conducteurs d'électricité, connus sous le nom de polyanilines. Ces polymères, une classe récemment inventée de matériaux synthétiques, ont un « grand potentiel d'applications technologiques » et pourraient ouvrir des fenêtres sur de « nouveaux phénomènes physiques fondamentaux » (p.170). Cependant, en raison de leur haute réactivité, les atomes de carbone peuvent former un nombre virtuellement infini de structures, rendant une recherche systématique de nouvelles molécules aux propriétés intéressantes presque impossible. Dans cet article, les auteurs appliquent une approche basée sur les AG à la tâche de concevoir de nouvelles molécules aux propriétés prédéfinies, en partant d'une population initialement générée aléatoirement de candidats. Ils concluent que leur méthodologie peut être un « outil très efficace » (p.174) pour guider les expérimentateurs dans la recherche de nouveaux composés et est suffisamment générale pour être étendue à la conception de nouveaux matériaux appartenant à pratiquement toute classe de molécules.
  
  Weismann, Hammel et Bäck 1998 ont appliqué des algorithmes évolutionnaires à un problème industriel « non trivial » (p.162) : la conception de revêtements optiques multicouches utilisés pour des filtres qui réfléchissent, transmettent ou absorbent la lumière de fréquences spécifiées. Ces revêtements sont utilisés, par exemple, dans la fabrication de lunettes de soleil ou de disques compacts. Leur fabrication est une tâche précise : les couches doivent être déposées dans une séquence particulière et avec des épaisseurs spécifiques pour produire le résultat souhaité, et les variations environnementales incontrôlables dans l'environnement de fabrication, telles que la température, la pollution et l'humidité, peuvent affecter les performances du produit fini. De nombreux optima locaux ne sont pas robustes face à de telles variations, ce qui signifie que la qualité maximale du produit doit être payée au prix de taux plus élevés de déviation indésirable. Le problème particulier considéré dans cet article comportait également plusieurs critères : en plus de la réflectance, la composition spectrale (couleur) de la lumière réfléchie a également été prise en compte.
  
  L'AE fonctionnait en variant le nombre de couches de revêtement et l'épaisseur de chacune, et a produit des conceptions qui étaient « nettement plus robustes aux variations de paramètres » (p.166) et avaient une performance moyenne supérieure aux méthodes traditionnelles. Les auteurs concluent que « les algorithmes évolutionnaires peuvent rivaliser avec, voire surpasser les méthodes traditionnelles » (p.167) de conception de revêtements optiques multicouches, sans avoir à incorporer des connaissances spécifiques au domaine dans la fonction de recherche et sans avoir à initier la population avec de bonnes conceptions initiales.
  
  Une autre utilisation des AG dans le domaine de l'ingénierie des matériaux mérite d'être mentionnée : Robin et al. 2003 ont utilisé des AG pour concevoir des motifs d'exposition pour un faisceau de lithographie électronique, utilisé pour graver des structures à l'échelle submicrométrique sur des circuits intégrés. Concevoir ces motifs est une tâche très difficile ; il est fastidieux et gaspilleur de les déterminer expérimentalement, mais la haute dimensionnalité de l'espace de recherche défait la plupart des algorithmes de recherche. Jusqu'à 100 paramètres doivent être optimisés simultanément pour contrôler le faisceau électronique et empêcher les effets de diffusion et de proximité qui ruineraient autrement les fines structures en cours de sculpture. Le problème direct - déterminer la structure résultante en fonction de la dose électronique - est simple et facile à simuler, mais le problème inverse de déterminer la dose électronique pour produire une structure donnée, ce qui est ce qui est résolu ici, est beaucoup plus difficile et aucune solution déterministe n'existe.
  
  Les algorithmes génétiques, qui sont « connus pour être capables de trouver de bonnes solutions à des problèmes très complexes de haute dimensionnalité » (p.75) sans avoir besoin d'être fournis avec des informations spécifiques au domaine sur la topographie du paysage de recherche, ont été appliqués avec succès à ce problème. Les auteurs de l'article ont employé un AG en régime permanent avec sélection à la roue de la fortune dans une simulation informatique, ce qui a donné des motifs d'exposition « très bien optimisés » (p.77). Par contraste, un type d'algorithme de grimpeur de coteau connu sous le nom d'algorithme simplex-descendant a été appliqué au même problème, sans succès ; la méthode SD est rapidement tombée dans des optima locaux qu'elle ne pouvait pas échapper, produisant des solutions de mauvaise qualité. Une approche hybride des méthodes AG et SD n'a également pas pu améliorer les résultats délivrés par l'AG seul.
  
  
• Mathématiques et algorithmique
  Bien que certaines des applications les plus prometteuses et des démonstrations les plus convaincantes de la puissance des AG soient dans le domaine de la conception en ingénierie, elles sont également pertinentes pour les problèmes mathématiques « purs ». Haupt et Haupt 1998 (p.140) discutent de l'utilisation des AG pour résoudre des équations aux dérivées partielles non linéaires d'ordre élevé, généralement en trouvant les valeurs pour lesquelles les équations sont égales à zéro, et donnent comme exemple une solution GA quasi-parfaite pour les coefficients de l'équation Super Korteweg-de Vries d'ordre cinq.
  
  Trier une liste d'éléments par ordre est une tâche importante en informatique, et un réseau de tri est un moyen efficace d'accomplir cela. Un réseau de tri est une liste fixe de comparaisons effectuées sur un ensemble de taille donnée ; à chaque comparaison, deux éléments sont comparés et échangés s'ils ne sont pas dans l'ordre. Koza et al. 1999, p. 952, ont utilisé la programmation génétique pour faire évoluer des réseaux de tri minimaux pour des ensembles de 7 éléments (16 comparaisons), 8 éléments (19 comparaisons) et 9 éléments (25 comparaisons). Mitchell 1996, p.21, discute de l'utilisation des algorithmes génétiques par W. Daniel Hillis pour trouver un réseau de tri à 61 comparaisons pour un ensemble de 16 éléments, soit une seule étape de plus que le plus petit connu. Cet exemple est particulièrement intéressant pour deux innovations qu'il utilise : les chromosomes diploïdes, et plus notablement, la coévolution hôte-parasite. Les réseaux de tri et les cas de test ont évolué l'un à côté de l'autre ; les réseaux de tri ont reçu une meilleure aptitude en fonction du nombre de cas de test qu'ils triaient correctement, tandis que les cas de test recevaient une meilleure aptitude en fonction du nombre de réseaux de tri qu'ils pouvaient « tromper » pour qu'ils trient incorrectement. Le GA avec coévolution a fonctionné nettement mieux que le même GA sans elle.
  
  Un dernier exemple notable des AG dans le domaine de l'algorithmique peut être trouvé dans Koza et al. 1999, qui ont utilisé la programmation génétique pour découvrir une règle pour le problème de classification par majorité dans les automates cellulaires unidimensionnels qui est meilleure que toutes les règles connues écrites par des humains. Un automate cellulaire unidimensionnel peut être pensé comme une bande finie avec un nombre donné de positions (cellules) sur elle, chacune pouvant contenir soit l'état 0 soit l'état 1. L'automate fonctionne pendant un nombre donné d'étapes temporelles ; à chaque étape, chaque cellule acquiert une nouvelle valeur basée sur sa valeur précédente et la valeur de ses voisins les plus proches. (Le Jeu de la Vie est un automate cellulaire bidimensionnel.) Le problème de classification par majorité consiste à trouver un tableau de règles tel que, si plus de la moitié des cellules sur la bande sont 1 initialement, toutes les cellules passent à 1 ; sinon, toutes les cellules passent à 0. Le défi réside dans le fait que toute cellule individuelle ne peut accéder qu'à des informations sur ses voisins les plus proches ; par conséquent, les ensembles de règles efficaces doivent trouver un moyen de transmettre des informations sur les régions lointaines de la bande.
  
  Il est connu qu'une solution parfaite à ce problème n'existe pas - aucun ensemble de règles ne peut classer avec précision toutes les configurations initiales possibles - mais au cours des vingt dernières années, il y a eu une longue succession de solutions de plus en plus meilleures. En 1978, trois chercheurs ont développé la dite règle GKL, qui classe correctement 81,6 % des états initiaux possibles. En 1993, une règle meilleure avec une précision de 81,8 % a été découverte ; en 1995, une autre règle avec une précision de 82,178 % a été trouvée. Toutes ces règles ont nécessité un travail important par des humains intelligents et créatifs pour être développées. Par contraste, la meilleure règle découverte par une exécution de programmation génétique, donnée dans Koza et al. 1999, p.973, a une précision globale de 82,326 % - meilleure que toutes les solutions créées par des humains développées au cours des deux dernières décennies. Les auteurs notent que leurs nouvelles règles sont qualitativement différentes des règles précédemment publiées, employant des représentations internes fines de la densité d'état et des ensembles complexes de signaux pour communiquer des informations sur de longues distances.
  
  
• Militaire et forces de l'ordre
  Kewley et Embrechts 2002 ont utilisé des algorithmes génétiques pour faire évoluer des plans tactiques pour des batailles militaires. Les auteurs notent que "[l]a planification d'une bataille militaire tactique est une tâche complexe et de haute dimension qui embarrasse souvent les professionnels expérimentés" (p.163), non seulement parce que de telles décisions sont généralement prises dans des conditions de haut stress, mais aussi parce que même des plans simples nécessitent de prendre en compte un grand nombre de variables et de résultats conflictuels : minimiser les pertes de ses propres forces, maximiser les pertes ennemies, contrôler le terrain souhaité, économiser les ressources, et ainsi de suite. Les planificateurs humains ont du mal à gérer la complexité de cette tâche et doivent souvent recourir à des approches "rapides et sales", comme faire ce qui a fonctionné la dernière fois.
  
  Pour surmonter ces difficultés, les auteurs de l'article cité ont développé un algorithme génétique pour automatiser la création de plans de bataille, en conjonction avec un programme de simulateur de bataille graphique. Le commandant entre le résultat souhaité, et l'AG fait évoluer automatiquement un plan de bataille ; dans la simulation utilisée, des facteurs tels que la topographie du terrain, la couverture végétale, la vitesse de déplacement des troupes et la précision de tir ont été pris en compte. Dans cette expérience, la co-évolution a également été utilisée pour améliorer la qualité des solutions : les plans de bataille pour les forces ennemies ont évolué en parallèle des plans des forces amies, obligeant l'AG à corriger toute faiblesse de son propre plan qu'un ennemi pourrait exploiter. Pour mesurer la qualité des solutions produites par l'AG, elles ont été comparées aux plans de bataille pour le même scénario produits par un groupe d'"experts militaires expérimentés... considérés comme très capables de développer des cours d'action tactiques pour la taille des forces utilisées dans cette expérience" (p.166). Ces experts chevronnés ont élaboré leur propre plan et, lorsque la solution de l'AG était terminée, ils ont eu l'occasion de l'examiner et de la modifier à leur guise. Enfin, tous les ensembles de plans ont été exécutés plusieurs fois sur le simulateur pour déterminer leur qualité moyenne.
  
  Les résultats parlent d'eux-mêmes : la solution évoluée a surpassé à la fois le plan des experts militaires et le plan produit par leurs modifications de la solution de l'AG. "...[L]es plans produits par des algorithmes automatisés avaient une performance moyenne significativement plus élevée que ceux générés par des experts militaires expérimentés" (p.161). De plus, les auteurs notent que le plan de l'AG avait un bon sens tactique. (Il impliquait une attaque en deux vagues sur la position ennemie par des pelotons d'infanterie mécanisée soutenus par des hélicoptères d'attaque et des éclaireurs terrestres, en conjonction avec des véhicules aériens sans pilote effectuant des reconnaissances pour diriger le tir d'artillerie.) De plus, le plan évolué comprenait des unités amies individuelles effectuant des missions doctrinales - une propriété émergente qui est apparue au cours de l'exécution, plutôt que d'être spécifiée par l'expérimentateur. Dans des champs de bataille modernes de plus en plus interconnectés, le potentiel attrayant d'un algorithme évolutif capable d'automatiser la production de plans tactiques de haute qualité devrait être évident.
  
  Une utilisation intéressante des AG dans les forces de l'ordre a été rapportée dans Naik 1996, qui a décrit le logiciel "FacePrints", un projet visant à aider les témoins à identifier et décrire des suspects criminels. L'image clichée de l'artiste du dessin policier dessinant le visage du suspect en réponse aux indications des témoins est une méthode difficile et inefficace : la plupart des gens ne sont pas bons à décrire les aspects individuels du visage d'une personne, tels que la taille du nez ou la forme de la mâchoire, mais sont plutôt meilleurs pour reconnaître des visages entiers. FacePrints tire parti de cela en utilisant un algorithme génétique qui fait évoluer des images de visages basées sur des bases de données de centaines de caractéristiques individuelles qui peuvent être combinées d'un nombre immense de façons. Le programme montre aux témoins des images de visages générées aléatoirement, qui choisissent celles qui ressemblent le plus à la personne qu'ils ont vue ; les visages sélectionnés sont ensuite mutés et croisés ensemble pour générer de nouvelles combinaisons de caractéristiques, et le processus se répète jusqu'à ce qu'un portrait précis du visage du suspect émerge. Dans un cas de vol à main armée réel, les portraits finaux créés par les trois témoins étaient étonnamment similaires, et l'image résultante a été imprimée dans le journal local.
  
  
• Biologie moléculaire
  Chez les êtres vivants, les protéines transmembranaires sont des protéines qui traversent une membrane cellulaire. Les protéines transmembranaires remplissent souvent des fonctions importantes, telles que la détection de la présence de certaines substances à l'extérieur de la cellule ou leur transport à l'intérieur de la cellule. La compréhension du comportement d'une protéine transmembranaire nécessite d'identifier le segment de cette protéine qui est réellement intégré dans la membrane, ce qui est appelé le domaine transmembranaire. Au cours des deux dernières décennies, les biologistes moléculaires ont publié une série d'algorithmes de plus en plus précis à cette fin.
  
  Toutes les protéines utilisées par les êtres vivants sont composées des mêmes 20 acides aminés. Certains de ces acides aminés sont hydrophobes, ce qui signifie qu'ils sont repoussés par l'eau, et d'autres sont hydrophiles, ce qui signifie qu'ils sont attirés par l'eau. Les séquences d'acides aminés qui font partie d'un domaine transmembranaire sont plus susceptibles d'être hydrophobes. Cependant, l'hydrophobie n'est pas une caractéristique précisément définie, et il n'existe pas d'échelle unique et consensuelle pour la mesurer.
  
  Koza et al. 1999, chapitre 16, a utilisé la programmation génétique pour concevoir un algorithme destiné à identifier les domaines transmembranaires d'une protéine. La programmation génétique a été dotée d'un ensemble d'opérateurs mathématiques standards à utiliser, ainsi que d'un ensemble de fonctions booléennes de détection d'acides aminés qui retournent +1 si l'acide aminé à une position donnée est l'acide aminé qu'elles détectent, et -1 dans le cas contraire. (Par exemple, la fonction A? prend en argument un nombre correspondant à une position au sein de la protéine, et retourne +1 si l'acide aminé à cette position est l'alanine, qui est désignée par la lettre A ; dans le cas contraire, elle retourne -1). Une variable de mémoire partagée unique maintenait un compteur en cours d'exécution de la somme globale, et lorsque l'algorithme s'est achevé, le segment de protéine a été identifié comme un domaine transmembranaire si sa valeur était positive. Étant donné uniquement ces outils, impliquerait-il pour un concepteur humain la création de nouvelles informations pour produire une solution efficace à ce problème ?
  
  Les solutions produites par la programmation génétique ont été évaluées selon leur aptitude en les testant sur 246 segments de protéine dont le statut transmembranaire était connu. L'individu le meilleur de l'exécution a ensuite été évalué sur 250 cas de test supplémentaires, hors échantillon, et comparé aux performances des quatre meilleurs algorithmes écrits par des humains connus à la même fin. Le résultat : la programmation génétique a produit un algorithme d'identification de segments transmembranaires avec un taux d'erreur global de 1,6 % - nettement inférieur à celui des quatre algorithmes écrits par des humains, le meilleur d'entre eux ayant un taux d'erreur de 2,5 %. L'algorithme conçu génétiquement, que les auteurs ont surnommé la règle 0-2-4, fonctionne comme suit :
  
  
  • Augmenter la somme en cours d'exécution de 4 pour chaque instance d'acide aminé acide glutamique (électriquement chargé et très hydrophile) dans le segment de protéine.
  • Augmenter la somme en cours d'exécution de 0 pour chaque instance d'acide aminé alanine, phénylalanine, isoleucine, leucine, méthionine ou valine (tous des acides aminés très hydrophobes) dans le segment de protéine.
  • Augmenter la somme en cours d'exécution de 2 pour chaque instance de tous les autres acides aminés.
  • Si [(SUM - 3,1544)/0,9357] est inférieur à la longueur du segment de protéine, classer ce segment comme un domaine transmembranaire ; sinon, le classer comme un domaine non transmembranaire.
  
  
• Reconnaissance de motifs et mining de données
  Competition in the telecommunications industry today is fierce, and a new term - "churn" - has been coined to describe the rapid rate at which subscribers switch from one service provider to another. Churn costs telecom carriers a large amount of money each year, and reducing churn is an important factor in increasing profitability. If carriers can contact customers who are likely to switch and offer them special incentives to stay, churn rates can be reduced; but no carrier has the resources to contact more than a small percent of its customers. The problem is therefore how to identify customers who are more likely to churn. All carriers have extensive databases of customer information that can theoretically be used for this purpose; but what method works best for sifting through this vast amount of data to identify the subtle patterns and trends that signify a customer's likelihood of churning?
  
  Au, Chan et Yao 2003 applied genetic algorithms to this problem to generate a set of if-then rules that predict the churning probability of different groups of customers. In their GA, the first generation of rules, all of which had one condition, was generated using a probabilistic induction technique. Subsequent generations then refine these, combining simple, single-condition rules into more complex, multi-condition rules. The fitness measure used an objective "interestingness" measure of correlation which requires no subjective input. The evolutionary data-mining algorithm was tested on a real-world database of 100,000 subscribers provided by a Malaysian carrier, and its performance was compared against two alternative methods: a multilayer neural network and a widely used decision-tree-based algorithm, C4.5. The authors state that their EA was able to discover hidden regularities in the database and was "able to make accurate churn prediction under different churn rates" (p.542), outperforming C4.5 under all circumstances, outperforming the neural network under low monthly churn rates and matching the neural network under larger churn rates, and reaching conclusions more quickly in both cases. Some further advantages of the evolutionary approach are that it can operate efficiently even when some data fields are missing and that it can express its findings in easily understood rule sets, unlike the neural net.
  
  Among some of the more interesting rules discovered by the EA are as follows: subscribers are more likely to churn if they are personally subscribed to the service plan and have not been admitted to any bonus scheme (a potential solution is to admit all such subscribers to bonus schemes); subscribers are more likely to churn if they live in Kuala Lumpur, are between 36 and 44 in age, and pay their bills with cash (presumably because it is easier for subscribers who pay cash, rather than those whose accounts are automatically debited, to switch providers); and subscribers living in Penang who signed up through a certain dealer are more likely to churn (this dealer may be providing poor customer service and should be investigated).
  
  Rizki, Zmuda et Tamburino 2002 used evolutionary algorithms to evolve a complex pattern recognition system with a wide variety of potential uses. The authors note that the task of pattern recognition is increasingly being performed by machine learning algorithms, evolutionary algorithms in particular. Most such approaches begin with a pool of predefined features, from which an EA can select appropriate combinations for the task at hand; by contrast, this approach began from the ground up, first evolving individual feature detectors in the form of expression trees, then evolving cooperative combinations of those detectors to produce a complete pattern recognition system. The evolutionary process automatically selects the number of feature detectors, the complexity of the detectors, and the specific aspects of the data each detector responds to.
  
  To test their system, the authors gave it the task of classifying aircraft based on their radar reflections. The same kind of aircraft can return quite different signals depending on the angle and elevation at which it is viewed, and different kinds of aircraft can return very similar signals, so this is a non-trivial task. The evolved pattern recognition system correctly classified 97.2% of the targets, a higher net percentage than any of the three other techniques - a perceptron neural network, a nearest-neighbor classifier algorithm, and a radial basis algorithm - against which it was tested. (The radial basis network's accuracy was only 0.5% less than the evolved classifier, which is not a statistically significant difference, but the radial basis network required 256 feature detectors while the evolved recognition system used only 17.) As the authors state, "The recognition systems that evolve use fewer features than systems formed using conventional techniques, yet achieve comparable or superior recognition accuracy" (p.607). Various aspects of their system have also been applied to problems including optical character recognition, industrial inspection and medical image analysis.
  
  Hughes et Leyland 2000 also applied multiple-objective GAs to the task of classifying targets based on their radar reflections. High-resolution radar cross section data requires massive amounts of disk storage space, and it is very computationally intensive to produce an actual model of the source from the data. By contrast, the authors' GA-based approach proved very successful, producing a model as good as the traditional iterative approach while reducing the computational overhead and storage requirements to the point where it was feasible to generate good models on a desktop computer. By contrast, the traditional iterative approach requires ten times the resolution and 560,000 times as many accesses of image data to produce models of similar quality. The authors conclude that their results "clearly demonstrate" (p.160) the ability of the GA to process both two- and three-dimensional radar data of any level of resolution with far fewer calculations than traditional methods, while retaining acceptably high accuracy.
  
  
• Robotique
  Le tournoi international RoboCup est un projet visant à promouvoir les avancées en robotique, en intelligence artificielle et dans les domaines connexes en proposant un problème standard où de nouvelles technologies peuvent être testées – plus précisément, il s'agit d'un tournoi annuel de football entre des équipes de robots autonomes. (L'objectif déclaré est de développer une équipe de robots humanoïdes capable de battre l'équipe de football humaine championne du monde d'ici 2050 ; à l'heure actuelle, la plupart des équipes de robots concurrentes sont à roues.) Les programmes qui contrôlent les membres de l'équipe robotique doivent afficher un comportement complexe, décidant quand bloquer, quand frapper, comment se déplacer, quand passer le ballon à des coéquipiers, comment coordonner la défense et l'attaque, etc. Dans la ligue de simulation du concours de 1997, David Andre et Astro Teller ont présenté une équipe nommée Darwin United dont les programmes de contrôle ont été développés automatiquement de zéro par programmation génétique, un défi à la sagesse conventionnelle selon laquelle « ce problème est tout simplement trop difficile pour une telle technique » (Andre et Teller 1999, p. 346).
  
  Pour résoudre ce problème difficile, Andre et Teller ont fourni à l'algorithme de programmation génétique un ensemble de fonctions de contrôle primitives telles que tourner, se déplacer, frapper, etc. (Ces fonctions étaient elles-mêmes sujettes à changement et à raffinement au cours du processus d'évolution.) Leur fonction d'aptitude, écrite pour récompenser une bonne performance en général plutôt que le marquage spécifiquement, a fourni une liste d'objectifs de plus en plus importants : se rapprocher du ballon, frapper le ballon, garder le ballon du côté adverse du terrain, se déplacer dans la bonne direction, marquer des buts et gagner le match. Il convient de noter qu'aucun code n'a été fourni pour enseigner spécifiquement à l'équipe comment atteindre ces objectifs complexes. Les programmes évolués ont ensuite été évalués à l'aide d'un modèle de sélection hiérarchique : d'abord, les équipes candidates ont été testées sur un terrain vide et rejetées si elles ne marquaient pas de but dans les 30 secondes. Ensuite, elles ont été évaluées face à une équipe de poteaux de « frappe » stationnaires qui frappent le ballon vers le côté opposé du terrain. Troisièmement, l'équipe a joué un match contre l'équipe gagnante du concours RoboCup 1997. Enfin, les équipes ayant marqué au moins un but contre cette équipe se sont affrontées entre elles pour déterminer laquelle était la meilleure.
  
  Parmi les 34 équipes de sa division, Darwin United a finalement terminé 17e, se plaçant carrément au milieu du peloton et surpassant la moitié des entrées écrites par des humains. Bien qu'une victoire au tournoi aurait incontestablement été plus impressionnante, ce résultat est compétitif et significatif en soi, et apparaît encore plus ainsi à la lumière de l'histoire. Il y a environ 25 ans, les programmes informatiques jouant aux échecs étaient à leurs balbutiements ; un ordinateur n'avait récemment participé qu'à un tournoi régional pour la première fois, bien qu'il n'ait pas gagné (Sagan 1979, p. 286). Mais « une machine qui joue aux échecs au niveau intermédiaire de l'expertise humaine est une machine très capable » (ibid.), et l'on peut dire que la même chose est vraie pour le football robotique. Tout comme les machines jouant aux échecs concourent aujourd'hui au niveau de grand maître mondial, quels types de systèmes la programmation génétique produira-t-elle dans 20 ou 30 ans ?
  
  
• Routage et planification
  Burke et Newall 1999 used genetic algorithms to schedule exams among university students. The timetable problem in general is known to be NP-complete, meaning that no method is known to find a guaranteed-optimal solution in a reasonable amount of time. In such a problem, there are both hard constraints - two exams may not be assigned to the same room at the same time - and soft constraints - students should not be assigned to multiple exams in succession, if possible, to minimize fatigue. Hard constraints must be satisfied, while soft constraints should be satisfied as far as possible. The authors dub their hybrid approach for solving this problem a "memetic algorithm": an evolutionary algorithm with rank-based, fitness-proportionate selection, combined with a local hill-climber to optimize solutions found by the EA. The EA was applied to data sets from four real universities (the smallest of which had an enrollment of 25,000 students), and its results were compared to results produced by a heuristic backtracking method, a well-established algorithm that is among the best known for this problem and that is used at several real universities. Compared to this method, the EA produced a result with a quite uniform 40% reduction in penalty.
  
  He et Mort 2000 applied genetic algorithms to the problem of finding optimal routing paths in telecommunications networks (such as phone networks and the Internet) which are used to relay data from senders to recipients. This is an NP-hard optimization problem, a type of problem for which GAs are "extremely well suited... and have found an enormous range of successful applications in such areas" (p.42). It is also a multiobjective problem, balancing conflicting objectives such as maximizing data throughput, minimizing transmission delay and data loss, finding low-cost paths, and distributing the load evenly among routers or switches in the network. Any successful real-world algorithm must also be able to re-route around primary paths that fail or become congested.
  
  In the authors' hybrid GA, a shortest-path-first algorithm, which minimizes the number of "hops" a given data packet must pass through, is used to generate the seed for the initial population. However, this solution does not take into account link congestion or failure, which are inevitable conditions in real networks, and so the GA takes over, swapping and exchanging sections of paths. When tested on a data set derived from a real Oracle network database, the GA was found to be able to efficiently route around broken or congested links, balancing traffic load and maximizing the total network throughput. The authors state that these results demonstrate the "effectiveness and scalability" of the GA and show that "optimal or near-optimal solutions can be achieved" (p.49).
  
  This technique has found real-world applications for similar purposes, as reported in Begley et Beals 1995. The telecommunications company U.S. West (now merged with Qwest) was faced with the task of laying a network of fiber-optic cable. Until recently, the problem of designing the network to minimize the total length of cable laid was solved by an experienced engineer; now the company uses a genetic algorithm to perform the task automatically. The results: "Design time for new networks has fallen from two months to two days and saves US West $1 million to $10 million each" (p.70).
  
  Jensen 2003 and Chryssolouris et Subramaniam 2001 applied genetic algorithms to the task of generating schedules for job shops. This is an NP-hard optimization problem with multiple criteria: factors such as cost, tardiness, and throughput must all be taken into account, and job schedules may have to be rearranged on the fly due to machine breakdowns, employee absences, delays in delivery of parts, and other complications, making robustness in a schedule an important consideration. Both papers concluded that GAs are significantly superior to commonly used dispatching rules, producing efficient schedules that can more easily handle delays and breakdowns. These results are not merely theoretical, but have been applied to real-world situations:
  
  As reported in Naik 1996, organizers of the 1992 Paralympic Games used a GA to schedule events. As reported in Petzinger 1995, John Deere & Co. has used GAs to generate schedules for a Moline, Illinois plant that manufactures planters and other heavy agricultural equipment. Like luxury cars, these can be built in a wide variety of configurations with many different parts and options, and the vast number of possible ways to build them made efficient scheduling a seemingly intractable problem. Productivity was hampered by scheduling bottlenecks, worker teams were bickering, and money was being lost. Finally, in 1993, Deere turned to Bill Fulkerson, a staff analyst and engineer who conceived of using a genetic algorithm to produce schedules for the plant. Overcoming initial skepticism, the GA quickly proved itself: monthly output has risen by 50 percent, overtime has nearly vanished, and other Deere plants are incorporating GAs into their own scheduling.
  
  As reported in Rao 1998, Volvo has used an evolutionary program called OptiFlex to schedule its million-square-foot factory in Dublin, Virginia, a task that requires handling hundreds of constraints and millions of possible permutations for each vehicle. Like all genetic algorithms, OptiFlex works by randomly combining different scheduling possibilities and variables, determines their fitness by ranking them according to costs, benefits and constraints, then causes the best solutions to swap genes and sends them back into the population for another trial. Until recently, this daunting task was handled by a human engineer who took up to four days to produce the schedule for each week; now, thanks to GAs, this task can be completed in one day with minimal human intervention.
  
  As reported in Lemley 2001, United Distillers and Vintners, a Scottish company that is the largest and most profitable spirits distributor in the world and accounts for over one-third of global grain whiskey production, uses a genetic algorithm to manage its inventory and supply. This is a daunting task, requiring the efficient storage and distribution of over 7 million barrels containing 60 distinct recipes among a vast system of warehouses and distilleries, depending on a multitude of factors such as age, malt number, wood type and market conditions. Previously, coordinating this complex flow of supply and demand required five full-time employees. Today, a few keystrokes on a computer instruct a genetic algorithm to generate a new schedule each week, and warehouse efficiency has nearly doubled.
  
  Beasley, Sonander et Havelock 2001 used a GA to schedule airport landings at London Heathrow, the United Kingdom's busiest airport. This is a multiobjective problem that involves, among other things, minimizing delays and maximizing number of flights while maintaining adequate separation distances between planes (air vortices that form in a plane's wake can be dangerous to another flying too closely behind). When compared to actual schedules from a busy period at the airport, the GA was able to reduce average wait time by 2-5%, equating to one to three extra flights taking off and landing per hour - a significant improvement. However, even greater improvements have been achieved: as reported in Wired 2002, major international airports and airlines such as Heathrow, Toronto, Sydney, Las Vegas, San Francisco, America West Airlines, AeroMexico, and Delta Airlines are using genetic algorithms to schedule takeoffs, landings, maintenance and other tasks, in the form of Ascent Technology's SmartAirport Operations Center software (see http://www.ascent.com/faq.html). Breeding and mutating solutions in the form of schedules that incorporate thousands of variables, "Ascent beats humans hands-down, raising productivity by up to 30 percent at every airport where it's been implemented."
  
  
• Ingénierie des systèmes
  Benini et Toffolo 2002 applied a genetic algorithm to the multi-objective task of designing wind turbines used to generate electric power. This design "is a complex procedure characterized by several trade-off decisions... The decision-making process is very difficult and the design trends are not uniquely established" (p.357); as a result, there are a number of different turbine types in existence today and no agreement on which, if any, is optimal. Mutually exclusive objectives such as maximum annual energy production and minimal cost of energy must be taken into account. In this paper, a multi-objective evolutionary algorithm was used to find the best trade-offs between these goals, constructing turbine blades with the optimal configuration of characteristics such as tip speed, hub/tip ratio, and chord and twist distribution. In the end, the GA was able to find solutions competitive with commercial designs, as well as more clearly elucidate the margins by which annual energy production can be improved without producing overly expensive designs.
  
  Haas, Burnham et Mills 1997 used a multiobjective genetic algorithm to optimize the beam shape, orientation and intensity of X-ray emitters used in targeted radiotherapy to destroy cancerous tumors while sparing healthy tissue. (X-ray photons aimed at a tumor tend to be partially scattered by structures within the body, unintentionally damaging internal organs. The challenge is to minimize this effect while maximizing the radiation dose delivered to the tumor.) Using a rank-based fitness model, the researchers began with the solution produced by the conventional method, an iterative least-squares approach, and then used the GA to modify and improve it. By constructing a model of a human body and exposing it to the beam configuration evolved by the GA, they found good agreement between the predicted and actual distributions of radiation. The authors conclude that their results "show a sparing of [healthy organs] that could not be achieved using conventional techniques" (p.1745).
  
  Lee et Zak 2002 used a genetic algorithm to evolve a set of rules to control an automotive anti-lock braking system. While the ability of antilock brake systems to reduce stopping distance and improve maneuverability has saved many lives, the performance of an ABS is dependent on road surface conditions: for example, an ABS controller that is optimized for dry asphalt will not work as well on wet or icy roads, and vice versa. In this paper, the authors propose a GA to fine-tune an ABS controller that can identify the road surface properties (by monitoring wheel slip and acceleration) and respond accordingly, delivering the appropriate amount of braking force to maximize the wheels' traction. In testing, the genetically tuned ABS "exhibits excellent tracking properties" (p.206) and was "far superior" (p.209) to two other methods of braking maneuvers, quickly finding new optimal values for wheel slip when the type of terrain changes beneath a moving car and reducing total stopping distance. "The lesson we learned from our experiment... is that a GA can help to fine-tune even a well-designed controller. In our case, we already had a good solution to the problem; yet, with the help of a GA, we were able to improve the control strategy significantly. In summary, it seems that it is worthwhile to try to apply a GA, even to a well-designed controller, because there is a good chance that one can find a better set of the controller settings using GAs" (p.211).
  
  As cited in Schechter 2000, Dr. Peter Senecal of the University of Wisconsin used small-population genetic algorithms to improve the efficiency of diesel engines. These engines work by injecting fuel into a combustion chamber which is filled with extremely compressed and therefore extremely hot air, hot enough to cause the fuel to explode and drive a piston that produces the vehicle's motive force. This basic design has changed little since it was invented by Rudolf Diesel in 1893; although vast amounts of effort have been put into making improvements, this is a very difficult task to perform analytically because it requires precise knowledge of the turbulent behavior displayed by the fuel-air mixture and simultaneous variation of many interdependent parameters. Senecal's approach, however, eschewed the use of such problem-specific knowledge and instead worked by evolving parameters such as the pressure of the combustion chamber, the timing of the fuel injections and the amount of fuel in each injection. The result: the simulation produced an improved engine that consumed 15% less fuel than a normal diesel engine and produced one-third as much nitric oxide exhaust and half as much soot. Senecal's team then built a real diesel engine according to the specifications of the evolved solution and got the same results. Senecal is now moving on to evolving the geometry of the engine itself, hopefully producing even greater improvements.
  
  As cited in Begley et Beals 1995, Texas Instruments used a genetic algorithm to optimize the layout of components on a computer chip, placing structures so as to minimize the overall area and create the smallest chip possible. Using a connection strategy that no human had thought of, the GA came up with a design that took 18% less space.
  
  Finally, as cited in Ashley 1992, a proprietary software system known as Engineous that employs genetic algorithms is being used by companies in the aerospace, automotive, manufacturing, turbomachinery and electronics industries to design and improve engines, motors, turbines and other industrial devices. In the words of its creator, Dr. Siu Shing Tong, Engineous is "a master 'tweaker,' tirelessly trying out scores of 'what-if' scenarios until the best possible design emerges" (p.49). In one trial of the system, Engineous was able to produce a 0.92 percent increase in the efficiency of an experimental turbine in only one week, while ten weeks of work by a human designer produced only a 0.5 percent improvement.
  
  Granted, Engineous does not rely solely on genetic algorithms; it also employs numerical optimization techniques and expert systems which use logical if-then rules to mimic the decision-making process of a human engineer. However, these techniques are heavily dependent on domain-specific knowledge, lack general applicability, and are prone to becoming trapped on local optima. By contrast, the use of genetic algorithms allows Engineous to explore regions of the search space that other methods miss.
  
  Engineous has found widespread use in a variety of industries and problems. Most famously, it was used to improve the turbine power plant of the Boeing 777 airliner; as reported in Begley et Beals 1995, the genetically optimized design was almost 1% more fuel-efficient than previous engines, which in a field such as this is "a windfall". Engineous has also been used to optimize the configuration of industrial DC motors, hydroelectric generators and steam turbines, to plan out power grids, and to design superconducting generators and nuclear power plants for orbiting satellites. Rao 1998 also reports that NASA has used Engineous to optimize the design of a high-altitude airplane for sampling ozone depletion, which must be both light and efficient.

Arguments créationnistes

Haut

Comme on pourrait s'y attendre, la démonstration dans le monde réel de la puissance de l'évolution que représentent les algorithmes génétiques (GA) s'est révélée surprenante et déconcertante pour les créationnistes, qui ont toujours affirmé que seul le dessein intelligent, et non la variation aléatoire et la sélection, aurait pu produire le contenu informationnel et la complexité des êtres vivants. Ils ont donc soutenu que le succès des algorithmes génétiques ne nous permet pas d'inférer quoi que ce soit sur l'évolution biologique. Les critiques de deux anti-évolutionnistes, représentant deux points de vue différents, seront abordées : le créationniste de la Terre jeune, le Dr Don Batten d'Answers in Genesis, qui a écrit un article intitulé " Algorithmes génétiques -- montrent-ils que l'évolution fonctionne ?", et le créationniste de la Terre ancienne et partisan du dessein intelligent, le Dr William Dembski, dont le récent livre No Free Lunch (Dembski 2002) aborde ce sujet.

• Don Batten
• William Dembski

Don Batten

• Certain caractéristiques des êtres vivants sont qualitatives, alors que les algorithmes génétiques (AG) sont toujours quantitatifs
  Batten affirme que les AG doivent être quantitatifs, afin que toute amélioration puisse être sélectionnée. C'est vrai. Il ajoute ensuite : « De nombreuses caractéristiques biologiques sont qualitatives : elles fonctionnent ou elles ne fonctionnent pas ; il n'existe donc pas de moyen progressif de passer d'une absence de fonction à une fonction. » Cette affirmation n'a cependant pas été démontrée et n'est pas étayée par des preuves. Batten ne tente même pas de donner un exemple d'une caractéristique biologique qui « fonctionne ou ne fonctionne pas » et qui ne pourrait donc pas être construite progressivement.
  
  Mais même s'il offrait une telle caractéristique, comment pourrait-il prouver qu'il n'existe aucun chemin progressif vers elle ? Même si nous ne connaissons pas de tel chemin, s'ensuit-il qu'il n'en existe aucun ? Bien sûr que non. Batten affirme en effet que si nous ne comprenons pas comment certaines caractéristiques ont évolué, alors il est impossible pour ces caractéristiques d'avoir évolué : un exemple classique de la fallacie logique élémentaire de l'argument par ignorance. L'espace de recherche de toutes les variantes possibles de n'importe quelle caractéristique biologique donnée est énorme, et dans la plupart des cas, nos connaissances ne couvrent qu'une fraction infinitésimale des possibilités. Il est fort probable qu'il existe de nombreux chemins vers une structure que nous ne connaissons pas encore ; il n'y a aucune raison de croire que notre ignorance actuelle limite nos progrès futurs. En fait, l'histoire nous donne raison d'être confiants : les scientifiques ont fait d'énormes progrès pour expliquer l'évolution de nombreuses structures et systèmes biologiques complexes, tant macroscopiques que microscopiques (voir par exemple ces pages sur l'évolution des systèmes moléculaires complexes, des gènes « horloges », de la langue du pic ou du scarabée bombardier). Nous sommes en droit de croire qu'il est probable que ceux qui nous ont jusqu'ici échappé seront également élucidés à l'avenir.
  
  En fait, les AG eux-mêmes nous donnent un excellent motif de croire cela. De nombreux problèmes auxquels ils ont été appliqués sont des questions d'ingénierie et de conception complexes où la solution n'était pas connue à l'avance et où le problème ne pouvait donc pas être « truqué » pour aider au succès de l'algorithme. Si les créationnistes avaient raison, il aurait été tout à fait raisonnable d'attendre que les algorithmes génétiques échouent lamentablement, une fois sur l'autre, lorsqu'ils sont appliqués à ces problèmes ; mais, au contraire, c'est exactement l'inverse qui s'est produit : les AG ont découvert des solutions puissantes et de haute qualité à des problèmes difficiles dans une grande variété de domaines. Cela remet sérieusement en question l'existence même de problèmes tels que ceux décrits par Batten, dont les solutions seraient inaccessibles à un processus évolutif.
  
  
• Les algorithmes génétiques sélectionnent une caractéristique à la fois, alors que les êtres vivants sont multidimensionnels
  Batten affirme que dans les algorithmes génétiques, « une seule caractéristique est sélectionnée, alors que tout être vivant est multidimensionnel », et soutient que chez les êtres vivants possédant des centaines de caractéristiques, « la sélection doit agir sur toutes les caractéristiques qui affectent la survie », alors que « [u]n algorithme génétique ne fonctionnera pas avec trois ou quatre objectifs différents, ou je oserais dire même seulement deux ».
  
  Cet argument révèle l'ignorance profonde de Batten concernant la littérature pertinente. Même une brève revue des travaux réalisés sur les algorithmes évolutionnistes (ou un regard sur une section précédente de cet essai) aurait révélé que les algorithmes génétiques multiobjectifs constituent un domaine de recherche majeur et florissant au sein du champ plus large de l'informatique évolutionniste, et l'aurait empêché de faire une telle affirmation incorrecte et embarrassante. Il existe des articles de revue, des numéros entiers de revues prestigieuses sur l'informatique évolutionniste, des conférences entières et des livres entiers sur le sujet des algorithmes génétiques multiobjectifs. Coello 2000 fournit une revue très exhaustive, avec cinq pages de références à des articles sur l'utilisation d'algorithmes génétiques multiobjectifs dans une large gamme de domaines ; voir également Fleming et Purshouse 2002 ; Hanne 2000 ; Zitzler et Thiele 1999 ; Fonseca et Fleming 1995 ; Srinivas et Deb 1994 ; Goldberg 1989, p.197. Pour certains livres et articles discutant de l'utilisation d'algorithmes génétiques multiobjectifs pour résoudre des problèmes spécifiques, voir : Obayashi et al. 2000 ; Sasaki et al. 2001 ; Benini et Toffolo 2002 ; Haas, Burnham et Mills 1997 ; Chryssolouris et Subramaniam 2001 ; Hughes et Leyland 2000 ; He et Mort 2000 ; Kewley et Embrechts 2002 ; Beasley, Sonander et Havelock 2001 ; Sato et al. 2002 ; Tang et al. 1996 ; Williams, Crossley et Lang 2001 ; Koza et al. 1999 ; Koza et al. 2003. Pour un dépôt exhaustif de citations sur les algorithmes génétiques multiobjectifs, voir http://www.lania.mx/~ccoello/EMOO/.
  
  
• Les AG ne permettent pas la possibilité d'extinction ou de catastrophe d'erreur
  Batten affirme que, dans les AG, « Quelque chose toujours survit pour poursuivre le processus », alors que ce n'est pas nécessairement vrai dans le monde réel - en bref, les AG ne permettent pas la possibilité d'extinction.
  
  Cependant, ce n'est pas vrai ; l'extinction peut survenir. Par exemple, certains AG utilisent un modèle de sélection appelé seuil, dans lequel les individus doivent avoir une fitness supérieure à un certain niveau prédéterminé pour survivre et se reproduire (Haupt et Haupt 1998, p. 37). Si aucun individu ne répond à ce critère dans un tel AG, la population peut en effet disparaître. Mais même dans les AG qui n'utilisent pas de seuil, des états analogues à l'extinction peuvent se produire. Si les taux de mutation sont trop élevés ou les pressions de sélection trop fortes, alors un AG ne trouvera jamais de solution viable. La population peut devenir désordonnée de manière désespérée lorsque des mutations délétères s'accumulent plus vite que la sélection ne peut les éliminer, perturbant ainsi les candidats plus aptes (catastrophe d'erreur), ou elle peut errer inutilement, incapable d'obtenir tout gain de fitness suffisamment important pour être sélectionné. Tout comme dans la nature, il doit y avoir un équilibre, sinon aucune solution ne sera atteinte. Le seul avantage qu'un programmeur a à cet égard est que, si cela se produit, il peut recharger le programme avec des valeurs différentes - pour la taille de la population, pour le taux de mutation, pour la pression de sélection - et recommencer. Évidemment, ce n'est pas une option pour les êtres vivants. Batten dit : « Il n'y a pas de règle en évolution qui stipule que certains organismes dans la population évoluant resteront viables peu importe les mutations qui se produisent », mais il n'y a pas de telle règle dans les algorithmes génétiques non plus.
  
  Batten affirme également que « les AG que j'ai examinés artificiellement préservent le meilleur de la génération précédente et le protègent des mutations ou de la recombinaison au cas où rien de meilleur ne serait produit dans l'itération suivante ». Cette critique sera abordée au point suivant.
  
  
• Les AG ignorent le coût de la substitution
  La prochaine affirmation de Batten est que les AG négligent le «Dilemme de Haldane», qui stipule qu'un allèle qui contribue moins à la fitness d'un organisme mettra un temps proportionnellement plus long pour devenir fixé dans une population. Évidemment, à quoi il fait référence, c'est la technique de sélection élitiste, qui sélectionne automatiquement le meilleur candidat à chaque génération, peu importe à quel point son avantage par rapport à ses concurrents est minime. Il a raison de suggérer qu'en nature, de très légers avantages compétitifs pourraient mettre beaucoup plus de temps à se propager. Les algorithmes génétiques ne sont pas un modèle exact de l'évolution biologique à cet égard.
  
  Cependant, cela est hors sujet. La sélection élitiste est une idéalisation de l'évolution biologique - un modèle de ce qui se produirait en nature si la chance n'intervenait pas de temps en temps. Comme Batten l'admet, le dilemme de Haldane ne stipule pas qu'une mutation légèrement avantageuse ne deviendra jamais fixée dans une population ; il stipule qu'il faudra plus de temps pour qu'elle le fasse. Cependant, lorsque le temps de calcul est précieux ou qu'un chercheur en AG souhaite obtenir une solution plus rapidement, il peut être souhaitable de sauter ce processus en mettant en œuvre l'élitisme. Un point important est que l'élitisme n'affecte pas quelles mutations apparaissent, il ne fait que garantir la sélection des meilleures parmi celles qui apparaissent. Il ne ferait pas de différence quelle que soit la force de la sélection si les mutations augmentant l'information ne survenaient pas. En d'autres termes, l'élitisme accélère la convergence une fois qu'une bonne solution a été découverte - il ne provoque pas un résultat qui ne se serait pas produit autrement. Par conséquent, si les algorithmes génétiques avec élitisme peuvent produire de nouvelles informations, alors l'évolution dans la nature peut le faire également.
  
  De plus, tous les AG n'utilisent pas la sélection élitiste. Beaucoup ne le font pas, se reposant uniquement sur la sélection à la roue de la roulette et d'autres techniques d'échantillonnage stochastique, et pourtant ceux-ci ont été tout aussi réussis. Par exemple, Koza et al. 2003, p.8-9, donne des exemples de 36 cas où la programmation génétique a produit des résultats compétitifs à l'humain, y compris la recréation automatisée de 21 inventions précédemment brevetées (six d'entre elles ont été brevetées pendant ou après 2000), dont 10 dupliquent la fonctionnalité du brevet d'une nouvelle manière, et incluant également deux nouvelles inventions brevetables et cinq nouveaux algorithmes qui surpassent tous les algorithmes écrits par l'humain pour le même objectif. Comme le Dr Koza l'énonce dans une référence antérieure au même travail (1999, p.1070) : « La stratégie élitiste n'est pas utilisée. » D'autres articles cités dans cet essai dans lesquels l'élitisme n'est pas utilisé incluent : Robin et al. 2003 ; Rizki, Zmuda et Tamburino 2002 ; Chryssolouris et Subramaniam 2001 ; Burke et Newall 1999 ; Glen et Payne 1995 ; Au, Chan et Yao 2003 ; Jensen 2003 ; Kewley et Embrechts 2002 ; Williams, Crossley et Lang 2001 ; Mahfoud et Mani 1996. Dans chacun de ces cas, sans aucun mécanisme pour garantir que les meilleurs individus étaient sélectionnés à chaque génération, sans exempter ces individus d'un changement aléatoire potentiellement délétère, les algorithmes génétiques produisent toujours des résultats puissants, efficaces et compétitifs à l'humain. Ce fait peut surprendre des créationnistes tels que Batten, mais il est entièrement attendu par les partisans de l'évolution.
  
  
• Les GA ignorent les contraintes de temps de génération
  Cette critique est déroutante. Batten affirme qu'une seule génération dans un GA peut prendre des microsecondes, alors qu'une seule génération dans tout organisme vivant peut prendre n'importe quel délai, de minutes à des années. C'est vrai, mais il n'est pas expliqué comment cela porte sur la validité des GA comme preuve de l'évolution. Si un GA peut générer de nouvelles informations, peu importe le temps que cela prend, alors assurément l'évolution dans la nature peut le faire aussi ; c'est tout ce que cet essai entend démontrer. La seule question restante serait alors de savoir si l'évolution biologique a réellement eu assez de temps pour provoquer des changements significatifs, et la réponse à cette question serait du ressort des biologistes, des géologues et des physiciens, pas des programmeurs informatiques.
  
  La réponse que ces scientifiques ont fournie est pleinement conforme aux échelles de temps évolutives, cependant. De nombreuses lignes de preuves indépendantes, y compris la datation par isochrones radiométriques, les taux de refroidissement des naines blanches, l'absence d'isotopes à demi-vie courte dans la nature, les taux de récession des galaxies lointaines, et l'analyse du rayonnement cosmique micro-ondes convergent toutes vers la même conclusion : une Terre et un univers âgés de plusieurs milliards d'années, facilement assez longtemps pour que l'évolution produise toute la diversité de la vie que nous voyons aujourd'hui selon toutes les estimations raisonnables.
  
  
• Les AG utilisent des taux de mutation et de reproduction irréalistes
  Batten affirme, sans fournir aucune preuve ou citation à l'appui, que les AG « produisent couramment des centaines ou des milliers de « descendants » par génération », un taux que même les bactéries, les organismes biologiques qui se reproduisent le plus rapidement, ne peuvent égaler.
  
  Cette critique rate la cible à plusieurs égards. D'abord, si la métrique utilisée est (comme elle devrait l'être) le nombre de descendants par génération, plutôt que le nombre de descendants par unité de temps absolu, alors il existe clairement des organismes biologiques capables de se reproduire à des taux plus rapides que ceux des bactéries et approximativement égaux aux taux que Batten prétend être irréalistes. Par exemple, une seule grenouille peut pondre des milliers d'œufs à la fois, chacun ayant le potentiel de se développer en un adulte. Bien sûr, la plupart de ceux-ci ne survivront généralement pas en raison des limitations de ressources et de la prédation, mais alors la plupart des « descendants » dans chaque génération d'un AG ne le feront pas non plus.
  
  Deuxièmement, et plus important encore, un algorithme génétique travaillant sur la résolution d'un problème n'est pas censé représenter un seul organisme. Au contraire, un algorithme génétique est plus analogue à une population entière d'organismes - après tout, ce sont les populations, et non les individus, qui évoluent. Bien sûr, il est tout à fait plausible qu'une population entière ait collectivement des centaines ou des milliers de descendants par génération. (Le créationniste Walter ReMine commet la même erreur à l'égard du programme « renard » du Dr Richard Dawkins. Voir cet Article du Mois pour plus d'informations.)
  
  En outre, Batten dit que le taux de mutation est artificiellement élevé dans les AG, tandis que les organismes vivants possèdent des mécanismes de contrôle d'erreur conçus pour limiter le taux de mutation à environ 1 sur 10 milliards de paires de bases (bien que ce chiffre soit trop faible - le chiffre réel est plus proche de 1 sur 1 milliard. Voir Dawkins 1996, p.124). Eh bien, bien sûr, c'est vrai. Si les AG mutaient à ce taux, ils mettraient bien trop de temps à résoudre des problèmes du monde réel. Il est clair que ce qui devrait être considéré comme pertinent est le taux de mutation par rapport à la taille du génome. Le taux de mutation devrait être suffisamment élevé pour promouvoir une quantité suffisante de diversité dans la population sans submerger les individus. Un humain moyen possédera entre une et cinq mutations ; ce n'est pas du tout irréalistes pour les descendants d'un AG.
  
  
• Les GA ont des génomes artificiellement petits
  L'argument de Batten selon lequel le génome d'un algorithme génétique « est artificiellement petit et ne fait qu'une seule chose » est malheureusement erroné. Tout d'abord, comme nous l'avons vu, il n'est pas vrai qu'un GA ne fasse qu'une seule chose ; il existe de nombreux exemples d'algorithmes génétiques conçus spécifiquement pour optimiser plusieurs paramètres simultanément, souvent bien plus de paramètres simultanément qu'un concepteur humain ne pourrait jamais le faire.
  
  Et comment Batten quantifie-t-il exactement « artificiellement petit » ? De nombreux algorithmes évolutionnaires, tels que la programmation génétique de John Koza, utilisent des codages de longueur variable où la taille des solutions candidates peut croître de manière arbitrairement grande. Batten affirme que même l'organisme vivant le plus simple possède beaucoup plus d'informations dans son génome que ce qu'un GA a jamais produit, mais si les organismes vivant aujourd'hui peuvent avoir des génomes relativement grands, c'est parce que beaucoup de complexité a été acquise au cours de milliards d'années d'évolution. Comme l'article Probability of Abiogenesis le souligne, il existe de bonnes raisons de croire que les premiers organismes vivants étaient beaucoup plus simples que n'importe quelle espèce actuellement existante : des molécules autorépliquantes probablement pas plus longues que 30 ou 40 sous-unités, ce qui pourrait facilement être spécifié par les 1800 bits d'informations que Batten semble admettre au moins un GA a générés. Les algorithmes génétiques sont également une technique très récente dont le plein potentiel n'a pas encore été exploité ; les ordinateurs numériques eux-mêmes n'ont que quelques décennies, et comme Koza (2003, p. 25) le souligne, les techniques de calcul évolutionnaire ont généré des résultats de plus en plus substantiels et complexes au cours des 15 dernières années, en synchronie avec l'augmentation rapide continue de la puissance de calcul souvent appelée « Loi de Moore ». Tout comme la vie primitive était très simple par rapport à ce qui a suivi, les algorithmes génétiques d'aujourd'hui, malgré les résultats impressionnants qu'ils ont déjà produits, sont susceptibles de donner naissance à des choses bien plus grandes dans le futur.
  
  
• Les AG ignorent la possibilité que des mutations se produisent dans tout le génome
  Batten semble ne pas comprendre comment fonctionnent les algorithmes génétiques, et il le démontre en faisant cet argument. Il affirme que dans la réalité, « les mutations se produisent dans tout le génome, et non seulement dans un gène ou une section qui spécifie un trait donné ». C'est vrai, mais lorsqu'il dit que ce n'est pas le cas pour les AG, il se trompe. Tout comme chez les organismes vivants, les AG permettent aux mutations et aux recombinaisons de se produire n'importe où dans les génomes de leurs solutions candidates ; tout comme chez les organismes vivants, les AG doivent éliminer les changements délétères tout en sélectionnant simultanément les bénéfiques.
  
  Batten continue ensuite de prétendre que « le programme lui-même est protégé des mutations ; seules les séquences cibles sont mutées », et si le programme lui-même était muté, il s'effondrerait rapidement. Cette critique, cependant, est sans objet. Il n'y a aucune raison pour laquelle le programme directeur d'un AG devrait être muté. Le programme ne fait pas partie de l'algorithme génétique ; le programme est ce qui supervise l'algorithme génétique et mute les solutions candidates, qui sont ce que le programmeur cherche à améliorer. Le programme exécutant l'AG n'est pas analogue à la machinerie reproductive d'un organisme, une comparaison que Batten tente de faire. Au contraire, il est analogue aux lois naturelles invariantes qui régissent les environnements dans lesquels les organismes vivants vivent et se reproduisent, et celles-ci ne sont pas susceptibles de changer et n'ont pas besoin d'être « protégées » contre cela.
  
  
• Les AG ignorent les problèmes de complexité irréductible
  En utilisant l'argument de « complexité irréductible » de Michael Behe, créationniste de la Terre ancienne, Batten soutient que « De nombreuses caractéristiques biologiques nécessitent la présence et le fonctionnement conjoint de nombreux composants différents pour exister du tout », alors que cela ne se produit pas dans les algorithmes génétiques.
  
  Cependant, il est trivial de montrer que cette affirmation est fausse, car les algorithmes génétiques ont produit des systèmes de complexité irréductible. Par exemple, le circuit de reconnaissance vocale évolué par le Dr Adrian Thompson (Davidson 1997) est composé de 37 portes logiques de base. Cinq d'entre elles ne sont même pas connectées au reste du circuit, pourtant les 37 sont nécessaires au fonctionnement du circuit ; si l'une d'elles est déconnectée de son alimentation, l'ensemble du système cesse de fonctionner. Cela correspond à la définition de Behe d'un système de complexité irréductible et démontre qu'un processus évolutif peut produire de telles choses.
  
  Il convient de noter qu'il s'agit du même argument que le premier, simplement présenté dans un langage différent, et donc la réfutation est la même. La complexité irréductible n'est pas un problème pour l'évolution, que cette évolution se produise chez des êtres vivants dans la nature ou dans du silicium sur une puce de processeur d'ordinateur.
  
  
• Les AG ignorent la polygénie, la pléiotropie et d'autres complexités génétiques
  Batten soutient que les algorithmes génétiques (AG) ignorent les questions de polygénie (la détermination d'un trait par plusieurs gènes), de pléiotropie (un gène affectant plusieurs traits), et de gènes dominants et récessifs.
  
  Cependant, aucune de ces affirmations n'est vraie. Les AG n'ignorent pas la polygénie et la pléiotropie : ces propriétés sont simplement autorisées à apparaître naturellement plutôt que d'être codées délibérément. Il est évident que dans tout système complexe et interdépendant (c'est-à-dire un système non linéaire), la modification ou la suppression d'une partie provoquera un effet d'onde de choc de changements à travers tout le système ; ainsi, les AG incorporent naturellement la polygénie et la pléiotropie. « Dans la littérature sur les algorithmes génétiques, l'interaction des paramètres est appelée épistasie (un terme biologique pour l'interaction des gènes). Lorsque l'épistasie est faible ou inexistante, les algorithmes de recherche de minimum [c'est-à-dire les alpinistes --A.M.] fonctionnent le mieux. Les algorithmes génétiques brillent lorsque l'épistasie est moyenne à élevée... » (Haupt et Haupt 1998, p. 31, emphase originale).
  
  De même, il existe certaines implémentations d'algorithmes génétiques qui possèdent bien des chromosomes diploïdes et des gènes dominants et récessifs (Goldberg 1989, p. 150 ; Mitchell 1996, p. 22). Cependant, celles qui n'en ont pas sont simplement plus proches des organismes haploïdes, tels que les bactéries, que des organismes diploïdes, tels que les êtres humains. Puisque (selon certaines mesures) les bactéries sont parmi les organismes les plus réussis de cette planète, de tels AG restent un bon modèle de l'évolution.
  
  
• Les AG n'ont pas de cadres de lecture multiples
  Batten discute de l'existence de cadres de lecture multiples dans les génomes de certains êtres vivants, dans lesquels les séquences d'ADN codent pour différentes protéines fonctionnelles lorsqu'elles sont lues dans des directions différentes ou avec des décalages de départ différents. Il affirme que « Créer un AG pour générer un tel codage dense en informations semblerait être hors de question ».
  
  Un tel défi appelle une réponse, et voici celle-ci : Soule et Ball 2001. Dans cet article, les auteurs présentent un algorithme génétique avec plusieurs cadres de lecture et un codage dense, lui permettant de stocker plus d'informations que la longueur totale de son génome. Comme les codons à trois nucléotides qui spécifient les acides aminés dans les génomes des organismes vivants, les codons de cet AG étaient des chaînes binaires à cinq chiffres. Étant donné que les codons avaient cinq chiffres de long, il y avait cinq cadres de lecture possibles. La séquence 11111 sert de codon « start » et 00000 de codon « stop » ; parce que les codons de départ et d'arrêt pouvaient se produire n'importe où dans le génome, la longueur de chaque individu était variable. Les régions du chromosome qui ne tombaient pas entre les paires start-stop étaient ignorées.
  
  L'AG a été testé sur quatre problèmes classiques de maximisation de fonction. « Initialement, la majorité des bits ne participent à aucun gène, c'est-à-dire que la plupart d'un chromosome est non codant. Encore une fois, c'est parce que dans les individus aléatoires initiaux, il y a relativement peu de paires de codons start-stop. Cependant, le nombre de bits qui ne participent diminue extrêmement rapidement. » Au cours de l'exécution, l'AG peut augmenter la longueur effective de son génome en introduisant de nouveaux codons de départ dans différents cadres de lecture. À la fin de l'exécution, « la quantité de chevauchement est assez élevée. De nombreux bits participent à plusieurs (et souvent tous les cinq) gènes. » Sur tous les problèmes de test, l'AG a commencé, en moyenne, avec 5 variables spécifiées ; à la fin de l'exécution, ce nombre avait augmenté à une moyenne d'environ 25.
  
  Dans les problèmes de test, l'AG avec cadres de lecture multiples a produit des solutions nettement meilleures qu'un AG standard sur deux des quatre problèmes et des solutions moyennes meilleures sur les deux autres. Dans un problème, l'AG a réussi à compresser 625 bits d'information au total dans un chromosome de seulement 250 bits de long en utilisant des cadres de lecture alternatifs. Les auteurs qualifient ce comportement de « extrêmement sophistiqué » et concluent que « Ces données montrent qu'un AG peut utiliser avec succès les cadres de lecture malgré la complexité ajoutée » et « Il est clair qu'un AG peut introduire de nouveaux 'gènes' au besoin pour résoudre un problème donné, même avec les difficultés imposées par l'utilisation de codons de départ et d'arrêt et de gènes chevauchants ».
  
  
• Les AG ont des buts préétablis
  Comme plusieurs autres, cette objection montre que Batten ne comprend pas entièrement ce qu'est un algorithme génétique et comment il fonctionne. Il soutient que les AG, contrairement à l'évolution, ont des buts prédéterminés et spécifiés dès le départ, et comme exemple de cela, il offre le programme « renard » du Dr Richard Dawkins.
  
  Cependant, le programme du renard n'est pas un véritable algorithme génétique, et n'est pas représentatif des algorithmes génétiques, précisément pour cette raison. Il n'était pas destiné à démontrer le pouvoir de résolution de problèmes de l'évolution. Au contraire, son seul but était de montrer la différence entre la sélection en une seule étape (le fameux « tornado soufflant dans une décharge produisant un 747 ») et la sélection cumulative, en plusieurs étapes. Il avait bien un but spécifique prédéterminé dès le départ. Les vrais algorithmes génétiques, en revanche, n'en ont pas.
  
  Dans un sens très général, les AG ont bien un but : à savoir, trouver une solution acceptable à un problème donné. Dans ce même sens, l'évolution a aussi un but : produire des organismes mieux adaptés à leur environnement et ainsi bénéficier d'un succès reproductif plus grand. Mais tout comme l'évolution est un processus sans buts spécifiques, les AG ne spécifient pas dès le départ comment un problème donné doit être résolu. La fonction d'aptitude est simplement mise en place pour évaluer dans quelle mesure une solution candidate fonctionne bien, sans spécifier aucune manière particulière dont elle devrait fonctionner et sans porter de jugement sur la manière qu'elle invente. La solution elle-même émerge alors par un processus de mutation et de sélection.
  
  La prochaine affirmation de Batten montre clairement qu'il ne comprend pas ce qu'est un algorithme génétique. Il soutient que « Peut-être si le programmeur pouvait concevoir un programme permettant à tout de se produire et ensuite mesurer la survivabilité des « organismes », cela pourrait s'approcher de ce que l'évolution est censée faire » - mais c'est exactement ainsi que fonctionnent les algorithmes génétiques. Ils génèrent aléatoirement des solutions candidates et les mutent aléatoirement sur de nombreuses générations. Aucune configuration n'est spécifiée à l'avance ; comme le dit Batten, tout est permis. Comme l'écrit John Koza (2003, p. 37), écho étrange des mots de Batten : « Une caractéristique importante... est que la sélection [en programmation génétique] n'est pas avide. Des individus qui sont connus pour être inférieurs seront sélectionnés dans une certaine mesure. Le meilleur individu de la population n'est pas garanti d'être sélectionné. De plus, le pire individu de la population ne sera pas nécessairement exclu. Tout peut arriver et rien n'est garanti. » (Une section précédente a discuté de ce point très précis comme l'une des forces d'un AG.) Et pourtant, en appliquant un filtre sélectif à ces candidats mutuant aléatoirement, des solutions efficaces, complexes et puissantes à des problèmes difficiles émergent, des solutions qui n'ont été conçues par aucune intelligence et qui peuvent souvent égaler ou surpasser des solutions qui ont été conçues par des humains. L'affirmation légère de Batten selon laquelle « Bien sûr que c'est impossible » est carrément contredite par la réalité.
  
  
• Les AG ne génèrent pas réellement de nouvelles informations
  La dernière critique de Batten est la suivante : « Avec un AG particulier, nous devons demander dans quelle mesure l'« information » générée par le programme est réellement spécifiée dans le programme, plutôt que d'être générée de novo. » Il accuse les AG de ne souvent rien faire d'autre que de trouver le meilleur moyen pour que certains modules interagissent, lorsque à la fois les modules eux-mêmes et les façons dont ils peuvent interagir sont spécifiés à l'avance.
  
  Il est difficile de savoir quoi faire de cet argument. Tout problème imaginable – termes d'une équation de calcul, molécules dans une cellule, composants d'un moteur, actions sur un marché financier – peut être exprimé en termes de modules qui interagissent de manières données. Si tout ce que l'on a sont des modules non spécifiés qui interagissent de manières non spécifiées, il n'y a aucun problème à résoudre. Cela signifie-t-il que la solution à aucun problème nécessite la génération de nouvelles informations ?
  
  En ce qui concerne la critique de Batten sur l'information contenue dans la solution étant préspecifiée dans le problème, le meilleur moyen de dissiper ses inquiétudes est de souligner les nombreux exemples où les AG commencent avec des populations initiales générées aléatoirement qui ne sont en aucun way conçues pour aider l'AG à résoudre le problème. Certains de ces exemples incluent : Graham-Rowe 2004 ; Davidson 1997 ; Assion et al. 1998 ; Giro, Cyrillo et Galvão 2002 ; Glen et Payne 1995 ; Chryssolouris et Subramaniam 2001 ; Williams, Crossley et Lang 2001 ; Robin et al. 2003 ; Andreou, Georgopoulos et Likothanassis 2002 ; Kewley et Embrechts 2002 ; Rizki, Zmuda et Tamburino 2002 ; et surtout Koza et al. 1999 et Koza et al. 2003, qui discutent de l'utilisation de la programmation génétique pour générer 36 inventions compétitives par rapport à l'homme dans la conception de circuits analogiques, la biologie moléculaire, l'algorithmique, la conception de contrôleurs industriels et d'autres domaines, tous partant de populations de candidats initiaux générés aléatoirement.
  
  Il est vrai que certains AG commencent avec des solutions générées intelligemment qu'ils cherchent ensuite à améliorer, mais cela est sans pertinence : dans de tels cas, l'objectif n'est pas seulement de retourner la solution initialement entrée, mais de l'améliorer par la production de nouvelles informations. Dans tous les cas, même si la situation initiale est telle que la décrit Batten, trouver le moyen le plus efficace dont un certain nombre de modules peuvent interagir sous un ensemble donné de contraintes peut être une tâche loin d'être triviale, et dont la solution implique une quantité considérable de nouvelles informations : la planification dans les aéroports internationaux, par exemple, ou les chaînes d'assemblage d'usines, ou la distribution de fûts entre entrepôts et distilleries. Encore une fois, les AG se sont révélés efficaces pour résoudre des problèmes dont la complexité submergerait n'importe quel humain. À la lumière des multiples innovations et des solutions inattendues et efficaces issues des AG dans de nombreux domaines, la revendication de Batten selon laquelle « La quantité de nouvelles informations générées (par un AG) est généralement tout à fait triviale » résonne en effet de manière creuse.

William Dembski

Le récent livre du créationniste de la Terre ancienne, le Dr William Dembski, No Free Lunch: Why Specified Complexity Cannot Be Purchased Without Intelligence, est largement consacré au sujet des algorithmes évolutionnistes et à leur relation avec l'évolution biologique. En particulier, le livre de Dembski s'intéresse à une qualité évasive qu'il appelle « complexité spécifiée », qu'il affirme être contenue en abondance dans les êtres vivants, et qu'il affirme de plus être incapable d'être générée par les processus évolutionnistes, laissant le « dessein » par des mécanismes non spécifiés par un « concepteur intelligent » non identifié comme seule alternative. Pour étayer son cas, Dembski fait appel à une classe de théorèmes mathématiques connus sous le nom de théorèmes No Free Lunch, qu'il prétend prouver que les algorithmes évolutionnistes, en moyenne, ne fonctionnent pas mieux qu'une recherche aveugle.

Richard Wein a écrit une excellente et complète réfutation de Dembski, intitulée Not a Free Lunch But a Box of Chocolates, et ses points ne seront pas reproduits ici. Je me concentrerai plutôt sur le chapitre 4 du livre de Dembski, qui traite en détail des algorithmes génétiques.

Dembski avance un argument principal contre les algorithmes génétiques (AG), développé en détail tout au long de ce chapitre. Bien qu'il ne nie pas qu'ils puissent produire des résultats impressionnants — en effet, il dit qu'il y a quelque chose de « étrangement convaincant et presque magique » (p.221) dans la manière dont les AG peuvent trouver des solutions qui ne ressemblent à rien de conçu par les êtres humains —, il soutient que leur succès est dû à la complexité spécifiée qui est « introduite clandestinement » dans ceux-ci par leurs concepteurs humains et qui est ensuite incarnée dans les solutions qu'ils produisent. « En d'autres termes, toute la complexité spécifiée que nous obtenons d'un algorithme évolutionnaire doit d'abord être introduite dans sa construction et dans les informations qui guident l'algorithme. Les algorithmes évolutionnaires ne génèrent ou ne créent donc pas de complexité spécifiée, mais n'utilisent simplement qu'une complexité spécifiée déjà existante » (p.207).

Le premier problème évident dans l'argumentation de Dembski est le suivant. Bien que son chapitre sur les algorithmes évolutionnistes s'étende sur environ 50 pages, les 30 premières de celles-ci ne traitent que de l'algorithme du « renard » du Dr Richard Dawkins, qui, comme déjà discuté, n'est pas un véritable algorithme génétique et ne représente pas les algorithmes génétiques. Les deux autres exemples de Dembski - les antennes génétiques en fil tordu d'Edward Altshuler et Derek Linden et les réseaux de neurones jouant aux dames de Kumar Chellapilla et David Fogel - ne sont introduits que dans les 10 dernières pages du chapitre et sont discutés pendant trois pages, au total. C'est une carence sérieuse, compte tenu du fait que le programme du « renard » ne représente pas la majorité des travaux réalisés dans le domaine de l'informatique évolutive ; néanmoins, les arguments de Dembski relatifs à celui-ci seront analysés.

En ce qui concerne le programme des renards, Dembski déclare que « Dawkins et ses collègues darwinistes utilisent cet exemple pour illustrer la puissance des algorithmes évolutifs » (p. 182), et, encore une fois, « Les darwinistes... sont très séduits par l'exemple METHINKS IT IS LIKE A WEASEL et le voient comme illustrant la puissance des algorithmes évolutifs à générer une complexité spécifiée » (p. 183). Il s'agit d'un homme de paille de la création de Dembski (non pas seulement parce que le livre de Dawkins a été écrit bien avant que Dembski n'ait inventé ce terme !). Voici ce que Dawkins dit vraiment sur le but de son programme :

"Ce qui compte, c'est la différence entre le temps nécessaire à la sélection cumulative et le temps que le même ordinateur, travaillant à plein régime au même rythme, mettrait pour atteindre la phrase cible s'il était contraint d'utiliser l'autre procédure de sélection par étapes uniques : environ un million de millions de millions de millions de millions d'années." (Dawkins 1996, p.49, emphase originale)

En d'autres termes, le programme du blaireau était destiné à démontrer la différence entre deux types de sélection : la sélection en un seul pas, où un résultat complexe est produit par le pur hasard en un seul saut, et la sélection cumulative, où un résultat complexe est construit petit à petit via un processus de filtrage qui préfère préserver les améliorations. Il n'a jamais été destiné à être une simulation de l'évolution dans son ensemble.

La sélection en un seul pas est le processus absurde et improbable fréquemment attaqué dans la littérature créationniste en le comparant à un ouragan traversant un décharge pour produire un avion 747, ou à une explosion dans une imprimerie produisant un dictionnaire. La sélection cumulative est ce que l'évolution utilise réellement. Utiliser la sélection en un seul pas pour obtenir un résultat fonctionnel d'une complexité significative, il faudrait attendre, en moyenne, plusieurs fois l'âge actuel de l'univers. Utilisant la sélection cumulative, cependant, ce même résultat peut être atteint en un laps de temps relativement très court. Démontrer cette différence était l'objectif du programme du renard de Dawkins, et c'était le seul objectif de ce programme. Dans une note de bas de page de ce chapitre, Dembski écrit : « Il est remarquable à quel point l'exemple de Dawkins est recyclé sans aucune indication des difficultés fondamentales qui l'accompagnent » (p. 230), mais ce sont uniquement les conceptions erronées dans l'esprit des créationnistes tels que Dembski et Batten, qui attaquent le programme du renard pour ne pas démontrer quelque chose qu'il n'était jamais destiné à démontrer, qui donnent naissance à ces « difficultés ».

Contrairement à tous les exemples d'algorithmes évolutionnistes discutés dans cet essai, le programme du renard possède en effet un résultat unique et prédéfini, et la qualité des solutions qu'il génère est jugée en les comparant explicitement à ce résultat prédéfini. Par conséquent, Dembski a tout à fait raison lorsqu'il dit que le programme du renard ne génère pas de nouvelle information. Cependant, il fait ensuite un saut gigantesque et totalement injustifié lorsqu'il extrapole cette conclusion à tous les algorithmes évolutionnistes : « En tant que seule possibilité que l'algorithme évolutionniste de Dawkins puisse atteindre, la séquence cible possède en fait une complexité minimale.... Les algorithmes évolutionnistes sont donc incapables de générer une véritable complexité » (p. 182). Même Dembski semble reconnaître cela lorsqu'il écrit : « ...la plupart des algorithmes évolutionnistes dans la littérature sont programmés pour rechercher un espace de solutions possibles à un problème jusqu'à ce qu'ils trouvent une réponse - pas, comme le fait Dawkins ici, en programmant explicitement la réponse à l'avance » (p. 182). Mais ensuite, après avoir donné une raison parfaitement valable pour laquelle le programme du renard n'est pas représentatif des algorithmes génétiques dans leur ensemble, il va inexplicablement faire précisément cette généralisation fallacieuse !

En réalité, le programme des mustélidés diffère considérablement de la plupart des algorithmes génétiques, et l'argument par analogie de Dembski ne tient donc pas. Les vrais algorithmes évolutionnistes, tels que ceux discutés dans cet essai, ne se contentent pas de retrouver des solutions déjà découvertes par d'autres méthodes ; ils sont confrontés à des problèmes dont la solution optimale n'est pas connue à l'avance et doivent découvrir cette solution par eux-mêmes. En effet, si les algorithmes génétiques ne pouvaient faire que redécouvrir des solutions déjà programmées en eux, quel serait l'intérêt de les utiliser ? Ce serait un exercice de redondance. Cependant, l'intérêt scientifique (et commercial) répandu pour les AG démontre qu'il y a bien plus de substance en eux que le plutôt trivial exemple que Dembski tente de réduire à ce champ entier.

Après avoir dressé puis démantelé ce faux argument, Dembski passe à sa prochaine ligne d'argumentation : selon lui, la complexité spécifiée exhibée par les résultats d'algorithmes évolutifs plus représentatifs a, comme le programme du renard, été « introduite clandestinement » par les concepteurs de l'algorithme. « Mais invariablement, nous constatons que lorsque la complexité spécifiée semble être générée gratuitement, elle a en fait été préchargée, introduite clandestinement ou cachée à la vue » (p. 204). Dembski suggère que le lieu de « cachette » le plus courant de la complexité spécifiée se trouve dans la fonction d'aptitude de l'AG. « Ce que [l'algorithme évolutif] a fait, c'est tirer parti de la complexité spécifiée inhérente à la fonction d'aptitude et l'utiliser pour rechercher puis localiser la cible... » (p. 194). Dembski développe ensuite son argument selon lequel, avant qu'un AE ne puisse rechercher un paysage d'aptitude donné pour une solution, un mécanisme doit d'abord être employé pour sélectionner ce paysage d'aptitude parmi ce qu'il appelle un espace des phases de tous les paysages d'aptitude possibles, et si ce mécanisme est également évolutif, un autre mécanisme doit d'abord être employé pour sélectionner sa fonction d'aptitude d'un espace des phases encore plus vaste, et ainsi de suite. Dembski conclut que la seule façon d'arrêter cette régression à l'infini est par l'intelligence, qu'il estime posséder une capacité irréductible et mystérieuse à sélectionner une fonction d'aptitude à partir d'un espace des phases donné sans avoir recours à des espaces des phases d'ordre supérieur. « Il n'existe qu'un seul générateur connu de complexité spécifiée, et c'est l'intelligence » (p. 207).

Dembski a raison lorsqu'il écrit que la fonction d'aptitude « guide un algorithme évolutif vers la cible » (p. 192). Cependant, il a tort d'affirmer que le choix de la bonne fonction d'aptitude est un processus qui nécessite la génération d'une complexité spécifiée encore plus grande que celle produite par l'algorithme évolutif lui-même. Comme Koza (1999, p. 39) l'écrit, la fonction d'aptitude indique à un algorithme évolutif « ce qui doit être fait », et non « comment le faire ». Contrairement à l'exemple non représentatif du programme renard, la fonction d'aptitude d'un algorithme évolutif ne spécifie généralement aucune forme particulière que la solution devrait prendre, et par conséquent, on ne peut pas dire qu'elle contribue à la « complexité spécifiée » de la solution évoluée dans un sens quelconque.

Un exemple illustrera le point avec plus de détails. Dembski affirme que dans l'expérience de dames de Chellapilla et Fogel, leur choix de maintenir le critère de victoire constant d'une partie à l'autre « a inséré une énorme quantité de complexité spécifiée » (p. 223). Il est certainement vrai que le produit final de ce processus affichait une grande quantité de complexité spécifiée (quels que soient les critères choisis pour définir ce terme). Mais est-il vrai que la mesure de fitness choisie contenait autant de complexité spécifiée ? Voici ce que Chellapilla et Fogel disent réellement :

"Pour apprécier le niveau de jeu qui a été atteint, il peut être utile de considérer l'expérience de pensée suivante. Supposons que vous soyez invité à jouer à un jeu sur un plateau de huit par huit cases aux couleurs alternées. Il y a 12 pièces sur chaque côté disposées d'une manière spécifique pour commencer la partie. On vous explique les règles de déplacement des pièces (c'est-à-dire en diagonale, sauts forcés, rois) et que la différence de pièces est disponible comme fonctionnalité. On ne vous indique cependant pas si cette différence est favorable ou défavorable (il existe une version du jeu de dames appelée 'dames suicide', où l'objectif est de 'perdre' le plus rapidement possible) ni si cette information a même de la valeur. Plus important encore, on ne vous indique pas l'objectif du jeu. Vous faites simplement des coups et à un certain moment un observateur externe déclare la partie terminée. Il ne fournit cependant pas de rétroaction sur le fait que vous ayez gagné, perdu ou fait match nul. Les seules données que vous recevez proviennent d'un minimum de cinq telles parties et sont présentées sous la forme d'un score global de points. Ainsi, vous ne pouvez pas savoir avec certitude quelles parties ont contribué au résultat global ou dans quelle mesure. Votre défi consiste à induire les coups appropriés dans chaque partie en vous basant uniquement sur ce niveau grossier de rétroaction." (Chellapilla et Fogel 2001, p. 427)

Il dépasse les limites de l'absurde que Dembski affirme que cette mesure de fitness ait inséré une "énorme" quantité de complexité spécifiée. Si un être humain qui n'avait jamais entendu parler des dames de jeu recevait les mêmes informations, et que nous revenions plusieurs mois plus tard pour découvrir qu'il était devenu un expert de dames de jeu classé internationalement, devrions-nous conclure que de la complexité spécifiée a été générée ?

Dembski affirme que pour renverser son argument, « il faut montrer que trouver l'information qui guide un algorithme évolutif vers une cible est substantiellement plus facile que de trouver la cible directement par une recherche aveugle » (p.204). Je soutiens que c'est précisément le cas. Intuitivement, il ne devrait pas surprendre que la fonction d'aptitude contienne moins d'information que la solution évoluée. C'est précisément la raison pour laquelle les GA ont trouvé un usage si répandu : il est plus facile (nécessite moins d'information) d'écrire une fonction d'aptitude qui mesure à quel point une solution est bonne, que de concevoir une bonne solution à partir de zéro.

En termes plus informels, considérez les deux exemples de Dembski, l'antenne génétique fil tordu et le réseau neuronal capable de jouer aux dames, nommé Anaconda, qui a évolué. Il faut beaucoup d'informations détaillées sur le jeu de dames pour élaborer une stratégie gagnante (considérez Chinook et sa gigantesque bibliothèque de finales). Cependant, il ne faut pas d'informations tout aussi détaillées pour reconnaître une telle stratégie lorsqu'on la voit : tout ce qu'il faut observer, c'est que cette stratégie bat systématiquement ses adversaires. De même, une personne qui ne sait rien de la manière de concevoir une antenne qui rayonne uniformément sur une région hémisphérique dans une plage de fréquence donnée pourrait tout de même tester une telle antenne et vérifier qu'elle fonctionne comme prévu. Dans les deux cas, déterminer ce qui constitue une haute fitness est beaucoup plus facile (nécessite moins d'informations) que de trouver comment atteindre une haute fitness.

Admettons-le, même si choisir une fonction d'aptitude pour un problème donné nécessite moins d'informations que de résoudre effectivement le problème défini par cette fonction d'aptitude, il faut quand même quelques informations pour spécifier la fonction d'aptitude en premier lieu, et il est légitime de se demander d'où provient cette information initiale. Dembski peut toujours s'interroger sur l'origine de l'intelligence humaine qui nous permet de décider de résoudre un problème plutôt qu'un autre, ou sur l'origine des lois naturelles de l'univers qui rendent possible l'existence et la prospérité de la vie et l'occurrence de l'évolution. Ce sont des questions valables, et Dembski a le droit de s'interroger à leur sujet. Cependant, à ce stade - apparemment sans que Dembski lui-même s'en rende compte - il a maintenant dévié de son argument initial. Il ne prétend plus que l'évolution ne peut pas se produire ; au contraire, il demande essentiellement pourquoi nous vivons dans un univers où l'évolution peut se produire. En d'autres termes, ce que Dembski ne semble pas réaliser, c'est que la conclusion logique de son argument est le créationnisme théiste. Il est pleinement compatible avec un Dieu qui (comme de nombreux chrétiens, y compris le biologiste évolutionniste Kenneth Miller, le croient) a utilisé l'évolution comme son outil créateur et a organisé l'univers de telle sorte qu'il ne soit pas seulement probable, mais certain.

Je conclurai en dissipant quelques autres erreurs mineures au chapitre 4 de No Free Lunch. Pour commencer, bien que Dembski, contrairement à Batten, soit clairement conscient du domaine de l'optimisation multi-objectif, il énonce à tort que « tant qu'une forme d'univalence n'est pas atteinte, l'optimisation ne peut commencer » (p. 186). La discussion de cet essai sur les algorithmes génétiques à multiples objectifs démontre l'erreur de cette affirmation. Peut-être que d'autres techniques de conception ont cette restriction, mais l'une des vertus des AG est précisément qu'ils peuvent faire des compromis et optimiser simultanément plusieurs objectifs mutuellement exclusifs, et les superviseurs humains peuvent ensuite choisir la solution qui réalise le mieux leurs objectifs parmi le groupe final de solutions Pareto-optimales. Aucune méthode de combinaison de multiples critères en un seul n'est nécessaire.

Dembski indique également que les PG « semblent moins aptes à construire des systèmes intégrés qui nécessitent plusieurs parties pour réaliser des fonctions nouvelles » (p.237). Les nombreux exemples détaillés dans cet essai (en particulier l'utilisation par John Koza de la programmation génétique pour concevoir des circuits analogiques complexes) montrent également que cette affirmation est fausse.

Enfin, Dembski mentionne que l'INFORMS, l'organisation professionnelle de la communauté de la recherche opérationnelle, accorde très peu d'attention aux AG, et cela « est une raison d'être sceptique quant à la portée et au pouvoir généraux de la technique » (p. 237). Cependant, le simple fait qu'une société scientifique particulière n'utilise pas largement les AG ne signifie pas que de telles utilisations ne sont pas répandues ailleurs ou en général, et cet essai a cherché à montrer que c'est en effet le cas. Les techniques évolutives ont trouvé une grande variété d'utilisations dans pratiquement tous les domaines de la science que l'on pourrait citer, ainsi que parmi de nombreuses entreprises du secteur commercial. Voici une liste partielle :

• Lockheed Martin (Gibbs 1996)
• GlaxoSmithKline (Gillet 2002)
• LBS Capital Management (Naik 1996)
• First Quadrant (Begley and Beals 1995)
• Texas Instruments (Begley and Beals 1995)
• U.S. West (Begley and Beals 1995)
• John Deere & Co. (Petzinger 1995)
• Volvo (Rao 1998)
• Ascent Technology (Wired 2002)
• Boeing (Ashley 1992)
• British Petroleum (Lemley 2001)
• Ford Motor Company (Lemley 2001)
• Unilever (Lemley 2001)
• United Distillers and Vintners (Lemley 2001)

Par contraste, compte tenu du manque de découvertes scientifiques et de recherches stimulées par le dessein intelligent, Dembski se trouve dans une position peu favorable pour se plaindre du manque d'applications pratiques. Le dessein intelligent est une hypothèse vide de sens, ne nous apprenant rien d'autre que « Un certain concepteur a fait quelque chose, d'une manière ou d'une autre, à un certain moment, pour provoquer ce résultat. » Par contraste, cet essai a, j'espère, démontré que l'évolution est une stratégie de résolution de problèmes riche en applications pratiques.

Conclusion

Haut

Même les créationnistes trouvent impossible de nier que la combinaison de la mutation et de la sélection naturelle peut produire une adaptation. Néanmoins, ils tentent toujours de justifier leur rejet de l'évolution en divisant le processus évolutif en deux catégories - « microévolution » et « macroévolution » - et en soutenant que seule la seconde est controversée, et que tout changement évolutif que nous observons n'est qu'un exemple de la première.

Aujourd'hui, la microévolution et la macroévolution sont des termes qui ont un sens pour les biologistes ; elles sont définies, respectivement, comme l'évolution en dessous du niveau de l'espèce et l'évolution au niveau de l'espèce ou au-dessus. Mais la différence cruciale entre la façon dont les créationnistes utilisent ces termes et la façon dont les scientifiques les utilisent est que les scientifiques reconnaissent que ces deux concepts sont fondamentalement le même processus avec les mêmes mécanismes, n'opérant simplement à des échelles différentes. Les créationnistes, en revanche, sont contraints de postuler un type de fossé infranchissable séparant les deux, afin de pouvoir nier que les processus de changement et d'adaptation que nous observons en action dans le présent peuvent être extrapolés pour produire toute la diversité observée dans le monde vivant.

Cependant, les algorithmes génétiques rendent cette vision insoutenable en démontrant la continuité fondamentale du processus évolutif. Prenons, par exemple, un problème consistant à programmer un circuit pour discriminer entre un ton de 1 kilohertz et un ton de 10 kilohertz, et répondre respectivement avec des sorties constantes de 0 et 5 volts. Disons que nous avons une solution candidate capable de discriminer avec précision les deux tons, mais que ses sorties ne sont pas tout à fait constantes comme requis ; elles produisent de petites ondes plutôt que la tension invariable requise. Supposons, selon la vision créationniste, que modifier ce circuit de son état actuel à la solution parfaite serait une « microévolution », un petit changement à la portée de la mutation et de la sélection pour le produire. Mais sûrement, un créationniste arguerait qu'arriver à cet même état final à partir d'une disposition initiale complètement aléatoire des composants serait une « macroévolution » et hors de portée d'un processus évolutif. Cependant, les algorithmes génétiques ont réussi à accomplir les deux, évoluant le système d'une disposition aléatoire vers la solution quasi-parfaite et enfin vers la solution parfaite et optimale. À aucune étape du processus, une difficulté insoluble ou un fossé qui ne pouvait être comblé n'est apparu. À aucun moment, une intervention humaine était requise pour assembler un noyau de composants à complexité irréductible (malgré le fait que le produit fini contient effectivement une telle chose) ou pour « guider » le système évolutif au-dessus d'un pic difficile. Le circuit a évolué, sans aucune guidance intelligente, d'un état complètement aléatoire et non fonctionnel vers un état fortement complexe, efficace et optimal. Comment cela peut-il ne pas être une démonstration expérimentale convaincante de la puissance de l'évolution ?

Il a été dit que l'évolution culturelle humaine a surpassé le type biologique - que nous, en tant qu'espèce, avons atteint un point où nous sommes capables de contrôler consciemment notre société, notre environnement et même nos gènes à un degré suffisant pour rendre le processus évolutif insignifiant. Il a été dit que les caprices culturels de notre société en rapide mutation, plutôt que le rythme comparativement glacialement lent de la mutation génétique et de la sélection naturelle, est ce qui détermine l'aptitude aujourd'hui. Dans un certain sens, cela peut tout à fait être vrai.

Mais dans un autre sens, rien ne pourrait être plus éloigné de la vérité. L'évolution est un processus de résolution de problèmes dont nous commençons à peine à comprendre et exploiter la puissance ; malgré cela, elle est déjà à l'œuvre partout autour de nous, façonnant notre technologie et améliorant notre vie, et à l'avenir, ces utilisations ne feront que se multiplier. Sans une compréhension détaillée du processus évolutif, aucun des innombrables progrès que nous devons aux algorithmes génétiques n'aurait été possible. Il y a une leçon ici pour ceux qui nient la puissance de l'évolution, ainsi que pour ceux qui nient que la connaissance de celle-ci ait un bénéfice pratique. Bien que cela puisse sembler incroyable, l'évolution fonctionne. Comme l'a dit le poète Lord Byron : "'Tis strange but true; for truth is always strange, stranger than fiction."

Références et ressources

Haut

"Apprentissage adaptatif : Volez dans les cieux intelligents." Wired, vol.10, no.3 (mars 2002). Disponible en ligne à http://www.wired.com/wired/archive/10.03/everywhere.html?pg=2.

Altshuler, Edward et Derek Linden. « Conception d'une antenne filaire à l'aide d'un algorithme génétique. » Journal of Electronic Defense, vol. 20, no. 7, p. 50-52 (juillet 1997).

Andre, David and Astro Teller. "Evolving team Darwin United." In RoboCup-98 : Coupe du monde de robot soccer II, Minoru Asada and Hiroaki Kitano (eds). Lecture Notes in Computer Science, vol.1604, p.346-352. Springer-Verlag, 1999.

• Voir aussi : Willihnganz, Alexis. « Logiciel qui écrit du logiciel. » Salon, 10 août 1998. Disponible en ligne à http://www.salon.com/tech/feature/1999/08/10/genetic_programming/.

Andreou, Andreas, Efstratios Georgopoulos et Spiridon Likothanassis. « Prévision des taux de change : un algorithme hybride basé sur des réseaux de neurones adaptatifs optimisés génétiquement. » Computational Economics, vol.20, no.3, p.191-210 (décembre 2002).

Ashley, Steven. « Engineous explore l'espace du dessein. » Mechanical Engineering, février 1992, p.49-52.

Assion, A., T. Baumert, M. Bergt, T. Brixner, B. Kiefer, V. Seyfried, M. Strehle et G. Gerber. « Contrôle des réactions chimiques par des impulsions laser femtoseconde à phase façonnée optimisées par rétroaction. » Science, vol. 282, p. 919-922 (30 octobre 1998).

Au, Wai-Ho, Keith Chan, et Xin Yao. « Un algorithme de fouille de données évolutionnaire novateur avec des applications à la prédiction du churn. » IEEE Transactions on Evolutionary Computation, vol.7, no.6, p.532-545 (décembre 2003).

Beasley, J.E., J. Sonander et P. Havelock. « Planification des atterrissages d'avions à l'aéroport de Londres Heathrow en utilisant une heuristique de population. » Journal of the Operational Research Society, vol.52, no.5, p.483-493 (mai 2001).

Begley, Sharon et Gregory Beals. « Logiciel au naturel. » Newsweek, 8 mai 1995, p.70.

Benini, Ernesto et Andrea Toffolo. « Conception optimale d'éoliennes à axe horizontal utilisant la théorie des éléments de pale et le calcul évolutionnaire. » Journal of Solar Energy Engineering, vol.124, no.4, p.357-363 (novembre 2002).

Burke, E.K. et J.P. Newall. « Un algorithme évolutionnaire multistades pour le problème des horaires. » IEEE Transactions on Evolutionary Computation, vol. 3, no. 1, p. 63-74 (avril 1999).

Charbonneau, Paul. « Algorithmes génétiques en astronomie et en astrophysique. » The Astrophysical Journal Supplement Series, vol.101, p.309-334 (décembre 1995).

Chellapilla, Kumar et David Fogel. « Faire évoluer un programme d'expert aux échecs sans utiliser d'expertise humaine. » IEEE Transactions on Evolutionary Computation, vol. 5, no. 4, p. 422-428 (août 2001). Disponible en ligne à http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar et David Fogel. « Anaconda bat Hoyle 6-0 : une étude de cas comparant un programme d'échecs évolué à des logiciels disponibles sur le marché. » Dans Proceedings of the 2000 Congress on Evolutionary Computation, p. 857-863. IEEE Press, 2000. Disponible en ligne à http://www.natural-selection.com/NSIPublicationsOnline.htm.

Chellapilla, Kumar et David Fogel. « Vérification de la notation experte d'Anaconda en rivalisant avec Chinook : expériences sur la co-évolution d'un joueur de dames utilisant un réseau de neurones. » Neurocomputing, vol.42, no.1-4, p.69-86 (janvier 2002).

Chryssolouris, George et Velusamy Subramaniam. « Planification dynamique des ateliers de fabrication utilisant des algorithmes génétiques. » Journal of Intelligent Manufacturing, vol.12, no.3, p.281-293 (juin 2001).

Coale, Kristi. « Darwin dans une boîte. » Wired News, 14 juillet 1997. Disponible en ligne à http://www.wired.com/news/technology/0,1282,5152,00.html.

Coello, Carlos. « Une enquête mise à jour sur les techniques d'optimisation multiobjectif basées sur les algorithmes génétiques. » ACM Computing Surveys, vol.32, no.2, p.109-143 (juin 2000).

Davidson, Clive. « Créatures issues du silicium primordial. » New Scientist, vol.156, no.2108, p.30-35 (15 novembre 1997). Disponible en ligne à http://www.newscientist.com/hottopics/ai/primordial.jsp.

Dawkins, Richard. L'Horloger aveugle : pourquoi les preuves de l'évolution révèlent un univers sans dessein. W.W. Norton, 1996.

Dembski, William. No Free Lunch: Pourquoi la complexité spécifiée ne peut être acquise sans intelligence. Rowman & Littlefield, 2002.

Fleming, Peter et R.C. Purshouse. « Algorithmes évolutionnaires dans l'ingénierie des systèmes de contrôle : une revue. » Control Engineering Practice, vol. 10, p. 1223-1241 (2002).

Fonseca, Carlos and Peter Fleming. "An overview of evolutionary algorithms in multiobjective optimization." Calcul évolutionniste, vol.3, no.1, p.1-16 (1995).

Forrest, Stephanie. « Algorithmes génétiques : principes de la sélection naturelle appliqués à l'informatique. » Science, vol.261, p.872-878 (1993).

Gibbs, W. Wayt. « Programmer avec la boue primordiale. » Scientific American, octobre 1996, p.48-50.

Gillet, Valerie. « Approches basées sur les réactifs et les produits pour la conception de bibliothèques combinatoires. » Journal of Computer-Aided Molecular Design, vol.16, p.371-380 (2002).

Giro, R., M. Cyrillo et D.S. Galvão. « Conception de polymères conducteurs à l'aide d'algorithmes génétiques. » Chemical Physics Letters, vol. 366, no. 1-2, p. 170-175 (25 novembre 2002).

Glen, R.C. et A.W.R. Payne. « Un algorithme génétique pour la génération automatisée de molécules dans des contraintes. » Journal of Computer-Aided Molecular Design, vol.9, p.181-202 (1995).

Goldberg, David. Algorithmes génétiques dans la recherche, l'optimisation et l'apprentissage automatique. Addison-Wesley, 1989.

Graham-Rowe, Duncan. « La radio émerge de la soupe électronique. » New Scientist, vol.175, no.2358, p.19 (31 août 2002). Disponible en ligne à http://www.newscientist.com/news/news.jsp?id=ns99992732.

• Voir aussi : Bird, Jon et Paul Layzell. « The evolved radio and its implications for modelling the evolution of novel sensors. » Dans Proceedings of the 2002 Congress on Evolutionary Computation, p.1836-1841.

Graham-Rowe, Duncan. « Circuit électronique « évolue » à partir de cristaux liquides. » New Scientist, vol.181, no.2440, p.21 (27 mars 2004).

Haas, O.C.L., K.J. Burnham et J.A. Mills. « Améliorer la sélectivité physique dans le traitement du cancer : une approche de modélisation systémique et d'optimisation. » Control Engineering Practice, vol. 5, no. 12, p. 1739-1745 (décembre 1997).

Hanne, Thomas. « Optimisation multiobjectif globale utilisant des algorithmes évolutionnaires. » Journal of Heuristics, vol.6, no.3, p.347-360 (août 2000).

Haupt, Randy et Sue Ellen Haupt. Algorithmes génétiques pratiques. John Wiley & Sons, 1998.

He, L. et N. Mort. « Algorithmes génétiques hybrides pour le routage de secours des réseaux de télécommunications. » BT Technology Journal, vol. 18, no. 4, p. 42-50 (oct. 2000).

Holland, John. « Algorithmes génétiques. » Scientific American, juillet 1992, p. 66-72.

Hughes, Evan et Maurice Leyland. « Utilisation d'algorithmes génétiques multiples pour générer des modèles de diffuseurs de points radar. » IEEE Transactions on Evolutionary Computation, vol.4, no.2, p.147-163 (juillet 2000).

Jensen, Mikkel. « Génération d'ordonnancements flexibles et robustes pour ateliers d'usinage à l'aide d'algorithmes génétiques. » IEEE Transactions on Evolutionary Computation, vol.7, no.3, p.275-288 (juin 2003).

Kewley, Robert et Mark Embrechts. « Système de planification tactique militaire computationnel. » IEEE Transactions on Systems, Man and Cybernetics, Part C - Applications and Reviews, vol.32, no.2, p.161-171 (mai 2002).

Kirkpatrick, S., C.D. Gelatt et M.P. Vecchi. « Optimisation par recuit simulé. » Science, vol.220, p.671-678 (1983).

Koza, John, Forest Bennett, David Andre et Martin Keane. Programmation génétique III : invention darwinienne et résolution de problèmes. Morgan Kaufmann Publishers, 1999.

Koza, John, Martin Keane, Matthew Streeter, William Mydlowec, Jessen Yu and Guido Lanza. Programmation génétique IV : Intelligence machine compétitive avec l'humain. Kluwer Academic Publishers, 2003.

• Voir aussi : Koza, John, Martin Keane et Matthew Streeter. « Inventions évolutives ». Scientific American, février 2003, p. 52-59.

Keane, A.J. et S.M. Brown. « La conception d'une antenne de satellite avec des performances vibratoires améliorées en utilisant des techniques d'algorithmes génétiques. » Dans Adaptive Computing in Engineering Design and Control '96 - Proceedings of the Second International Conference, I.C. Parmee (éd.), p.107-113. Université de Plymouth, 1996.

• Voir également : Petit, Charles. « Touché par la nature : Mettre l'évolution au travail sur la chaîne de montage. » U.S. News and World Report, vol.125, no.4, p.43-45 (27 juillet 1998). Disponible en ligne à http://www.genetic-programming.com/published/usnwr072798.html.

Lee, Yonggon et Stanislaw H. Zak. « Conception d'un contrôleur de système antipatinage génétique neuronal flou. » IEEE Transactions on Evolutionary Computation, vol.6, no.2, p.198-211 (avril 2002).

Lemley, Brad. « Machines qui pensent. » Discover, janvier 2001, p.75-79.

Mahfoud, Sam et Ganesh Mani. « Prévisions financières en utilisant des algorithmes génétiques. » Applied Artificial Intelligence, vol.10, no.6, p.543-565 (1996).

Mitchell, Melanie. Introduction aux algorithmes génétiques. MIT Press, 1996.

Naik, Gautam. « Retour à Darwin : sous le soleil et dans les cellules, la science cherche des réponses à des énigmes de haute technologie. » The Wall Street Journal, 16 janvier 1996, p. A1.

Obayashi, Shigeru, Daisuke Sasaki, Yukihiro Takeguchi, et Naoki Hirose. « Calcul évolutionnaire multiobjectif pour l'optimisation de la forme d'aile supersonique. » IEEE Transactions on Evolutionary Computation, vol.4, no.2, p.182-187 (juillet 2000).

Petzinger, Thomas. « À Deere, ils savent qu'un scientifique fou peut être le plus grand atout d'une entreprise. » The Wall Street Journal, 14 juillet 1995, p.B1.

• Voir également : « L'évolution des affaires, avec une touche de l'Institut Santa Fe. » SFI Bulletin, hiver 1998. Disponible en ligne à http://www.santafe.edu/sfi/publications/Bulletins/bulletin-winter98/feature.html.

Porto, Vincent, David Fogel et Lawrence Fogel. « Méthodes alternatives d'entraînement des réseaux de neurones. » IEEE Expert, vol. 10, no. 3, p. 16-22 (juin 1995).

Rao, Srikumar. « L'évolution à la vitesse de la lumière. » Forbes, vol.161, no.1, p.82-83 (12 janvier 1998).

Rizki, Mateen, Michael Zmuda et Louis Tamburino. « Systèmes de reconnaissance de motifs en évolution. » IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, p. 594-609 (décembre 2002).

Robin, Franck, Andrea Orzati, Esteban Moreno, Otte Homan, et Werner Bachtold. « Simulation et optimisation évolutive de la lithographie par faisceau d'électrons avec des algorithmes génétiques et simplex-downhill. » IEEE Transactions on Evolutionary Computation, vol. 7, no. 1, p. 69-82 (février 2003).

Sagan, Carl. Broca's Brain: Réflexions sur la romance de la science. Ballantine, 1979.

Sambridge, Malcolm et Kerry Gallagher. « Localisation de l'hypocentre des séismes en utilisant des algorithmes génétiques. » Bulletin de la Société sismologique d'Amérique, vol.83, no.5, p.1467-1491 (octobre 1993).

Sasaki, Daisuke, Masashi Morikawa, Shigeru Obayashi et Kazuhiro Nakahashi. « Optimisation de la forme aérodynamique des ailes supersoniques par des algorithmes génétiques multiobjectifs à domaine adaptatif. » Dans Optimisation multi-critère évolutionnaire : Première conférence internationale, EMO 2001, Zurich, Suisse, mars 2001 : Actes, K. Deb, L. Theile, C. Coello, D. Corne et E. Zitler (éd.). Notes de cours en informatique, vol. 1993, p. 639-652. Springer-Verlag, 2001.

Sato, S., K. Otori, A. Takizawa, H. Sakai, Y. Ando et H. Kawamura. « Application des algorithmes génétiques à la conception optimale d'une salle de concert. » Journal of Sound and Vibration, vol. 258, no. 3, p. 517-526 (2002).

Schechter, Bruce. « Donner une tournure darwinienne au moteur diesel. » The New York Times, 19 septembre 2000, p. F3.

• Voir aussi : Patch, Kimberly. « Un algorithme évolue vers un moteur plus efficace. » Technology Research News, juin/juillet 2000. Disponible en ligne à http://www.trnmag.com/Stories/062800/Genetically_Enhanced_Engine_062800.html.

Srinivas, N. et Kalyanmoy Deb. « Optimisation multiobjectif utilisant le tri par dominance non dominée dans les algorithmes génétiques. » Computing de l'évolution, vol. 2, no. 3, p. 221-248 (automne 1994).

Soule, Terrence et Amy Ball. « Un algorithme génétique avec plusieurs cadres de lecture. » Dans GECCO-2001 : Proceedings of the Genetic and Evolutionary Computation Conference, Lee Spector et Eric Goodman (éd.). Morgan Kaufmann, 2001. Disponible en ligne à http://www.cs.uidaho.edu/~tsoule/research/papers.html.

Tang, K.S., K.F. Man, S. Kwong et Q. He. « Algorithmes génétiques et leurs applications. » IEEE Signal Processing Magazine, vol. 13, no. 6, p. 22-37 (novembre 1996).

Weismann, Dirk, Ulrich Hammel, et Thomas Bäck. « Conception robuste de revêtements optiques multicouches au moyen d'algorithmes évolutionnaires. » IEEE Transactions on Evolutionary Computation, vol. 2, no. 4, p. 162-167 (novembre 1998).

Williams, Edwin, William Crossley et Thomas Lang. « Études de compromis sur les temps de réitération moyens et maximaux pour les constellations de satellites utilisant un algorithme génétique multiobjectif. » Journal of the Astronautical Sciences, vol. 49, no. 3, p. 385-400 (juillet-septembre 2001).

• Voir également : « Sélectionner de meilleures orbites pour les constellations de satellites. » Spaceflight Now, 18 octobre 2001. Disponible en ligne à http://spaceflightnow.com/news/n0110/18orbits/.
• « Sélection darwinienne d'orbites de satellites à usage militaire. » Space.com, 16 octobre 2001. Disponible en ligne à http://www.space.com/news/darwin_satellites_011016.html.

Zitzler, Eckart et Lothar Thiele. « Algorithmes évolutionnaires multiobjectifs : une étude de cas comparative et l'approche Strength Pareto. » IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, p. 257-271 (novembre 1999).