Les algorithmes génétiques

Les algorithmes génétiques ont été inventés dans les années 60. Depuis les années 80, ils sont devenus une technique "à la mode", on les trouve dans de nombreuses applications industrielles, où ils sont utilisés par exemple pour calculer la forme d'une aile d'avion, pour diagnostiquer des pannes complexes, pour traiter des images médicales.

Programme génétique et programme informatique

Tant que l'on considère les ordinateurs comme des machines à qui l'on confie des suites d'opérations, que l'on a définies dans les moindres détails alors ils ne pourront nous surprendre. Une des voies pour dépasser l'ordinateur exécutant est l'algorithme génétique. Il possède deux qualités essentielles : les bonnes solutions qu'il obtient n'ont pas été fournies par le programmeur de façon explicite, mais ont été découvertes par l'algorithme. Il peut être en principe être appliqué à une classe assez large de problèmes, car son fonctionnement dépend peu du problème posé.

A chaque instant, un algorithme génétique garde en mémoire une population d'individus. Ces individus sont des solutions du problème posé. Au début ce sont de bien piètres solutions. Généralement, ils ont été tirés au hasard lors du début du processus. Mais comme dans la nature, l'important n'est pas d'être une bonne solution dans l'absolu, c'est d'être moins mauvais que les autres. Ces solutions sont essayées, les meilleurs se reproduisent entre elles à la manière des êtres vivants, par croisements génétiquse. Les nouvelles solutions obtenues sont essayées, et ainsi de suite jusqu'à ce que de bonnes solutions soient découvertes.

Le principe de l'évolution par sélection naturelle n'est pas la seule caractéristique empruntée à l'idée de nature. Leur génome n'est pas fait de molécule d'ADN, mais de chaÓne binaire (suite de 0 et de 1). Il définit une tentative de solution.

Le fonctionnement d'un algorithme génétique

1. Le codage par paramètres du problème

La question évidente qui se pose au concepteur d'un algorithme génétique est de savoir comment représenter le problème qu'il veut traiter. Il ne faut pas limiter les possibilités de coupures dans le génome. Il est préférable de ne tenir compte d'aucune informatique de nature sémantique.

1. Faire vivre une population artificielle.

Le fonctionnement d'un algorithme génétique repose en grande partie sur la sélection des individus qui vont se reproduire. Dans le cas le plus simple, ce sont ceux qui ont obtenu la meilleure note lors de l'évaluation.

Il serait maladroit de fixer une fécondité liée à la note obtenue, il vaut mieux la déterminer de façon aveugle en tenant compte uniquement du rang obtenu.

Les croisements et les mutations

On obtient les individus de la nouvelle génération par croisement des génomes de meilleurs de ceux de l'ancienne. A cela, il faut ajouter un taux de mutation qui permette d'engendrer des solutions nouvelles qui étaient jusque là absentes de la population.

• Les pertes d'allèles
• Écologie artificielle (nourriture)
• Le problème du maximum local
• Les équilibres ponctués
• Aptitude insulaire : sortie d'un maximum local
• Codage non positionnel du génome
• La diploïdie

Dossier Vie Artificielle