UN ALGORITHME GENETIQUE POUR SAUVER LE PERE NOEL

Notre mission

Cette année le Pere Noël rencontre un énorme problème.
Il a oublié le code secret de son coffre fort contenant la liste des cadeaux à distribuer !!

Notre mission va donc consister à trouver ce code secret afin qu'il puisse distribuer ses cadeaux à temps.

Le code secret à retrouver est "JoyeuXnoEl2019" et se trouve stocké dans la mémoire numérique du coffre fort.

Nous pouvons essayer de le trouver en cherchant toutes les combinaisons possibles. Le mot comportant 16 caractères dont des minuscules, des majuscules, des chiffres. Cela risque de prendre un certains temps avant d'y parvenir. Il nous faut donc trouver une autre solution en faisant appel aux algorithmes génétiques.

Les algorithmes génétiques

Les algorithmes génétiques utilisent la notion de sélection naturelle (Darwin) et l'appliquent à une population de solutions potentielles au problème donné.

Imaginons le cas similaire à notre problème où le mot à trouver est "CHAT".

La première étape va consister à créer une population d'individus composés de gènes (Dans notre cas les gènes seront les lettres de l'alphabet ainsi que les chiffres de 1 à 9)

CHAT comporte 4 lettres. Les individus vont donc comporter 4 gènes choisis au hasard :
Individu 1: C O Z P
Individu 2: O H 1 T
...

La seconde étape va être de calculer l'aptitude (fitness) de chaque individu. Dans notre cas 1 point est donné à chaque lettre correctement placée :
Individu 1: C O Z P = 1 points
Individu 2: O H 1 T = 2 points

Nous classons ensuite les individus par ordre décroissant d'aptitude :
Individu 2: O H 1 T = 2 points
Individu 1: C O Z P = 1 points

Vient la phase de selection d'individus parmis la population. Cette selection est composée d'élites et d'autres individus permettant d'assurer la diversité génétique.
Une fois la selection réalisée on procède aux croisements d'individus donnant alors naissance à des enfants afin de créer une nouvelle population

Vient enfin la mutation génétique s'appliquant à certains enfants pour respecter le principe d'évolution.

Ces phases étant réalisées plusieurs fois jusqu'à obtenir un résultat satisfaisant.

L'ensemble de ces étapes sont détaillées dans le code qui suit. A noter que nous utilisons nos propres méthode de selection et de croisement afin de rendre l'explication plus simple.

Attention, les algorithmes génétiques ne sont pas des algorithmes d'apprentissage ! mais peuvent être utilisés dans le cas de l'intelligence artificielle notemment pour selectionner les neurones les plus performants dans le cadre du deep learning

Résolution du problème

Nous définissons tous les gènes qui composeront les individus et qui sont necessaires à la résolution de notre problème

In [198]:
#Genes des individus
GENES = "abcdefgijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890"

Fonctions utiles

