Principes

Comme leur nom l'indique, les AGs ont certains points communs avec la génétique en biologie.

Un individu est un ensemble de données concaténées, chacune de ses données représente un gène.

L'ensemble des individus représente la population, tandis que chacune des populations (une par étape de l'algorithme est une génération.

D'une génération à l'autre, l'individu le plus apte à répondre à la problématique est conservé tandis que les autres sont obtenus via le croisement des individus de la génération précédente. Au terme de ces croisements, des modifications peuvent avoir lieu: les mutations.

Objectif

A la fin de ce cours, votre code sera capable de trouver, de lui-même, une chaîne de caractères définie. Bien sûr, l'utilité est faible, mais il s'agit de pouvoir traiter ensuite toute sorte de données, comme par exemple, utiliser l'AG pour estimer une courbe à partir d'un ensemble de points fournis.

Pour ce cours, le code devra retrouver la chaîne de caractères "Hello World".

Description

Pour fonctionner, l'AG a besoin:

• d'une fonction d'évaluation permettant d'indiquer la proximité ou l'erreur entre l'individu et la solution optimale. Dans notre cas, la distance entre chaque caractère sera utilisée, la fonction d'évaluation pour une distance optimale vaudra donc 0.
• d'une fonction de croisement qui permet d'obtenir une nouvelle génération à partir d'une génération pré-existante, prenant une partie de deux individus pour en former un nouveau, et ce pour l'ensemble de la population.
• de paramètres de mutation, indiquant les chances pour un nouvel individu d'être altéré, et la force de cette altération.

Création des méthodes

Avant le code :

# Imports
import random
import time
import string

# Le mot à trouver
target = "Hello World"

1/ Calcul de distance et localisation du meilleur individu

Avant toute chose, il faut réfléchir à la manière de représenter nos données.

Nous traiterons des chaînes de caractères. En Python, une chaîne de caractères fonctionne (presque) exactement comme une liste de caractères, et ces caractères peuvent être remplacés par leur code ASCII, qui est numérique.

Comme dit précédemment, nous allons définir notre individu cible comme la liste des codes ASCII de "H", "e", "l", "l", ... "d", qui aura comme distance 0.

Puisque nous avons les codes ASCII des caractères à disposition, il est simple de trouver, pour chaque indice de la liste, la distance entre le caractère cible et le caractère courant, qui n'est rien de plus qu'une simple différence. De même, la distance globale de la chaîne est une somme des distances.

Une fois les distances d'un ensemble de chaînes obtenues, celles-ci peuvent être ordonnées.

# Conversion d'une chaîne de caractères en liste de valeurs ASCII
def string_to_int_list(string):
    return [ord(character) for character in list(string)]

# La fonction de cacul de distance entre deux mots
def get_distance(mot1, mot2):
    motListe1 = string_to_int_list(mot1)
    motListe2 = string_to_int_list(mot2)
    liste = []
    for i in range(len(motListe1)):
        liste.append(abs(motListe1[i] - motListe2[i]))
    
    return sum(liste)

# La fonction permettant de retrouver le mot le plus proche d'une cible
def get_best(mot, listeCible):
    if (len(listeCible) > 0):
        motProche = listeCible[0]
        distanceMotProche = get_distance(mot, listeCible[0])
        for i in range(len(listeCible)):
            if (get_distance(mot, listeCible[i]) < distanceMotProche):
                motProche = listeCible[i]
                distanceMotProche = get_distance(mot, listeCible[i])
                
        return motProche, distanceMotProche
    else:
       
        return "", -1

2/ Création d'une première génération

Bien que nous connaissions le mot cible, nous partirons d'une population constituée d'un ensemble de mots générés aléatoirement.

