Algorithmes Evolutionnaires et Algorithmes Génétiques

En vérité, aux tout premiers temps, naquit Chaos. Hésiode
To create a little flower is the labour of ages. William Blake

Les Algorithmes Evolutionnaires (AE) sont inspirés du concept de sélection naturelle élaboré par Charles Darwin. Le vocabulaire employé est directement calqué sur celui de la théorie de l’évolution et de la génétique. Nous parlerons donc d’individus (solutions potentielles), de population , de gènes (variables), de chromosomes , de parents , de descendants, de reproduction, de croisement , de mutations , etc. Et nous nous appuierons constamment sur des analogies avec les phénomènes biologiques.

La sélection naturelle

S’il n’existe pas de preuve générale de l’efficacité des AE, il est par contre aisé de constater l’efficacité de la sélection naturelle dans le monde vivant. Si l’on adhère à ce paradigme, il est clair que l’évolution a permis l’émergence d’organismes étonnamment adaptés à leur environnement. Les AE sont conçus par analogie avec ce processus d’évolution biologique et tirent leur puissance des mêmes mécanismes, que nous allons rappeler sommairement.

The Origin of Species by means of Natural Selection or the Preservation of favoured races in the struggle for life
 Chapter 1 : Variation under domestication
 Chapter 2 : Variation under Nature
 Chapter 3 : Struggle for existence
 Chapter 4 : Natural Selection
 Chapter 5 : Laws of variation
 ...

Figure 1 : titre complet et premiers chapitres de The Origin of Species (1859), dans la langue de l’auteur.

Dans The Origin of Species(1859), Darwin montre que l’apparition d’espèces distinctes se fait par le biais de la sélection naturelle de variations individuelles (voir figure 2). Cette sélection naturelle est fondée sur la lutte pour la vie, due à une population tendant naturellement à s’étendre mais disposant d’un espace et de ressources finis. Il en résulte que les individus les plus adaptés ( the fittest en anglais) tendent à survivre plus longtemps et à se reproduire plus aisément. Le terme " adapté " se réfère à l’environnement, que l’on peut définir comme étant l’ensemble des conditions externes à un individu, ce qui inclut les autres individus. Les lois de variation (croisements et mutations) furent expliquées plus tard par Mendel, puis par la génétique moderne.

Le point clef est l’apparition, par hasard, de variations individuelles. C’est ce hasard qui permet d’expliquer les phénomènes d’évolution et d’adaptation sans avoir recourt ni à une création, ni à une modification directe de l’hérédité par le milieu, ni même à une finalité. Dans ce cadre, les espèces évoluent et s’adaptent à leur environnement mais sans tendre vers aucun but prédéterminé, et même sans forcément tendre vers plus de complexité (la simplicité est parfois préférable).

Notons que les mêmes principes sont à l’origine de l’efficacité du système immunitaire : celui-ci produit d’énormes quantités d’anticorps aléatoires. Ceux qui se révèlent par hasard efficaces sont alors, par un mécanisme de rétroaction, produits en plus grande quantité [Monod 1970 et Wills, 1991]. Enfin, les principes de l’évolution sont maintenant utilisés par les biologistes pour produire de nouvelles enzymes : de très nombreuses séquences d’ADN synthétisées aléatoirement sont soumises à une sélection et des mutations (évolution en éprouvette) jusqu’à obtention des propriétés désirées.

Dernière remarque : si la compétition a certaines vertus, et même des vertus certaines, chacun sait bien que "l’union fait la force", la Nature la première. Pour preuve, je citerai certaines étapes de l’évolution telles que l’intégration des mitochondries aux cellules, le passage des organismes monocellulaires aux organismes pluricellulaires, les phénomènes de symbiose et bien sûr la vie en société. De tels phénomènes coopératifs peuvent donc être sélectionnés et ouvrir de nouvelles voies à la vie. L’algorithme très simple que nous présentons ne prend pas en compte ces mécanismes, mais rien n’interdit de le faire (bon courage) !

Algorithmes Evolutionnaires et Algorithmes Génétiques

Généralités

Figure 2

Organigramme d’un Algorithme Evolutionnaire.

La Figure 2 présente l’organigramme d’un AE. Il s’agit de simuler l’évolution d’une population d’individus divers (généralement tirée aléatoirement au départ) à laquelle on applique différents opérateurs (recombinaisons, mutations…) et que l’on soumet à une sélection, à chaque génération. Si la sélection s’opère à partir de la fonction d’adaptation, alors la population tend à s’améliorer [Bäck, 1996 et Bäck, 1997]. Un tel algorithme ne nécessite aucune connaissance du problème : on peut représenter celui-ci par une boîte noire comportant des entrées (les variables) et des sorties (les fonctions objectif). L’algorithme ne fait que manipuler les entrées, lire les sorties, manipuler à nouveau les entrées de façon à améliorer les sorties, etc. [Whitley, 1993] C’est ainsi qu’ont procéder les éleveurs pendant des millénaires : ils ont réussi à modifier selon leurs désirs de nombreuses espéces animales sans connaissance en génétique ou biologie moléculaire.

