INFORMATIQUE GENERALE

2ème séance : Introduction aux algorithmes génétiques.

Introduction à la calculabilité

Beaucoup de problèmes sont difficilement solubles exactement. La difficulté ne vient pas de la complexité du problème mais de la taille excessive de l'espace des solutions. Par exemple, le problème du voyageur de commerce a une taille de l'espace de solutions qui varie en factorielle (n-1) où n est le nombre de villes où il faut passer. On s'apercoit qu'à seulement 100 villes, il y a 9,3.10¹⁵³ solutions. Il est alors impensable de pouvoir les tester toutes pour trouver la meilleure.

C'est pourquoi, des heuristiques approchées ont été essayées pour la résolution de tout un tas de problèmes où la recherche systématique n'est pas possible. Ces heuristiques doivent être peu coûteuses en temps machine et doivent permettre de trouver une solution pas trop mauvaise qui justifie leur utilisation à la place d'une recherche par Monte-Carlo (hasard quadrillé) ou par toute autre méthode.

Ainsi sont nés beaucoup d'algorithmes comme le recuit simulé, la méthode tabou, les approches min-max, alpha-beta ou encore les algorithmes génétiques. Nous nous interesserons essentiellement à ces derniers.

Introduction aux algorithmes génétiques

Les heuristiques de calcul sont souvent issus d'un processus ou phénomène physique / naturel duquel ils s'inspirent. Les algorithmes génétiques ne dérogent pas à cette règle et sont directement inspirés du mécanisme d'évolution d'une espèce, la génétique.

Un peu de génétique

L'évolution dans la nature survient quand des entités ont la capacité de se reproduire, qu'il existe une population de ces entités, qu'il existe une variété (diversité) à travers ces entités, et que la survie des entités dépend des différences entre elles. Toute entité vivante possède un génotype et le phénotype.

Le génotype. Le génotype est constitué de gènes situés sur des chromosomes stockés dans le noyau des cellules sous la forme d'une longue chaine d'acide déoxyribonucléique (ADN). Dans la nature, l'ADN est un polymère constitué par l'enchaînement de quatres molécules, les nucléotides adénime (A), cytosime (C), guanine (G) et la thymine (T). On peut donc décrire l'ADN par des chaînes de quatre caractères ACGT. L'ADN constitue l'ensemble des chromosomes, ou le génome d'un individu.

Le phénotype. Le phénotype est l'ensemble des protéines et des enzymes qui peuvent être fabriqués à partir de l'ADN. En fait, l'ADN est copiée par un messager (ARN) qui au niveau du ribosome, se traduit en chaînes d'acides aminés formant les protéines et les enzymes. En général, on compte une protéine (un enzyme) par gène. Ce sont les protéines et les enzymes qui dictent la structure et le comportement des cellules qui permettent à un individu de réaliser des tâches dans son environnement, de survivre et de reproduire à des taux différents.

La reproduction se traduit par la transmission du génome aux individus de la progéniture ce qui permet de préserver les gènes menant à des performances supérieures. Occasionnellement, un processus naturel, la mutation génétique, introduit une variation dans les chromosomes.

Or les individus les mieux adaptés, c'est-à-dire capables de mieux effectuer les tâches nécessaires à leur survie, se reproduisent à des taux les plus élevés, alors que les individus les moins adaptés se reproduisent à des taux plus faibles. Ce sont les principes de survie et reproduction décrit par Charles Darwin dans « On the Origin of Species By Means of Natural Selection » en 1859. Il s'avère alors qu'une population ayant une grande variété va, de génération en génération, contenir des individus dont le génotype se traduit par une meilleure adaptation, et ceci à cause de la contrainte de la sélection naturelle.

Photographie au microscope électronique d'ADN en réplication

Les algorithmes génétiques

L'algorithme génétique ne fait que transposer ce que fait la nature à des systèmes artificiels. Il simule les processus évolutifs Darwiniens et génétiques s'appliquant aux chromosomes. Il transforme un ensemble d'objets mathématiques, une population d'individus souvent représentés par des chaînes de caractères pour imiter les chaînes d'ADN, chacun ayant une valeur d'adaptation, en une nouvelle population. L'algorithme fait donc appel à quatres opérateurs de base :