Viennent ensuite les fonctions utiles à savoir :

  • La génération aléatoire d'un gène
  • La génération d'un individu (composé de gènes choisi aléatoirement)
  • La génération de la population (composée d'individus)
  • Le calcul de l'aptitude d'un individu
  • Le classement des individus en fonction de leur aptitude
  • La manipulation génétique qui permettra d'engendrer de nouveaux individus et de résoudre notre problème
In [177]:
#Les imports
import random
In [178]:
#Generation d'un gêne de façon aléatoire
#Le gène est choisi parmis la liste de gènes définie précédemment
def generationGene():
    return random.choice(GENES)
In [179]:
generationGene()
Out[179]:
'a'
In [180]:
#Generation d'un individu (Composé de gènes)
#Le nombre de gène à générer est fonction de la taille du code secret
def generationIndividu(codeSecret):
    return [generationGene() for i in range(len(codeSecret))]
In [181]:
generationIndividu("test")
Out[181]:
['N', 'b', 'a', 'k']
In [182]:
#Generation de la population (Composée d'individus)
#Le nombre d'individus à générer est passé en paramètre
def generationPopulation(nombreIndividus,codeSecret):
    return [generationIndividu(codeSecret) for i in range(nombreIndividus)]
In [183]:
population = generationPopulation(5,"test")

#On affiche la population pour simple vérification
i=0
for individu in population:
    print("I:"+str(i)+" "+str(individu))
    i = i+1

I:0 ['F', 'S', 'f', 'Y']
I:1 ['F', 'K', 'o', 'S']
I:2 ['B', 'T', 'p', 'S']
I:3 ['T', 'a', 'v', 't']
I:4 ['P', 'u', 'U', 'T']
In [184]:
#Calcul de l'aptitude d'un individu
#On ajoute 1 point d'aptitude par lettre présente et bien placée dans l'ensemble des gènes de l'individu 
#par rapport au code secret
def calculAptitude(individu,codeSecret):
    aptitude = 0
    for gene, gene_attendu in zip(individu,codeSecret):
        if gene == gene_attendu:
            aptitude = aptitude +1
    return aptitude
In [185]:
#Calcul de l'aptitude du premier individu
#Combien de lettres sont elles bien placées ?
print(population[0])
calculAptitude(population[0],"test")

['F', 'S', 'f', 'Y']
Out[185]:
0
In [186]:
#Classement des individus de la population par ordre décroissant d'aptitude
#Ce classement inverse est réalisé à l'aide d'une fonction lambda
#Le résultat est un tableau dont la première colonne contient l'individu et la seconde son aptitude.
def classementIndividus(population,codeSecret):
    classement_individus = []
    for individu in population:
        classement_individus.append((individu,calculAptitude(individu,codeSecret)))
    return sorted(classement_individus, key=lambda x: x[1], reverse=True)
In [187]:
classement = classementIndividus(population,"test")
for individu in classement:
    print(individu)

(['T', 'a', 'v', 't'], 1)
(['F', 'S', 'f', 'Y'], 0)
(['F', 'K', 'o', 'S'], 0)
(['B', 'T', 'p', 'S'], 0)
(['P', 'u', 'U', 'T'], 0)

Manipulations génétiques

Nous voici présent à la fonction qui va permettre de :

  • Selectionner les individus (ceux ayant une meilleure aptitude)
  • Croiser les individus de forte aptitude permettant de créer des enfants
  • Muter génétiquement les enfants comme cela se produit dans la nature
In [1]:
def generationFuture(population,pourcentageElitisme,tauxMutation,codeSecret):
    
    #1: On classe les individus de la population passée en paramètre
    classement_individus = classementIndividus(population,codeSecret)
    
   
    #2: On crée 2 tableaux. L'un contenant l'individu gagnant, l'autre un tableau contenant les individus classés mais 
    #sans leur valeur d'aptitude
    individu_gagnant = []
    individus_classes = []
    
    #3: Parcours des individus
    for individu, aptitude in classement_individus:
    
        #On stock l'individu sans son aptitude dans un nouveau tableau
        individus_classes.append(individu)
    
        #Si l'aptitude est égale à la longueur du mot secret à trouver, cela signifie que nous avons trouvé la solution.
        if aptitude==len(codeSecret):
            individu_gagnant.append(individu)
      
        if individu_gagnant:
            return population,individu_gagnant
    
    
    
    
    #4: Selection des meilleurs individus (elites) devenant alors parents
    #Leur nombre est fonction du pourcentage d'élites passé en paramètre
    nombreElites = int(len(population)*pourcentageElitisme)
    parents = individus_classes[:nombreElites] 
    

    #5: On selectionne d'autres parents pour maintenir la diversité génétique
    #Cette selection se fait au hasard
    #Si la roulette sort une valeur inférieure à 0.05 alors on ajoute l'individus aux parents
    for individu in individus_classes[nombreElites:]:
        roulette = random.random()
        if roulette < 0.05:
            parents.append(individu)
    
   
    #6: Croisement des parents pour créer une nouvelle génération
    nombreDeParentsSelectionnes = len(parents)
    nombreEnfantsSouhaites = len(population)-nombreDeParentsSelectionnes
    
    
    #Le nombre de gènes du père sera égal à la longueur du code secret divisé par deux
    nombreGenesPere = len(codeSecret)//2
    
    #Le nombre de gènes de la mère sera égal à la longueur du mot - le nombre de gène du père
    nombreGenesMere = len(codeSecret)-nombreGenesPere
    

    #Tant que nous n'avons pas le nombre d'enfants souhaité,
    #On choisi 2 parents au hasard
    #On extrait les gènes du père en fonction du nombre déterminé précédemment
    #On extrait les gènes de la mère en fonction du nombre déterminé précédemment
    #On concatène les deux pour obtenir un enfant
    enfants = []
    while len(enfants) < nombreEnfantsSouhaites:
        pere = random.choice(parents)
        mere = random.choice(parents)
        enfant = pere[:nombreGenesPere] + mere[nombreGenesMere:]
        enfants.append(enfant)
        
    #Mutation génétique de certain enfants
    #Cette mutation se fait aussi au hasard
    #- Tant sur le choix de l'individu 
    #- Tant sur le gene à modifier
    for enfant in enfants :
        if random.random() < tauxMutation:
            indexGene = int(random.random()*(len(codeSecret)))
            enfant[indexGene] = generationGene()
        
    #Ajout des enfants à la liste des parents pour créer la population
    parents.extend(enfants)
    
    
    return parents,individu_gagnant

Recherche de la solution

In [200]:
CODE = "JoyeuXnoEl2019"
NOMBRE_INDIVIDUS = 100
POURCENTAGE_ELITE = 0.20 
TAUX_MUTATION =0.1

#On définit un maximum de générations pour éviter une boucle infinie dans le cas où aucune solution n'est trouvée
MAXIMUM_GENERATIONS = 10000

#Generation d'une population initiale
population = generationPopulation(NOMBRE_INDIVIDUS,CODE)

#Execution de l'algorithme génétique
i=0
individu_gagnant = None

while not individu_gagnant and i<MAXIMUM_GENERATIONS:
    population, individu_gagnant = generationFuture(population,POURCENTAGE_ELITE,TAUX_MUTATION,CODE)
    i = i+1
    
if individu_gagnant:
    print("Solution trouvée :"+str(individu_gagnant)+" Nb générations = "+str(i))
else:
    print("Pas de solution trouvée...")
    

Solution trouvée :[['J', 'o', 'y', 'e', 'u', 'X', 'n', 'o', 'E', 'l', '2', '0', '1', '9']] Nb générations = 249

Par ce petit exemple, nous venons de découvrir le principe de fonctionnement des algorithmes génétiques. Bien entendu la forme présentée de l'algorithme est assez simple. Il existe en effet de nombreuses fonctions de selections et de croisements d'individus pour lesquelles nous aurons l'occasion de revenir en détail dans un exemple plus complet trés prochainement.

In [ ]: