Algorithme génétique

Fonctionnement

Heuristique

Pour résoudre ces problèmes, nous utilisons des heuristiques afin de trouver la solution optimale, ou à défaut, la moins mauvaise, pour le problème.

L'idée principale des heuristiques est d'explorer l'espace des solutions en essayant de converger vers la meilleure solution.
Cependant, il est important d’éviter une convergence prématurée de l'algorithme vers un extremum, ou optimum, local.
Un extremum local est la meilleure solution dans une zone restreinte, en opposition à l’extremum global, qui est la meilleure solution dans l’ensemble.

Voici un exemple d'une heuristique où la meilleure solution est la valeur la plus proche de 4 :

Principes

Les algorithmes génétiques utilisent la théorie de Darwin sur l’évolution des espèces.
Elle repose sur trois principes : le principe de variation, le principe d'adaptation et le principe d'hérédité.

Le principe de variation : Chaque individu au sein d’une population est unique. Ces différences, plus ou moins importantes, vont être décisives dans le processus de sélection.
Le principe d'adaptation : Les individus les plus adaptés à leur environnement atteignent plus facilement l'âge adulte. Ceux ayant une meilleure capacité de survie pourront donc se reproduire davantage.
Le principe d’hérédité : Les caractéristiques des individus doivent être héréditaires pour pouvoir être transmises à leur descendance. Ce mécanisme permettra de faire évoluer l’espèce pour partager les caractéristiques avantageuse à sa survie.

Paradigme

Ce paradigme, associé avec la terminologie de la génétique, nous permet d’exploiter les algorithmes génétiques : Nous retrouvons les notions de Population, d’Individu, de Chromosome et de Gène.

• La population est l’ensemble des solutions envisageables.
• L’individu représente une solution.
• Le Chromosome est une composante de la solution.
• Le Gène est une caractéristique, une particularité.

Avec ces notions, nous obtenons trois opérateurs d’évolution…

Opérateurs d'évolution

Il y a trois opérateurs d'évolution dans les algorithmes génétiques :

• La sélection : Choix des individus les mieux adaptés.
• Le croisement : Mélange par la reproduction des particularités des individus choisis.
• La mutation : Altération aléatoire des particularités d'un individu.

Sélection

La sélection consiste à choisir les individus les mieux adaptés afin d'avoir une population de solution la plus proche de converger vers l'optimum global.
Cet opérateur est l'application du principe d'adaptation de la théorie de Darwin.

Il existe plusieurs techniques de sélection. Voici les principales utilisées :

• Sélection par rang : Cette technique de sélection choisit toujours les individus possédant les meilleurs scores d'adaptation.
• Probabilité de sélection proportionnelle à l'adaptation : Technique de la roulette ou roue de la fortune, pour chaque individu, la probabilité d'être sélectionné est proportionnelle à son adaptation au problème.
• Sélection par tournoi : Cette technique utilise la sélection proportionnelle sur des paires d'individus, puis choisit parmi ces paires l'individu qui a le meilleur score d'adaptation.
• Sélection uniforme : La sélection se fait aléatoirement, uniformément et sans intervention de la valeur d'adaptation.

Voici un exemple avec des individus en représentation binaire une fois la sélection effectuée :

On réalise ensuite un croisement entre deux chromosomes parmi la population restante...

Croisement

Le croisement, ou enjambement, crossing-over, est le résultat obtenue lorsque deux chromosomes partage leurs particularités.
Celui-ci permet le brassage génétique de la population et l'application du principe d’hérédité de la théorie de Darwin.

Il existe deux méthodes de croissement : simple ou double enjambement.

• Le simple enjambement consiste à fusionner les particularités de deux individus à partir d'un pivot, afin d'obtenir un ou deux enfants :

  

• Le double enjambement repose sur le même principe, sauf qu'il y a deux pivots :

  

On réalise ensuite une mutation sur les enfants obtenues lors du croisement...

Mutation

La mutation consiste à altérer un gène dans un chromosome selon un facteur de mutation. Ce facteur est la probabilité qu'une mutation soit effectuée sur un individu.
Cet opérateur est l'application du principe de variation de la théorie de Darwin et permet, par la même occassion, d'éviter une convergence prématurée de l'algorithme vers un extremum local.

Voici un exemple de mutation sur un individu ayant un seul chromosome :

Avec ces trois opérateurs d'évolution, nous pouvons appliquer les algorithmes génétiques.

Algorithme

Les principes de bases étant expliqués, voici le fonctionnement des algorithmes génétiques :

Quelques explications :

• La génèse est l'étape de la création d'une population aléatoire. C'est le point de départ de notre algorithme

• L'évaluation est l'analyse des individus pour analyser si une solution est disponible. Pour ceci, nous utilisons un fonction de coût, ou d'erreur, afin de définir le score d'adaptation des individus lors du processus de sélection.

• Nous effectuons une boucle tant que l'évaluation estime que la solution n'est pas optimale.