1. l'évaluation du niveau d'adaptation d'un individu.
2. la sélection : c'est le choix des individus en fonction du niveau d'adaptation.
3. le croissement : c'est le mélange des bagages génétiques.
4. la mutation : le bagage génétique est modifié abruptement.

Exemple :

Nous disposons d'une fonction à n variables (n pouvant être très grand) pour laquelle il nous faut trouver le minimum. De nombreux problèmes peuvent se rapporter à ce schéma.

But :

Min ( F(n₁, n₂, n₃, ... n_p) )
n_i

La première étape consiste à trouver une représentation d'un individu. En effet, le p-uplet de réels qui représente un point dans l'espace des p variables, est un représentant du phénotype, les paramètres décodées. Il nous faut trouver une fonction qui code à la manière de l'ADN notre problème. Le choix le plus direct est la représentation des réels sous forme de chaînes de bits (un bit est l'unité d'information binaire, 0 ou 1). Un génome est une chaîne de bits (sa longueur est le nombre de bits d'un réel multiplié par p) qui représente les bits des réels mis bout à bout.

Ainsi nous disposons d'une fonction decode qui à partir d'une chaine de bits donne un p-uplet (il est à noter que la fonction code est inutile dans un algorithme génétique).

La deuxième étape consiste à pouvoir calculer pour un individu sa valeur d'adaptation. Supposons que notre fonction a des valeurs comprises entre 0 et 1 (on peut la plupart du temps s'y ramener en faisant un changement d'échelle). La fonction d'adaptation devra être maximum vers 0 et minimum en 1. Voici un choix :

Valeur d'adaptation (individu) = 1 - F( individu )

D'autres solutions sont possibles qui permettent de favoriser plus les faibles valeurs ( (1-F)^1/2 ) ou bien de laisser plus de choix pour la diversité comme (1-F)². Il faut trouver un juste équilibre entre la sélection et la diversité.

Ainsi nous disposons d'une fonction valuation qui donne pour chaque individu un nombre réel.

Ces deux étapes étant faites, nous pouvons maintenant décrire l'algorithme génétique :

Remarques :

Nous n'avons pas donné de critère d'arrêt dans l'algorithme. Ce critère peut prendre plusieurs formes :

• on peut ne générer qu'une population de taille fixe.
  
• on peut suivre le meilleur élement de la population et décider que s'il ne s'est pas amélioré les x dernières générations, on s'arrête.
  
• on peut suivre la différence de valuation entre les deux meilleurs individus et si elle est inférieure à une certaine tolérance, on s'arrête.

Le coeur de l'agorithme se situe dans la fonction de choix au hasard mais pondéré d'un individu. Cette fonction prend comme entrée un vecteur de valeurs d'adapation et renvoi un entier. L'illustration du choix pondéré est donné par la roue de la fortune, chaque case représentant un individu et la taille de la case est donné par la valeur d'adaptation. Voici un exemple de codage :

entier HasardPondere(tableau de reel : valu) { // La probabilite de tirage d'un individu est // valuation(individu) / Somme de toutes les valuations Somme = Somme de toutes valeurs d'adaptation // calcule la somme des valuations r = réel tiré au hasard entre 0 et 1. // on tire une valeur au hasard a = 1 sommepartielle = valu[a] tant que ( r > sommepartielle ) a = a+1 sommepartielle = sommepartielle + valu[a] fin tant que retourne a }

Introduction aux algorithmes génétiques.

Présentation adaptée du livre "La vie artificielle",
Jean-Claude HEUDIN, Hermes 1994

Principes fondamentaux.

Un algorithme génétique permet de simuler des mécanismes du vivant. Les principes ci dessous caractérisent cette approche :

• Le système est composé d'une population d'individus simples indépendants les uns des autres.
  
• Chaque individu définit ses réponses à son environnement local et ses interactions avec les autres.
  
• Il n'existe pas de chef qui donne des ordres aus autres individus.
  
• Il n'existe pas de règle dictant un comportement global.
  
• Tout comportement ou propriété d'un niveau supérieur émerge uniquement des interactions entre individus.

La simulation débute par la création d'une

Nous avons déja utilisé des principes voisins dans l'exemple de l'automate cellulaire. Un algorithme génétique se distingue de cet exemple par la prise en compte pour chaque individu :

1. d'un génotype, ensemble des informations génétiques codées dans le génome, sous forme d'un enesemble de règles locales simples,
   
2. d'un phénotype, l'organisme qui émerge du développement guidé par le génotype dans le milieu environnant.

Les algorithmes génétiques sont fondés sur l'utilisation d'un code individuel universel à l'instar de l'ADN, le génome, et sur l'étude de l'évolution d'une population d'individus, comme dans l'étude du vivant. Peut-on pour autant parler de l'émergence d'une vie artificielle ?

 

Conception d'un algorithme génétique.

L'utilisation d'un algorithme génétique nécessite le choix préalable d'un code génétique représentant le problème à traiter. Le choix de ce codage est essentiel car il va déterminer essentiellement les performances de l'algorithme. Le code est représenté sous forme d'une chaîne de bits ou de caractères, chaine analogue à un chromosome. Il y a une nombre fini de chaînes.

Sur ces codes s'appliquent des opérateurs génétiques, dont les principaux sont :

• opérateur de reproduction, qui duplique le code d'un individu pour en créer un nouveau,
  
• opérateur de croisement, qui mélange les chromosomes des individus parents pour créer le code génétique d'un individu fils,
  
• opérateur de mutation, qui apporte une modification aléatoire au code génétique d'un individu,
  
• opérateur de sélection, qui choisit dans une population les individus qui survivront à la génération suivante, en fonction d'une valeur d'adaptation
  
• opérateur d'évaluation, qui mesure le degré d'adaptation d'un individu à son environnement.

Le cycle de vie se résume alors à ceci :

1. sélectionner les individus les mieux adaptés, seuls jugés aptes à survivre :
   
   1. évaluer le degré d'adaptation de chaque individu à son environnement,
      
   2. sélectionner des paires de génotypes en fonction de la valeur de l'adaptation de leur phénotype à l'environnement,
      
2. appliquer des opérateurs de diversification de la population car il est prouvé qu'une population qui vivrait en cercle fermé et serait xénophobe et raciste dégénèrerait et disparaitrait :
   
   1. l'opérateur de croisement ou
      
   2. l'opérateur de mutation,
      
3. développer les génotypes pour obtenir les phénotypes de la nouvelle génération, puis recommencer le cycle.

Cycle de vie
de l'évolution des espèces
régies par les algorithmes génétiques.

Opérateurs génétiques

Reproduction : copier à l'identique un génome. Ce mécanisme est déclanché pour chaque chromosome sélectionné selon la valeur de la fonction d'adaptation.

Evaluation de la fonction d'adaptation : intuitivement, c'est une sorte de mesure de l'efficacité de la solution considérée. C'est cette fonction que l'algorithme génétique cherche à maximaliser.

Croisement : à partir de deux chromosomes le croisement produit deux nouveaux chromosomes incorporant chacun du matériel génétique pris dans le patrimoine initial. Pour développer un opérateur de croisement, trois étapes sont nécessaires :

1. choix de deux chromosomes survivants, c'est à dire sélectionnés par la procédure de reproduction,
   
2. choix au hasard d'un emplacement où couper ces deux chromosomes,
   
3. recoller les portions de chromosomes en les croisant. Les deux chromosomes de départ ont ainsi échangé des segments de code génétique.

Le croisement ne doit pas être appliquée systématiquement, mais en fonction d'une probabilité, paramètre de la simulation. Une probabilités de l'ordre de 0,6 est souvent choisie.

Mutation : opérateur d'importance secondaire, mais qui permet d'éviter une convergence prématurée vers un maximum local, en maintenant une diversité de solution. Pour l'appliquer, choisir au hasard un bit du chromosome et modifier sa valeur. La mutation ne doit pas être appliquée systématiquement, mais en fonction d'une probabilité, paramètre de la simulation. Les probabilités de l'ordre de 0,01 à 0,03 sont généralement choisies.

 

Exercice du TD

Parcours d'un labyrinthe

Cet exercice est tiré de l'ouvrage : L'ordinateur génétique (Jean-Louis DESSALLES, Hermes mai 1996)

Pour aider Thésée à vaincre le Minotaure dans le Labyrinthe de Dédale, Ariane lui donna un fil. La programmation d'un parcours de labyrinthe emprunte classiquement son algorithme au mythe d'Ariane. Un mobile parcourt le labyrinthe en appliquant les principes suivants :

• "marquer" le chemin d'où l'on vient,
  
• essayer à chaque carrefour l'embranchement le plus à gauche,
  
• "marquer" les embranchements sans issue déjà empruntés.
  

La résolution par un algorithme génétique se base sur une idée différente, celle de la sélection naturelle entre individus. Chaque individu est un chemin dans le labyrinthe, tentative de solution, partant de l'entrée.

Un individu dont le génome est aléatoire a très peu de chances de guider vers une sortie. Ces individus évoluent au rythme des générations. A chaque génération peuvent se produire des mutations, modifiant le patrimoine génétique. En sélectionnant à chaque génération dans la population des individus - chemins ceux qui sont les "meilleurs", c'est à dire qui s'approchent plus de la sortie que les autres, nous pouvons espérer obtenir à terme des individus menant à une solution.

Avant de programmer l'algorithme génétique, il est nécessaire de définir le codage employé, c'est à dire de préciser le lien entre la chaine de bits constituant le génome et un chemin dans le labyrinthe. Voici trois façons d'envisager ce codage d'un chemin :

1. Représenter pour chaque case du labyrinthe la direction à prendre. Il y a à chaque fois quatre directions possibles, que l'on peut donc coder sur deux bits : 00 = est, 01 = nord, 10 = ouest, 11 = sud. Un labyrinthe 10x10 fait 100 cases, le génome d'un individu comportera 200 bits. Par exemple le génome 01101011110001... représente le chemin partant de l'entrée nord - ouest - ouest - sud -...
   Toutes les solutions du labyrinthe, chemins de longueur minimale menant de l'entrée à une sortie, correspondent à des individus qui peuvent exister. Le mécanisme des générations successives avec mutation - sélection - croisement fait émerger ces individus, parmi les 2²⁰⁰ possibles (environ 10²⁰). Comment évaluer un individu ? La plupart ont un génome qui les fait boucler, ou buter sur une paroi. L'on peut prendre comme mesure la distance existant entre l'abcisse atteinte et la sortie, onzième case du côté droit du labyrinthe.
   
2. Pour avoir un code génétique plus économe, l'on peut indiquer les étapes succesives du chemin plutôt que de donner une stratégie pour chaque case. Cela consiste à coder les décisions successives que le mobile doit prendre, toujours avec un code sur 2 bits pour indiquer la direction.
   Alors 00110000... signifie aller vers l'est, puis vers le sud, puis deux fois vers l'est, etc. Si l'on considère que les chemins menant à la sortie ont tous une longueur inférieure à 55 décisions (55 est un choix arbitarire, dicté par l'expérience), le génome a 110 bits.
   Le code génétique 0011000000... signifie aller vers l'est, puis vers le sud, puis trois fois vers l'est, etc.
   
