the new scientific reference

[Le Lab’] Algorithme génétique : manipulation de caractères6 minutes de lecture

[

Il y a peu nous abordions la théorie sur les algorithmes génétiques. En voici maintenant une application simple et concrète qui permet de mieux comprendre le fonctionnement évolutif de ce type d’algorithmes.

Un problème

Nous souhaitons résoudre un problème simple à savoir faire trouver à l’ordinateur une phrase qui aura au préalable été définie. Vous me direz surement que le problème est un peu inutile sachant que l’on connaît déjà la réponse au problème qui est la phrase à trouver !

Détrompez-vous ! Cet exemple vous permettra de mettre en application assez simplement un AG et ainsi d’en voir tous les mécanismes.

Allez c’est parti !

Une solution

Initialisation

La première question est la suivante : comment structurer le problème de manière à pouvoir y appliquer un algorithme évolutif génétique ?

  • Individu : chaque individu sera dans notre cas une chaîne de caractères de longueur n la longueur de l’objectif
  • Génome : le génome de chaque individu est constitué d’un seul élément : la chaîne de caractère
  • Allèle : l’allèle ici est un caractère codé sur 8 bits ASCII

Il y a donc n allèles par génome et donc par individu.

Il nous reste à définir les croisements et mutation :

  • Croisement : dans notre cas, un croisement se résume à sélectionner deux parents au hasard, à choisir un pivot entre 1 et n et à croiser les deux bouts de génomes entre eux pour former un enfant et croiser le reste pour former un deuxième enfant
  • Mutation : nous considérons la mutation ici comme un décalage avant ou après de plus ou moins 1 à 7 caractères suivant l’ordre ASCII. A noter que la mutation a dans notre cas une chance sur deux d’apparaître. En effet, dans notre exemple, beaucoup de mutations sont nécessaires pour pouvoir arriver à une solution optimale en un minimum de générations.

Enfin, nous définissons une population de 500 individus par génération. De plus, nous souhaitons, à chaque génération, ne conserver que les 20 meilleurs. Cela semble peu mais dans notre cas, nous avons qu’une seule solution à notre problème, nous souhaitons donc converger le plus rapidement possible sans pour autant converger vers une solution locale.

A noter que notre fonction d’évaluation ici est seulement une fonction qui retourne l’écart cumulé entre les caractères de l’individu actuel par rapport au caractère optimal à avoir (sous entendu la bonne lettre de notre chaîne de caractère).

Codage

Nous choisissons le langage Java pour coder notre AG car il semble tout à fait indiqué : langage objet, parfait pour un algorithme génétique qui s’inspire de choses réelles, concrètes, à mettre sous forme d’objet.

public class AlgorithmeGenetique {

    public static void main(String[] args) {
        int counter = 0;
        Generation generation = new Generation(500, 20, 500, "Science Exploits");
        generation.initialiserGenerationZero();
        while (generation.recupererIndividu(0).recupererScore() != 0) {
            generation.executerSelection();
            System.out.print("Génération " + counter + " : ");
            generation.recupererIndividu(0).recupererGenome().afficherGenome();
            generation.executerCroisement();
            generation.executerMutation();
            counter++;
        }

    }

}
import java.util.ArrayList;
import java.util.Collections;
import java.util.concurrent.ThreadLocalRandom;

public class Generation {
    
    private final int nbIndividus;
    private final int nbIndividusAlpha;
    private final int probaMutation;
    private final String objectif;
    
    private final ArrayList<Individu> groupe;
    
    public Generation(int nbIndividus, int nbIndividusAlpha, int probaMutation, String objectif) {
        this.nbIndividus = nbIndividus;
        this.nbIndividusAlpha = nbIndividusAlpha;
        this.objectif = objectif;
        this.probaMutation = probaMutation;
        this.groupe = new ArrayList<>();
    }
    
    public void initialiserGenerationZero() {
        for (int individu = 0; individu < nbIndividus; individu++) {
            groupe.add(new Individu(objectif.length()));
            groupe.get(individu).recupererGenome().genererGenomeAleatoire();
            groupe.get(individu).mettreAjourScore(objectif);
        }
    }
    
    public void executerSelection() {
        for (int individu = 0; individu < nbIndividus; individu++) {
            groupe.get(individu).mettreAjourScore(objectif);
        }
        Collections.sort(groupe);
    }
    
    public void executerCroisement() {
        for (int individu = nbIndividusAlpha; individu < nbIndividus; individu++) {
            groupe.get(individu).transformerEnEnfant(
                    groupe.get(ThreadLocalRandom.current().nextInt(0, nbIndividusAlpha)).recupererGenome(),
                    groupe.get(ThreadLocalRandom.current().nextInt(0, nbIndividusAlpha)).recupererGenome());
        }
    }
    
    public void executerMutation() {
        for (int individu = 0; individu < nbIndividus; individu++) {
            if (ThreadLocalRandom.current().nextInt(0, 1000) < probaMutation) {
                groupe.get(individu).muter();
            }
        }
    }
    
    public Individu recupererIndividu(int indice) {
        return groupe.get(indice);
    }
}
import java.util.concurrent.ThreadLocalRandom;

public class Individu implements Comparable<Individu> {

    private final Genome genome;
    private int score;

    public Individu(int tailleChaine) {
        this.genome = new Genome(tailleChaine);
        this.score = 0;
    }

    public void mettreAjourScore(String objectif) {
        score = 0;
        for (int indice = 0; indice < objectif.length(); indice++) {
            score += Math.abs(genome.recupererCaractere(indice) - (int) objectif.charAt(indice));
        }
    }

    public void transformerEnEnfant(Genome genome1, Genome genome2) {
        int pivot = ThreadLocalRandom.current().nextInt(0, genome.recupererTailleGenome());
        //int pivot = genome.recupererTailleGenome()/2;
        for (int indice = 0; indice < pivot; indice++) {
            genome.modifierCaractere(indice, genome1.recupererCaractere(indice));
        }
        for (int indice = pivot; indice < genome.recupererTailleGenome(); indice++) {
            genome.modifierCaractere(indice, genome2.recupererCaractere(indice));
        }
    }

    public void muter() {
        int indice = ThreadLocalRandom.current().nextInt(0, genome.recupererTailleGenome());
        int ecart = ThreadLocalRandom.current().nextInt(1, 7);
        if (ThreadLocalRandom.current().nextInt(0, 2) == 0) {
            genome.modifierCaractere(indice, genome.recupererCaractere(indice) - ecart);
        } else {
            genome.modifierCaractere(indice, genome.recupererCaractere(indice) + ecart);
        }
    }

    public Genome recupererGenome() {
        return genome;
    }

    public int recupererScore() {
        return score;
    }

    @Override
    public int compareTo(Individu autreIndividu) {
        return (this.score - autreIndividu.score);
    }

}
import java.util.concurrent.ThreadLocalRandom;

public class Genome {

    private final int tailleChaine;
    private final char[] chaine;

    public Genome(int tailleChaine) {
        this.tailleChaine = tailleChaine;
        this.chaine = new char[tailleChaine];
    }

    public void genererGenomeAleatoire() {
        for (int indice = 0; indice < tailleChaine; indice++) {
            chaine[indice] = (char) ThreadLocalRandom.current().nextInt(32, 256);
        }
    }

    public void afficherGenome() {
        System.out.println(chaine);
    }

    public void modifierCaractere(int indice, int valeur) {
        chaine[indice] = (char) valeur;
    }

    public int recupererCaractere(int indice) {
        return (int) chaine[indice];
    }

    public int recupererTailleGenome() {
        return tailleChaine;
    }

}

Voici ci-dessous un exemple de l’exécution de notre programme. Il est important de savoir que chaque exécution est différente : en effet, les individus sont à chaque fois générés au hasard au lancement de l’algorithme et seul l’individu final est identique entre les différentes simulations.

Génération 0 : Y<…„{o1(n&‚pyQGl
Génération 1 : Y<…„{o1(n&‚pydvx
Génération 2 : Y<…„{of5nWƒdvx
Génération 3 : Y<…„{oa%@}qpydvx
Génération 4 : l~~V{oa%@}qnudvx
Génération 5 : \~~V{ob%C}qpudvx
Génération 6 : Y~~V{ob C}qpudvx
Génération 7 : Sy~V{ob%@}qnpdvx
Génération 8 : SyxV{ob C}qpuivx
Génération 9 : Sy~^{lb C}qnpdvx
Génération 10 : SyxVvob Cxonphvx
Génération 11 : Syzd{ob Cxqnpiux
Génération 12 : Stx^{hb Cwqnogvx
Génération 13 : Swtd{hb Cwqnogvx
Génération 14 : Swtdpib!Cwqnpivx
Génération 15 : Swtdpid Cwqnpivt
Génération 16 : SrndpibCxqnpivs
Génération 17 : SlndpibCxqnpivt
Génération 18 : Slndpbb Cxqmpitr
Génération 19 : Sihdpbb Cxqmpitr
Génération 20 : Sdndpbb Cxqmpitr
Génération 21 : Sdhdpbb Cxqmpitr
Génération 22 : Sdidpbd Cxqmpitr
Génération 23 : Sdidpbd Exqmpitr
Génération 24 : Sdidpbd Exqmpits
Génération 25 : Sdidocd Exqmoits
Génération 26 : Scidocd Exqmoits
Génération 27 : Sdidnce Exqmoits
Génération 28 : Scidnce Exqmoits
Génération 29 : Scieoce Exqloits
Génération 30 : Science Exoloits
Génération 31 : Science Exqloits
Génération 32 : Science Exploits

 

On constate donc que l’ordinateur évolue tout seul vers la solution optimale du problème sans que l’on ai besoin de lui indiquer le chemin : il évalue chaque individu, sélectionne les meilleurs et les mélange afin d’obtenir un individu encore plus proche de la solution parfaite. On a seulement renseigné à l’ordinateur les paramètres de notre individu, ainsi que la fonction d’évaluation qui est la clé de cette évolution.

A propos de l'auteur

Corentin POTRON

Actuellement élève-ingénieur et rédacteur du site Science Exploits, j'aime partager ma passion pour les nouvelles technologies, l'informatique, et les sciences en général. Je suis un fervent adepte de la philosophie DIY et du logiciel libre. Je suis ici pour vous partager mes trouvailles, mes projets et mes intérêts du moment.

Par Corentin POTRON
the new scientific reference

Archives

Recevez nos derniers articles par mail !

Recevez nos derniers articles par mail !

Rejoignez notre liste pour recevoir notre newsletter hebdomadaire gratuitement avec les derniers articles du site Science Exploits !

Vous venez de vous inscrire avec succès, à bientôt !