~ FONDEMENTS THEORIQUES.
~ PRINCIPES : - Evaluation et sélection
- Croisements
- Mutations
~ APPLICATION : - Problème du codage
- Critère d'évaluation
- Sélection
- Croisement
- Mutation
Les algorithmes génétiques ont été inventés par Jonh Holland dans les années 60. Repris notamment par Golberg dans les années 70, cette technique connait aujourd'hui un franc succès. On l'utilise dans la résolution de problèmes complexes, nécessitant des temps de calcul élevés.
FONDEMENTS THEORIQUES.
Le principe des algorithmes génétiques s’inspire directement des lois de la sélection naturelle, décrites par Darwin. Celles-ci stipulent le tri des espèces par l’environnement. En effet, les conditions changeantes du milieu (climat, pénurie de nourriture, sècheresse, prédateurs) entraînent la disparition des espèces ne pouvant s’y adapter. La nature sélectionne ainsi les créatures dont le phénotype (= ensemble des caractéristiques génétiquement déterminées d’un individu) est en adéquation avec les nouvelles conditions imposées. Les animaux ne répondant pas à ces exigences de l'environnement s'éteignent en même temps que le code génétique dont ils sont porteurs puisqu'aucun de ses représentants n'est en mesure de survivre pour les transmettre à une éventuelle descendance.
En revanche, les espèces survivantes, préservées grâce aux caractéristiques physiques héritées de leur génome, se reproduisent et leur code génétique perdure. Ce dernier peut alors être vu comme une configuration « gagnante », propre à remporter le problème de la survie. La résolution de problèmes par algorithmes génétiques est basée sur cette métaphore.
PRINCIPES.
Un problème se résumant à un ensemble de contraintes, on peut l'assimiler à un "environnement" auquel pourront s'adapter un nombre retreint d'individus qui sont ici les "solutions" du problème en question. Comme des entités biologiques, les solutions s'adaptent par leur seule capacité à remplir les contraintes imposées par le problème. C'est ce qui les distingue des autres individus inadaptés, à savoir, le vaste ensemble des réponses erronées.
Face à un problème donné, plusieurs morceaux de code informatique vont être générés aléatoirement. Chacun d’eux est la représentation binaire d’une réponse au problème posé. Ils doivent être vus comme des individus porteurs d’une information génétique unique. Ce que l’on se propose de faire, c’est de sélectionner uniquement les individus dont le code génétique est une configuration remplissant au mieux les contraintes du problème. Les autres ne pourront pas survivre et leur code génétique sera écarté. En général, à la première génération de ces codes, la totalité des réponses proposées est fausse. Aucune d’elle ne s’impose comme solution au problème mais certaines s’en rapprochent plus que d’autres.
On va tout d’abord procéder à une sélection des codes, conserver les meilleurs et éliminer ceux qui s’éloignent le plus de la solution. Ensuite, on va faire « évoluer » les codes gagnants vers des configurations susceptibles de représenter une meilleure réponse au problème, une solution mieux adaptée.
Evaluation et sélection :
On utilise tout d'abord un « évaluateur », qui va assigner à chaque code une valeur apellée fitness, témoin de sa capacité à résoudre le problème. Cette valeur aura des répercussions sur la probabilité de reproduction de l'individu. Si la fitness d’une séquence est très grande, alors celle-ci aura d’autant plus de chance d’être conservée et présente à la génération suivante, car on procède à un tirage aléatoire pour désigner les individus survivants : plus leur fitness est élevée, plus ils auront de chance d'être désignés par le hasard. Quant aux séquences les moins adaptées, possédant une faible fitness, elles disparaitront généralement au terme de quelques générations.
Croisements et évolution naturelle :
Lorsque la sélection est terminée, on procède à des « cassures » dans les séquences survivantes, la zone de cassure étant aléatoirement déterminée. On "croise" ensuite des pans de séquences entre elles, c'est à dire que les individus échangent des parties de leur code pour créer des individus nouveaux, inexistants à la génération précédente. Cela reprend le mécanisme biologique de « brassage génétique », permettant à un être de produire des gamètes génétiquement uniques par combinaisons de pans de son propre génome.
Mutation et évolution accidentelle:
A la suite des opérations de sélection et de croisement, on mime à nouveau un phénomène biologique, celui de mutation. Au niveau biologique, une mutation est une modification de l’information génétique par dégradation ou substitution locale de paires de bases (une base peut être vue comme l’équivalent biologique du bit, plus petite unité codante de la molécule d’ADN). Dans le cas des algorithmes génétiques, on va procéder de même, en changeant la valeur d’un bit arbitrairement choisi parmi tous les bits de la population présente.
Après l’étape de mutation, on effectue une nouvelle sélection en calculant la fitness de chaque individu.
Les générations se succèdent et les individus créés sont de mieux en mieux adaptés au problème, c’est à dire qu’ils se rapprochent de plus en plus de la solution. Bientôt, l’un deux « sera » la solution.
APPLICATION.
Afin de mieux apréhender le fonctionnement des algorithmes génétiques, nous vous proposons de suivre la résolution du problème dit du « voyageur de commerce » :
« Un voyageur de commerce doit visiter 5 villes. Les distances respectives entre celles-ci sont toutes connues et le voyageur souhaiterait optimiser son parcours en le rendant le plus court possible. Dans quel ordre doit-il visiter ses 5 destinations, sachant qu'il ne doit jamais repasser par la même ville ? »
Problème du codage.
On doit pouvoir générer des codes qui représentent des parcours possibles. Le moyen le plus simple (et pas le plus efficace) est de coder une ville sur cinq bits. On peut par exemple poser :
_ « 10000 » représente la ville A.
_ « 01000 » représente la ville B.
_ « 00100 » représente la ville C.
_ « 00010 » représente la ville D.
_ « 00001 » représente la ville E.
De là, on peut coder un parcours sur 25 bits, en mettant bout à bout 5 séquences de 5 bits représentant chacune une ville. Par exemple, « 1000001000001000001000001 » représente le parcours ABCDE. En premier lieu, on génère aléatoirement plusieurs codes de ce type, tous viables, c’est à dire contenant obligatoirement le codage des 5 villes.
Notons que ce codage est fort grossier et va entrainer plusieurs problèmes.
Critère d’évaluation.
Le codage correspondant au parcours ABCDE va représenter un certain nombre de kilomètres, égal à l’addition des distances AB, BC, CD et DE.
Le but du problème étant de minimiser le kilométrage k du voyageur, un critère évident d’évaluation est donné par la fonction : « inverse du kilométrage », soit 1/k.
Ainsi, plus le kilométrage d’un parcours est élevé, plus la fitness du code correspondant est faible, et plus sa probabilité de conservation à la génération suivante est ténue. Ces mauvaises solutions, très éloignées du parcours idéal, seront donc rapidement éliminées par sélection.
Sélection.
On calcule F, la fitness globale de la première génération.
F= somme des fi, où fi représente la fitness d’un individu, soit l’inverse du kilométrage que représente son parcours. La probabilité de survie d’un individu s’obtient en calculant p, où p= fi / F.
On procède ensuite à n tirages aléatoires, et on calcule n×p.
Si n×p<1, l’individu concerné ne sera pas sélectionné et disparaîtra.
Croisements.
C’est ici qu’apparaissent les problèmes liés à notre codage « bestial ».
En effet, en temps normal, on coupe les séquences à n’importe quel endroit, par exemple comme ceci :
« 010110 » et « 100011 » sont coupés après le deuxième bit : « 01/0110 » et « 10/0011 ».
On procède alors au mélange des deux séquences et on obtient : « 10/0110 » et « 01/0011 ».
Dans notre problème, si on s’autorise à couper n’importe où, on obtiendra des individus non-viables, dôté d’une séquence incompréhensible car ne renvoyant à rien. C’est le cas si on coupe au milieu d’une ville :
« 10/000 »(A) et « 00/100 »(C) donnent « 10/100 » et « 00/000 ».
Ce croisement, qui donne donc deux non-solutions, ne va pas dans le sens d’une amélioration de la population. Pour corriger le problème, il faut nécessairement définir des zones de coupure autorisée. En temps normal, la zone de coupure est déterminée par un nombre tiré au hasard et compris entre 1 et n-1, n étant la taille des séquences. Ici, on tirera un nombre parmi l’ensemble {5,10,15,20}.
Cela fait, un problème subsiste encore. En effet, si on croise les séquences ABDEC et DBAEC, en coupant entre les 2 premières villes, on obtient ABAEC et DBDEC, soit deux individus non-viables puisque répétant certaines villes et en omettant d’autres.
On peut pallier à ce problème en assignant une pénalité sévère à la fitness des séquences ne respectant pas les critères de « réponses plausibles ». Ainsi, leurs probabilités de sélection chutent et ces codes erronés seront vraissemblablement éliminés dès la génération suivante.
Mutation.
D’ordinaire, on tire un nombre au hasard, compris entre 1 et N, où N est égal au nombre total de bits présent dans la population. (Dans notre cas, si on a 4 individus en deuxième génération, N= 4×25=100). Si le nombre tiré est 52, cela signifie que la mutation concernera la troisième séquence (les 50 premiers bits se rapportent aux 2 premiers individus), et portera sur son deuxième bit. Ce dernier passera à 1 s’il était à 0, et inversement. On retrouve ici les problèmes liés à notre codage, pour les mêmes raisons que celles rencontrées lors du croisement. On ne peut pas désigner un bit de cette manière aléatoire, car quelle que soit sa position, l’individu engendré ne sera jamais viable :
Prenons l’individu BDCAE. Si le bit à modifier est le deuxième, il concerne le codage de la ville B : « 01000 » sera donc transformé en « 00000 », ce qui ne signifie rien dans le codage choisi. Si le bit à modifier avait été le troisième, sur B cela donne « 01100 », ce qui là non plus ne renvoye à rien. On le constate, des mutations classiques n’apportent aucune amélioration au système. Il faut ici avoir recours à des mutations particulières, remplaçant le codage entier d’une ville par celui d’une autre.
Par exemple, si DCBAE est touché sur la ville B, cela donne DC*AE, où * est un élément à choisir au hasard parmi l’ensemble{A,C,D,E}.
Mais quelle que soit la ville choisie pour remplacer B, on aboutira à une séquence invalide car faisant apparaître 2 fois la même ville.
La solution finale est de procéder à l’échange entre 2 individus :
DCEBA et CEDAB sont concernés.Tout d’abord, on permute 2 villes au sein du premier individu, en l’occurrence B et A : On a maintenant DCEAB. On permute les même villes au sein de la deuxième séquence et on a CEDBA.
On obtient cette fois 2 individus viables tous les deux. Ces nouvelles combinaisons amélioreront-elles la population des solutions possibles ? La plupart du temps, à l’image des systèmes vivants, les mutations s’avèrent rarement avantageuses en terme d’adaptation. Elles conduisent souvent à des individus non-viables (ce que, nous venons de le voir, l’informatique peut compenser). D’un autre côté, ce mécanisme peut donner naissance à des individus inédits et parfois mieux adaptés que ses paires. Ce sont elles qui sont en grande partie à l’oeuvre dans l’évolution des espèces.
On voit ici comment l’informatique a su tirer profit des modèles naturels. Une génération purement aléatoire de codes, évalués par l’impitoyable filtre de la survie conduit irréversiblement à un affinement de la population, laquelle ne doit sa présence qu’à sa seule capacité à résoudre le problème posé. Cette technique permet d’explorer le champ des possibles selon un parallèlisme massif. Générées en aveugle, de multiples formes de solutions sont présentées à l’évaluateur. C’est le hasard qui détermine les séquences, et s’il mène fréquemment à des combinaisons hors de propos, ce n’est pas un problème puisqu’elles se voient expressément éliminées. Les pistes interressantes sont toujours conservées, ce qui permet au hasard de finalement désigner la solution.
Les limitations relatives à ce puissant outil se cantonent aux questions de codage de l’information et de détermination d’un critère d’évaluation pertinent.