3. L'on peut aussi essayer d'optimiser en décidant de tenir compte des parois dans le génome. Sur chaque case, le mobile a quatre directions possibles : nord, ouest, sud, est. Dans chacune de ces directions, les parois peuvent prendre 8 aspects différents : chacune des trois issues potentielles (à gauche, tout droit, à droite) peut être libre ou bloquée :

1. Cela fait donc 32 stratégies. Beaucoup consistent à foncer dans un mur, c'est le mécanisme de l'évolution qui fera le tri entre les stratégies gagnantes et perdantes !
   
   Le robot explorateur arrivant sur une case en reconnait la configuration. Reste alors le choix entre les quatre points cardinaux, choix de stratégie qui se code sur 2 bits. Le génome fait donc 64 bits. Lire dans le génome de l'individu (le parcours) la valeur sur deux bits associée à la direction, permet de choisir la direction non barrée la mieux notée.

Voilà trois codage différents. Il y en a encore d'autres possibles. Chacun a ses qualités et ses défauts : il trouve la solution la plus courte, la plus immédiate, la plus à droite, etc.

La fonction d'évaluation de la performance de chaque individu est de guider le robot explorateur le plus près du bord Est du labyrinthe, et de favoriser les chemins sortants les plus courts. Par exemple, nous pouvons accorder 1 point par case qui nous rapproche de l'est, plus 10 points pour chaque étape économisée par rapport au chemin de longueur maximum. La valeur 55 est, de manière arbitraire, la longueur maximale au bout de laquele l'on interrompt le robot s'il n'a pas trouvé la sortie.