Gardez à l'esprit que la taille de votre population définira la vitesse d'exécution de votre code. Ainsi, bien qu'un ensemble d'individus important aura la diversité pour atteindre rapidement (en termes d'itérations) la solution, un ensemble plus restreint passera chacune des itérations rapidement.

# Générer une chaîne aléatoire de longueur fixe
def word_list_init(tailleListe , longueurMot):
    listeMot = []
    for i in range(tailleListe):
        listeMot.append("".join([chr(random.randint(97, 122)) for j in range(longueurMot)]))
        
    return listeMot

3/ Passage d'une génération à une autre

Les opérations de base sont maintenant établies, il est temps de rendre notre système évolutif.

D'une génération à l'autre, les individus doivent évoluer. Mais, il n'est pas certain que cette évolution se fasse dans la direction espérée.

La théorie de l'évolution dans le domaine biologique indique que l'espèce la plus adaptée à son environnement survivra plus probablement que d'autres. Dans notre cas, nous pouvons discerner l'individu le plus proche de la solution et le conserver (il "survit"). Ainsi, le meilleur individu d'une génération ne peut pas être moins adapté que celui d'une génération passée (principe de non-régression).

Le reste de la population de la nouvelle génération est produite comme dans le cas de la biologie. Deux parties complémentaires (chromosomes) de deux individus (parents) seront combinées pour obtenir un nouvel individu (enfant).

# Fonction permettant de généer un nouveau mot à partir de deux autres
def crossover(mot1, mot2):
    motFinal = ""
    milieu = int(len(mot1)/2)
    for i in range(len(mot1)):
        if i < milieu:
            motFinal = motFinal + mot1[i]
        else:
            motFinal = motFinal + mot2[i]
    
    return motFinal

# Fonction permettant de généer une nouvelle génération
def new_generation(listeInitial):
    newGenerationListe = []
    meilleur, distance = get_best(target, listeInitial)
    newGenerationListe.append(meilleur)
    for i in range(len(listeInitial)-1):
        motAlea1 = listeInitial[random.randint(0, len(listeInitial)-1)]
        motAlea2 = listeInitial[random.randint(0, len(listeInitial)-1)]
        newGenerationListe.append(crossover(motAlea1, motAlea2))
        
    return newGenerationListe

4/ Créer la diversité génétique

Le principe de mutation permet d'ajouter de la diversité lors de l'évolution de l'AG. En effet, avec une faible population, il est presque certain que le croisement normal d'éléments finisse dans une impasse, on parle de minimum local.

Dans notre cas, la notion de minimum local n'a pas véritable lieu d'être. Il nous suffit d'ajouter de nouveaux éléments innovants pour permettre à l'AG de reprendre son évolution.

Cette innovation prend la forme d'une altération d'un (ou plusieurs) caractère(s) d'un individu lors de sa création pour une nouvelle génération. Pour s'assurer que l'on ne dégrade pas le meilleur individu, il est conseillé de lui éviter cette étape.

La mutation est définie suivant deux paramètres principaux. Tout d'abord, sa probabilité, entre 0 et 1, définit sa fréquence. Aussi, sa force définit l'effet de la mutation, et peut prendre n'importe quelle forme, de +1/-1 à une réaffectation aléatoire. Cette mutation peut s'appliquer lettre par lettre, sur le mot entier, ou sur un ensemble de lettres aléatoires.

# Fonction permettant de réaliser la mutation d'une liste de mots
def mutation(liste):
    listeFinal = []
    meilleur, distance = get_best(target, liste)
    listeFinal.append(meilleur)
    liste.remove(meilleur)
    for i in range(len(liste)):
        item = liste[i]
        if(random.randint(0,1)):
            position = random.randint(0, len(item)-1)
            codeAscii = ord(item[position]) + random.randint(-1, 1)
            if codeAscii < 0:
                codeAscii = 0
            if codeAscii > 255:
                codeAscii = 255
            item = item[:position] + chr(codeAscii) + item[position+1:]
            listeFinal.append(item)
        else:
            listeFinal.append(item)
            
    return listeFinal

Le bloc suivant vous permet de tester l'exécution de votre code dans les conditions de test finales.

# Espace de test et d'exécution final
test_length = 20
target = "Hello word"
print([target])

start = time.time()
ended_amount = 0

distance = 0
list_best = []

while time.time() - start < 900:
    population = word_list_init(6,test_length)
    meilleur, distance = get_best(target, population)
    
    while distance > 0:
        population = new_generation(mutation(population))
        meilleur, distance = get_best(target, population)
        print("La distance est : " + str(distance) + " " + meilleur)
        if time.time() - start > 900:
            break
        if distance == 0:
            print(meilleur)
            break
    break
    ended_amount += 1
    print("Finished ", ended_amount, "times.")    
    
print("After 15 minutes, finished", ended_amount, "times and stopped with a distance of", distance)