Algorithme génétique
Les algorithmes génétiques appartiennent à la famille des algorithmes évolutionnistes.
Leur but est d'obtenir une approximation de la solution à un problème NP-complet par un mécanisme d'optimisation.
Les algorithmes génétiques utilisent la notion de sélection naturelle développée au XIXe siècle par Darwin et l'appliquent à une population de solutions potentielles au problème donné.
Pourquoi avons-nous besoin de tels algorithmes ?
Certains problèmes sont trop complexes pour que l'on puisse proposer un algorithme, ou lorsqu'il n'y a aucune méthode exacte pour les résoudre, d'une modélisation délicate et/ou confuse où la solution au problème est inconnue. Ou alors un algorithme tolérant aux variations de données, susceptible de s'adapter à une nouvelle situation, pour qu'il évolue.
Par exemple, comment effectuer le déplacement d'un robot ? Comment faire réagir ce robot suite à une bousculade, une perte d'équilibre ? Comment adapter le comportement du robot face au danger ?
Les algorithmes génétiques propose une solution à ces questions.
Ces algorithmes sont aussi un excellent support au domaine du Machine Learning, qui est un champ d'étude de l'intelligence artificiel. Ceux-ci peuvent être utilisés pour optimiser un réseau de neurones, notamment en entraînant le réseau par l'utilisation de nouvelles informations dans les connexions synaptiques, améliorant ainsi la topologie du réseau pour obtenir une règle d'apprentissage optimale : C'est ce qu'on appelle la neuroevolution.
Un exemple d'application utilisant la neuroevolution est un robot marchant sur deux jambes. Il est très difficile de le faire marcher : Un programme générique ne marchera pas, et si on réussit, celui-ci risque de ne plus fonctionner si le centre d'équilibre change légèrement suite à un défaut de fabrication ou un changement de composant/fournisseur.
Au lieu de supporter ce chagrin inévitable, nous pouvons utiliser les algorithmes génétiques et les réseaux de neurones afin d'enseigner au robot comment apprendre à marcher plutôt que d'enseigner au robot comment marcher.
Les algorithmes génétiques peuvent également être utilisés pour optimiser des systèmes reposant sur la logique floue, en effectuant la génération et/ou l'optimisation des règles ou des opérateurs dans ces systèmes.
Liste des domaines d'applications
On retrouve les algorithmes génétiques dans différents domaines d’applications, notamment en Bioinformatique, Phylogénie, Économie, Sciences numériques, Robotiques, Industries, Mathématique, Physique et Chimie.
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.
Cas pratique
Hello World !
Pour ce cas pratique nous allons utiliser un algorithme génétique afin de reproduire le texte "Hello World !".
Bien que ce problème soit trivial, le but de ce cas pratique est de comprendre pas à pas comment utiliser et implémenter les algorithmes génétiques.
L'individu
Commençons par définir l'individu : dans notre cas celui-ci est composé que d'un seul chromosome.
Un chromosome sera composé de plusieurs gènes représentant les lettres du texte, ainsi que de son coût :
var Chromosome = function(code) { if (code) { this.code = code; } this.cost = 9999; }; Chromosome.prototype.code = ''; Chromosome.prototype.random = function(length) { while (length--) { this.code += String.fromCharCode(Math.floor(Math.random() * 255)); } };
Pour définir son coût, on définit une fonction effectuant le delta entre le but à atteindre et l'état actuel de l'individu, ou chromosome dans notre cas.
Cette fonction sera utilisé par la fonction d'évaluation et de sélection.
Chromosome.prototype.calcCost = function(compareTo) { var total = 0; for (i = 0; i < this.code.length; i++) { total += (this.code.charCodeAt(i) - compareTo.charCodeAt(i)) * (this.code.charCodeAt(i) - compareTo.charCodeAt(i)); } this.cost = total; };
Ensuite, on définit la fonction de croisement entre deux chromosome en effectuant un simple enjambement.
Celle-ci retournera deux enfants, mais il est tout à fait possible de retourner un ou plusieurs enfants.
Chromosome.prototype.mate = function(chromosome) { var pivot = Math.round(this.code.length / 2) - 1; var child1 = this.code.substr(0, pivot) + chromosome.code.substr(pivot); var child2 = chromosome.code.substr(0, pivot) + this.code.substr(pivot); return [new Chromosome(child1), new Chromosome(child2)]; };
Enfin, on définit la fonction de mutation avec sa probabilité.
Si la mutation survient, on choisit aléatoirement un gène/caractère. Sa mutation sera le replacement de la lettre sélectionnée par la suivante ou la précente dans l'alphabet ASCII.
Chromosome.prototype.mutate = function(chance) { if (Math.random() > chance) return; var index = Math.floor(Math.random() * this.code.length); var upOrDown = Math.random() <= 0.5 ? -1 : 1; var newString = ''; var newChar = String.fromCharCode(this.code.charCodeAt(index) + upOrDown); for (i = 0; i < this.code.length; i++) { if (i == index) newString += newChar; else newString += this.code[i]; } this.code = newString; };
La population
La population dans ce cas pratique est une collection de texte, avec un but à atteindre ("Hello World !") et une taille limite.
Son initialisation est la Genèse.
var Population = function(goal, size) { this.members = []; this.goal = goal; this.generationNumber = 0; this.size = size; while (size--) { var chromosome = new Chromosome(); chromosome.random(this.goal.length); this.members.push(chromosome); } };
Ensuite, on définit la fonction de sélection. Celle-ci utilisera une sélection par rang en ne sélectionnant que les deux tiers des individus les mieux adaptés.
Pour ceci, nous avons besoin d'une fonction de tri qui effectuera une comparaison sur le score d'adaptation, ou le coût.
Population.prototype.sort = function() { this.members.sort(function(a, b) { return a.cost - b.cost; }); this.members.splice(this.size, this.members.length); }; Population.prototype.select = function() { var index = Math.min( (this.members.length * 2) / 3, this.size ); this.members.splice(index, this.members.length); };
On souhaite maintenant pouvoir effectuer les opérations de croisement et de mutation sur l'ensemble de la population.
Pour le croisement, uniquement la moitié des individus se reproduiront avec un/une partenaire au hasard.
Pour la mutation, chaque individu aurra une probabilité de 70% d'être affecter.
Population.prototype.mate = function() { for (var i = 0, max = this.members.length / 2; i < max; i++) { var random = i; while (random == i) { random = Math.floor(Math.random() * max); } var children = this.members[i].mate(this.members[random]); this.members.push(children[0]); this.members.push(children[1]); } }; Population.prototype.mutate = function() { for (var i = 0; i < this.members.length; i++) { this.members[i].mutate(0.7); this.members[i].calcCost(this.goal); if (this.members[i].code == this.goal) { this.sort(); return true; } } };
Enfin, on définit la fonction de génération qui implémentera la boucle d'évolution de notre algorithme.
Le programme dispose des composants nécessaires à la résolution du problème "Hello World !".
Population.prototype.generation = function() { for (var i = 0; i < this.members.length; i++) { this.members[i].calcCost(this.goal); } this.sort(); this.select(); this.mate(); if (this.mutate()) { return true; } this.generationNumber++; this.generation(); }; var population = new Population("Hello, world!", 2000); population.generation();
Liste d'exemples
Voici une liste d'exemples utilisant les algorithmes génétiques :
- Cryptanalyse : Bruteforce pour obtenir la clef privée sur des clés asymétriques.
- Finance : Prédiction de l'évolution d'une action.
- Résolution des Sudokus : Obtenir la solution à un sudoku.
- Planning : Obtenir le meilleur planning en fonction de dispositions.
- Plan de table : Effectuer la meilleure disposition de table en fonction des affinités de chacun.
- Robotique : Comportement intuitif et apprentissage.
- Data Mining : Création et utilisation de règles pour obtenir de nouvelles informations.
0 commentaires:
Enregistrer un commentaire