Il vous est demandé en TD d'étudier et de concevoir en groupe un algorithme génétique de recherche de solution dans un labyrinthe.

Le travail de programmation et de tests sera à faire par binômes au cours de la semaine.

En cas de besoin, aide à la résolution :

Une applet Java de résolution de labyrinthe :

• la page d'accueil : « Genetic algoritms - Maze solver »
  http://home.sol.no/~bergar/mazega.htm
  
• annonce et critique dans JavaWorld :
  http://www.javaworld.com/javaworld/apprev/ar13.mazega.html
  
• et l'applet :
  http://jr.ttisms.com/pjf/maze/

Un logiciel de résolution de labyrinthe par réseau de neurones :
http://www.digitalbiology.com/

Bibliographie

support papier :

L'ouvrage de référence :
Algorithmes génétiques
David Goldberg, Addison Wesley, juin 1994, 417 pages

Une bonne introduction à la vie artificielle :
La vie artificielle
Jean-Claude Heudin, Hermes 9/94, 267 pages

Ouvrage sur l'IA ayant de bonne qualités pédagogiques :
Intelligence artificielle et informatique théorique
J.-M. ALLIOT & T. SCHIEX, Cepadues editions mars 1994, 520 pages

L'exercice sur la résolution d'un labyrinthe est tiré de l'ouvrage :
L'ordinateur génétique
Jean-Louis DESSALLES, Hermes mai 1996, 141 pages

Un roman passionnant, par un grand écrivain de science fiction et un grand chercheur en intelligence artificielle :
Le Problème de Turing.
Harry Harrison & Marvin Minsky &emdash; Ailleurs et demain, Collection française de Science-Fiction publiée par Robert Laffont, 8/1994

Edition originale : "The Turing Option", Warner Books :

What would happen if man's highest technical achievement, the computer, was combined with the most highly evolved organ on the planet, the human brain? For Brian Delaney, theory becomes reality when gunmen storm his high security laboratory and put a bullet in his skull.

Miraculously, Brian survives and scientists reconstruct his brain with the very nerve reprogramming techniques and computer-human connections that Brian himself helped invent. Now, as much machine as man, Brian's challenge is to regain his past and rediscover the scientific knowledge he lost - before his enemies dare to strike again.

In an astonishing blend of science fact and fiction that ranks with Michael Crichton's Jurassic Park and Carl Sagan's Contact, The Turing Option takes us to the furthest edge of tomorrow's computer technology today.

dans le Cyberespace :

Dossier du magazine Webdo sur la vie artificielle (de nombreux liens) :
http://www.webdo.ch/hebdo/hebdo_1996/hebdo_01/viart_01_sommaire.html

« La vie artificielle vous titille les cellules grises ? vous trouverez presque tout à partir de Zooland ! »
Zooland, répertoire sur la vie artificielle, très complet sur algorithmes génétiques, automates cellulaires, etc. :
http://research.de.uu.net:8080/public/zooland/

Le projet Tierra de vie artificielle :
http://www.hip.atr.co.jp/~ray/tierra/tierra.html
Logiciel pour créer un élevage de vers dans son PC : ftp://ftp.de.uu.net/pub/research/ci/Alife/tom-ray/
ou dans son Mac : http://www.santafe.edu/~smfr/mactierra.html
Les séparateurs animés de ces pages sont une visulisation de la vie d'une population de vers issue du projet Tierra.

« The genetic algorithms archive » nombreux liens sur l'état de la recherche en ce domaine :
http://www.aic.nrl.navy.mil/galist/

Scott Robert Ladd - Artificial Life :
http://www.frontier.net/~srladd/alcentral.html

Vivarium, simulation sur Mac :
http://web-hou.iapc.net/~koops/vivarium/giantworld.hqx

Document : http://www.mines.u-nancy.fr/~tisseran/cours/algo-genetique/genetique.html
Dernière mise à jour : mai 1998