Figure 6

On peut symboliser un problème d’optimisation par une boîte noire . Les sorties (en haut) peuvent être optimisées en manipulant les entrées (en bas) jusqu’à obtenir le résultat voulu, sans aucune connaissance de l’intérieur de la boîte. Les AE sont une automatisation de cette méthode d’essai et erreur.

Les AE constituent une approche originale : il ne s’agit pas de trouver une solution analytique exacte, ou une bonne approximation numérique, mais de trouver des solutions satisfaisant au mieux différents critères, souvent contradictoires. S’ils ne permettent pas de trouver à coup sûr la solution optimale de l’espace de recherche, du moins peut-on constater que les solutions fournies sont généralement meilleures que celles obtenues par des méthodes plus classiques, pour un même temps de calcul.

Historique

Les AE font partie du champ de l’Intelligence Artificielle (IA). Il s’agit d’IA de bas niveau, inspirée par " l’intelligence " de la Nature. Intelligence que l’on peut définir de la façon suivante : " the capability of a system to adapt its behaviour to meet its goals in a range of environments " [Fogel, 1995].

Trois types d’AE ont été développés isolément et à peu près simultanément, dans les années 60, par différents scientifiques : les Algorithmes Génétiques , les Stratégies d’Evolution , et la Programmation Evolutionnaire . Présentant des différences marquées à l’origine, ils tendent de plus en plus à se confondre suite à leurs emprunts respectifs [Bäck, 1997]. Dans les années 90, ces trois champs ont commencé à sortir de leur isolement et ont été regroupés sous le terme anglo-saxon d’ Evolutionnary Computation . Ainsi en avril 1997, un IEEE Transactions on Evolutionary Computation a vu le jour [Fogel, 1997].

Notons que les AE incluent également la Programmation Génétique qui consiste à faire évoluer le code d’un logiciel afin qu’il remplisse au mieux certaines taches. Citons enfin le domaine de la Vie Artificielle où l’on tente de reproduire les mécanismes de la vie dans la mémoire d’un ordinateur afin de mieux comprendre l’organisation et l’évolution du vivant.

Parmi les AE que nous venons de citer, nous avons choisi de traiter des Algorithmes Génétiques (AG). En effet, ils nous paraissaient concilier au mieux puissance, généralité et facilité de programmation. Leur particularité est qu’ils sont fondés sur le Néo-Darwinisme, c’est-à-dire l’union de la théorie de l’évolution et de la génétique moderne. Ainsi, les variables sont généralement codées en binaire (par analogie avec les quatre lettres de l’alphabet génétique) sous forme de gènes dans un chromosome. Des opérateurs génétiques (croisement, mutation) sont appliqués à ces chaînes binaires que sont les chromosomes [Bäck, 1996 et Goldberg, 1994].

Applications

Les applications des AG sont multiples : optimisation de fonctions numériques difficiles (discontinues, multimodales, bruitées…), traitement d’image (alignement de photos satellites, reconnaissance de suspects…), optimisation d’emplois du temps, optimisation de design, contrôle de systèmes industriels [Beasley, 1993a], apprentissage des réseaux de neurones [Renders, 1995], etc. Les AG peuvent être utilisés pour contrôler un système évoluant dans le temps (chaîne de production, centrale nucléaire…) car la population peut s’adapter à des conditions changeantes. En particulier, ils supportent bien l’existence de bruit dans la fonction à optimiser. Ils peuvent aussi servir à déterminer la configuration d’énergie minimale d’une molécule ou à modéliser le comportement animal.

Les AG sont également utilisés pour optimiser des réseaux (câbles, fibres optiques, mais aussi eau, gaz…), des circuits VLSI [Beasley, 1993a], des antennes [Reineix, 1997]… Ils peuvent être utilisés pour trouver les paramètres d’un modèle petit-signal à partir des mesures expérimentales [Menozzi, 1997]. Des commutateurs optiques adiabatiques ont été optimisés à l’aide des Stratégies d’Evolutions (autres AE) chez SIEMENS AG [Moosburger, 1997]. On envisage l’intégration d’AG dans certaines puces électroniques afin qu’elles soient capables de se reconfigurer automatiquement en fonction de leur environnement (Evolving Hardware en anglais ) .

Dans le chapitre suivant, nous présenterons les techniques de base que nous avons testées.

Chapitre suivant