Brevet FR2631720A1 — publié le 19891124

La présente invention concerne le domaine des algorithmes génétiques, en particulier celui des algorithmes génétiques utilisables pour la résolution de problèmes. Les algorithmes génétiques procurent une méthode permettant d'améliorer un ensemble donné d'objets. La base théorique est donnée par les processus de sélection naturelle et de survie des mieux adaptés. Dans leur forme classique, les algorithmes génétiques peuvent permettre de résoudre de nombreux problèmes. Le problème du "Dilemme du Prisonnier" illustre cependant les limites des algorithmes génétiques classiques. Le Dilemme du Prisonnier est un problème de la théorie des jeux qui a été largement exploré (avec des nombreuses interprétations psychologiques, sociologiques et géopoli- tiques), dans lequel deux joueurs peuvent coopérer ou ne pas coopérer. Les joueurs se déplacent simultanément et sans communiquer entre eux. Chaque joueur reçoit alors une récompense qui est fonction de son déplacement et de celui de l'autre joueur. Dans le jeu du Dilemme du Prisonnier, les récompenses sont conçues de telle sorte que, si un joueur choisit de ne pas coopérer, ce joueur recevra toujours une récompense supérieure à celle qu'il aurait reçue s'il avait choisi de coopérer (abstraction faite de ce que fait l'autre joueur). Cependant, si les deux joueurs, égoïstement, décident de ne pas coopérer, ils se trouveront tous les deux dans une situation pire que s'ils avaient coopéré. Le jeu n'est pas un jeu dont le résultat global est une opération blanche car, entre autres choses, la situation sera meilleure pour les deux joueurs s'ils décident tous les deux de coopérer. Si l'on applique l'algorithme génétique classique à un problème particulier, il faut créer un schéma permettant de représenter les solutions possibles du problème sous forme d'un chromosome individuel d'une population étendue de chromosomes. Dans la technique antérieure, chaque chromosome -individuel de cette population devait prendre la forme d'une chaîne de caractères d'un alphabet déterminé, le plus souvent une succession de zéros et de uns (c'est-à-dire de "bits" binaires) de même dimension. La création d'un tel schéma de représentation (schéma de codage) est inhérente à l'algorithme génétique classique car les codes subissent une manipulation lorsque l'algorithme génétique est mis effecti- vement en oeuvre. Dans le cas d'un jeu, un individu de cette population est une "stratégie" particulière pour mener ce jeu. Une "stratégie" est, pour un joueur donné d'un jeu, une manière de spécifier comment le joueur va se déplacer en un point particulier donné compte tenu de tous les déplacements permis et des informations sur l'état du jeu dont dispose le joueur. Dans le cas du jeu du Dilemme du Prisonnier, les déplacements autorisés pour un joueur donné sont toujours les deux termes d'une même alternative - le joueur peut coopérer ou ne pas coopérer. Les informations dont dispose le joueur consistent en l'historique des déplacements précédents depuis le début du jeu. Le chapitre de Genetic Algorithms and Simulated Annealing (1987) intitulé The Evolution of Strategies in the Iterated Prisoner's Dilemma par Robert Axelrod, qui concerne la manière de mener un jeu, illustre la nature générale des algorithmes génétiques classiques et la manière dont ils s'appliquent à des problèmes particuliers. En particulier, il illustre le processus par lequel on transforme un problème mathématique en une forme mettant en oeuvre des chaînes de zéros et de uns (c'est-à-dire des chaînes de "bits" binaires) de dimensions identiques. On peut alors appliquer l'algorithme génétique classique au problème. Dans son article sur le Dilemme du Prisonnier, Axelrod commence par remarquer qu'il y a quatre manières possibles dont a pu avoir lieu le coup précédent: pour chacun des deux joueurs, coopération ou non coopération. Afin de pouvoir représenter ce jeu dans le cadre de l'algorithme génétique classique, Axelrod décide de ne baser le déplacement à venir d'un joueur que sur la connaissance de l'historique des trois coups précédents. Une fois cette limitation posée, il existe alors 64 (c'est-à-dire 4 fois 4 fois 4) historiques possibles des coups précédents. Dans ce type de schéma de représentation, l'historique des coups des deux joueurs sur les trois derniers coups est associé à l'une des positions sur 64 bits d'une chaîne binaire de longueur 64. Par exemple, la position binaire 64 peut se référer à des coups coopératifs des deux joueurs sur les trois coups précédents (c'est-à-dire que les coups précédents sont du type "CCCCCC"). Un "1" à la position binaire 64 de cette chaîne de longueur 64 peut alors signifier pour le joueur que, si les coups précédents ont été "'CCCCCC", il doit coopérer dans le coup en cours. La chaîne complète de 64 zéros et uns constitue une manière complète d'indiquer au joueur la façon de se déplacer lors du coup suivant en fonction de l'historique des trois coups précédents (dans son article, Axelrod étend en fait cette chaîne binaire à une longueur 70 pour pouvoir ajouter six positions binaires spéciales permettant de traiter le cas du tout début de la partie, lorsqu'il n'y a pas d'historique). Après avoir développé le schéma de représentation, l'algorithme génétique commence par créer de manière aléatoire une population de chaînes binaires individuelles de longueur 70. Le "degré d'adaptation" de chacune de ces chaînes individuelles (stratégies), est alors évaluée dans un "environnement" (qui, dans ce cas, consiste en une série de parties différentes). Afin de jouer une partie particulière de la série dans cet "environnement", il est nécessaire de se référer, pour chaque déplacement, à la position binaire appropriée de la chaîne de 70 zéros et uns, ensuite d'effectuer le déplacement indiqué dans la partie, puis de jouer la totalité de la partie, et enfin de déterminer la récompense donnée au joueur par la partie lorsqu'il a suivi cette stratégie individuelle particulière. Ces récompenses sont alors cumulées (et moyennées) sur la totalité de la série de parties afin de déterminer le degré moyen d'adaptation d'une stratégie individuelle particuli- ère. Comme chacune des 70 positions binaires de la chaîne binaire de longueur 70 représente un historique antérieur différent, la série de parties utilisée pour évaluer une chaîne individuelle donnée contiendrait, idéalement, un nombre statistiquement significatif de déplacements différents prenant en compte chacun des 70 historiques antérieurs. L'algorithme génétique procède ensuite à l'identifi- cation, dans la population actuelle, des meilleures stratégies individuelles et crée pour la génération suivante d'individus une descendance à partir des stratégies individuelles les plus adaptées. Comme dans la nature, chaque descendance hérite de certains traits génétiques de chaque parent par un processus de "croisement" de certains traits génétiques de chaque parent. Le processus de reproduction par les mieux adaptés et de croisement tend à produire, au bout de plusieurs générations, une population présentant un degré global d'adaptation croissant dans l'environnement en question. En appliquant l'algorithme génétique classique au jeu du Dilemme du Prisonnier, Axelrod a obtenu des résultats parallèles à ceux d'autres recherches mathématiques et compétitions internationales sur la meilleure manière de jouer à ce jeu. Cependant, on remarquera que l'algorithme génétique classique impose quatre limitations importantes qui restreignent son intérêt pour résoudre ce problème de jeu particulier et d'autres problèmes qui ont été étudiés. En premier lieu, la nécessité que chaque individu de la population soit une chaîne de longueur constante a obligé Axelrod à limiter arbitrairement le joueur a ne considerer qu'un nombre prédéterminé de coups antérieurs (trois coups, en l'occurence) pour décider de la manière d'effectuer le déplacement suivant. De ce fait, on risque d'ignorer l'historique antérieur d'un opposant qui aurait effectué des "attaques surprises" de diversion dans le cas o ces attaques auraient eu lieu plus de trois coups avant. Il est évident que, dans de nombreuses situations, un joueur dont la stratégie imposerait l'ignorance arbitraire et intention- nelle de l'historique antérieur disponible (en particulier, un historique aussi limité que les trois coups antérieurs) prêterait le flanc à diverses contres-stratégies dévasta- trices simples du joueur opposé. En second lieu, l'utilisation d'une chaîne binaire (une chaîne de zéros et de uns) a amené à un schéma de représentation impliquant un nombre astronomique de stratégies "différentes" simplement pour ne tenir compte que des trois coups précédents (270 stratégies - plus de 1000 milliards de milliards). Mais, si le schéma de représentation n'avait pas besoin d'être rigidement structuré à l'avance avant de commencer à exécuter l'algorithme génétique classique, on aurait pu faire évoluer un schéma de représentation n'impliquant qu'un nombre relativement limité d'historiques pertinents possibles (par exemple, "l'opposant coopère toujours", "l'opposant coopère environ la moitié du temps", etc.). En troisième lieu, les individus de la population étaient des descriptions représentatives (codages) de la stratégie, et non des-procédures activables exécutant directement le déplacement effectif dans le jeu. Toute stratégie particulière que l'on envisageait et souhaitait inclure dans la population devait être tout d'abord codée en une chaîne binaire de longueur 70 avant de pouvoir être insérée dans la population. Et, avant de pouvoir jouer un coup d'après une stratégie, il fallait décoder la chaîne binaire de longueur en instructions exécutables permettant d'effectuer un déplacement dans une situation particulière. En quatrième lieu, les chaînes binaires de longueur fixe ne procurent pas de structure hiérarchisée des solutions potentielles au problème. La chaîne binaire est unidimensionnelle, et tous les éléments de la chaîne opèrent au même niveau. On verra plus loin en quoi, pour résoudre des problèmes, une structure hiérarchisée présente un sens et un intérêt. Quelle que soit la structure de la solution, le processus de sélection naturelle constitue un outil puissant pour la résolution de problèmes. La Nature et ses exemples divers d'entités biologiques qui survivent dans des environnements divers le démontrent bien. Dans la Nature, des combinaisons complexes de traits donnent à des populations biologiques particulières la capacité de s'adapter, de survivre et de se 6 2631720 reproduire dans leurs environnements. L'adaptation complexe, relativement rapide et efficace, ainsi que les relativement bons résultats provisoires, qui apparaissent dans une population d'individus de la Nature en réponse à des changements de l'environnement est également impression- nante. Les processus de la Nature qui permettent à des populations biologiques de s'adapter à leur environnement, ainsi que les processus de la Nature qui permettent à ces populations de s'adapter à des changements successifs de leurs environnements (avec survie et reproduction des mieux adaptés) constituent un modèle très utile. Ce modèle peut permettre de développer des processus de résolution d'une très grande variété de problèmes complexes, pour lesquels on estime généralement qu'il faut de l'intelligence" pour les résoudre. Dans la Nature, le gène est l'unité fonctionnelle élémentaire par laquelle l'information héréditaire est transmise des parents à leur descendance. Les gènes apparaissent en des emplacements particuliers (appelées "loci") situés le long de molécules d'acide désoxyribo- nucléique (ADN). L'ADN est une longue molécule biologique filiforme qui présente la propriété de véhiculer une information héréditaire et celle de servir de modèle pour la production de répliques d'elle-même. Toutes les formes de vie connues sur la Terre (comprenant les bactéries, les champignons, les plantes, les animaux et les êtres humains) sont basés sur la molécule d'ADN. Le "code génétique" de la molécule ADN consiste en longues chaînes (séquences) de quatre valeurs géniques possibles pouvant apparaître aux différents loci le long de la molécule d'ADN. Pour l'ADN, les quatre valeurs géniques possibles correspondent à quatre "bases" nommées adénine, guanine, cytosine et thymine (généralement abrégées en A, G, C et T, respectivement). Le "code génétique" de l'ADN consiste ainsi en longues chaînes telles que CTCGACGGT... Lorsque de la reproduction des cellules vivantes, le code génétique de l'ADN est lu. Des sous-séquences formées de trois bases d'ADN sont utilisées pour spécifier l'un de vingt acides aminés. Les grosses molécules de protéines biologiques sont, quant à elles, constituées d'un nombre quelconque, compris entre 50 et 500, de ces acides aminés. Le code génétique est ainsi utilisé pour spécifier et contrôler la constitution de nouvelles cellules vivantes à partir d'acides aminés. Un chromosome est constitué d'un très grand nombre de loci avec une valeur génique particulière (appelée "allèle") à chaque locus. Le jeu de chromosomes est formé, pour un être humain, de 23 chromosomes, et un chromosome humain contient habituellement environ 150 millions de valeurs géniques. Ensemble, les 23 chromosomes humains donnent l'information nécessaire à la description d'un individu humain, et contiennent environ 3 milliards de gènes. Ces 3 milliards de gènes constituent ce qu'on appelle le "génome" d'un être humain particulier. Les génomes complets des 000 000 000 êtres humains environ constituent ensemble la totaalité de la réserve d'information génétique de l'espèce humaine. On sait que certaines valeurs géniques présentes en certains endroits de certains chromosomes commandent certains traits de l'individu, notamment des traits tels que la couleur des yeux, la sensibilité à certaines maladies, etc. On peut ainsi considérer l'ensemble de la population mondiale des êtres humains comme le produit d'un algorithme génétique. L'ouvrage du professeur John H. Holland intitulé Adaptation in Natural and Artificial Systems résume les recherches de Holland sur les algorithmes génétiques et présente une théorie mathématique d'ensemble de l'adaptation des systèmes à la fois naturels et artificiels. Une partie essentielle de cet ouvrage décrit un "algorithme génétique" configuré d'après les méthodes par lesquelles la Nature assure l'adaptation biologique. Cependant, une limitation de ce travail tient au fait que l'on utilise des chaînes binaires de longueur fixe pour représenter la population. Le US-A-4 697 242 au nom de Holland est un exemple d'un processus utilisant des chaines binaires de longueur fixe dans un algorithme génétique. 8 2631720 Des études empiriques par divers chercheurs ont montré ce dont sont capables de tels algorithmes génétiques dans divers domaines, notamment l'optimisation des fonctions (De Jong, 1980), le fonctionnement d'un gazoduc (Goldberg, 1983), la reconnaissance des formes (Englander, in Grefenstette, 1985), et de nombreux autres domaines. Dans le chapitre intitulé An Overview de la collection 1987 de Genetic Algorithms and Simulated Annealing, Lawrence Davis et Martha Steenstrup ont affirmé que "dans tous les travaux de Holland, et dans les travaux de nombre de ses étudiants, les chromosomes sont des chaînes de bits - des listes de zéros et de uns" et, continuent-t-ils, qu'en outre "certains chercheurs ont explorés l'utilisation d'autres représentations, souvent en liaison avec des algorithmes industriels. Parmi les autres représentations possibles, on a par exemple les listes ordonnées (pour le rangement.dans des compartiments), les listes imbriquées (pour les problèmes d'ordonnancement en usine) Ies listes à éléments variables (pour le dessin des semiconducteurs), et les représentations utilisées par Glover et Grefenstette dans le présent volume". Certains chercheurs ont essayé de résoudre les problèmes de recherche et d'optimisation au moyen de schémas conçus sur le principe de l'évolution en utilisant des stratégies du type "mutation et conservation du meilleur". Des exemples en sont donnés par Box (1957), Hicklin (1986) et par l'ouvrage de Fogel, Owens et Walsh intitulé Artificial Intelligence Through Simulated Evolution. Les quelques résultats obtenus à la suite de ces efforts sont resté extrêmement spécifiques à des applications et domaines particuliers, et sont largement le reflet d'une mise en application intelligente 'du concept de mutation plus qu'une utilisation de celui-ci comme technique générale permettant de réaliser des accroissements progressifs du degré d'adaptation de populations. Il est important de noter que la mutation n'est pas le moyen premier par lequel, dans la Nature, les populations biologiques améliorent leur degré d'adaptation, et n'est pas non plus le moyen premier utilisé par la présente invention. Depuis l'ouvrage de Holland en 1975, Holland et divers collaborateurs ont développé une nouvelle application des algorithmes génétiques classiques, appelée "système classi- ficateur". Un système classificateur est un groupe de règles. Chaque règle est formée d'une partie conditionnelle et d'une partie d'action (par exemple, une règle SI-ALORS). La partie conditionnelle et la partie d'action de chaque règle sont comme les individus de l'algorithme génétique classique, en ce qu'ils sont formés par une chaîne de zéros et de uns de longueur fixe. Dans un système classificateur, des messages (constitués de chaînes binaires) sont reçus de l'environnement et ils activent celles des règles dont la partie conditionnelle (la partie "SI") concorde avec le message incident (chaîne binaire). Cette activation déclenche la partie d'action (la partie "ALORS") de la règle. La partie d'action d'une règle émet alors un nouveau message (chaîne binaire). Les systèmes classificateurs sont décrits dans l'article de 1978 intitulé Cognitive Systems Based on Adaptative Algorithms (de Holland et Judith S. Reitman,) publié dans Pattern Directed Inference Systems, sous la direction de D. A. Waterman et Frederick Hayes-Roth, et dans la thèse de David E. Goldberg de 1983 intitulée Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning. Dans les systèmes classificateurs, on affecte un crédit à des chaînes de règles individuelles qui sont appelées par un schéma d'allocation de crédit à la manière de- personnes qui "font la chaîne". Le processus de Holland est une combinaison d'un système classificateur et d'un algorithme à transmission de proche en proche. Un article de 1987 de Cory Fujiki et John Dickinson paru dans Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms (sous la direction de John J.Grefenstette) décrit un programme informatique de système classificateur écrit en LISP permettant de résoudre le Dilemme du Prisonnier à partir de chaînes binaires de longueur fixe et de règles de classification SI-ALORS. Les algorithmes génétiques classiques sont dits "linéaires" car ils manipulent des chaînes (séquences) de caractères d'un alphabet fixe (habituellement, des chaînes de chiffres binaires 0 et 1). A l'opposé, dans un cas de figure "non linéaire", les objets à manipuler sont des expressions hiérarchisées formées par une configuration hiérarchisée de fonctions et d'arguments. On peut trouver dans la littérature les raisons pour lesquelles on a limité les algorithmes génétiques classiques à des chaînes binaires de longueur fixe. En premier lieu, dans sa thèse de 1983 intitulée Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning, David E. Goldberg affirme que toute chaine binaire de longueur fixe classique peut toujours être interprétée (par le truchement d'un schéma de représentation bien défini) en fonction du problème que l'on cherche à résoudre. On pourrait appeler cette propriété "propriété de bonne définition" de la chaîne, et c'est une propriété qu'il est souhaitable d'avoir. En second lieu, si chaque individu de la population est formé d'une chaîne binaire de longueur fixe, l'opération de croisement, lorsqu'on l'appliquera à deux individus de la population, produira toujours une autre chaîne binaire de longueur fixe. On pourrait appeler cette propriété "propriété de fermeture", et il s'agit également d'une propriété qu'il est souhaitable d'avoir. Bien entendu, les chaines binaires de longueur fixe ne sont pas la seule manière d'obtenir ces propriétés souhaitables de fermeture et de bonne définition. Dans Adaptation in Natural and Artificial Systemns, (1975, page 71), Holland prend position en faveur des chaînes formées uniquement de zéros et de uns (c'est-à-dire des chaînes binaires) des algorithmes génétiques classiques, sur la base du fait que, dans l'espace de recherche, le nombre de chaînes qui sont automatiquement recherchées au moyen de ce qu'il appelle le "parallélisme implicite" de l'algorithme génétique classique est plus élevé lorsque les chaines ne là 2631720 correspondent qu'à deux possibilités. Cette remarque est correcte; cependant, ce ne devrait pas être une remarque déterminante. Pour diverses raisons qui seront indiquées plus bas, si on limite l'algorithme génétique au monde unidimensionnel des chaînes linéaires de longueur fixe (et, en particulier, aux chaînes binaires de longueur fixe), on s'interdit de pouvoir résoudre de nombreux problèmes. Le domaine de l'informatique présente de très nombreux autres cas o il est tout à fait irréaliste de supposer que, pour résoudre le problème, on connaitra à l'avance la dimension ou la forme de celui-ci, de manière à pouvoir utiliser cette information pour prédéfinir rigidement par avance la dimension et la forme de la recherche. Un exemple élémentaire de la théorie de l'information illustrera cette remarque. Les codes de Huffman sont des chaînes binaires de longueur variable qui sont utilisées pour maximiser la quantité d'informations qui peut être transmise par une voie donnée. Les codes de Huffman sont plus ou moins semblables à un code Morse dans lequel on affecte des codes de faible longueur aux messages les plus fréquents (les lettres telles que "e") et des codes de grande longueur aux messages moins fréquents. L'algorithme de codage de Huffman commence avec les messages que l'on doit transmettre et leur probabilité d'apparition. L'algorithme affecte ensuite des chaînes binaires relativement courtes aux messages les plus fréquents et des chaînes binaires relativement longues aux messages les plus rares. La taille des chaînes nécessaire dans un schéma de codage de Huffman n'est pas connue à l'avance; elle n'est déterminée qu'après application de l'algorithme à l'ensemble particulier de messages et à leurs probabilité respectives. Toute tentative de déchiffrement d'un code de Huffman par recherche de concondance des chaînes doit prendre en compte la longueur des chaînes binaires les plus longues effectivement utilisées par l'algorithme de codage. L'utilisation de chaînes binaires de longueur fixe dans les algorithmes génétiques classiques limite la capacité de ceux-ci à résoudre de nombreux problèmes. Les trois exemples distincts que l'on va donner illustrent d'autres limitations des algorithmes génétiques classiques. Dans un premier exemple, supposons que l'on souhaite qu'un ordinateur se programme lui-même pour résoudre le problème consistant à trouver le point d'intersection de deux droites concourantes. Le point d'intersection de deux droites est le couple de nombres qui vérifie les deux équations linéaires à deux variables qui représentent les droites. Le programme d'ordinateur que l'on cherche à obtenir utilisera donc les coefficients des deux équations ainsi que divers opérateurs mathématiques (par exemple la multiplication, la soustraction, etc.) pour donner la- réponse cherchée. Pour rendre plus réaliste le problème consistant à apprendre à un ordinateur à se programmer lui-même, il est préférable de ne pas spécifier à l'avance la dimension ou la forme de l'expression mathématique permettant de résoudre le problème. Ce problème sera encore plus réaliste si l'ordinateur a accès à divers signaux d'entrée non significatifs et à des opérations mathématiques étrangères, ce qui brouillera sa recherche de la solution du problème. Il n'existe pas de manières simple ou commode d'associer de façon univoque une chaine binaire de longueur prédéterminée à une expression mathématique arbitraire composée d'opérations mathématiques spécifiées (fonctions) et d'arguments. Une chaîne binaire de longueur n ne peut représenter que 2n objets différents (abstraction faite du schéma de représentation). Même si l'on donne à n une valeur importante préétablie, on aura toujours des expressions mathématiques supplémentaires. Avant de continuer, il faut souligner qu'il n'est pas nécessaire de représenter des objets de dimension infinie. Ce que l'on doit éviter, c'est de préétablir arbitrairement une limite de dimension et de forme des objets à représenter (un objet donné ayant luimême toujours une dimension finie). Dans la plupart des problèmes, la dimension et la forme de la solution ne sont pas nécessairement connues à l'avance. Le processus de résolution du problème doit être libre de développer des solutions proposées sans limites préétablies de dimension et de forme de solution. Même si une longueur maximale arbitraire, spécifiée à l'avance, était acceptable, la méthode d'association de chaque expression mathématique arbitraire (par exemple A * B + C - D * E * F) à une chaîne binaire rendrait nécessairement obscures les opérations mathématiques sousjacentes concernées. Le procédé extrêmement complexe utilisé par Godel en 1931 dans sa démonstration du Théorème de l'Incomplétude est un exemple d'une telle méthode permettant de réaliser ce type d'association. Le problème de ce premier exemple met donc en lumière la nécessité de pouvoir représenter des expressions mathématiques arbi- traires (mettant en jeu divers fonctions et arguments) dont la longueur ne soit pas arbitrairement limitée à l'avance (contrairement à des simples chaînes binaires de zéros et de uns de même longueur fixe). On notera que, si l'on suppose que les deux droites de ce problème se coupent toujours, le problème est entièrement numérique. En revanche, si les deux droites peuvent éventuellement être parallèles, la réponse qu'un programme d'ordinateur donnerait à cette version généralisée du problème pourrait, de façon appropriée, être une réponse symbolique (par exemple "les équations ne sont pas homogènes et les droites sont parallèles") au lieu de donner la position numérique du point d'intersection. Cette situation peut être aisément reconnue par un programme informatique s'il effectue un contrôle afin de vérifier si une certaine valeur calculée (le discriminant) vaut zéro. Cette version généralisée du problème de ce premier exemple met donc en lumière la nécessité que le programme informatique qui fournit normalement une donnée de sortie numérique puisseprendre éventuellellement en considératioon un traitement symbolique et une donnée de sortie symbolique. Comme second exemple, considérons le problème consistant à prévoir les éléments futurs d'une séquence de nombres à partir d'un échantillonnage des premiers nombres de la séquence. Ce problème est un exemple d'induction. 14 2631720 L'induction est le processus logique par lequel on observe des exemples particuliers d'un certain processus (par exemple: "jusqu'à présent, le soleil s'est levé tous les matins de ma vie") pour en "induire" ensuite une règle sous-jacente raisonnable du processus (par exemple: "le soleil se lève toujours le matin"). Lorsque l'on applique un raisonnement inductif, on ne démontre jamais. que le résultat est correct. Néanmoins, le processus d'induction est très important et réside véritablement au coeur de tout processus d'apprentissage. A l'opposé, la déduction est le processus logique par lequel on part de certains prémisses (ou faits) donnés et de règles déductives d'inférence pour aboutir à une conclusion logique par application répétée des règles déductives aux prémisses ou faits originaux donnés. La suite d'étapes utilisée dans une déduction pour aboutir à une conclusion est appelée démonstration. Si l'on se donne un échantillon d'une suite de nombres tels que 0, 2, 4, 6, 8, 10, 12, 14 il n'est pas difficile d'induire raisonnablement que le nombre suivant de la séquence sera 16. Le nombre 16 est une induction raisonnable car chaque élément précédent de la suite correspond à deux fois la position de l'élément dans la séquence (le premier élément étant compté comme position 0). On notera cependant que même les éléments de cette séquence numérique simple ne peuvent pas être représentés par des chaînes dont la longueur a été spécifiée par avance. De nombreuses séquences intéressantes impliquent des opérations mathématiques complexes. Par exemple, le sixième élément de la suite 2, 4, 8, 16, 32 peut être exprimé directement sous forme mathématique comme étant égal à deux élevé à la puissance 6 (c'est-à-dire 64). Cette suite peut être également exprimée mathématiquement sous forme récursive c'est-à-dire en définissant le sixième élément d'après l'élément ou les éléments précédents de la séquence. Dans ce cas, le mième élément de la séquence sera deux fois l'élément m-l de la suite (dans cet exemple, 2 fois 32 donneront 64). Pour certaines suites mathématiques importantes, on ne connait pas d'expression non récursive de chaque élément de la séquence, et l'utilisation d'une forme récursive devient une nécessité et non plus seulement un choix. La suite de Fibonacci bien connue 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 est contruite en additionnant entre eux les deux éléments précédents de la séquence. Par exemple, 8 est la somme de 3 et de 5, et 13 est la somme de 5 et 8. De façon générale, le mième élément de la suite de Fibonacci est la somme de l'élément m-1 et de l'élément m-2 de la séquence (étant sous-entendu que les deux premiers éléments de la séquence ont une valeur "par défaut" de 1). Ainsi, le problème de l'induction des suites met en lumière la nécessité de pouvoir représenter aussi bien des formes récursives que des expressions mathématiques arbitraires (mettant en jeu des fonctions et des arguments). Ii met également une fois de plus l'accent sur la nécessité de pouvoir représenter des chaines dont la longueur n'a pas été préétablie. Comme troisième exemple, considérons l'irritant problème mathématique connu sous le nom de "problème du Commis Voyageur". Dans ce problème, on donne au commis voyageur un tableau kilométrique indiquant les distances entre un nombre donné de villes, et il doit passer une fois par chacune des villes (en revenant à son point de départ) en couvrant le moins de kilomètres possible. Il n'existe pas de formule mathématique générale connue donnant la solution de ce problème apparemment simple. Il n'existe pas de processus général de calcul (c'est-à-dire de programme informatique ou algorithme) connu permettant de résoudre ce problème (si ce n'est par la "force brute", c'est-à-dire par une évaluation exhaustive de tous les circuits possibles). Le nombre d'itinéraires possibles est égal à la factorielle du nombre de villes. Il devient prohibitif, même pour les ordinateurs les plus puissants, de tenter de résoudre ainsi ce problème, même pour un nombre relativement limité de villes. Par exemple, pour 14 villes seulement, il existe 87 178 291 200 itinéraires possibles. 26 1720 Cependant, du fait de l'importance pratique de ce type de problème complexe d'optimisation (qui possède de nombreuses versions industrielles équivalentes impliquant la minimisa- tion de coûts, de durées ou autres ressources), il existe une littérature abondante décrivant les efforts passés en vue de résoudre ce problème, y compris diverses procédures de calcul qui donnent en pratique des résultats qui semblent raisonnablement bons dans les limites d'un temps de calcul d'ordinateur raisonnable. L'ouvrage The Traveling Salesman Problem de Eugene L. Lawler, J.K.Lenstra, A. H. G. Rinnooy Kan et D. B. Shmoys est un résumé récent des progrès de la recherche sur ce problème. De façon intuitive, une manière particulièrement naturelle d'attaquer le problème du Commis Voyageur semble consister à décomposer l'ensemble des villes en sous-itinéraires plus petits, plus faciles à gérer, puis de trouver la meilleure manière de visiter toutes les villes du sousitinéraire, et enfin de trouver la meilleure manière d'assembler les sousitinéraires en un grand itinéraire. Par exemple, si l'on doit visiter les capitales des états des USA, il semble clair que l'on doit grouper les six capitales d'état de la Nouvelle-Angleterre en une sous-itinéraire commençant à Hartford, Connecticut et finissant à Montpelier, Vermont, puis d'analyser la meilleure manière de visiter les quatre autres villes du sous-itinéraire. En revanche, pour les capitales des états du Middle West il est loin d'être évident de savoir à l'avance quelle devra être la taille du sous-itinéraire, ou quelles villes devront être visitées pour avoir le meilleur sous-itinéraire. D'ailleurs, toute tentative de prédétermination arbitraire de la taille du sous-itinéraire ou bien du contenu du sous-itinéraire semblerait constituer une anticipation de la meilleure solution globale. Le problème du Commis Voyageur met ainsi en lumière la nécessité de pouvoir représenter sans dédoublements (c'est-à-dire sans permutation) un ensemble arbitraire d'éléments et divers sous-ensembles arbitraires de ces éléments, de taille arbitrairement variable. Il souligne - 17 également la nécessité de pouvoir développer des hiérarchies dans lesquelles des solutions à des sous-problèmes sont manipulées et rassemblées hiérarchiquement pour obtenir les solutions du problème principal d'origine. En fait, on résoud de nombreux problèmes mathématiques en commençant par "décomposer" un problème plus large en sous-problèmes plus réduit. On essaye ensuite de résoudre chacun des sous-problèmes. Enfin, on rassemble les solutions des sous-problèmes en une solution au problème d'origine. Le problème consistant à résoudre des jeux d'équations en très grand nombre avec de nombreuses variables et celui consistant à résoudre des équations polynomiales d'ordre élevé sont des exemples de problèmes dans lesquels on peut utiliser la décomposition. Dans certains cas, il existe une symétrie entre ce processus de rassemblement et la solution aux sous-problèmes individuels. C'est-à-dire que, dans ce processus de rassemblement, les solutions aux sous-problèmes peuvent être manipulées de la même manière que si elles étaient ellesmêmes les éléments d'un sous-problème. Par exemple, dans le cas du problème du Commis Voyageur, le processus de combinaison des sousitinéraires en un grand itinéraire peut revenir à traiter chacun des sousitinéraires comme s'il correspondait à une ville unique (c'est-à-dire à l'élément de base d'une sous-itinéraire) puis en essayant de trouver la meilleure manière de visiter ces "villes". Cd type de symétrie se présente également souvent lorsque l'on résoud des problèmes par décomposition. Même si l'on a pas de symétrie, une "hiérarchisation" se présente lorsque l'on résoud un problème par décomposition. Au niveau le plus bas de la hiérarchie, on résoud le sous-problème. La hiérarchisation consiste à combiner les solutions du sous-problème pour donner la solution du problème plus large. Dans la programmation des ordinateurs en général, on trouve couramment quelque chose de semblable. Par exemple, de façon typique, un programme principal appelle des sousprogrammes (ou sous-procédures). Le programme principal est au sommet de la hiérarchie, organisée typiquement pour procurer une vue générale de la solution au problème pris dans son ensemble. Chacun des sous-programmes appelés par le programme principal se trouve un niveau plus bas dans la hiérarchie. S'il se trouve que l'un des sous-programmes appelle lui-même un autre sous-programme, ce second sous-programme se trouvera dans la hiérarchie un niveau plus bas que le sous-programme qui l'a appelé. Les organisations sociales complexes (telles que les sociétés et les organisations militaires) sont organisées de façon semblable en hiérarchies. La capacité à décomposer des problèmes en hiérarchies ou sous-programmes est généralement importante dans la résolu- tion des problèmes. Une part importante des articles que l'on pourra trouver dans les Proceedings of the Internatiomal Conference on Genetic Algorithms and their Applications de 1985 et 1987, ainsi que d'autres articles de la littérature, discutent les difficultés d'applications de l'algorithme génétique classique au problème du Commis Voyageur et à d'autres problèmes impliquant des permutations. Ce dont on a besoin est une manière d'appliquer certains des principes généraux de la sélection biologique naturelle qui sont incarnés dans l'algorithme génétique classique (par exemple, la survie du mieux adapté et le croisement des traits des parents dans la descendance) à une catégorie de problèmes beaucoup plus large. En particulier, ce dont on a besoin est un procédé permettant de créer de manière adaptative des programmes informatiques impliquant des combinaisons complexes de fonctions mathématiques, de leurs arguments, d'expressions récursives, de traitements symboli- ques et autres structures de données complexes (telles que des permutations) sans limitation a priori de la taille, de la forme ou de la complexité des programmes. L'un des buts de la présente invention est de proposer un algorithme génétique permettant de fournir des solutions à une large catégorie de problèmes. Un autre but de la présente invention est de proposer un processus à algorithme génétique sans limite prédéterminée de taille, de forme ni 2631t720 de complexité des éléments de la population en question. Parmi les documents traitant de ce problème, on pourra se référer aux documents suivants: - US-A-4 697 242 "Adaptative Computing System Capable of Learning and Discovery ", au nom-de Holland et al., délivré le 29 septembre 1987; - Box, G.E.P. - Evolutionary Operation: A Method for Increasing Industrial Productivity in Journal of the Royal Statistical Society 6(2),81-101; - Davis, Lawrence (sous la direction de) - Genetic Algorithms and Simulated Annealing, Pitman, Londres, 1987; - Fogel, L.J., Owens, A.J. et Walsh, M.J. - Artificial Intelligence Through Simulated Evolution, John Wiley, New York, 1966; Fujiki, Cory - An Evaluation of Holland's Genetic Operators Applied to a Program Generator, mémoire de maîtrise de sciences, Department of Computer Science, University of Idaho, 1986; - Goldberg, David E. - Computer-Aided Gas Pipeline Operation Using Genetic Algorithms and Rule Learning (Thèse de doctorat, University of Michigan, 1983) in Dissertational Abstracts International 44(10), 3174B (microfilms de l'Université n 8402282); - Grefenstette, John J. (sous la direction de) - Proceedings of an International Conference on Genetic Algorithms and their Applications, Pittsburgh, 1985; - Grefenstette, John J. (sous la direction de) - Genetic Algorithms and their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1987; - Hicklin, Joseph F. Application of the Genetic Algorithm to Automatic Program Generation, mémoire de maîtrise de sciences, Department of Computer Science, University of Idaho, 1986; - Holland, John H. - Adaptation in Natural and Artificial 263 1 720 Systems, The University of Michigan Press, Ann Arbor, 1975; - Holland, J. H. et Reitman, J.S. - Cognitive Systems Based on Adaptative Algorithms in Waterman, D.A. et Hayes-Roth, F. (sous la direction de) - Pattern Directed Inference Systems (pages 313 à 329), Academic Press, New York, 1978; Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A:H.G. et Shmoys, D.B. - The Traveling Saleman Problem, John Wiley & Sons, New York, 1986. Dans son aspect le plus général, la présente invention concerne les algorithmes génétiques non linéaires. Le processus de la présente invention opère sur une population d'entités qui exécutent des tâches et dont la dimension et la forme peuvent varier. Chaque itération du processus comporte une activation, une affectation de valeur, une sélection, un choix, une exécution et une addition. Tout d'abord, chaque entité fait l'objet d'une activation lui permettant d'atteindre son objectif et de produire un résultat. Puis on associe une valeur au résultat de chaque activation et on l'affecte à l'entité correspondante. Ensuite, on sélectionne au moins une entité dont la valeur associée est relativement élevée. Puis on choisit une opération de croisement, de permutation ou de reproduction. Si l'on a choisi un croisement, l'entité sélectionnée exécute alors l'opération de croisement. Le croisement crée de nouvelles entités en combinant des parties -d'au moins une entité sélectionnée avec des parties d'au moins une autre entité. Pour exécuter une permutation, l'entité sélectionnée est réorganisée sans gain ni perte d'ensemble. Une reproduction conserve l'entité sélectionnée dans la population. Enfin, on ajoute à la population les entités nouvellement produites. Plus précisément, la présente invention a pour objet un processus de résolution de problèmes, dans lequel on utilise une population d'entités o chaque entité présente une aptitude active à résoudre des problèmes et peut changer de dimension et de forme, ce processus comprenant des itérations d'une suite d'étapes telles que ladite population tende à offrir des solutions améliorées. Ce processus est caractérisé en ce que chaque itération comporte les étapes suivantes: activation de chaque entité de manière à obtenir un résultat; affectation d'une valeur à chacun de ces résultats et association de chacune de ces valeurs à l'entité correspondante qui a produit le résultat; sélection d'au moins une entité dans la population, cette sélection étant essentiellement basée, dans la majorité des cas, sur la valeur associée à chacune des entités, préférence étant donnée à celles des entités qui ont une valeur associée relativement forte plutôt qu'à celles des entités qui ont une valeur associée relativement faible; choix et exécution d'une opération, l'opération ainsi choisie étant une opération de croisement, de reproduction ou de permutation; si l'opération choisie est un croisement, création d'au moins une nouvelle entité par croisement à partir d'un groupe d'entités, ce groupe comprenant les entitéd sélectionnées à l'étape de sélection et au moins une autre entité sélectionnée dans ladite population, de sorte que toute nouvelle entité créée par croisement comprenne au moins une partie des entités sélectionnées à l'étape de sélection et au moins une partie desdites autres entités; si l'opération choisie est une reproduction, conservation des entités sélectionnées à l'étape de sélection, de sorte que ces entités restent inchangées; si l'opération choisie est une permutation, permutation des entités sélectionnées à l'étape de sélection, de manière à réordonner des parties de chacune des entités sélectionnées avec possibilité de reconfor- mation, afin de créer une nouvelle entité à partir de chacune des entités sélectionnées; et addition desdites nouvelles entités à la population. La présente invention a également pour objet un ordinateur, comprenant une population d'entités de longueur variable o chacune de ces entités peut changer de dimension 263 1720 et de forme, pour la mise en oeuvre d'un processus itératif permettant de modifier cette population par création de nouvelles entités de telle sorte que le degré d'adaptation de cette population tende à s'améliorer à l'approche d'une solution d'un problème. Selon l'invention, cet ordinateur est caractérisé en ce qu'il comprend, en combinaison: - des moyens pour créer une population initiale d'entités de longueur variable, - une mémoire pour conserver cette population initiale d'entités de longueur variable, - un processeur, relié à cette mémoire, pour aller rechercher lesdites entités conservées et exécuter des instructions déterminées par ces instructions recherchées, ce processeur affectant des valeurs aux résultats de l'exécution des instructions de ces entités recherchées et sélectionnant au moins un entité présentant- une valeur relativement élevée, cette valeur étant associée à un degré d'adaptation voulu en direction de ladite solution, ce processeur exécutant ensuite au moins une opération de croisement, de reproduction, ou de permutation sur chacune des entités sélectionnées, de telle sorte que (a) si l'opération choisie est un croisement, il crée au moins une nouvelle entité par croisement à partir d'un groupe d'entités, ce groupe comprenant au moins l'une des entités sélectionnées présentant une valeur relativement élevée et au moins une autre entité ne faisant pas partie de ces entités sélectionnées présentant une valeur relativement élevée, de sorte que toute nouvelle entité créée par croisement comprenne au moins une partie des entités sélectionnées présentant une valeur relativement élevée; (b) si l'opération choisie est une reproduction, il conserve chacune des entités sélectionnées, de sorte que ces entités restent inchangées; (c) si l'opération choisie est une permutation, il permute chacune des entités sélectionnées à l'étape de sélection, de manière à réordonner des parties de chacune des entités sélectionnées avec possibilité de reconformation, afin de créer une Z631720 nouvelle entité- à partir de chacune des entités sélectionnées, cette opération créant de nouvelles entités qui sont ensuite, pour exécution ultérieure par le processeur, ajoutées à la population d'entités conservée dans ladite mémoire. On va maintenant donner des exemples de réalisation de l'invention, en référence aux figures annexées. La figure 1 est une représentation en diagramme arborescent d'une s-expression LISP. La figure 2 est une représentation en diagramme arborescent d'un programme LISP. La figure 3 est un diagramme en forme d'organigramme explicitant la présente invention. La figure 4 est une représentation en diagramme arborescent d'une opération de croisement entre points internes. La figure 5 est une représentation en diagramme arborescent d'une opération de croisement entre points externes. La figure 6 est une représentation en diagramme arborescent d'une opération de croisement entre un point interne et un point externe. La figure 7 est une représentation en diagramme arborescent d'une opération de permutation. La figure 8 est un diagramme par blocs du mode de réalisation en traitement parallèle de la présente invention. La figure 9 est une représentation graphique d'un problème en équations linéaires. La figure 10 est une représentation en diagramme arborescent d'une sexpression appartenant à la population initiale, permettant de résoudre le problème en équations linéaires de la présente invention. La figure 11 est une représentation en diagramme arborescent d'une opération de croisement correspondant au problème de la suite de Fibonacci. La figure 12 est une représentation en diagramme arborescent d'itinéraires et de sous-itinéraires du problème du Commis Voyageur. La figure 13 est une représentation en diagramme arborescent de sous-sousitinéraires du problème du Commis Voyageur. La présente invention décrit un processus à algorithme génétique permettant de résoudre des problèmes. Dans la description qui va suivre, on a donné de nombreux détails particuliers afin de permettre une compréhension approfondie de la présente invention. Il sera cependant évident pour le spécialiste de cette technique que la présente invention peut être mise en oeuvre sans recourir à ces détails particuliers. Inversement, des procédés et des structures bien connus n'ont pas été décrits en détail afin de ne pas alourdir inutilement la description de la présente invention. La présente invention opère sur une population d'entités. Les entités doivent être capables de produire un résultat objectivement observable. Afin de pouvoir être efficaces, les actions des entités doivent aller dans le sens d'un but constructif, même si leurs résultats ne correspondent pas toujours à cet objectif. Le processus itératif de la présente invention produit des populations qui tendent à réaliser leurs objectifs constructifs mieux que les populations précédentes. Bien que le mode de réalisation préféré utilise comme entités des programmes informatiques, l'utilisation d'autres types d'entités reste dans le cadre de la présente invention. Par exemple, des combinaisons de circuits électriques pourraient constituer une population sur laquelle pourrait opérer le processus itératif de la présente invention. Les circuits pourraient se reproduire et se croiser jusqu'à ce que la population donne des solutions suffisamment efficaces d'un problème qui leur aurait été soumis. Une autre population pourrait également être formée par différents concepts de structures d'automobiles, les éléments de ces structures constituant différents allèles pouvant être croisés et réarrangés. Ainsi, bien que dans la description qui va suivre on utilise comme entités des programmes d'ordinateur, cette description ne constitue pas une limitation de la présente invention. Les langages informatiques FORTRAN, COBOL, ALGOL, PL/1, PASCAL, C, PROLOG, ADA, BASIC, etc. offrent la possibilité d'écrire des expressions mathématiques complexes, des expressions récursives, des structures de données complexes et des expressions symboliques. Certains de ces langages permettent d'écrire des expressions symboliques qui sont exécutables sous la forme de procédures (ou programmes) de calcul à l'intérieur même du langage. En outre, certains de ces langages peuvent générer des expressions symboliques, bien que souvent ce processus soit malcommode et inefficace. En général, la plupart des langages informatiques ne permettent pas d'écrire des expressions arbitrairement complexes. De plus, la plupart d'entre eux ne permettent pas de retarder l'affectation effective de la mémoire (et des types de mémoires) de l'ordinateur à des telles expressions jusqu'au dernier moment précédant l'exécution effective de l'expression. Un tel procédé de la gestion de la mémoire est appelé "allocation dynamique de la mémoire" ou "liaison tardive". Il existe cependant un langage informatique qui possède toutes les caractéristiques décrites plus haut et qui est généralement disponible sous des formes relativement efficaces sur un grand nombre d'ordinateurs. Ce langage est le LISP, qui constitue le langage informatique de choix dans de nombreuses applications d'intelligence artificielle. Au fil des années, de nombreux dialectes du langage LISP ont été créés. Un dialecte de LISP appelé "Common LISP" a commencé à émerger comme standard. 26 2Z631720 La structure de base du langage de programmation LISP est une liste d'éléments (un ensemble ordonné d'éléments contenus à l'intérieur d'un couple de parenthèses). Une source importante de la simplicité, de la généralité et de la puissance du LISP vient du fait que l'on traite le premier élément de toute liste rencontrée sous la forme d'une fonction à exécuter - ce que l'on appelle "évaluation" -, les autres éléments de la liste étant traités en tant qu'arguments de cette fonction. En outre, sauf indication contraire, le LISP lit, évalue et retourne une valeur pour chacune de ces fonctions qu'il rencontre. Ainsi, dans le LISP, des programmes informatiques entiers peuvent apparaître simplement sous la forme de fonctions à l'intérieur de fonctions elles-mêmes à l'intérieur d'autres fonctions (ce que l'on appelle souvent "composition de fonctions"). L'application des fonctions aux arguments rencontrés commande le déroulement du programme LISP. En d'autres termes, la structure de contrôle est, dans le LISP, basée sur la composition de fonctions. Dans le LISP, on peut avoir de -nombreuses fonctions à l'intérieur du couple de parenthèses le plus à l'extérieur, à savoir des fonctions pour exécuter des opérations arithmétiques, des fonctions pour exécuter des opérations récursives, des fonctions pour modifier des expressions symboliques, des fonctions pour modifier conditionnellement le déroulement du programme, et d'autres fonctions complexes. Une caractéristique essentielle du LISP est que les programmes LISP ont la même forme que les données (et que les fonctions). Comme les caractéristiques ci-dessus l'indiquent, le LISP est un langage fonctionnel de programmation. Le LISP n'est pas le seul langage fonctionnel de programmation existant, et il n'est pas non plus le seul langage fonctionnel de programmation possible. Il est cependant le langage de cette catégorie le plus couramment utilisé, et il convient parfaitement à ce dont on a besoin dans l'immédiat. En dépit des résultats complexes obtenus, le LISP peut être considéré comme étant très simple car il se contente de 26 31720 lire, évaluer et retourner une valeur pour chacune des fonctions mentionnées.plus haut qu'il rencontre. Cette apparente simplicité donne au LISP une très grande souplesse (notamment, la souplesse qui lui permet de prendre en compte des procédures de calcul qui se modifient elles- mêmes et s'éxécutent elles-mêmes). Cette très grande souplesse fait que, dans le cas de la présente invention, le LISP est le langage informatique préféré. Par exemple, si l'on considère l'expression mathématique simple généralement écrite sous la forme 5 * 4 - 3 * 2. Pour évaluer cette expression, on doit tout d'abord évaluer * 4. On évalue 5 * 4 en exécutant la fonction de multiplication (*) sur les deux arguments (5 et 4). La structure de base du LISP est une liste de rubriques (c'est-à-dire un ensemble ordonné de rubriques contenues à l'intérieur d'un jeu deparenthèses). En outre, sauf indication contraire, le LISP considère que la première rubrique de chaque liste rencontrée est une fonction et que les autres rubriques de la liste sont des arguments de cette fonction. Le LISP représente ainsi 5 * 4 sous la forme (* 5 4). On a ici une fonction (à savoir la fonction de multiplication, symbolisée par I"*") comme première rubrique de la liste et les deux arguments de la fonction (à savoir les deux nombres à multiplier) placés ensuite. De la même façon, LISP représente 3 * 2 sous la forme (* 3 2). Après avoir exécuté (évalué) ces deux multiplications, on a ensuite la fonction de soustraction, avec ces deux arguments (à savoir, 20 et 6). Les deux- valeurs obtenues par évaluation des deux fonctions de multiplication sont considérées comme étant des arguments de la fonction de soustraction, qui exécute l'opération de soustraction, à savoir (- (* 5 4) (* 3 2)). Des expressions telles que * (- (* 5 4) (* 3 2)) sont, en LISP, appelées s-expressions. Ici, la fonction de soustraction (-) est exécutée sur le résultat précédemment obtenu pour (* 5 4) et (* 3 2). Lorsque l'on utilise comme argument d'une fonction un simple nombre ou une simple variable (comme par exemple "3" ou "2" dans la multiplication 3 * 2), ce nombre est appelé "argument 263 1720 atomique". La situation contraire se présente lorsque l'on compose des fonctions dont l'argument dont l'une des fonctions est lui-même le résultat de l'exécution d'une fonction antérieure (imbriquée). Il est ainsi possible de représenter des expressions mathématiques de complexité croissante en imbriquant de cette manière les résultats précédents à l'intérieur de nouvelles expressions. Il peut être utile de présenter de façon graphique les expressions d'un langage fonctionnel de programmation. Les expressions fonctionnelles peuvent être visualisées graphiquement sous la forme d'une arborescence avec des références sur les différents points de l'arborescence. En particulier, toute expression de ce type peut être visualisée sous la forme d'une arborescence référencée à racine, dans lequel les points internes de l'arborescence sont référencés par des fonctions et les extrémités des lignes rayonnant vers le bas à partir chacun de ces points internes sont référencées par les arguments de cette fonction. On peut si on le souhaite s'éloigner autant que l'on veut de la racine de l'arborescence à partir des termes vers le bas dans de telles arborescences référencées à racine. Les points externes de l'arborescence (quelquefois appelés "feuilles") sont référencés par des arguments atomiques. La racine de l'arborescence est le point interne particulier référencé par la fonction exécutée en premier. Dans une s-expression du LISP, la première fonction est la fonction LISP située la plus à l'extérieur (c'est-à-dire la fonction qui se trouve à l'intérieur de la parenthèse gauche de la s-expression LISP située la plus à l'extérieur). La figure 1 illustre ceci dans le cas du LISP pour l'expression 5 * 4 - 3 * 2. Dans la notation habituelle de cette expression arithmétique représentée par l'expression , la fonction 104 (multiplication) opère sur les arguments 102 et 106 (à savoir, respectivement, 5 et 4) et la fonction 112 (multiplication) opère sur les arguments et 114 (à savoir, respectivement, 3 et 2). La fonction 108 (soustraction) opère ensuite sur les résultats de ces deux fonctions, qui en constituent les arguments. La Z631720 -2 9 fonction 108 est dans la hiérarchie à un niveau supérieur à celui des fonctions 104 et 112. Sur la figure 1, la s-expression LISP 120 est exprimée par la fonction 124 (multiplication) opérant sur les S arguments 126 (le nombre 5) et 128 (le nombre 4) et par la fonction 130 (multiplication) opérant sur les arguments 132 (le nombre 3) et 134 (le nombre 2). La fonction 122 (soustraction) opère ensuite sur les résultats de ces deux évaluations. Dans la présentation graphique de la figure 1, le point interne 150 de l'arborescence 130 de racine 140 est référencé par la fonction multiplication (*) et les points externes 156 et 158 de l'arborescence sont référencés par les deux arguments de la fonction de multiplication (à savoir, respectivement, par 5 et par 4). On trouve les arguments d'une fonction donnée (telle que la fonction de multiplication représentée par le point interne 150) en suivant les lignes 152 et 154 qui rayonnent vers le bas depuis le point interne 150. De la même façon, le point interne 160 de l'arborescence est référencé par la fonction de multiplication et les points externes de l'arborescence 166 et 168 sont référencés par les deux arguments de la fonction de multiplication (à savoir, respectivement, par 3 et par 2). On trouve les arguments de la fonction 160 en suivant les lignes 162 et 164 qui rayonnent vers le bas depuis le point interne 160. Le point interne de l'arborescence 140 est référencé par la fonction de soustraction. On trouve les arguments de la fonction de soustraction en suivant les lignes 142 et 144 qui rayonnent vers le bas depuis le point 140. Il se trouve que ces arguments sont les résultats des opérations de multiplication précédemment exécutés. On peut trouver des arguments sur des points externes (s'il s'agit d'"atomes") ou sur des points internes (par exemple lorsque les arguments d'une fonction, comme ici pour la soustraction , sont le résultat de fonctions précédentes). Le point interne 140 est la racine de l'arborescence et il est référencé par la fonction la plus à l'extérieur 263 1 720 (soustraction) 122 de la s-expression LISP 120 (c'est-à-dire par la fonction qui se trouve juste après la parenthèse gauche la plus à l'extérieur de la s-expression LISP). L'avantage d'un langage informatique tel que le Common LISP pour exécuter un travail de ce type provient de la souplesse considérable qui tient au fait que l'on se contente d'appliquer de façon répétée cette structure de base très simple. Les fonctions disponibles en LISP peuvent comprendre des fonctions autres que les opérations arithmétiques simples de multiplication et de soustraction. Elles comprennnent des fonctions mathématiques plus complexes telles que: l'extraction de racine carrée, l'exponentiation, etc.; les fonctions de contrôle de programme telles que PROGN qui permettent d'exécuter en série une, suite d'expressions LISP; les opérations récursives (lorsqu'une fonction renvoie à elle-même dans le processus de sa propre évaluation); les fonctions itératives (telles que DOTIMES) qui provoquent l'exécution répétée de certaines fonctions (typiquement, avec des arguments qui varient); les fonctions conditionnelles - qui font que certaines fonctions alternatives spécifiées sont exécutées si une certaine fonction prédicat est (ou n'est pas) satisfaite -; et les fonctions symboliques qui opèrent sur des symboles (au lieu d'opérer sur des nombres). Par exemple, supposons que l'on veuille, dans un programme informatique, commencer par imprimer la chaîne symbolique "BONJOUR", puis donner à la variable C la valeur de la somme des variables A et B, et enfin imprimer la valeur de C seulement si C est supérieur à 4. Sur la figure 2, la sexpression LISP (c'est-à-dire le programme) 700 exécute ces tâches. La fonction PROGN 701 permet de combiner en un seul programme une série de trois étapes principales. La première étape principale de la série concerne l'opération exécutée par la fonction 702 (PRINT) sur l'argument symbolique de la chaîne 704 ("BONJOUR"). La seconde étape principale concerne l'opération exécutée par la fonction 706 (SETQ). sur une variable 708 (C) et le résultat de l'opération exécutée par la fonction 710 31 2631720 (addition) sur les arguments 712 (la variable A) et 714 (la variable B). La fonction SETQ affecte une valeur (son second argument) à une variable (son premier argument). Enfin, la troisième étape principale concerne l'opération exécutée par la fonction conditionnelle 716 (WHEN) sur deux arguments. Le premier argument est une fonction prédicat dans laquelle la relation 718 ("supérieur à") opère sur les arguments 720 (la variable C) et 722 (le nombre 4). Le second argument est la fonction 724 (PRINT) qui opère sur l'argument 726 (la variable C). Graphiquement, ce programme (ou s-expression) LISP peut être représenté sous la forme d'une arborescence dont les points internes sont référencés par des fonctions et o les extrémités des lignes rayonnant vers le bas à partir de chacun de ces points internes sont référencées par les arguments de cette fonction. Dans cette représentation graphique, l'un des points internes est la racine de l'arborescence, et la racine est référencée par la fonction qui apparaît juste après la première parenthèse gauche de la s-expression LISP. Ici, la racine de l'arborescence 730 est référencée par la fonction PROGN. La fonction PROGN possède trois arguments. Les trois lignes 732, 734 et 736 qui rayonnent vers le bas depuis le point interne 730 (la racine) correspondent aux trois arguments de PROGN. Le premier argument de PROGN est la fonction 738, qui est la fonction PRINT. Elle constitue le point d'extrémité de la première ligne 732 qui rayonne vers le bas depuis le point interne 730. La fonction PRINT possède un argument, 740. Dans le cas de la fonction PRINT, celle-ci possède un seul argument, qu'elle imprime. Dans ce cas, l'argument est la chaîne symbolique 740 "BONJOUR". Cette chaîne 740 "BONJOUR" est un argument atomique et apparaît sur un point externe (feuille) de l'arborescence. Le second argument de PROGN est la fonction 742, qui est la fonction SETQ. La fonction SETQ possède deux arguments 744 et 746. Le second argument de SETQ est lui-même une fonction 746 (addition) opérant sur les deux arguments 748 263 1 720 (la variable A) et 750 (la variable B). Les deux arguments 748 et 750 sont les variables A et B (qui sont des atomes LISP). Ils apparaissent en des points externes (feuilles) de l'arborescence. Le premier argument de SETQ est 744 (la variable C), à laquelle on donne la valeur de la somme de A et de B. Le troisième argument de SETQ est la fonction 752, qui est la fonction WHEN. La fonction WHEN possède deux arguments, 754 et 756. Le premier argument de la fonction WHEN est une fonction prédicat 754 ("supérieur à") La fonction prédicat 754 possède deux arguments 758 (la variable C) et 760 (le nombre 4). La fonction prédicat 754 renvoie une valeur qui est soit T (True: "vrai") soit NIL ("faux"), selon que son premier argument 758 (la variable C) est supérieur à son second argument760 (le nombre 4), ou non. La fonction WHEN exécute son second argument 756 (la fonction PRINT) si l'évaluation de Son premier argument 754 donne T ("vrai"). La fonction PRINT 756 possède un argument 762 (la valeur numérique de la variable C). On notera que la fonction PRINT offre une certaine latitude d'utiisation: elle peut prendre en compte aussi bien un argument symbolique (tel que la chaîne "BONJOUR" en 740) soit un nombre (tel que la variable C en 762). Bien que l'on puisse faire tourner le LISP sur pratiquement n'importe quel ordinateur, il est préférable d'utiliser un ordinateur spécialement conçu pour l'exécution des fonctions LISP. L'ordinateur Explorer II de Texas Instruments est particulièrement avantageux pour cela car il contient une puce de microprocesseur spécialement conçue (appelée MegaChip) qui exécute directement les fonctions LISP. La MegaChip contient le microcode de base qui correspond directement aux opérations de base du LISP. Sont incluses, notamment, les opérations LISP de base permettant de construire des piles (qui, entre autres choses, conserveront les renvois à des appels répétés de fonctions) et d'exécuter d'autres opérations particulières du LISP. On pourrait programmer une puce de microprocesseur classique (telle que le Intel 80286 contenu dans l'ordinateur IBM PC-AT) de manière à exécuter les diverses fonctions LISP en adaptant ses instructions informatiquees génériques aux besoins du LISP. Par ailleurs, il est particulièrement avantageux de faire tourner les programmes LISP sur des ordinateurs ayant une mémoire interne très étendue, du fait des structures complexes que l'on doit développer lorsque l'on utilise le LISP dans des applications, telles que celle décrite ici, qui nécessitent souvent des tailles mémoires importantes. Dès lors que, dans un ordinateur donné, la mémoire nécessaire n'est pas disponible en mémoire interne, le fonctionnement devient particulièrement inefficace. Comme la résolution des problèmes nécessite souvent des structures complexes, le fait d'avoir une efficacité médiocre peut faire la différence entre la capacité à résoudre ou non le problème. Le mode de réalisation préféré de la présente invention utilise un ordinateur Explorer II avec 32 000 000 octets (32 mégaoctets) de mémoire interne. Après avoir généré une population de procédures de calcul, on exécute ces procédures et on affecte au résultat de l'exécution une valeur dans 1'environnement concerné. C'est pourquoi un aspect important, dans toute mise en oeuvre de ce système, est la capacité à générer des procédures de calcul (programmes d'ordinateur) puis à les exécuter pour donner un résultat. Lorsque l'oh utilise des représentations LISP sur un ordinateur ayant une mémoire suffisante, la présente invention peut résoudre des problèmes que l'on ne pouvait pas traiter auparavant par les méthodes de l'art antérieur. La présente description expose une méthode générale et des exemples particuliers de la présente invention. On décrira d'abord le processus proprement dit. Ensuite, on présentera trois exemples d'application de celui-ci. Les trois exemples illustreront l'application de la présente invention à des équations linéaires, à des suites et au problème du Commis Voyageur. La figure 3 est un organigramme du processus de la présente invention. Le processus 1300 commence par l'étape 263 1 720 1302 "créer la population initiale", qui crée un certain nombre de programmes (habituellement, de façon aléatoire). Si le test d'achèvement du processus 1304 est vérifié (par exemple, si l'on trouve dans la population d'individus une solution optimale connue au problème, si l'on obtient un certaine amélioration du degré moyen d'adaptation de la population, etc.), le processus prend fin à l'étape "fin" 1301. Dans le cas contraire, le processus poursuit l'itération. La boucle itérative de base du processus commence par l'étape 1306 "exécuter chaque programme", par laquelle chaque programme est exécuté. L'étape suivante 1312 "affecter à chaque programme une valeur et lui associer la valeur" permet d'affecter une valeur (degré d'adaptation) à chaque résultat produit par l'exécution, et associe la valeur au programme qui l'a produite. Après affectation et association, l'étape 1314 "éliminer le(s) programme(s) de relativement faible degré d'adaptation" permet d'éliminer les éléments les moins adaptés de la population (le terme "programme(s)" utilisé ici correspondant à l'expression "programme ou programmes"). Bien qu'elle ne soit pas essentielle, l'étape 1314 améliore le degré moyen d'adapta- tion et limite les besoins en mémoire en contenant la population à l'intérieur de limites raisonnables. L'étape "sélectionner un programme de valeur d'adaptation relative- ment élevée" 1316 extrait au moins un programme qui sera utilisé dans l'opération suivante. Le(s) programme(s) choisi présente A l'étape 1318 "choisir une opération à exécuter", le processus détermine par quelle opération commencer. "croisement" 1320 et "reproduction" 1330 sont les opérations de base que l'on exécute; cependant, "permutation" 1340 joue également un rôle. Eventuellement, on peut utiliser l'opération "mutation'" 1350. Habituellement, la très grande majorité des opérations sont des opérations de reproduction et de croisement. Par exemple, dans une population de 1000 individus, le procédé particulier peut spécifier qu'une nouvelle population de taille 1000 sera créée en 263 1720 sélectionnant parmi les individus les mieux adaptés de la population 350 groupes de deux parents en vue d'un croisement, en sélectionnant 250 individus de degré d'adaptation élevé en vue d'une reproduction simple et en sélectionnant 50 individus de degré d'adaptation élevé en vue d'une opération de permutation. Les 350 groupes de deux parents produiront par croisement un total de 700 nouveaux descendants. Ces 700 descendants, conjointement avec les 250 individus conservés en tant que résultat de la reproduction simple et les 50 descendants produit en tant que résultat de l'opération de permutation, maintiendront la taille totale de la population à un niveau de 1000 individus. Les paramètres peuvent également spécifier, en outre, que la mutation d'un allèle isolé aura lieu avec une probabilité p = 0,0001. Ainsi, si l'individu moyen possède Q points o la mutation pourrait avoir lieu, on mutera un-total de Q * N * p allèles (dans une population de taille N). Si Q vaut 10, l'opération de mutation modifiera alors un allèle sur 10 C0 dans une population de 1000.individus. Si, en sélectionnant les 350 groupes de deux parents ci-dessus, on effectue la sélection avec des probabilités strictement proportionnées au degré d'adaptation, le même individu pourra être sélectionné plus d'une fois (c'est-à-dire que l'on aura sélection avec possibilité de remplacement). Cependant, si on le souhaite, on pourrait s'écarter de cette manière de procéder - qui est la manière théorique préférée - et créer un groupe commun d'individus de degré d'adaptation relativement élevé destinés à être unis, puis y sélectionner (sans remplacement) 350 groupes de deux parents. On comprendra qu'il existe un très grand nombre de variantes proches du processus général.. Par commodité, on pourra utiliser certaines de ces variantes. Le croisement 1320 nécessite un groupe d'au moins deux programmes (habituellement, deux parents) de sorte que l'on doit extraire un (des) second(s) programme(s) afin de l'unir (les unir) au(x) programme(s) sélectionné(s). Il n'existe pas de méthode absolue pour choisir le(s) second(s) parent(s), mais il est préférable de ne choisir que des individus de degré d'adaptation relativement élevé plutôt que de les choisir au hasard. On unit les parents en associant le(s) programme(s) sélectionné(s) au(x) second(s) programme(s) que l'on a extrait. A chaque union, à l'étape 1322 "sélection des points de croisement", on sélectionne de façon aléatoire un point de croisement distinct parmi les points aussi bien internes qu'externes de chaque parent. Puis, à l'étape 1324 "effectuer le croisement", on produit par croisement les programmes nouvellement créés à partir du groupe que l'on a marié. Habituellement, deux parents produiront deux descendants. On notera également qu'il n'est absolument pas nécessaire de maintenir une taille de population constante. La version de l'opération de croisement produisant deux descendants à partir de- deux parents possède la propriété commode de maintenir une taille de population constante (on remarquera que les autres opérations produisent chacun un descendant à partir d'un parent, de sorte qu'elles maintiennent également une taille de population constante). En revanche, si l'opération de croisement agit sur un groupe de parents en nombre supérieur à deux, la taille de la population peut croître. Par exemple, si l'on a uni un groupe de trois parents, on aura sélectionné deux points de croisement pour chaque parent et il y aura donc 27 descendants possibles (3 x 3 x 3). Même si l'on exclut les trois descendants équivalant aux trois parents d'origine, il y aura 24 nouveaux descendants possibles disponibles. En général, si l'on a N parents, on sélectionnera sur chacun N-1 points de croisement et on aura NN-N nouveaux descendants disponibles. Lorsque l'opération produit plus de descendants que de parents, on peut soit autoriser une croissance de la population, soit ramener ia population à une taille voulue (que l'on suppose constante) lorsqu'aura lieu le cycle suivant de reproduction proportionnée au degré d'adaptation. Pour l'opération 1330 "reproduction", le programme sélectionné reste inchangé. Le procédé préféré de sélection des procédures de calcul en vue de la reproduction consiste à sélectionner celles-ci avec une probabilité 37 2631720 proportionnelle à leur degré normalisé d'adaptation. Si l'on sélectionne l'opération de permutation, le -processus continue ensuite à l'étape 1340 "permutation". À l'étape 1342 "sélection d'un point de permutation", on sélectionne de façon aléatoire un point de permutation parmi les points internes de l'individu sélectionné. On exécute ensuite l'étape 1344 "effectuer la permutation" en réordonnançant aux points de permutation-les sous-procédures et/ou paramètres du programme sélectionné. Si l'on choisit l'option de mutation, on arrive à l'étape 1350 "mutation". A l'étape 1352 "sélection du point de mutation", on extrait l'emplacement de la mutation pour chaque programme sélectionné. L'étape 1354 "effectuer la mutation" génère ensuite de façon aléatoire, pour chacun des programmes sélectionnés, une partie d'un programme et l'insère au point de mutation. La portion insérée est habituellement un point isolé, mais peut être également un sous-programme. Finalement, les nouveaux programmes créés sont insérés dans la population en 1360 et le processus retourne au test d'achèvement 1304. On peut tenir un historique complet.de l'évolution du processus depuis la création de la population initiale d'individus jusqu'à la population actuelle d'individus. En fait, en composant des s-expressions LISP, on dispose d'un moyen idéal pour des historiques d'évolution. Supposons que l'on appelle Il, I2, I3,... les individus de la population initiale. On peut soit conserver directement ces individus soit conserver l'algorithme aléatoire (et les semences aléatoires) utilisés pour engendrer les membres initaux. Lorsque l'on exécute un croisement sur deux individus (par exemple sur Il et I2, au point p du parent n 1 et au point q du parent n 2), la fonction LIST peut être utilisée en LISP pour créer une s-expression à cinq éléments - à savoir, la chaîne symbolique "CROISEMENT", les identités des deux individus que l'on a croisé ensemble (c'est-à-dire Il et I2) et les deux points de croisement (c'est-à-dire p et q). Dans cet exemple, la s-expression serait: (CROISEMENT Il I2 p q). 38 2631720 Cette nouvelle chaîne constituerait l'identité (c'est-à-dire l'historique d'évolution) du nouvel individu créé. Si l'on exécutait ensuite un croisement au point r du résultat du premier croisement exposé plus haut, avec l'individu initial I3 au point s, l'historique d'évolution de l'individu résultant serait de la forme: (CROISEMENT(CROISEMENT Il I2 p q) I3 r s). Si l'on exécutait ensuite sur cet individu un autre croisement (ou autre opération), cette chaîne deviendrait, à son tour, l'argument d'une nouvelle opération LIST. De la même façon, lorsque l'on opère sur un individu une permutation, on peut utiliser la fonction LIST pour créer une s-expression à trois éléments - à savoir, la chaîne symbolique "PERMUTATION", l'identité de l'individu et le point de permutation. Pour une opération de permutation effectuée sur l'individu I4 au point t, on aurait ainsi, par exemple: (PERMUTATION I4 t). La première étape du processus itératif consiste effectuer l'activation de chaque entité. L'activation signifie que l'on fait en sorte que chaque entité essaye d'atteindre son but, produisant un résultat objectif. Dans le mode de réalisation préféré, les entités sont des programmes informatiques et l'activation nécessite donc l'exécution des programmes de la population. La seconde étape du processus affecte une valeur d'adaptation au résultat objectif et associe cette valeur d'adaptation à son entité correspondante. Pour des programmes informatiques, la valeur d'adaptation est généralement un nombre ou un vecteur donnant une idée du résultat de l'exécution du programme, bien que la valeur d'adaptation puisse être constituée par toute représentation symbolique utilisée dans un ordinateur. En général, certaines des entités se révéleront supérieures à d'autres lorsqu'on leur affecte une valeur après interaction avec "l'environnement" du problème. La meilleure valeur (degré d'adaptation) peut être le nombre le plus faible (comme ici, lorsque l'on mesure l'écart entre un résultat et une solution idéale connue). Dans d'autres problèmes, la meilleure valeur (degré d'adaptation) peut être le nombre le plus élevé (par exemple, si l'on considère un score de concordances réalisées). La valeur (degré d'adaptation) affectée peut être une valeur numérique isolée, ou bien être un vecteur de valeurs quoique, le plus souvent, il soit plus commode d'avoir une valeur numérique unique. Dans de nombreux problèmes (par exemple, dans le cas du problème du Commis Voyageur), on ne connaît pas la meilleure valeur. Cependant, même dans de tels problèmes, on sait si des nombres élevés (ou faibles) dénotent ou non une meilleure adaptation, et on peut identifier la meilleure valeur atteinte par le processus à un instant donné. Dans un procédé commode d'organisation des valeurs brutes d'adaptation, on normalise les valeurs brutes puis on effectue un calcul de probabilités à partir des valeurs normalisées. On affecte à la meilleure valeur brute 15.d'adaptation une adaptation normalisée de 1, on affecte à la pire valeur une valeur de 0, et on affecte à toutes les valeurs brutes intermédiaires une valeur comprise entre 0 et 1. La probabilité de sélection est déterminée par la relation: P(i) = f4x P(i) étant la probabilité de sélection de l'individu i dont le degré d'adaptation normalisée est fi et n étant le nombre. total d'individus de la population. Ainsi, la probabilité pour un individu d'être sélectionné est égale à la valeur d'adaptation normalisée de l'individu divisée par la somme de toutes les valeurs d'adaptation normalisées de la population. De cette manière, les valeurs d'adaptation normalisées sont comprises entre 0 et 1, la valeur 1 étant associée à la meilleure adaptation et la valeur 0 à la pire, la.somme des probabilités de tous les individus étant égale à 1. Il peut être également souhaitable d'éliminer de la population les procédures de calcul individuelles ayant des valeurs d'adaptation relativement faibles. En pratique, il 263 1720 peut être également commode de retarder cette action jusqu'à ce que l'on ait créé une nouvelle génération d'individus. L'une des caractéristiques essentielles de l'ensemble de ce processus est que les nouvelles populations d'individus ont tendance à présenter, après un certain temps, une valeur (degré'd'adaptation) moyenne croissante dans l'environnement concerné. En outre, une autre caractéristique de l'ensemble de ce processus est que, si l'environnement change, les nouvelles populations d'individus présenteront également une valeur (degré d'adaptation) moyenne croissante dans le nouvel environnement concerné. A tout instant donné, il existe dans toute population finie un individu dont la valeur d'adaptation propre est la meilleure de toute la population. En outre, pour certains environnements on connait la meilleure valeur d'adaptation. Tel est par exemple le cas lorsque l'on mesure l'adaptation sous forme d'un écart par rapport à une réponse connue 41 2631720 d'adaptation) moyenne générale, mais donne à la population une capacité à s'adapter efficacement aux changements de l'environnement. Lors de liexécution de l'ensemble du processus, il est souvent commode de marquer celui des individus (ou quelquefois deux individus) de la population ayant dans cette population la meilleure valeur d'adaptation à un instant donné. Ces meilleurs individus que l'on a marqué ne sont alors pas retirés (en tant que parents) mais, au contraire, sont conservés dans la population d'une génération à l'autre tant qu'il restent les meilleurs. Cette manière de procéder empêche de perdre les individus les mieux adaptés de la population, et procure également un point de référence commode à des fins d'analyse. S'il se trouve que l'on connaît la meilleure solution du problème en question, au bout d'un certain nombre de générations la meilleure solution connue sera souvent le meilleur individu. La troisième étape consiste à-sélectionner les entités qui seront utilisées pour exécuter les opérations. Il existe un certain nombre de méthodes de sélection, qui tendent à sélectionner les entités ayant des valeurs relativement élevées. La manière de sélectionner les individus de la population qui semblé, théoriquement, la plus attrayante, consiste à effectuer cette sélection avec une probabilité proportionnée à la valeur d'adaptation (celle-ci ayant été normalisée entre 0 et 1). Ainsi, un individu ayant une valeur d'adaptation de 0,95 aura 19 fois plus de chances d'être sélectionné qu'un individu ayant une valeur d'adaptation de 0,05. A l'occasion, on pourra sélectionner des individus ayant des valeurs d'adaptation relativement faibles. Cette sélection sera suffisamment rare, mais elle pourra avoir lieu. Si la distribution des valeurs d'adaptation normalisées est suffisamment plate, cette méthode' est particulièrement- commode à mettre en oeuvre. En revanche, si les valeurs d'adaptation sont fortement biaisées -(la plupart des valeurs se trouvant par exemple à proximité de 1,00), si l'on effectue simplement la sélection avec une probabilité 263 1 720 proportionnée au degré d'adaptation normalisé, l'avantage différentiel des individus les plus adaptés de la population sera relativement faible et l'exécution complète du processus se prolongera. C'est pourquoi, dans la pratique, on fera la sélection avec une égale probabilité entre ceux des individus qui ont des valeurs d'adaptation relativement élevées, au lieu de la faire avec une probabilité strictement proportionnée au degré d'adaptation normalisée. Habituellement, on réalise ceci en choisissant des individus dont le degré d'adaptation n'a pas dépassé une valeur de seuil donnée. Une manière de mettre en pratique cette façon de procéder consiste à sélectionner comme seuil un certain nombre d'écarts-type par rapport à la moyenne (par exemple, en sélectionnant tous les individus dont le degré d'adaptation se trouve à plus ou moins une fois l'écart-type du degré moyen d'adaptation). A propos de la sélection des individus en fonction de leur degré d'adaptation, l'expression "valeur relativement élevée" utilisée ici se réfère à une sélection basée soit sur une probabilité proportionnée au degré d'adaptation normalisé (ce qui constitue la manière de procéder qui, en théorie, est la manière préférentielle) soit sur une égale probabilité entre ceux des individus dont les valeurs d'adaptation n'a pas franchi un certain seuil. En pratique, 25. bien que, théoriquement, une sélection proportionnée au degré d'adaptation soit la plus justifiée, il peut être simple et commode de choisir, dans la meilleure moitié, les individus avec une égale probabilité. Une fois que l'on a achevé la sélection, il faut, à la quatrième étape, choisir une opération. Les opérations possibles comprennent le croisement, la permutation et la reproduction. L'opération préférée est le croisement, suivie par la reproduction et enfin la permutation. Cependant, cet ordre n'est indiqué que de façon générale, et, dans certains cas particuliers, un ordre différent peut se révéler meilleur. Le choix des opérations doit donc, principalement, se porter sur l'opération préférée, mais ce choix doit conserver une certaine latitude afin de pouvoir résoudre des 43 2631720 problèmes différents. Comme on le verra plus bas, l'opération essentielle pour introduire des nouveaux individus dans la population est l'opération de croisement. Pour illustrer, dans cet exemple, l'opération de croisement, on sélectionne un groupe de deux procédures de calcul dans la population des s-expressions individuelles ayant des valeurs d'adaptation relativement élevées, bien qu'il ne soit pas indispensable de limiter à deux individus la taille du groupe sélectionné. Une taille de deux individus correspond au cas le plus familier, car il évoque la reproduction sexuée avec un parent mâle et un parent femelle. Le processus mathématique sous-jacent peut néammoins permettre d'obtenir des résultats effectifs en "croisant" des informations héréditaires en provenance de trois parents ou plus à la fois. Cependant, l'avantage majeur de pouvoir combiner des traits provenant d'individus différents peut être atteint avec deux parents. Dans la forme préférée, tous les individus du groupe de parents ont des valeurs d'adaptation relativement élevées. Selon l'aspect le plus général, on a seulement besoin qu'au moins l'un des individus du groupe de parents ait une valeur d'adaptation relativement élevée. Les autres parents du groupe pourraient être constitués par n'importe quel élément de la population. Dans l'un ou l'autre cas, toute union impose que l'on ait au moins un parent de valeur d'adaptation relativement élevée. Pour les besoins de ce problème donné en exemple, supposons que l'on ait sélectionné un groupe de deux parents de valeurs d'adaptation relativement élevées. On utilise maintenant le groupe de parents pour créer deux nouvelles procédures' de calcul. La figure 4 illustre sous forme graphique un exemple. simple d'union de deux parents permettant de produire deux nouveaux descendants pour le problème donné, en exemple, concernant des équations linéaires. On notera qu'il n'y a pas besoin d'avoir exactement deux descendants et que, dans certaines versions du concept de base exposé ici, on peut ne produire qu'un seul descendant (o bien produire plus de deux descendants). 263 1720 Le parent n 1 est la procédure de calcul 400: (- (+ B1 B2) All) (* B2 A12)) Cette procédure de calcul peut également être représentée par l'arborescence référencée en son point de racine, avec la racine 410. La racine 410 est la fonction de soustraction et elle est reliée à deux arguments (les noeuds internes 412 et 413, respectivement). Le noeud 412 est la fonction d'addition, et elle est reliée aux feuilles 415 et 416 (les variables B1 et B2, respectivement). Le second argument de la racine 410, qui est le noeud 413, est la fonction de multiplication, qui est reliée aux feuilles 418 et 419 (les variables B2 et A12, respectivement) qui sont ses deux arguments. La sous-arborescence 411 comporte les éléments 413, 418 et 419. Le parent n 2 est la procédure de calcul 420: (- (* B1 A22) (- B2 All) Cette procédure de calcul peut être également représentée par l'arborescence référencée en son point de racine, avec la racine 430. La racine 430 est la fonction de soustraction et elle est reliée à deux arguments (les noeuds internes 432 et 434, respectivement). Le noeud 432 est la fonction de multiplication, et elle est reliée aux feuilles 435 et 436 (les variables B1 et A22, respectivement) correspondant à ses arguments. Le noeud 434 est la fonction de soustraction, et elle est reliée aux feuilles 437 et 438 (les variables B2 et All, respectivement) correspondant à ses arguments. Le second argument de la racine 410, qui est le noeud 413, est la fonction de multiplication, qui est reliée aux feuilles 418 et 419 (les variables B2 et A12, respectivement) qui sont ses deux arguments. L'arborescence 421 comporte les éléments 430, 432, 435 et 436, qui sont tous du parent n 2, à l'exception du second argument de la racine 430. Pour sélectionner le point de croisement, on commence par compter les points internes et externes de l'arborescence. L'arborescence dont la racine est 410 possède neuf points 410, 412,413, 414, 415, 416, 417, 418 et 419. On choisit de manière aléatoire comme point de croisement du parent n 1, l'un des neuf points 410, 412,413, 414, 415, 416, 417, 418 et 419 de l'arborescence du parent n 1 (c'est-àdire de l'arborescence dont la racine est 410). On utilise une distribution uniforme de probabilités (chaque point ayant ainsi une probabilité de 1/9e d'être sélectionné). Sur la figure, on a choisi le point 413. Il se trouve que le point 413 est un point interne de l'arborescence. De la même façon, on choisit de manière aléatoire comme point de croisement du parent n 2, l'un des sept points 430, 432, 434, 435, 436, 437 et 438 de l'arborescence du parent n 2 (c'est-à-dire, de l'arborescence dont la racine est 430). Sur la figure, on a choisi le point 434. Il se trouve que le point 434 est un point interne de l'arborescence. Chacun des sept points a une probabilité uniforme de 1/7e d'être choisi. Le descendant n 2 est produit en combinant certains des traits du parent n 1 et certains des traits du parent n 2. Plus précisément, on obtient -le descendant n 2 en substituant la sousarborescence (sous-procédure) 411 commençant au point de croisement sélectionné 413 du parent n l, à savoir (* B2 A12), dans l'arborescence 421 au point de croisement sélectionné 434 du parent n 2. Le descendant résultant 470 contient ainsi en sous-procédure au point 474 la sousprocédure 411 (* B2 A12) du parent n 1, point qui est relié à la seconde ligne provenant de la racine 430 de l'arborescence 421. Pour le reste, il est identique. au parent n 2, c'est-à-dire que sa racine est référencée par la fonction de soustraction dont l'argument est (* B1 A22) Cette union particulière produit la procédure de calcul 460, à savoir (- (* B1 A22) (* B2 A12)), qui constitue la solution correcte connue de la première variable xl d'un couple de deux équations linéaires à deux variables. En d'autres termes, le croisement des parents n 1 et n 2 (dont ni l'un ni l'autre ne correspond à la solution correcte du problème des équations linéaires) par les point de croisement 413 et 434 s'est révélé produire un descendant ayant le meilleur degré d'adaptation (c'est- à-dire correspondant à la solution correcte, déjà connue, du problème); On obtient de la même manière le descendant n 1, en combinant certains des traits du parent n 1 et certains des traits du parent n 2. Dans ce cas, les parties complémentaires de chaque parent se combinent entre elles. En particulier, le descendant n 1 est produit en substituant la sousarborescence (sous-procédure) du parent n 2 commençant au point de croisement 434, c'est-à-dire (- B2 All), dans l'arborescence du parent n 1 au point de croisement 413. Le descendant résultant 450 contient ainsi, au point 454, la sous-procédure (- B2 All) du parent n 2 en tant que sous-procédure. Pour le reste, il est semblable au parent n 1. La racine 452 est la fonction de soustraction, qui est reliée aux arguments des noeuds internes 442 et 454. Le noeud 442 est la fonction d'addition à laquelle sont reliés des arguments au noeud interne 444 et à la feuille 444 (la variable All). Le noeud interne 445 est la fonction d'addition, à laquelle sont reliés des arguments aux feuilles 446 et 448 (les variables B1 et B2, respective- ment).. Le noeud 454 est la fonction de soustraction, à laquelle sont reliés des arguments aux feuilles 456 et 458 (les variables B2 et A11, respectivement). Si deux points externes (feuilles) de l'arborescence avaient été choisis comme points de croisement, le croisement aurait été réalisé de la même façon avec les références (c'est-à-dire les arguments) des deux points échangés. La figure 5 illustre, dans l'exemple du problème des équations linéaires, l'union de deux parents avec un croisement n'ayant lieu que sur des points externes (feuilles). Le premier parent 500, qui est (- (* All A12 A21) B1), est représenté par l'arborescence dont la racine est 510. La racine 510 est la fonction de soustraction, à laquelle sont reliés des arguments au noeud interne 515 et à la feuille 512 (la variable B1). Le noeud 515 est la fonction de multiplication, à laquelle sont reliés des arguments aux feuilles 516, 517 et 518 (les 263 1720 variables All, A12 et A21, respectivement). Le point externe (feuille) 512 a été choisi comme point de croisement pour le premier parent et contient l'argument atomique de la variable B1. On notera que, pour pouvoir illustrer la généralité des fonctions, l'une des fonctions (ici, la fonction I"*") possède dans ceet exemple particulier trois arguments (ici, All, A12 et A21). Le second parent 520 est représenté par l'arborescence de racine 530. La racine 530 est la fonction de soustraction, à laquelle sont reliés des arguments aux feuilles 534 et 532 (les variables A22 et B2, respectivement). Le point externe (feuille) 532 a été choisi comme point de croisement du second parent, et contient l'argument atomique B2. - Le résultat de l'opération de croisement consiste en deux nouveaux descendants 540 et 560. Le premier descendant 540, qui est (- (* All A12 A21) B2), est représenté par l'arborescence de racine 550. L'arborescence 550 est la fonction de soustraction, à laquelle sont reliés des arguments au noeud interne 545 et à la feuille 552 (la variable B2). Le noeud 545 est la fonction' de multiplication, à laquelle sont reliés des arguments aux feuilles 546, 547 et 548 (les variables All, A12 et A21, respectivement). Cette arborescence est identique à l'arborescence de racine 510, c'est-à-dire au parent n 1, à l'exception du point externe (feuille) 552, qui est maintenant l'argument B2 (au lieu de B1), provenant du parent n 2. Le second descendant 560, qui est (- A22 B1), est représenté par l'arborescence de racine 570. La racine 570 est la fonction de soustraction, à laquelle sont reliés des arguments aux feuilles 574 et 572 (les variables A22 et BI, respectivement). Cette arborescence est identique à l'arborescence de racine 530, c'est-à-dire, au parent n 2, à l'exception du point externe (feuille) 572, qui est maintenant l'argument-B1 (au lieu de B2) provenant du parent n 1. On a ainsi croisé (échangé) les arguments B1 et B2 pour produire les deux descendants. La figure 6 illustre l'union de deux parents avec un croisement ayant lieu entre un point interne (c'est-à-dire 48 2631720 un point référencé par une fonction) et un point externe (c'est-à-dire un point référencé par un argument atomique). Le premier parent 600, qui est (+ (+ All A12) (* A21 A22)), est représenté par une arborescence de racine 610. La racine 610 est la fonction d'addition, à laquelle sont reliés des arguments aux noeuds internes 602 et 612. Le noeud 602 est la fonction d'addition, à laquelle sont reliés des arguments aux feuilles 604 et 606 (les variables All et A12, respectivement). Le noeud 612 est la fonction de multiplication, à laquelle sont reliés des arguments aux feuilles 614 et 616 (les variables A21 et A22, respectivement). Le point interne 612 a été choisi comme point de croisement pour le premier parent. Le second parent 620, qui est (- (B1 B2) (* B3 B4)), est représenté par une arborescence de racine 630. La racine 630 est la fonction de soustraction, à laquelle sont reliés des arguments aux noeuds internes 622 et 624. Le noeud 622 est la fonction de soustraction, à laquelle sont reliés des arguments aux feuilles 632 et 629 (les variables BI et B2, respectivement). Le noeud 624 est la fonction de multiplication, à laquelle sont reliés des arguments en 628 et 626 (les variables B3 et B4, respectivement). Le point externe 632 a été choisi comme point de croisement pour le second parent. Le résultat de l'opération de croisement consiste en deux nouveaux descendants. Le premier descendant 640, qui est (+ (+ All A12) B1), est représenté par l'arborescence de racine 650. La racine 650 est la fonction d'addition, à laquelle sont reliés des arguments au noeud interne 654 et à la feuille 652 (la variable B1). Le noeud 654 est la fonction d'addition, à laquelle sont reliés des arguments aux feuilles 656 et 658 (les variables All et A12, respectivement). Cette arborescence est identique à l'arborescence de racine 610, c'est-à-dire au parent n 1, à l'exception du fait que le second argument de la fonction "+" (addition) 652 est maintenant l'argument unique (atome) B1, provenant du parent n 2. Le second desendant 660, qui est (- (- (* A21 A22) B2) (* B3 B4)), est représenté par l'ar- borescence de racine'670. La racine 670 est la fonction de soustraction, à laquelle sont reliés des arguments aux noeuds internes 678 et 684. Le noeud 678 est la fonction de soustraction, à laquelle sont reliés des arguments au noeud interne 672 et à la feuille 682 (la variable B2). Le noeud 672 est la fonction de multiplication, à laquelle sont reliés des arguments aux feuilles 674 et 676 (les variables A21 et A22, respectivement). Le noeud 684 est la fonction de multiplication, à laquelle sont reliés des arguments aux feuilles 686 et 688 (les variables B3 et B4, respective- ment). Cette arborescence est identique à l'arborescence de racine 630, c'est-à-dire au parent n 2, à l'exception du fait que le point interne 672 (c'est-à-dire le premrier argument de la fonction de soustraction 678) est maintenant une fonction (multiplication) au lieu d'être l'argument atomique formé par la variable B1. Ainsi, indépendamment du fait que l'on sélectionne sur les arborescences des parents comme points de croisement des points internes ou externes, le résultat de l'opération de croisement est que l'on produit une descendance qui contient les traits des parents. En fait, la descendance résultant du croisement n'est formée que de sous-procédures provenant des parents. Dans la mesure o, en pratique, ceci n'est pas totalement le cas, on peut considérer que le résultat est celui obtenu par application d'un croisement aux parents puis par intervention d'une mutation (variation aléatoire). L'opération de croisement possède les propriétés précitées de fermeture et de bonne définition. A l'occasion, on peut unir un individu donné à lui-même. Dans l'algorithme génétique classique utilisant des chaînes binaires, un croisement par des parents identiques crée simplement deux exemplaires de l'individu originel. Lorsqu'il s'agit de procédures de calcul, l'union d'un individu avec luimême produit généralement deux individus différents (sauf s'il se trouve que les points de croisement choisis sont les mêmes). Les trois exemples d'union avec croisement ont été présentés ci-dessus en termes de représentation graphique 2631720 des procédures de calcul. Les représentations graphiques conviennent particulièrement bien à la démonstration du fait que l'opération de croisement revient à effectuer un "couper-coller". En outre, la méthode graphique de représentation est une manière générale de représenter les fonctions et les objets sur lesquels ils opèrent (qu'il s'agisse de procédures de calcul ou de machines)- et, en outre, n'est pas propre à un langage de programmation particulier ou à un mode de mise en oeuvre particulier. Comme exposé plus haut, on utilise de préférence le langage informatique LISP pour la mise en oeuvre réelle de ces processus dans un ordinateur. Sur la figure 6, on a illustré l'union de deux parents avec un croisement entre un point interne et sur un point externe. On se réfèrera dans la suite à la figure 6, car elle couvre les principes mis en oeuvre à la fois sur la figure 4 et sur la figure 5. Le parent n 1 de la figure 6 était la procédure de calcul LISP (+ (+ All A12) (* A21 A22)) et le parent no 2 de la figure 6 était la procédure de 2C calcul LISP (- (- B1 B2) (* B3 B4)). On va maintenant décrire la manière dont on réalise l'union des deux parents dans le cas o l'on utilise des procédures de calcul LISP. -En premier lieu, on compte le nombre de fonctions et d'arguments atomiques dans la s-expression LISP 600 de la figure 6. Pour la sexpression LISP 600, on a trois fonctions (la fonction "+", présente deux fois, et la fonction "*", présente une fois), et quatre arguments atomiques (à savoir All, A12, A21 et A22). Le compte global est donc de sept. On peut aisément réaliser en LISP ce comptage de plusieurs manières bien connues. Une manière particulière- ment simple utilise des fonctions LISP de base telle que CAR et CDR, qui sont incluses dans le microcode des puces de microprocesseur spécialement conçues pour traiter le LISP (telles que celle que l'on trouve dans l'ordinateur Explorer II de Texas Instruments). La fonction CAR permet, en LISP, d'examiner le premier élément d'une liste. Ici, le premier élément de la procédure de calcul 600 est la première fonction "+" (c'est-à-dire la fonction 51 2631720 d'addition apparaissant juste après la parenthèse gauche la plus à l'extérieur). Le "+" est identifié comme étant une fonction, et inclus dans le compte global. Entretemps, la fonction CDR aura été utilisé pour éliminer le premier élément de la liste, en retournant donc une liste comportant tous les éléments sauf le premier. Le reste de la procédure de calcul (qui est maintenant de taille plus restreinte que la procédure de calcul d'origine 600, o l'on a maintenant supprimé le premier élément *"+ ") peut être soumis à un traitement similaire, de manière récursive. En second lieu, une fois que l'on a compté le nombre de fonctions et d'arguments atomiques de la procédure de calcul 600, on appelle un générateur de nombres aléatoires afin de sélectionner un nombre compris entre 1 et 7 avec une probabilité uniforme (c'est-à-dire une probabilité de 1/7e pour chacune des sept possibilités). De tels générateurs de nombres aléatoires sont bien connus dans la technique, et sont souvent incluses dans un lot de fonctions utilitaires livré par les fabricants d'ordinateurs aux utilisateurs de leurs ordinateurs. Texas Instruments fournit un générateur de nombres aléatoires permettant de générer avec une distribution de probabilité uniforme un entier aléatoire compris entre certaines limites. Si le générateur de nombres aléatoires sélectionne l'entier 5, on choisira alors la fonction de multiplication (illustrée graphiquement au point 612) comme point de croisement du parent n 1. Cette identification est réalisée de façon très simple en numérotant les fonctions et arguments atomiques dans le même ordre que celui dans lequel la fonction de comptage les a rencontré (bien que l'on pourrait utiliser n'importe quel ordre à cet effet). Dans ce cas particulier, le point de croisement est le premier élément de la sous- liste (* A21 A22). Cette sous-liste est le troisième élément de la liste 600. On notera que, en LISP, une procédure de calcul est représentée par une liste - c'est-à-dire par un ensemble ordonné de rubriques se trouvant à l'intérieur d'un couple de parenthèses. De la même façon, on peut compter les fonctions et les 52 2631?20 arguments atomiques de la procédure de calcul 620. Pour le parent n 2, le compte global vaudrait ainsi sept. Dans cet exemple, on sélectionne l'argument atomique B1 comme point de croisement pour le parent n 2. Il se trouve que cet argument atomique se situe dans l'avant-dernier élément, à partir du haut, de la liste 620 - c'est-à-dire dans la sous-liste (- B1 B2). En fait, B1 est le second élément de cet avant-dernier élément, à partir du haut, de la liste 620. La troisième étape consiste à trouver le "fragment de croisement" de chaque parent. Lorsque le point de croisement d'un parent donné est un argument atomique, le "fragment de croisement" de ce parent est simplement constitué par l'argument atomique. Ainsi, par exemple, le fragment de croisement du parent n 2 est l'atome B1. Inversement, lorsque le point de croisement d'un' parent donné est une fonction, le "fragment de croisement" du parent est la liste complète dont la fonction est le premier élément. Ainsi, par exemple, le fragment de croisement du parent n 1 est la liste complète (* A21 A22). En obtenant les "fragments de croisement", on peut combiner des parties de chaque parent pour engendrer une descendance. Dans le cas ci-dessus, la liste ne comporte pas de sous-listes. Cependant, si cette liste contenait une sous-liste (c'est-à-dire, un argument qui serait lui-même une fonction d'autres arguments), on déplace également celle-ci. Cette remarque faite à propos des sous-listes peut être aisément illustrée en supposant que le premier élément de la liste 600 a été choisi comme point de croisement (au lieu que ce soit la fonction multiplication). Ce premier élément est la fonction "+". Le fragment de croisement associé à ce point de croisement est alors la totalité de la liste d'origine 600 - c'est-à-dire, la liste constituée par la fonction "+ " et les deux sous-listes (+ All A12) et (* A21 A22). La quatrième étape consiste à engendrer le descendant no 1. Le descendant n 1 est engendré en faisant en sorte que le parent n 1 joue le rôle du parent "base" (femelle) et que le parent n 2 joue le rôle du parent "fécondant" (mâle). De façon générale, on engendre un descendant au sein du parent femelle en remplaçant le fragment de croisement du parent femelle par le fragment de croisement du parent mâle. Dans ce cas particulier, le fragment de croisement du parent femelle, c'est-à-dire la liste (* A21 A22) dans son entier, est remplacé dans le parent femelle par le fragment de croisement du parent mâle, c'est-à-dire l'argument atomique B1. Le descendant n 1 résultant est donc (+ (+ All A12) B1). La cinquième étape consiste à engendrer le descendant n 2. Le descendant n 2 est engendré en faisant en sorte que le parent n 2 joue le rôle duparent "base" (femelle) et que le parent n 1 joue le rôle du parent "fécondant" (mâle). Dans ce cas particulier, le fragment de croisement du parent femelle, c'est-à-dire l'argument atomique B1, est remplacé dans le parent femelle par le fragment de croisement du parent mâle, c'est-à-;ire la liste (* A21 A22) dans son entier,. Le descendant n 2 résultant est donc (- (- (* A21 A22) B2) (* B3 B4)). Deux parents peuvent ainsi engendrer deux descendants. Dans certaines variantes du processus, un couple mâle- femelle donné n'engendre qu'un seul descendant; cependant, il est plus commode que deux parents engendrent deux descendants car, entre autres choses, on obtient ainsi l'effet induit utile, bien que non nécessaire, de maintenir à un niveau constant la taille de la population. Dans cette mise en oeuvre préférentielle du processus de croisement, chaque descendant est constitué d'un matériau génétique provenant soit de son parent mâle soit de son parent femelle. Le matériau génétique des deux parents se replace ainsi dans l'un des deux descendants. Pour l'opération de reproduction, on sélectionne parmi les procédures de calcul de la population une procédure de calcul présentant un degré d'adaptation relativement élevé. On laisse cette procédure de calcul inchangée dans la population. La méthode préférée de sélection des procédures de calcul pour la reproduction consiste à les sélectionner avec une probabilitéproportionnelle à leur degré d'adaptation normalisé. En d'autres termes, il y a survie et reproduction des individus les plus adaptés de la population des procédures de calcul. L'une des conséquences de l'opération de reproduction est que l'on élimine progressivement les individus de la population ayant des valeurs d'adaptation relativement faibles. On notera que l'opération de reproduction n'introduit rien de nouveau dans la population. Si l'on n'exécutait que des opérations de reproduction, on ne créerait pas de nouveaux individus. En fait, si l'on ne réalisait que des reproductions, il y aurait, progressivement, de moins en moins d'individus différents dans la population (bien que le degré d'adaptation moyen de la population tende à augmenter). L'opération de reproduction possède les propriétés"précitées de fermeture et de bonne définition. La reproduction des plus adaptés et le croisement sont les opérations de base qui permettent de varier et d'améliorer la population des individus constitués par les procédures de calcul. Il existe en outre une opération de permutation. La permutation opère sur un sujet isolé et produit une seule procédure de calcul. L'opération de permutation possède les propriétés précitées de fermeture et de bonne définition. La figure 7 illustre l'opération de permutation sur une procédure de calcul. L'opération de permutation est, ici encore, exécutée sur un individu de la population de relativement bon degré d'adaptation. L'un des buts de la permutation est d'introduire un nouvel ordonnancement dans des sousprocédures existantes d'une procédure de calcul donnée (ce qui peut éventuellement permettre l'émergence d'une nouvelle possibilité d'adaptation). Cependant, les chances d'aboutir à un tel cas de figure sont relativement minces (tout comme sont minces les chances d'aboutir par mutation aléatoire à la génération d'un mutant de degré d'adaptation élevé). Le but principal de la permutation est plutôt d'améliorer diverses sous-procédures se trouvant à l'intérieur d'une procédure de calcul donnée qui présente déjà un degré d'adaptation élevé. Potentiellement, un nouvel ordonnancement, dans une procédure de calcul ayant déjà une degré d'adaptation élevée, de sous-procédures existantes sera moins sujet à une disruption due à l'opération de croisement. Sur la figure 7, la procédure de calcul 900 sur laquelle on opère, à savoir (- (-A B C) (t D E F) (* G H I)), est repré- sentée par une arborescence de racine 910. La racine 910 est la fonction de soustraction, à laquelle sont reliés des arguments aux noeuds internes 902, 912 et 914. Le noeud 902 est la fonction de soustraction, à laquelle sont reliés des arguments aux feuilles 904, 906 et 908 (les variables A, B et C, respectivement). Le noeud 912 est la fonction d'addition, à laquelle sont reliés des arguments aux feuilles référencées par les variables D, E et F. Le noeud 914 est la fonction de multiplication, à laquelle sont reliés des arguments aux noeuds référencés par les variables G, H et I. On ne sélectionne pour l'opération de permutation que des points internes. A cet effet, on compte les points internes et on choisit l'un d'entre eux, de manière aléatoire et avec une distribution de probabilité uniforme, parmi les différentes possibilités existantes. L'arborescence de racine 910 possède quatre points internes 910, 902, 912 et 914. Une fois que l'on a choisi le point de permutation, toutes les lignes rayonnant vers le bas depuis ce point sont permutées (c'est-à-dire réordonnancées) de manière aléa- toire. Si l'on a K lignes rayonnant à partir d'un point de permutation donné, on a alors K! permutations possibles. Ainsi, si K vaut 3 (comme dans le cas du point interne 902), il y a six permutations possibles (c'est-à-dire 3 fois 2 fois 1) au point de permutation 902. On choisit, de manière aléatoire et avec une distribution de probabilité uniforme sur les six possibilités, l'une des six permutations possibles. L'une des six permutations possibles de trois éléments permute les éléments A, B, C en C, A, B. Supposons que c'est cette dernière qui a été choisie. La procédure de calcul 920, à savoir (- (-C A B) (+ D E F) (* G H I)), est représentée par l'arbo- 56 2631720 rescence de racine 930, et elle est constituée par l'arborescence que l'on obtient lorsque l'on applique cette permutation particulière à l'arborescence de racine 910 en utilisant le point de permutation 902. Dans cette nouvelle arborescence 930, la première ligne 902 rayonnnant depuis le point interne 932 aboutit à la référence C (au lieu de A, comme en 904). La seconde ligne 924 rayonnant depuis le point interne 932 aboutit à la référence A (au lieu de B, comme en 906). La troisième ligne 926 rayonnant depuis le point interne 932 aboutit à la référence B (au lieu de C, comme en 908). La deuxième et la troisième lignes provenant de 930 ont les mêmes arguments que la deuxième et la troisième lignes issues de la racine 910. On a ainsi réalisé la permutation de A, B, C en C, A, B au point de permutation 902. S'il se trouve que l'une des permutations particulières inverse exactement l'ordre des éléments, on l'appellera "inversion". Si le point interne 910 a été choisi comme point de permutation, la procédure de calcul 940, à, savoir (- (+ D E F) (* G H I) (- A B C)), représentée par l'arbores- cence de racine 950, constituera le résultat. Dans cette arborescence, la première ligne 942 rayonnant vers le bas depuis la racine 950 aboutit à la référence "+" (addition). La deuxième ligne 944 rayonnant vers le bas depuis le point interne 950 aboutit & la référence "*" (multiplication). La troisième ligne 946 rayonnnant vers le bas depuis le point * interne 950 aboutit à la référence "-" (soustraction). Ainsi, les trois éléments "-", "+" et "*" de l'arborescence 910 sont permutés suivant le nouvel ordre "+", "*" et "-". Chaque fonction a les mêmes arguments que l'arborescence correspondante de racine 910. Si l'on considère que l'opération de permutation opère sur les lignes rayonnant vers le bas depuis le point de permutation choisi, il n'y a pas de différence fondamentale entre la permutation d'arguments illustrés en 920 et la permutation de fonctions illustrée en 940. On a étudié l'un et l'autre cas simplement pour les illustrer tous les deux. 57 2631720 Une autre étape possible du processus de la présente invention est la mutation. L'opération de mutation altère, dans un individu, un point sélectionné de manière aléatoire. Il présente les propriétés mentionnées plus haut de fermeture et bonne définition. La mutation, à supposer qu'elle ait effectivement lieu, n'est exécutée que sur une toute petite fraction des allèles d'une toute petite fraction des entités de la population. Elle est de préférence exécutée sur des individus choisis de manière aléatoire dans la population dont le degré d'adaptation est relativement élevée. Le but de la mutation n'est pas de créer par accident un individu mutant dont le degré d'adaptation serait extrêmement élevé et qui améliorerait ainsi la population (bien qu'il existe une possibilité, très faible, que ceci arrive). En fait, la mutation joue un rôle qui, à l'occasion, peut être utile,en procurant un moyen d'introduire (ou de réintroduire) un nouveau matériau génétique dans la population. Généralement, même avec une population de taille modeste, toutes les valeurs géniques (allèles) possibles seront représentées quelque part dans la population. Ceci sera, de façon pratiquement certaine, le cas de la population initiale, si celle-ci est au moins de taille modeste et si elle est créée de manière aléatoire. En fait, l'un des écueils lors de la création d'une population initiale (en particulier si 100 % de la population initiale provient de cette création) est le risque de limiter accidentellement les possibilités de recherche à seulement une partie de l'espace de recherche potentiel. Par ailleurs, lorsque l'on élimine les individus de faible degré d'adaptation, il y a un faible risque que des allèles particuliers disparaissent complètement d'une population. Il y a également un faible risque que, plus tard, les allèles disparus deviennent nécessaires pour passer au degré supérieur de progrès du degré d'adaptation. Pour se prémunir contre cette conjonction peu probable de possibilités, l'opération de mutation peut se révéler utile. -En altérant, de temps en temps et de manière aléatoire, un allèle dans un très petit 58 2Z631720 nombre d'individus choisis au hasard, l'opération de mutation peut réintroduire à nouveau un allèle disparu d'une population. Pour achever le processus, on ajoute à la population les résultats de l'opération choisie. Lorsqu'une quelconque opération crée des nouveaux individus formés de procédures de calcul, ceux-ci sont ajoutés à la population existante d'individus. On peut alors exécuter immédiatement le processus d'exécution des nouvelles procédures de calcul afin de donner un résultat, puis affecter une valeur aux résultats. Ainsi, si l'étape suivante termine le processus itératif, les nouvelles procédures de calcul créées auront une valeur d'adaptation. Le processus de la présente invention peut tirer grandement parti d'un fonctionnement parallèle. Si l'on utilise un fonctionnement parallèle, le taux global d'activité augmente- en proportion pratiquement directe du nombre d'actions exécutées simultanément. La figure 8 est un schéma par blocs illustrant un traitement parallèle de la présente invention utilisant deux sous-populations, avec deux unités de traitement pour chacune. La sous-population Pi 1410 est reliée aux unités de traitement Uil 1411 et U12 1412. La sous-population P2 1420 est reliée aux unités de traitement U21 1421 et U22 1422. Une voie de communication 1430 relie les quatre unités de traitement. La figure 8 illustre deux sous-populations avec chacune deux unités de traitement; cependant, en règle générale, on pourrait avoir un nombre arbitraire de sous-populations et un nombre arbitraire d'unités de traitement. On peut avoir deux types d'actions parallèles. Dans le premier type, chacune des opérations (croisement, reproduction, permutation, etc.) est exécutée simultanément en parallèle sur différentes entités (ou différents groupes d'entités, pour le croisement) sélectionnées dans une population donnée d'individus. Si les entités sont des programmes informatiques, le traitement parallèle est réalisé par une machine informatique possédant plusieurs unités de traitement (de contrôle et arithmétiques) capables 59 2631720 de travailler simultanément sur des entités sélectionnées dans une même zone mémoire particulière de l'ordinateur. Pour illustrer ce premier type de traitement parallèle, considérons les unités de traitement Uns 1411 et U12 1412, qui sont rattachées à la souspopulation Pl 1410. Chaque unité de traitement peut accédezr à la souspopulation afin de sélectionner, en fonction de leur degré d'adaptation relatif, des entités pour effectuer les opérations, puis exécuter l'opération, ajouter de nouveaux programmes, et effectuer simultanément le reste du processus itératif. Le second type de traitement parallèle implique des actions ayant lieu simultanément dans deux (ou plus de deux) sous-populations différentes. Pour illustrer ce type de traitement parallèle, considérons la souspopulation Pi 1410 et la sous-population P2 1420. Les deux unités de traitement de P2 opèrent sur P2 pendant que les deux unités de traitement de Pl opèrent sur Pl. Les deux types de parallélismes sont extrêmement performants, du fait que l'on a besoin de ne faire transiter que très peu d'informations sur la voie de communication 1430. En outre, chaque unité de traitement n'a besoin d'exécuter qu'un faible nombre d'actions très simples en réponse aux informations reçues de puis la voie de communication 1430. La communication et la coordination sont exécutées par la voie de communication 1430, qui relie toutes les unités de traitement associées aux diverses sous-populations'. Dans un ordinateur, la voie de communication est un bus de communication. Pour illustrer l'efficacité du traitement parallèle, supposons que l'on effectue la sélection en utilisant des probabilités proportionnées au degré d'adaptation. Le calcul de cette probabilité pour un individu particulier nécessite habituellement deux éléments d'information, à savoir la valeur (degré d'adaptation) affectée au résultat de l'exécution de l'individu particulier, et le total de toutes ces valeurs pour tous les individus de la population prise dans son entier. Habituellement, ce calcul est exécuté en divisant la valeur (degré d'adaptation) affectée à 2631720 l'individu par le total correspondant à la population dans son entier. Après que l'on ait calculé une première fois le total pour l'ensemble de la population initiale, on modifie aisément ce total en incrémentant celui-ci à chaque individu nouvellement créé et en le décrémentant à chaque individu que l'on retire. Ce calcul simple peut être exécuté par chaque unité de traitement chaque fois qu'elle reçoit, via la voie de communication 1430, des informations concernant une insertion ou un retrait d'individu dans la population. De la même façon, chaque unité de traitement doit transmettre aux autres unités de traitement, via la voie de communication 1430, des informations chaque fois qu'elle insère ou retire un individu quelconque de la souspopulation à laquelle elle a accès. Le message est formé de l'incrément (dans la cas d'une insertion) ou du décrément (dans le cas d'un retrait) de la valeur totale (degré d'adaptation) de la population. On notera que ces messages sont relativement courts et ne nécessitent qu'un très faible effort d'émission et d'action, par rapport à l'effort considérablement supérieur nécessaire à l'exécution du processus itératif. Du fait que, les messages de traitement sont relativement mineurs par rapport à l'exécution de l'algorithme génétique, le taux global d'activité de cette configuration parallèle augmente en proportion directe du nombre d'actions à exécuter en parallèle. Dans le cas de programmes d'ordinateur, l'avantage que l'on peut tirer d'une activité parallèle (en utilisant des unités de traitement parallèles accédant à des sous-populations parallèles) se manifeste en termes de taux global d'activité du traitement informatique, qui augmente pratiquement en proportion directe du nombre d'actions parallèles. En d'autres termes, le volume de calculs exécutés par unité de temps augmente pratiquement en proportion directe du nombre d'actions parallèles. De temps en temps, on utilise également la voie de communication pour échanger des groupes importants d'individus entre sous-populations, afin que chaque sous-population reçoive en provenance d'autres 61 2631720 sous-populations un matériau génétique neuf ayant atteint une valeur d'adaptation relativement élevée. Ces transmissions occassionnelles d'informations accroissent la charge de gestion d'un système parallèle; cependant, comme elles n'ont lieu qu'occassionnellement (par exemple, après que l'on ait produit un grand nombre d'actions confinées aux souspopulations respectives), elles n'ont qu'une incidence mineure sur l'efficacité globale de la configuration parallèle. On va maintenant donner trois exemples d'application de la présente invention, concernant les équations linéaires, les suites et le problème du Commis Voyageur. Résolution d'équations linéaires Dans cet exemple, l'environnement dans lequel a lieu l'adaptation consiste en m ensembles de deux équations linéaires homogènes non indéterminées à deux variables. Si l'on supprime les indices identifiant le couple particulier d'équation en question, le couple d'équations typique est: All X1 + A12 X2 = Bl A21 Xl + A22 X2 = B2 Tout en restant dans le cas général, les coefficients de chaque couple d'équations ont été normalisés de telle sorte que le discriminant soit égal à 1. Ce problème particulier possède pour la première variable (xl) une solution mathématique connue qui, si on l'écrit sous la forme d'une sexpression en langage de programmation LISP, sera (- (* B1 A22) (* B2 A12) ). Une s-expression semblable donne la solution de la seconde variable (x2). Un critère naturel de mesure pour l'évaluation de la solution proposée par une s-expression est constitué par la somme des écarts par rapport à la solution mathématique connue donnée par la s-expression proposée. Cette somme est le cumul, sur la série de tous les couples d'équations, de la distance euclidienne entre le point formé par la solution proposée et le point correspondant à la solution réelle, connue. Une somme nulle, pour une s-expression particulière, signifie que l'expression est une solution parfaite. Une somme très faible représente le type de solution acceptable en pratique dans un calculateur numérique. Comme la solution de la seconde variable (x2) peut être directement obtenue à partir de l'une des deux équations (homogènes) d'un couple donné, une solution proposée à ce problème peut être considérée comme étant constituée simplement d'une unique s-expression valable dont la valeur retournée est la solution correspondant la première variable (xl) pour chaque couple d'équation de la série. La solution proposée peut alors être évaluée en obtenant la solution de la seconde variable à partir de celle de la première, puis en calculant la distance euclidienne. Enfin, on cumule les distances pour toute la série. Il se trouve que cette manière de procéder rend les arguments atomiques A12 et A22 étrangers à la solution de la variable (xl). La figure 9 montre un couple d'équations linéaires à deux variables xl et x2. Sur la figure 9, la première équation 310 correspond à la droite 320 tracée dans le plan défini par l'axe horizontal Xl 330 et l'axe vertical X2 340. La seconde équation 350 correspond à la droite 360 tracée sur le même plan. Le point d'intersection 370 possède une coordonnée (xl) 380 sur l'axe horizontal Xl 330 et une coordonnée (x2) 390 sur l'axe vertical X2 340. L'universalité dont proviennent les solutions proposées pour la première variable xl est celui formé par toutes les s-expressions LISP valides (avec un niveau d'imbrication des fonctions quelconque) construites à partir des arguments atomiques utiles d'entrée (All, A21, B1 et B2), des arguments atomiques étrangers d'entrée (A12 et A22), des fonctions utiles de multiplication et de soustraction ("*" et "-") et la fonction étrangère d'addition ("+"). La présence d'une fonction étrangère et d'arguments étrangers permet de rendre cet exemple de problème plus réaliste. L'espace de recherche dans lequel se trouve la solution à ce problème est ainsi un espace très étendu, non linéaire et non continu d'arborescences & racine dont les points sont référencés par divers symboles mathématiques (fonctions ou bien arguments). Un nombre important de structures arborescentes possibles peuvent représenter des s-expres- sions LISP valides, même si on limite arbitrairement le niveau d'emboîtement et si les fonctions n'ont toutes que deux arguments. Il existe en outre de nombreuses manières de référencer les points internes de ces arborescences par les fonctions disponibles, et il existe de nombreuses manières de référencer les points externes (feuilles) de ces arborescences par les arguments disponibles. Certaines s-expressions LISP de l'espace de recherche sont mathématiquement semblables à la solution la plus économe située plus haut (par exemple, si l'on ajoute (- All All) à la solution). Cependant, ces s-expressions numériquement équivalentes occasionnelles ne donnent aucune simplification utilisable du problème ni de réduction utilisable du nombre important (du point de vue combinatoire) de s-expressions possibles en jeu ici. La résolution de ces problèmes commence par la génération d'une population d'individus formée de s-expressions à partir des fonctions "*"', "-" et "+" et des arguments atomiques All, A12, A21, A22, B1 et B2. La population initiale peut être engendrée de façon entièrement aléatoire, c'est-à-dire que, en commençant par le sommet de l'arborescence, on choisit de façon aléatoire l'une des fonctions ou l'un des arguments disponibles. Si, pour ce premier choix, on choisit un argument atomique, le processus est achevé et la s-expression est formée par cet atome unique. Si l'on choisit une fonction, le processus continue. Si la fonction choisie nécessite K arguments (et, dans cet exemple de problème, K vaut 2 pour chacune des trois fonctions), on effectue une sélection aléatoire semblable pour chaque point d'extrémité de chacune des K lignes rayonnant vers le bas depuis le point initial. Cette sélection est également effectuée de manière aléatoire, et peut donner un argument atomique ou bien une fonction. Si c'est un argument atomique qui a été sélectionné, ce point particulier devient un point externe (feuille) de l'arborescence et on ne s'intéressera plus à cette ligne. Si c'est une fonction qui a été sélectionné, le processus continue alors de façon récursive, en effectuant des sélections supplémentaires de la même manière. Lorsque, à un certain point, on a sélectionné des arguments atomiques pour tous les points externes, le processus de construction' aléatoire de l'arborescence est alors achevé. La population initiale est simplement un sous-ensemble aléatoire du domaine dans lequel la recherche ultérieure devra avoir lieu. Dans certains problèmes, on peut "amorcer" le système en incluant certaines s-expressions (ou certaines parties de sexpressions) que l'on estime importantes eu égard au problème considéré. En outre, on peut interrompre le traitement du système à n'importe quel point et le reprendre avec la population d'individus existant à la fin de l'exécution précédente. Cette méthode de redémarrage des actions peut être considérée comme un amorçage de système par une population entière. La figure 10 est un exemple de génération aléatoire d'une population initiale de s-expressions utilisant en exemple l'expression 262, qui est: (+ (- B1 A12) (* (* B2 A21) B2)) En partant de la racine 264 de l'arborescence, on sélectionne l'une des fonctions disponibles ("*", "+" ou "-") ou l'un des arguments atomiques disponibles (All, A12, A21, A22, B1 ou B2). Sur cette figure, la fonction "+" (addition) a été sélectionné aléatoirement pour apparaître à la racine 264 de l'arborescence. Comme cette fonction possède deux arguments, on a deux lignes 266 et 268 qui rayonnent vers le bas depuis le point interne 264. Pour l'extrémité 270 de la ligne 266 et l'extrémité 272 de la ligne 268, on doit effectuer une autre sélection aléatoire semblable à partir de l'ensemble des fonctions disponibles ou arguments disponibles. Pour le point 270, c'est la 2631720 fonction "-" (soustraction) qui a été sélectionnée. Comme cette fonction a également deux arguments, on a deux lignes 274 et 276 qui rayonnent vers le bas depuis le point 270. Pour l'extrémité de chacune de ces lignes rayonnantes, on doit effectuer une sélection aléatoire semblable. Ici, c'est la variable B1 qui a été sélectionné pour l'extrémité 278 de la ligne 274. Comme B1 est un argument atomique, ceci met fin au processus pour cette branche de l'arborescence. De la même manière, c'est la variable A12 qui a été sélectionnée pour l'extrémité 280 de la ligne 276. Ceci met fin au processus pour la ligne 266 qui rayonne vers le bas depuis la racine 264. Pour le second argument de la racine 264 au point interne 272, c'est une fonction "*"1 (multiplication) qui a été sélectionnée. Comme cette fonction possède deux arguments, deux lignes 282 et 284 rayonnent vers le bas depuis le point 272. Pour le point 286 à l'extrémité de la ligne 282, c'est une autre fonction 11"*"11 (multiplication) qui a été sélectionnée. L'extrémité 288 de la première ligne 290, qui rayonne vers le bas depuis le point 286, possède l'argument atomique de la variable B2. Le point d'extrémité 292 de la seconde ligne 294, qui rayonne depuis le point 286, possède l'argument atomique de la variable A21. De la même façon, la ligne 284 qui rayonne vers le bas à partir du point 272 possède à son extrémité (feuille) 296 l'argument atomique de la variable B2. Ceci met fin à la génération aléatoire de l'arborescence et de la s-expression correspondante. Voici quelques exemples de s-expressions possibles qui auraient pû être produites, dans le cas de cet exemple, de manière aléatoire comme population initiale d'individus: (1) (+ All.A12) (2) (- (* B1 B2) A22) (3) (+ (- B1 A12) (* (* B2 A21) B2)) Si l'on examine l'une de ces expressions, l'exemple-(1) est formé.par la somme des coefficients de la première équation linéaire. Son interprétation est que la solution de la première variable (xl) dans un système de deux équations linéaires à deux variables serait toujours égale à la somme de All et A12, indépendamment des autres coefficients ou constantes de l'équation. Comme on peut s'y attendre, cette expression erronée produira généralement des solutions proposées éloignées des solutions correctes. Bien sûr, cette s-expression incorrecte pourrait éventuellement, par hasard, produire la solution correcte pour un couple d'équation particulier. Une fois que l'on a engendré la population d'individus, on exécute chacune des s-expressions de la population (c'està-dire que, en LISP, on les "évalue") afin de donner un résultat. En LISP, chaque s-expression peut être exécutée de manière à retourner un certain type de résultat numérique, symbolique, logique ou autre. En pratique, on répète cette exécution sur des séries (par exemple sur différentes parties dans le cas du Dilemme du Prisonnier, ou sur différents couples d'équations linéaires dans le problème exposé ici en exemple) afind'éviter des conclusions qui, accidentellement, induiraient en erreur. En effectuant cette évaluation sur une série de situations différentes, on obtient une meilleure mesure de la performance. Par exemple, (+ All A12) pourrait donner la solution correcte de la première variable (xl) pour un certain jeu inhabituel d'équations linéaires à deux variables, mais pas la solution au problème dans le cas général. Pour les besoins du problème donné ici en exemple, et afin de simplifier la discussion, le "résultat" de l'évaluation de la s-expression est ici simplement une valeur numérique de la première variable xl. Comme mentionné précédemment, si l'on permettait d'avoir des droites parallèles (c'est-à-dire des équations non homogènes) dans cet exemple, le "résultat" serait soit numérique soit symbolique. En variante, le "résultat" pourrait être également le couple (vecteur) de nombres {xl, x2} spécifiant les coordonnées du point du plan o se coupent les deux droites. Une fois que l'on a obtenu le résultat de l'exécution de la procédure de calcul (s- expression), on peut affecter au résultat une valeur dans l'environnement particulier concerné pour le problème particulier concerné. Dans le cas du problème donné ici en exemple, la solution de la seconde variable (x2) peut être directement obtenue à partir de la première variable (xl) en utilisant l'une ou l'autre des deux équations (homogènes) d'un couple d'équations donné. Les variables xl et x2 correspondent à un certain point du plan (le point dont l'abcisse est xl et dont l'ordonnée est x2), la solution réelle correspondant en fait à un autre point du plan. On peut calculer la distance entre ces deux points du plan. Les distances obtenues en évaluant la s-expression pour les autres couples d'équations linéaires peuvent être calculées de la même façon. La distance cumulée donne une mesure naturelle de la valeur (degré d'adaptation) d'un individu (s-expression) dans cet environnement. Si la somme de ces distances par rapport à un individu (ou s-expression) vaut zéro, la s-expression a alors la meilleure valeur possible (meilleur degré d'adaptation possible) dans cet environnement du fait qu'elle produit des points d'intersection qui sont parfaitement corrects dans chaque cas (c'est-à-dire qui présentent, dans chaque cas, une distance nulle par rapport aux points corrects). Induction de la loi d'une suite Dans cet exemple de problème, l'environnement dans lequel on doit réaliser l'adaptation consiste en une suite unique donnée: SO, S1, S2, S3,... Si,... Le but recherché est de produire une procédure de calcul (s-expression) correspondant à cette suite (c'est-à-dire, une procédure de calcul qui donne Si pour tout indice i). Une solution proposée à ce problème d'induction de la loi d'une suite consiste en une s-expression LISP utilisant l'argument INDICE et donnant la valeur de l'élément à la position INDICE de la suite. Le premier élément d'une suite est considéré, par convention, comme ayant une valeur INDICE de 0 (et non de 1). Par exemple! la suite 0, 2, 4, 6, 8, 10, 5... peut être représentée par la procédure de calcul (* 2 INDICE). En d'autres termes, la valeur de l'élément de la suite à la position INDICE de la suite vaut deux fois la valeur INDICE. Ce problème d'induction de la loi d'une suite n'a bien entendu pas de solution mathématique stricte. Néanmoins,- on peut évaluer les solutions proposées en fonction de la manière dont elles concordent avec les éléments connus disponibles de la suite. Dans ce cas, plus la fonction de concordance donne une valeur élevée, meilleure est la situation. La meilleure valeur, connue, de la fonction de concordance est la valeur que l'on aura si tous les éléments disponibles connus de la suite concordent exactement avec le résultat de l'exécution de la procédure de calcul considérée. Comme de nombreuses suites sont définies par récursion (c'està-dire que l'on utilise les éléments antérieurs de la suite pour définir les éléments ultérieurs), il est souhaitable d'avoir une fonction qui permette de renvoyer à la valeur de l'élément de la suite pour les k positions de la suite précédant la position courante (c'est-à-dire, la position dont le rang est INDICE). Par exemple, il peut être nécessaire d'exprimer Si en fonction de Si-1 (l'élément précédent de la suite) ou enfonction de Si-k (se trouvant k éléments avant dans la suite). On notera que, si la valeur de k est nulle, négative ou supérieure à INDICE, le renvoi que l'on essaye d'obtenir correspondra à des valeurs de la suite qui n'existent pas. Pour ces positions qui n'existent pas, une valeur par défaut doit être définie pour la fonction afin de la rendre complète. La fonction de renvoi doit donc avoir deux arguments. Le premier argument est k et le second argument est une valeur par défaut. La fonction de renvoi sera référencée "&". La fonction & (k,D) des variables k et D retourne la 69 - valeur de la suite pour la position INDICE-k chaque fois que INDICE-k est compris entre 0 et INDICE-1 et, dans le cas contraire, retourne la valeur par défaut D. Par exemple, la suite 2, 4, 8, 16, 32,... peut être représentée par la procédure de calcul (* 2 (& 1!2) car la valeur de l'élément de la suite de rang INDICE vaut, de façon générale, deux fois la valeur de la suite pour la position INDICE-1. On notera que lorsque INDICE vaut 0 (et que l'on tente de renvoyer à l'élément de la suite de rang -1), la valeur de la suite est deux fois la valeur par défaut de 1. De la même façon, par exemple, la suite de Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,... peut être exprimée sous la forme Si = Si-2 + Si-1 (étant entendu que, si Si-2 ou Si-1 renvoient à des éléments de la suite antérieurs à l'élément de la suite de rang 0, on utilisera une valeur par défaut de 1). La suite de Fibonnaci peut également être représentée par la procédure de calcul doublement récursive: (+ (& 1 1) (& 2 1)) À l'exception de l'argument spécial INDICE et à l'exception de la fonction de renvoi spéciale "&" nécessaire pour permettre des renvois à la suite elle-même, le processus d'induction de la loi d'une suite peut se dérouler en utilisant les mêmes fonctions disponible en LISP que celles qui étaient utilisées dans l'exemple des équations linéaires. La figure 11 illustre l'opération de croisement appliquée à deux parents dont les fonctions et arguments incluent la fonction spéciale "&" et l'argument spécial INDICE propres au problème de l'induction de la loi d'une suite. Le premier parent est la procédure de calcul 1000, à savoir (+ (* INDICE 2) (& 2 1)), représentée par l'arborescence de racine 1010. La racine 1010 est la fonction d'addition, à laquelle sont reliés desarguments aux noeuds internes 1016 et 1012. Le noeud 1016 est la fonction de multiplication, à laquelle sont reliés des arguments aux feuilles 1014 et 1015 (la variable INDICE et le nombre 2, respectivement). Le noeud 1012 est la fonction "&" (renvoi), à laquelle sont reliés des arguments aux feuilles 1018 et 1019 (les nombres 2 et 1, respectivement). La sousarborescence 1011 est formée des éléments 1012, 1018 et 1019. L'argument INDICE' apparaît comme l'un des arguments 1014 de la fonction de multiplication 1016 (I"*"). La fonction de renvoi apparaît au point interne 1012 de l'arborescence et opère sur les arguments 1018 et 1019 (les nombres 2 et 1, respectivement). Cette fonction "(& 2 1)" signifie: "donner la valeur des éléments de la suite située deux positions avant dans la suite, ou bien donner la valeur par défaut 1 si la position courante de la suite est seulement 0 ou 1". Le second parent est la procédure de calcul 1020, à savoir (+ (& 1 1) (& 2 0)), représentée par l'arborescence de racine 1030. La racine 1030 est la fonction d'addition, à laquelle sont reliés des arguments aux noeuds internes 1022 et 1032. Le noeud 22 est la fonction "&", à laquelle sont reliés des arguments aux feuilles 1024 et 1026 (les nombres 1 et 1). Le noeud 1032 est la fonction "&", à laquelle sont reliés des arguments aux feuilles 1034 et 1036 (les nombres 2 et 0, respectivement). L'arborescence 1021 comporte les éléments 1030, 1022, 1024 et 1026. Le point interne 1012 de l'arborescence de racine 1010 et le point interne 1032 de l'arborescence de racine 1030 sont choisis comme points de croisement. Le premier descendant 1040, à savoir (+ (* INDICE 2) (& 2 0)), est représenté par l'arborescence de racine 1050. La racine 1050 est la fonction d'addition, à laquelle sont reliés des arguments aux noeuds internes 1042 et 1052. Le noeud 1042 est la fonction de multiplication, auquel sont reliés des arguments aux feuilles 1044 et 1046 (la variable INDICE et le nombre 2, respectivement). Le noeud 1052 est la fonction "&", à laquelle sont reliés des arguments aux feuilles 1048 et 1054 (les nombres 2 et 0, respectivement). 263 1720 Le second descendant 1060, à savoir (+ (& 1 1) (& 2 1)), est représenté par l'arborescence de racine 1070, et il est composé -de l'arborescence 1021 du second parent 1020 combinée à la sous-arborescence 1011. La racine 1070 est la fonction d'addition, à laque.le sont reliés des arguments aux noeuds internes 1062 et i078. Le noeud 1062 est la fonction "&", à laquelle sont reliées les feuilles 1074 et 1076 (les nombres 2 et 1, respectivement). Ce second descendant constitue la solution correcte connue au problème de l'induction de la loi de la suite de Fibonacci. On notera que les suites qui sont ici en jeu n'ont pas besoin d'être des suites déterministes. Elles pourraient, au contraire, être produites par des processus probabilistes. Par exemple, la suite 0, 1, 2, 5, 4, 5, 8, 7,... pourrait - être engendrée en donnant simplement à l'élément de la suite une valeur égale à INDICE les trois-quarts du temps et une valeur égale à (+ INDICE 2) un quart du temps. Ici, lorsque INDICE valait 0, 1, 2, 4, 5 et 7, la valeur de l'élément la suite était 0, 1, 2, 4, 5 et 7, respectivement. En d'autres termes, la valeur de la suite était alors égale à INDICE. Mais, lorsque INDICE valait 3 et 6, la valeur de l'élément de la suite était, respectivement, 5. et 8. En d'autres termes, la valeur de l'élément de la suite était égal à INDICE + 2. Dans de tels cas, on n'obtiendra pas de concordance parfaite; cependant, les degrés d'adaptation les plus élevés correspondront aux procédures de calcul qui produisent des concordances plus souvent que d'autres. Problème du Commis Voyageur Dans cet exemple de problème, on donne à un commis voyageur un tableau kilométrique donnant les distances entre un nombre donné de villes, et on lui demande de passer une fois dans chacune des villes (et de revenir à son point de départ) en couvrant le moins de kilomètres possibles. Dans le problème du Commis Voyageur, on peut représenter un itinéraire passant par toutes les villes par une permutation des N villes, une "permutation" signifiant un ensemble ordonné des villes tel que chaque ville apparaisse une fois et une seule dans cet ensemble ordonné. Une partition d'un ensemble de N éléments consiste en un ensemble dé sous-ensembles tel que chacun des N éléments de l'ensemble original ne se retrouve dans un et un seul des sous- ensembles. Par exemple, une partition possible de l'ensemble de cinq nombres {1,2,3,4,5} est l'ensemble formé par les deux sous-ensembles {1,5} et {2,3,4}. La présente invention aborde le problème du Commis Voyageur en termes de partitionnement des N villes en sous-itinéraires. Ainsi, la représentation d'un itinéraire complet de toutes les villes implique la combinaison d'informations sur: (1) la partition concernée (c'est-à-dire la manière dont les N villes sont divisées en sous-itinéraires), (2) la première et la dernière ville de chaque sous-itinéraire, et (3) l'ordre des sous-itinéraires. L'arborescence de la figure 12 montre une représentation d'un itinéraire passant par 9 villes. La s-expression LISP 1100, à savoir (GO (G 1 2 3) (G 4 5) (G 6 7 8 9)), décrit la totalité de l'itinéraire et elle est représenté par une arborescence de racine 1110. La racine 1110 est la fonction GO, à laquelle sont reliés trois noeuds internes 1120, 1130, et 1140. Le noeud 1120 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1150, 1152 et 1154 (représentant, respectivement, les villes 1, 2 et 3). Le noeud 1130 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1156 et 1158 (représentant, respectivement, les villes 4. et 5). Le noeud 1140 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1160, 1162, 1164 et 1166 (représentant, respectivement, les villes 6, 7, 8 et 9). Le sousitinéraire 1120 de trois villes commencent à la ville 1, passe ensuite par la ville 2 et s'achève à la ville 3. Ensuite, un sous-itinéraire 1130 de deux villes commence à la ville 4 et s'achève à la ville 5. Enfin, le sous-itinéraire 1140 de quatre villes commence à la ville 6, passe ensuite par la ville 7, puis par la ville 8, et s'achève à la ville 9. Les fonctions G et GO sont des fonctions LISP qui 263 1720 retournent un résultat à partir de deux arguments. La fonction G est la fonction correspondant à l'accomplissement d'un sous-itinéraire. L'exécution de cette fonction retourne trois valeurs, à savoir la distance parcourue correspondant à ce sous-itinéraire, la première ville et la dernière ville. La fonction GO est utilisée comme fonction la plus extérieure. Elle ne retourne qu'une seule valeur, à savoir la distance parcourue pour la totalité de l'itinéraire. La fonction GO (à la différence de la fonction G) prend en compte la distance parcourue de la dernière ville jusqu'au point de départ auquel on revient enfin. La fonction GO se trouve en 1110 à la racine de l'arborescence de la figure 12. Si l'un quelconque des sous-itinéraires était lui-même formé de sousitinéraires, on utiliserait la fonction G pour des sous-sous-itinéraires. La figure 13 illustre des sous-sous-itinéraires. La s-expression 1200, à savoir (GO (G 1 2 3) (G 4 5) (G (G 6 7) (G 8 9))), est représentée par une arborescence de racine 1210. La racine 1210 est la fonction GO, à laquelle sont reliés des arguments aux noeuds internes 1220, 1230 et 1240. Le noeud 1220 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1222, 1224 et 1226 (représentant les villes 1, 2 et 3, respectivement). Le noeud 1230 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1232 et 1234 (représentant les villes 4 et 5, respectivement). Le noeud 1240 est la fonction G, à laquelle sont reliés des arguments aux noeuds internes 1250 et 1260. Le noeud 1250 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1252 et 1254 (représentant les villes 6 et 7, respectivement). Le noeud 1260 est la fonction G, à laquelle sont reliés des arguments aux feuilles 1262 et 1264 (représentant les villes 8 et 9, respectivement). Sur la figure 13, la référence 1250 correspond à un sous-sous-itinéraire concernant les villes 6 et 7 et la référence 1260 correspond à un soussous-itinéraire - concernant les villes 8 et 9. La distance parcourue pour la totalité de l'itinéraire 1200 de la figure 13 èst identique 74 -2631720 à la distance parcourue pour la totalité de l'itinéraire 1100 de la figure 12. La différence est que les sous-sous-itinéraires décrivent une sous-sous-structure différente à l'intérieur de l'itinéraire complet pris dans son ensemble. Q Les configurations et procédés particuliers décrits ici ne servent qu'à illustrer une application des principes de la présente invention. Le spécialiste de cette technique saura apporter de nombreuses modifications de forme et de détail sans sortir du cadre de la présente invention. 2631720 REVENDICATIONS 1. Un processus de résolution de problèmes, dans lequel on utilise une population d'entités o chaque entité présente une aptitude active à résoudre des problèmes et peut changer de dimension et de forme, ce processus comprenant des itérations d'une suite d'étapes telles que ladite population tende à offrir des solutions améliorées, processus caractérisé en ce que chaque itération comporte les étapes suivantes: - activation (1306) de chaque entité de manière à obtenir un résultat, - affectation (1312) d'une valeur à chacun de ces résultats et association (1312) de chacune de ces valeurs à l'entité correspondante qui a produit le résultat, - sélection (1316) d'au moins une entité dans la population, cette sélection-étant essentiellement basée, dans la majorité des cas, sur la valeur associée à chacune des entités, préférence étant donnée à celles des entités qui ont une valeur associée relativement forte plutôt qu'à celles des entités qui ont une valeur associée relativement faible, choix (1318) et exécution (1320; 1330; 1340) d'une opération, l'opération ainsi choisie étant une opération de croisement, de reproduction ou de permutation, - si l'opération choisie est un croisement (1320), création d'au moins une nouvelle entité par croisement à partir d'un groupe d'entités, ce groupe comprenant les entités sélectionnées à l'étape de sélection et au moins une autre entité sélectionnée dans ladite population, de sorte que toute nouvelle entité créée par croisement comprenne au moins une partie des entités sélectionnées à l'étape de sélection et au moins une partie desdites autres entités, - si l'opération choisie est une reproduction (1330), conservation des entités sélectionnées à l'étape de sélection, de sorte que ces entités restent inchangées, - si l'opération choisie est une permutation (1340), permutation des entités sélectionnées à l'étape de 7 6 sélection, de manière à réordonnancer des parties de chacune des entités sélectionnées avec possibilité de reconfor- mation, afin de créer une nouvelle entité à partir de chacune des entités sélectionnées, et - addition (1360) desdites nouvelles entités à la population. 2. Le processus de la revendication 1, dans lequel, en outre, l'étape de sélection (1316) comprend une sélection d'entités essentiellement basée sur une probabilité qui, dans la majorité des cas, est proportionnée aux valeurs associées à chacune de ces entités. 3. Le processus de la revendication 1, comportant en outre une opération de mutation telle que, si l'opération choisie est une mutation, une étape de-mutation (1350) prend place avant l'étape d'addition, les entités sélectionnées à l'étape de sélection étant mutées de telle sorte qu'au moins une partie de chacune des entités sélectionnées soit remplacée par une partie engendrée de manière aléatoire, de manière à produire une nouvelle entité comprenant des parties de l'entité sélectionnée et des parties formées d'éléments engendrés de manière aléatoire. 4. Le processus de la revendication 1, comprenant en outre une étape d'élimination (1314> permettant d'éliminer au moins une entité, les entités éliminées possédant des valeurs associées relativement faibles. 5. Le processus de la revendication 1, comprenant en outre une étape consistant à tenir un historique de l'évolution, de manière à garder trace de l'information héréditaire de ladite population. 6. Un processus pour un système informatique contenant une population de programmes de longueur variable, ce processus étant un processus itératif permettant de modifier cette population par création de nouveaux programmes de manière que le degré d'adaptation de la population ait tendance à croître, - processus caractérisé en ce que chacune de ses itérations comprend les étapes suivantes: - exécution (1306) de chaque nouveau programme de manière à donner un résultat, - affectation (1312) d'une valeur à chacun de ces résultats et association (1312) de chacune de ces valeurs au programme correspondant qui a produit le résultat, - sélection (1316) d'au moins un programme dans la population, cette sélection étant essentiellement basée, dans la majorité des cas, sur la valeur associée à chacun des programmes, préférence étant donnée à ceux des programmes qui ont une valeur associée-relativement forte plutôt. qu'à ceux des programmes qui ont une valeur associée relativement faible, - choix (1318) et exécution (1320; 1330; 1340) d'une opération, l'opération ainsi choisie étant une opération de croisement, de reproduction ou de permutation, - - si l'opération choisie est un croisement (1320), création d'au moins un nouveau programme par croisement à partir d'un groupe de programmes, ce groupe comprenant le(s) programme(s) sélectionné(s) à l'étape de sélection, et au moins un autre programme sélectionné dans ladite population, de sorte que tout nouveau programme créé par croisement comprenne au moins une partie du (des) programme(s) sélectionné(s) à l'étape de sélection et au moins une partie dudit (desdits) autre(s) programme(s), - si l'opération choisie est une reproduction (1330), conservation de celui (ceux) des programmes qui avai(en)t été sélectionné(s) à l'étape de sélection, de sorte que ce(s) programme(s) reste(nt) inchangé(s), - si l'opération choisie est une.permutation (1340) , permutation des programmes sélectionnés à l'étape de sélection, de manière à réordonnancer des parties de chacun des programmes sélectionnés, afin de créer un nouveau programme à partir de chacun des programmes sélectionnés, et - addition (1360) dudit (desdits) nouveau(x) programme(s) à la population. 7. Le processus de la revendication 6, dans lequel, en outre, l'étape de sélection (1316) comprend une sélection de programmes essentiellement basée sur une probabilité qui, dans la majorité des cas, est proportionnée aux valeurs associées à chacun de ces programmes. 8. Le processus de la revendication 6, comprenant en outre,une étape de mutation (1350) prenant place avant l'étape d'addition, le(s) programme(s) sélectionné(s) étant muté(s) de telle sorte que, dans le (chacun des) programme(s) sélectionné(s), au moins une partie de chaque programme sélectionné soit remplacée par une partie engendrée de manière aléatoire, de manière à produire un nouveau programme comprenant des parties du programme sélectionné et des parties formées de programmes engendrés de manière aléatoire. 9. Le processus de la revendication 6, comprenant en outre une étape d'élimination (1314) permettant d'éliminer au moins un programme, les programmes éliminés possédant des valeurs associées relativement faibles. 10. Le processus de la revendication 6, dans lequel l'opération de croisement (1320) comprend en outre l'élimination dudit groupe de la population. 11. Le processus de la revendication 6, dans lequel, en outre, l'opération de croisement (1320) consiste à prendre des sous-procédures dans au moins un programme sélectionné à l'étape de sélection et au moins un autre programme sélectionné afin de créer le(s)dit(s) nouveau(x) programme(s), de telle sorte que ce nouveau programme soit uniquement crée à partir de sous-procédures de programmes dudit groupe et puisse varier de dimension et de forme par rapport à l'un ou l'autre des programmes parents. 79 2631720 12. Le processus de la revendication 6, dans lequel, en outre, l'opération de permutation (1340) consiste à effectuer sur un programme une permutation produisant un réordonnancement des sous-procédures de ce programme. 13. Le processus de la revendication 6, dans lequel, en outre, l'opération de permutation (1340) consiste à effectuer sur un programme une permutation produisant un réordonnancement des arguments des sousprocédures de ce programme. 14. Le processus de la revendication 6, dans lequel, en outre, l'opération de permutation (1340) consiste à effectuer sur un programme une permutation produisant un réordonnancement aussi bien des arguments des sous-procédures de ce programme que des sous-procédures de ce programme. 15. Le processus de la revendication 11, dans lequel, en outre, l'opération de permutation (1340) consiste à effectuer sur un programme une permutation produisant un redistribution de tous les arguments des sous-procédures du programme entre toutes les sous-procédures, et un réordonnancement des sous-procédures de ce programme. 16. Le processus de la revendication 6, comprenant en outre une étape consistant à tenir un historique de l'évolution, de manière à garder trace de l'information héréditaire de ladite population. 17. Un ensemble de processus parallèles permettant, dans un système informatique à traitement parallèle comprenant une population de programmes de longueur variable o chaque programme s'exécute périodiquement en donnant un résultat et o l'on associe la valeur de ce résultat au programme qui lui correspond, de modifier ladite population par création de nouveaux programmes de telle sorte que le degré d'adaptation de cette population ait tendance à croître, 2631720 caractérisé en ce que chaque processus parallèle de l'ensemble comprend les étapes suivantes: - sélection (1316) d'au moins un programme dans la population, cette sélection étant essentiellement basée, dans la majorité des cas, sur la valeur associée à chacun des programmes, préférence étant donnée à ceux des programmes qui ont une valeur associée relativement forte plutôt qu'à ceux des programmes qui ont une valeur associée relativement faible, - exécution de l'une des opérations suivante: croisement (1320), au moins un nouveau programme étant créé par croisement à partir d'un groupe de programmes, ce groupe comprenant le(s) programme(s) sélectionné(s) à l'étape de sélection, et au moins un autre programme sélectionné dans ladite population, de sorte que tout nouveau programme créé par croisement comprenne au moins une partie du (des) programme(s) sélectionné(s) à l'étape de sélection et au moins une partie dudit (desdits) autre(s) programme(s), * reproduction (1330), le programme sélectionné à l'étape de sélection étant conservé dans la population de sorte que ce programme reste inchangé, * permutation (1340), des parties de chacun des programmes sélectionnés à l'étape de sélection étants réordonnancées de manière à créer au moins un nouveau programme à partir de chacun des programmes sélectionnés, et - addition (1360) desdits nouveaux programmes à la population. 18. L'ensemble de processus de la revendication 17, comprenant en outre une étape de mutation (1350) prenant place avant l'étape d'addition, le(s) programme(s) sélectionné(s) étant muté(s) de telle sorte que, dans le (chacun des) programme(s) sélectionné(s), au moins une partie de chaque programme sélectionné soit remplacée par une partie engendrée de manière aléatoire, de manière à 81 2631720 produire un nouveau programme comprenant des parties du programme sélectionné et des parties formées de programmes engendrés-de manière aléatoire. 19. L'ensemble de processus de la revendication 17, dans lequel chacun des processus parallèles exécute l'une desdites opérations, tous lesdits processus parallèles opérant ainsi sur ladite population. 20. L'ensemble de processus de la revendication 17, dans lequel chacun des processus parallèles opère sur une sous-population, distincte, de ladite population, ces sous-populations (Pl, P2) étant mêlées -entre elles périodiquement. 21. L'ensemble de processus de la revendication 17, dans lequel chacun des processus parallèles exécute l'une desdites opérations et opère sur une sous-population, distincte, de ladite population, ces sous-populations (PI, P2) étant mêlées entre elles périodiquement. 22. Le processus de la revendication 17, comprenant en outre une étape consistant à tenir un historique de l'évolution, de manière à garder trace de l'information héréditaire de ladite population. 23. Un ordinateur, comprenant une population d'entités de longueur variable o chacune de ces entités peut changer de dimension et de forme, pour la mise en oeuvre d'un processus itératif permettant de modifier cette population par création de nouvelles entités de telle sorte que le degré d'adaptation de cette population tende à s'améliorer à l'approche d'une solution d'un problème, ordinateur caractérisé en ce qu'il comprend, en combinaison: - des moyens pour créer une population initiale (Pi, P2) d'entités de longueur variable, - une mémoire (1410, 1420) pour conserver cette 82 2631720 population initiale d'entités de longueur variable, - un processeur (1411, 1412, 1421, 1422), relié à cette mémoire, pour aller rechercher lesdites entités conservées et exécuter des instructions déterminées par ces instructions recherchées, ce processeur affectant des valeurs aux résultats de l'exécution des instructions de ces entités recherchées et sélectionnant au moins un entité présentant une valeur relativement élevée, cette valeur étant associée à un degré d'adaptation voulu en direction de ladite solution, ce processeur exécutant ensuite au moins une opération de croisement, de reproduction, ou de permutation sur chacune des entités sélectionnées, de telle sorte que: (a) si l'opération choisie est un croisement (1320), il crée au moins une nouvelle entité par croisement à partir d'un groupe d'entités, ce groupe comprenant au moins l'une des entités sélectionnées présentant une valeur relativement élevée et au moins une autre entité ne faisant pas partie de ces entités sélectionnées présentant une valeur relativement élevée, de sorte que toute nouvelle entité créée par croisement comprenne au moins une partie des entités sélectionnées présentant une valeur relativement élevée, (b) si l'opération choisie est une reproduction (1330), il conserve chacune des entités sélectionnées, de sorte que ces entités restent inchangées, (c) si l'opération choisie est une permutation (1340), il permute chacune des entités sélectionnées à l'étape de sélection, de manière à réordonner des parties de chacune des entités sélectionnées avec possibilité de reconformation, afin de créer une nouvelle entité à partir de chacune des entités sélectionnées, cette opération créant de nouvelles entités qui sont ensuite, pour exécution ultérieure par le processeur, ajoutées à la population d'entités conservée dans ladite mémoire. 24. L'ordinateur de la revendication 23, dans lequel le processeur effectue essentiellement la sélection des entités sur la base de probabilités proportionnelles auxdites valeurs associées à ces entités. 25. L'ordinateur de la revendication 24, dans lequel le processeur exécute une opération supplémentaire de mutation (1350) telle que, si ladite opération choisie est une mutation, au moins une partie de chacune des entités sélectionnées soit remplacée par le résultat d'une génération aléatoire, de manière à produire une nouvelle entité. 26. L'ordinateur de la revendication 25, dans lequel, lors de la sélection de ladite entité de valeur élevée, le processeur élimine les entités de valeurs relativement faibles. 27. L'ordinateur de la revendication 26, dans lequel la mémoire conserve la situation de toutes les entités sélectionnées et éliminées. 28. L'ordinateur de la revendication 27, dans lequel, en outre, une pluralité de processeurs (1411, 1412, 1421, 1422) exécutent un traitement parallèle sur ladite population d'entités (P1, P2)