Algorithme génétique

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. 

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

Voici un exemple de fonctionnement avec un temps d'attente de 200ms pour visualiser chaque étape de génération.
Cliquez sur "Result" pour voir le résultat, la colonne de gauche est la représentation de l'individu et la colonne de droite son score.