Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest Chrome, Safari or Firefox browser.

Algorithme Génétique
LE ROUX Thomas
IR3
Exposé 2014 - ESIPE
Tout ce qui existe dans l’univers est le 
fruit du hasard et de la nécessité. 

Jacques Monod.
Sommaire
  • Introduction
  • Présentation
  • Domaines d'applications
  • Métaheuristique
  • Fonctionnement
  • Hello World
  • Utilisations
  • Limites
  • Conclusion
  • Bibliographie
Introduction
  • Famille des algorithmes évolutionnistes.
  • Obtenir une approximation de la solution par des 
    mécanismes d'optimisation.
  • Sélection naturelle sur une population de solutions 
    potentielles.
Présentation
  • Problèmes complexes.
  • Pas de méthode pour résoudre.
  • Modélisation délicate et/ou confuse.
  • Solution au problème est inconnue .
  • Évolution, Adaptation, Tolérance aux erreurs.
Présentation
  • Machine Learning.
  • Intelligence Artificiel.
  • Optimisation des réseaux de neurones.
  • Logique Floue.
Domaines d’applications
  • Bioinformatique
  • Phylogénie
  • Économie
  • Sciences numériques
  • Robotiques
  • Industries
  • Mathématique
  • Physique
  • Chimie
  • etc...
Métaheuristique
  • Méthodologie pour résoudre ces problèmes.
  • Découvrir la solution optimale.
  • Exploration de l'espace des solutions.
  • Convergence vers l'extremum global. 
  • Convergence prématurée de l'algorithme :
    Extremum     local
Métaheuristique
Fonctionnement
Variation
Adaptation
Hérédité
Paradigme
Population
Individu
Chromosome
Gène
Sélection
Croisement
Mutation
Opérateur d'évolution
Sélection
Croisement
Mutation
Algorithme
Hello World
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));
        }
};
Hello World
Hello World
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;

};
Hello World

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)];

};
Hello World
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;
};
Hello World
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);
        }

};
Hello World
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);

};
Hello World
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]);

        }

};
Hello World
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;
                }

        }

};
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();
};
Utilisations
  • Cryptanalyse.
  • Finance.
  • Résolution des Sudokus.
  • Planning des soutenances.
  • Plan de table.
  • Gestion de projet avec des ressources restreintes.
  • Robotique.
  • Data Mining.
  • etc...
Limites
  • Nombreuses itérations/calculs.
  • Mise en œuvre complexe: modélisation, paramètre. 
  • Fonction d'évaluation: définition, complexité.
  • Résultat incertain.
  • Optimaux locaux.
  • Allocation mémoire.
Conclusion
  • Algorithme évolutionniste.
  • Algorithme d'optimisation.
  • Algorithme complexe.
  • Modélisation.
  • Implémentation.
Questions ?

Use a spacebar or arrow keys to navigate