darwin

C1-ALGO-06 : Algorithmes évolutionnistes#

Objectifs pédagogiques#

  • Appréhender certains algorithmes évolutionnistes

  • Appliquer un algorithme génétique à un problème

Définition#

Les algorithmes évolutionnistes sont une classe d’algorithmes qui s’inspirent de la théorie de l’évolution de Charles Darwin. Cette classe d’algorithmes utilisent des processus qui imitent le vivant, notamment les trois grands mécanismes des êtres vivants :

  1. la reproduction

  2. la mutation

  3. la recombinaison

Selon la théorie de l’évolution, sur une population donnée d’individus tous différents, ceux qui ont unt chance de transmettre leurs caractéristiques sont ceux qui sont les mieux adaptés à leur environnement.

En algorithmique évolutionniste, un individu est une solution possible.

La très grande difficulté de ces algorithmes est la capacité que doit avoir le processus pour évaluer la qualité d’une solution. Cela se fait grâce à une fonction d’objectif (fitness function en anglais)

Algorithmes évolutionnistes#

il existe plusieurs classes d’algorithmes évolutionnistes

  1. les stratégies d’évolution

  2. les algorithmes génétiques

Algorithmes génétiques#

Les algorithmes génétiques s’inspirent des mécanismes de la génétique et particulièrement ceux liés à l’Acide désoxyribonucléique (ADN). La théorie de l’évolution considère que la majorité des caractéristiques d’un être vivant est contenue dans la double hélice de l’ADN.

ADN

Voici un algorigramme d’un algorithme génétique :

algogen

Initialisation#

Création de la population initiale. Chaque élément est un critère

Sélection#

Ici on sélectionne les différents individus. Il existe plusieurs méthodes pour sélectionner un individu parmi deux :

  1. la roulette (le hasard pur)

  2. la roulette biaisée

  3. Un tournoi entre les deux

  4. l’élitisme (on sélectionne que le meilleur)

  5. Un mixe

Algorithme génétique simple#

Dans cet exemple, nous souhaitons trouver la chaîne de bits ayant le plus de 1 pour une longueur fixe donnée.

Résoudre le problème du plus cours chemein#

Références#

  • Charles Darwin, On the Origin of Species by Means of Natural Selection}, 1859 : [Darwin, 1859]

  • David Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning , 1989 : [Goldberg, 1989]

  • homas Vallée, Murat Yildizoglu, Présentation des algorithmes génétiques et de leurs applications en économie, 2004, [Thomas Vallée, 2004]