[Tutoriel/Python] Les algorithmes génétiques (garantis sans OGM)

Bonjour tout le monde !

Durant le WE, j’ai repris un projet datant du début de l’année, une « Word Clock » (« horloge à mots »), dans le même style que la Qlocktwo, mais en version DIY. Pour ce projet, j’avais besoin de résoudre un problème d’agencement de lettres dans une matrice de forme arbitraire.

Je vous passe les détails du problème qui n’ont rien à voir avec le sujet de cet article. Le plus important à savoir est que pour résoudre ce problème de manière « bourrin », en testant toutes les possibilités d’agencement des différents mots dans la matrice, il faudrait pas moins de 34 488 115 200 essais dans le pire des cas, soit environ 7h30 de calcul en utilisant la pleine puissance de mon ordinateur de travail / gaming.

Face à un tel nombre d’essais, je mettais résigné en début d’année à agencer la matrice manuellement sur une feuille de papier quadrillé. Dans les faits, il existe bien un algorithme permettant d’agencer ce genre de matrice de lettres, sans avoir à faire une montagne d’essais, mais il est très compliqué à implémenter logiciellement. Et même en agençant manuellement la matrice, il faut une quantité non négligeable d’échecs avant de trouver une solution. Manquant de temps à l’époque (et manquant toujours de temps aujourd’hui), j’ai décidé de changer de technique (je suis coriace).

Je me suis rappelé avoir lu un article il y a fort longtemps, où une personne avait réalisé le même type de projet que moi, mais avait utilisé un algorithme évolutionniste pour résoudre le problème d’agencement de la matrice. Grâce à l’ami Google, j’ai pu retrouver l’article en question assez rapidement.

Comme je n’aime pas exécuter un programme bêtement sans comprendre comment il marche, j’ai fait quelques recherches sur les algorithmes génétiques et je suis tombé sur un tutoriel en anglais des plus intéressant. Ni une ni deux, j’ai implémenté mon propre générateur de matrice, qui marche plutôt bien (même s’il reste quelques bugs à résoudre). Fort de ce succès, j’ai décidé de reprendre ce tutoriel en anglais, de l’enrichir et de le publier en français, pour votre plus grand bonheur 😉

---

Sommaire

• Qu’est ce qu’un algorithme génétique ?
• Qu’est ce qu’on peut faire avec ce genre d’algorithmes ?
• Quelle différence avec la programmation génétique ?
• Comment résoudre un problème comme un dieu ?
  • 1. Définir un problème à résoudre/optimiser
  • 2. Comprendre les termes liés aux AG
  • 3. Se prendre pour Charles Darwin
  • 4. Revenir sur terre et coder
• Code complet de l’exemple
• Conclusion

---

Qu’est-ce qu’un algorithme génétique ?

Avant de commencer, posons-nous la question suivante : Qu’est-ce qu’un algorithme génétique ?

Un GA (abréviation de « Genetic Algorithm ») est un type d’algorithmes un peu particulier, appartenant à la famille des algorithmes évolutionnistes. Le but des GA est de trouver une solution optimum à un problème, dans un temps raisonnable, en n’utilisant aucun algorithme précis.

L’énorme avantage des GA réside dans le fait que ceux-ci n’ont besoin que de deux choses pour fonctionner : une suite de tests permettant de déterminer la validité des résultats obtenus, et une structure de données (arbitraire) pour stocker les résultats.

Il est ainsi possible de demander à un GA de trouver une solution à un problème pour lequel on ne connait pas exactement la solution voulue (ou qu’il existe plusieurs solutions), comme c’est le cas avec mes matrices de lettres dont l’agencement final n’est pas connu à l’avance et n’est (surement) pas unique.

Le principe de fonctionnement des GA est d’une simplicité déconcertante.
Les GA utilisent la notion de sélection naturelle, pour ne garder que les meilleurs résultats à chaque étape de la recherche du résultat parfait.
Les bons résultats restent en mémoire, se reproduisent pour former de nouveaux résultats et les mauvais résultats disparaissent dans le néant informatique.
C’est ni plus ni moins que la « dure loi de la vie », en version informatique.

Quand on parle « d’algorithmes génétiques », on s’attend tout de suite à tomber dans des calculs compliqués en lien direct avec le concept d’intelligence artificielle. Mais non, c’est juste la forme la plus basique d’algorithme qu’on puisse imaginer.

Qu’est ce qu’on peut faire avec ce genre d’algorithme ?

Le domaine d’application des GA est extrêmement large. On peut les utiliser pour trouver une simple suite de nombre fournissant un résultat connu (qui vient de dire « on’va casser de la checksum avec ça » au fond de la salle ?) ou carrément les utiliser en duo avec un réseaux de neurones artificiels pour créer des robots capables de reconnaître des images (en ne conservant que les réseaux ayant un taux de détection le plus élevé).

Ce qu’il faut bien comprendre, c’est que les GA sont des algorithmes d’optimisation. Ce sont des algorithmes qui cherchent la meilleure solution possible à un problème connu.
Si vous demandez à un GA de reconnaître des images, ça ne marchera pas. Par contre, si vous demandez à un GA de sélectionner le réseau de neurones artificiel ayant les meilleures capacités de détection d’un lot d’images données, là ça marchera.

Quelle différence avec la programmation génétique ?

GA et GP (abréviation de « Genetic Programming ») sont deux applications des algorithmes évolutionnistes, dans deux buts bien distincts.

Avec un GA, on cherche une solution optimum à un problème donné.
Avec un GP, on cherche à générer un programme (et non une solution) permettant de résoudre un problème donné.
D’un côté, on génère une solution, de l’autre un programme.

Imaginons que vous vouliez écrire « Hello World! » en Brainfuck.
Cela pourrez vous prendre des années avant d’arriver à un tel résultat. Mais si vous êtes malin, vous pouvez réaliser un programme utilisant les techniques de GP pour générer un autre programme (en Brainfuck), capable d’afficher « Hello World! ».
C’est un peu l’idée derrière le paradoxe du singe savant, mais en version évolutionniste, pas juste aléatoire.

Pour résumer, GA = trouver une solution optimum à partir d’un jeu de données initiales (optionnel) et d’une suite de tests. GP = générer un programme capable de résoudre un problème donné en fonction d’une suite de tests.

Comment résoudre un problème comme un dieu ?

Afin de comprendre comment marche un GA et comment implémenter ce genre de bestiole, nous allons réaliser un exemple tout simple (et relativement idiot) en Python.
Dans cet article, j’utilise Python 3.4.3, pour les utilisateurs de Python 2.x, il est grand temps pour vous d’entrer dans le 21e siècle 😉

1. Définir un problème à résoudre/optimiser

Pour trouver une solution à un problème, il faut d’abord définir le problème.

Le problème sera le suivant : deviner la phrase « Fuck fucking fucked fucker fucking fuckups fuck fucking fucked fucking fuckup fucking fucker’s fucking fuckup. », grammaticalement parfaitement valide en langue anglaise, bien que particulièrement indigeste (la preuve ici).

Cet exemple est un peu idiot dans le sens ou l’on connait déjà la solution optimum au problème qui est … la phrase d’origine. Mais cet exemple est particulièrement intéressant pour comprendre le fonctionnement des GA.

Pour trouver cette phrase en utilisant un algorithme bête et méchant testant toutes les permutations de lettres possible, il faudrait 2.8392137667797144e+132 essais dans le pire des cas, 2 839 213 766 779 714 416 208 296 124 562 517 712 318 911 565 184 836 172 974 571 090 549 372 219 192 960 637 992 933 791 850 638 927 971 728 600 024 477 257 552 869 537 611 776 essais pour être précis. Outch.

Et je part du principe que seules les lettres « ‘kpceu.drFfg nsi » sont utilisées. En incluant toutes les minuscules, majuscules et les trois caractères  » ‘. », il faudrait 2.7535682435584903e+191 essais dans le pire des cas. Je ne vous donne pas le chiffre à rallonge exact 😉

2. Comprendre les termes liés aux AG

Pour bien comprendre la suite de cet article, il faut maîtriser un certain nombre de termes techniques.

Individu

Un individu n’est rien de plus qu’un résultat. Quand on parle d’un individu en GA/GP, on parle en réalité d’une instance de la structure de données contenant un résultat, qu’il soit optimum ou non.

Dans notre exemple, un individu n’est rien d’autre qu’une simple chaîne de caractère.

Population

Une population n’est rien de plus qu’une collection, un regroupement d’individus.

Génération

Une génération n’est rien de plus qu’une étape dans l’évolution d’une population. Comme dans la vraie vie.

Sélection

La phase de sélection est une étape clef dans le fonctionnement des GA. C’est cette étape qui attribue un score à chaque individu en fonction de son adaptation au problème donné. Ce score est nommé « fitness » (= « aptitude pour … ») et en fonction des scores obtenus par chaque individu de la population, certains seront conservés pour la génération suivante et d’autres retourneront dans le néant.

Croisement

Le croisement est une étape qui consiste à prendre deux individus différents et de les faire se reproduire pour générer de nouveau individu.

Dans notre exemple, le croisement consiste à prendre 50% de la chaîne 1 et 50% de la chaîne 2, pour créer un troisième chaîne de caractères.

Mutation

La mutation est une étape qui consiste à introduire aléatoire des modifications dans les constituants d’un individu.

Dans notre exemple, le mutation consiste à modifier un caractère aléatoirement quelque part dans la chaîne de caractères d’un individu.

3. Se prendre pour Charles Darwin

Charles Darwin, acteur majeur de la théorie de l’évolution a écrit que :

• Toute espèce a naturellement des variations aléatoires.
• Si cette variation est gênante pour l’animal il a de fortes chances de mourir précocement ou de ne pas trouver de partenaire sexuel. Ainsi sa descendance est infime ou nulle et la variation disparaît avec lui.
• Si une variation permet à des animaux de survivre à une crise écologique ou avoir plus de partenaires sexuels alors leur descendance sera plus nombreuse et la variation se diffuse.

Croisement / Mutation / Sélection, le compte est bon. 😉

4. Revenir sur terre et coder

Passons maintenant de la théorie à la pratique.

from random import random
from string import ascii_letters

On commence notre programme par deux imports de bibliothèques logicielles.
Nous aurons ainsi besoin de la bibliothèque « random », et en particulier de la fonction random(), pour générer des nombres aléatoires.
Nous aurons aussi besoin de la constante « ascii_letters » de la bibliothèque « string » qui contient toutes les lettres minuscules et majuscules de la table ASCII.

choice = lambda x: x[int(random() * len(x))]

On déclare ensuite une lambda (une fonction en une ligne), qui mime le comportement de la fonction choice() de la bibliothèque « random », mais plus simplement et plus rapidement (la vitesse d’exécution est importante pour ce genre de script).

EXPECTED_STR = "Fuck fucking fucked fucker fucking fuckups fuck fucking fucked fucking fuckup fucking fucker's fucking fuckup."

On déclare ensuite notre chaîne de caractères que le script devra deviner en un minimum de générations.

CHANCE_TO_MUTATE = 0.1
GRADED_RETAIN_PERCENT = 0.2
CHANCE_RETAIN_NONGRATED = 0.05

On déclare ensuite un pourcentage (entre 0.0 = 0% et 1.0 = 100%) qui déterminera la probabilité pour qu’un individu soit sujet à une mutation (CHANCE_TO_MUTATE).
De même que le pourcentage d’individus « hauts gradés » qui sera retenu pour la génération suivante (GRADED_RETAIN_PERCENT).
Pour finir, on déclare le pourcentage de chance pour qu’un individu « faiblement gradé » soit quand même retenu pour la génération suivante (CHANCE_RETAIN_NONGRATED).

Le fait de permettre à des individus faiblement gradés d’être retenus pour la génération suivante permet de réduire les chances de rester bloquer à un « extremum local » (en gros, de rester bloqué autour d’une valeur fixe qui n’est pas la valeur maximum souhaitée).

Les valeurs communes sont : 10% de chance de mutation, 20% de « hauts gradés » retenus, 5% de chance pour un individu faible d’être sauvé.

POPULATION_COUNT = 100

On déclare ensuite la taille de notre population d’individus. Une valeur de 100 individus donne des résultats satisfaisants pour cet exemple.

GENERATION_COUNT_MAX = 100000

On déclare aussi un nombre maximum de générations, pour stopper le script si aucune solution n’est trouvée à temps (sous-entendu, avant que le développeur du script ne s’impatiente).

GRADED_INDIVIDUAL_RETAIN_COUNT = int(POPULATION_COUNT * GRADED_RETAIN_PERCENT)

LENGTH_OF_EXPECTED_STR = len(EXPECTED_STR)

MIDDLE_LENGTH_OF_EXPECTED_STR = LENGTH_OF_EXPECTED_STR // 2

ALLOWED_CHARMAP = ascii_letters + ' !\'.'

MAXIMUM_FITNESS = LENGTH_OF_EXPECTED_STR

On déclare ensuite un certain nombre de constantes pour le reste du script.

• Le nombre d’individus « hauts gradés » à retenir (GRADED_INDIVIDUAL_RETAIN_COUNT).
• La taille de la chaîne de caractères à deviner (LENGTH_OF_EXPECTED_STR).
• La moitié de la taille de la chaîne de caractères à deviner (MIDDLE_LENGTH_OF_EXPECTED_STR).
• La liste des caractères autorisés (ALLOWED_CHARMAP).
• Et pour finir, la valeur maximum du score qu’un individu peut obtenir (MAXIMUM_FITNESS).

Maintenant que les constantes du programme sont déclarées, on peut commencer le gros du travail.

def get_random_char():
    """ Return a random char from the allowed charmap. """
    return choice(ALLOWED_CHARMAP)

On commence par déclarer une fonction get_random_char() qui retourne un caractère aléatoire, tiré de la liste des caractères autorisés.

def get_random_individual():
    """ Create a new random individual. """
    return [get_random_char() for _ in range(LENGTH_OF_EXPECTED_STR)]

On continu ensuite en déclarant une fonction get_random_individual() qui retourne un individu (un tableau de caractères) constitué de caractères aléatoires générés par la fonction get_random_char().
N.B. J’utilise un tableau de caractères, et non une chaîne de caractères, car celles-ci sont immuables (non modifiables), contrairement aux tableaux.

def get_random_population():
    """ Create a new random population, made of `POPULATION_COUNT` individual. """
    return [get_random_individual() for _ in range(POPULATION_COUNT)]

On monte encore d’un niveau, en déclarant cette fois une fonction retournant une liste d’individus aléatoires qui constituera notre population.

def get_individual_fitness(individual):
    """ Compute the fitness of the given individual. """
    fitness = 0
    for c, expected_c in zip(individual, EXPECTED_STR):
        if c == expected_c:
            fitness += 1
    return fitness

Maintenant que nous disposons des structures de données pour les différentes étapes, il nous faut une fonction pour juger le niveau d’adaptation d’un individu à notre problème.
En gros, il nous faut une fonction qui calcule la valeur « fitness » d’un individu passé en argument.

Dans notre exemple, cette valeur « fitness » est assez simple à calculer. Pour chaque caractère au bon endroit (= au même endroit dans la chaîne de caractères recherchés et dans le tableau), on incrémente fitness de 1.
Dans un code plus « utile », cette fonction est en générale bien plus complexe. Par exemple, dans mon code pour mes matrices de lettres, cette fonction calcule la valeur de fitness d’un individu au moyen de 335 tests.

Il est impératif que cette fonction s’exécute le plus vite possible, car le script passe le plus clair de son temps dans cette fonction.

def average_population_grade(population):
    """ Return the average fitness of all individual in the population. """
    total = 0
    for individual in population:
        total += get_individual_fitness(individual)
    return total / POPULATION_COUNT

Pour des raisons de statistiques, on aura aussi besoin d’une fonction retournant la valeur moyenne de fitness d’une population.

def grade_population(population):
    """ Grade the population. Return a list of tuple (individual, fitness) sorted from most graded to less graded. """
    graded_individual = []
    for individual in population:
        graded_individual.append((individual, get_individual_fitness(individual)))
    return sorted(graded_individual, key=lambda x: x[1], reverse=True)

On aura aussi besoin d’une fonction jugeant une population, individu par individu et classant chaque individu du plus adapté ou moins adapté en fonction des scores obtenus par chacun.
Cette fonction retourne une liste de tuple(individu, fitness), trié par ordre décroissant de fitness.

def evolve_population(population):
    """ Make the given population evolving to his next generation. """

    # Get individual sorted by grade (top first), the average grade and the solution (if any)
    raw_graded_population = grade_population(population)
    average_grade = 0
    solution = []
    graded_population = []
    for individual, fitness in raw_graded_population:
        average_grade += fitness
        graded_population.append(individual)
        if fitness == MAXIMUM_FITNESS:
            solution.append(individual)
    average_grade /= POPULATION_COUNT

    # End the script when solution is found
    if solution:
        return population, average_grade, solution    

    # Filter the top graded individuals
    parents = graded_population[:GRADED_INDIVIDUAL_RETAIN_COUNT]

    # Randomly add other individuals to promote genetic diversity
    for individual in graded_population[GRADED_INDIVIDUAL_RETAIN_COUNT:]:
        if random() < CHANCE_RETAIN_NONGRATED:
            parents.append(individual)

    # Mutate some individuals
    for individual in parents:
        if random() < CHANCE_TO_MUTATE:
            place_to_modify = int(random() * LENGTH_OF_EXPECTED_STR)
            individual[place_to_modify] = get_random_char()

    # Crossover parents to create children
    parents_len = len(parents)
    desired_len = POPULATION_COUNT - parents_len
    children = []
    while len(children) < desired_len:
        father = choice(parents)
        mother = choice(parents)
        if True: #father != mother:
            child = father[:MIDDLE_LENGTH_OF_EXPECTED_STR] + mother[MIDDLE_LENGTH_OF_EXPECTED_STR:]
            children.append(child)

    # The next generation is ready
    parents.extend(children)
    return parents, average_grade, solution

La dernière étape de notre aventure consiste à déclarer une « super fonction » permettant de faire évoluer une population de la génération n à la génération n+1.
C’est LA fonction clef du système, sans elle, ce script n’est rien de plus qu’une recherche aléatoire.
Cette fonction étant particulièrement longue, je vais la découper en morceau et expliquer chaque morceau individuellement.

N.B. Cette fonction n’est volontairement pas découpée en sous-fonctions de plus petite taille afin d’éviter un nombre conséquent d’appels de fonction, appels qui sont très lents en Python.

    # Get individual sorted by grade (top first), the average grade and the solution (if any)
    raw_graded_population = grade_population(population)
    average_grade = 0
    solution = []
    graded_population = []
    for individual, fitness in raw_graded_population:
        average_grade += fitness
        graded_population.append(individual)
        if fitness == MAXIMUM_FITNESS:
            solution.append(individual)
    average_grade /= POPULATION_COUNT

La première étape de la fonction d’évolution consiste à juger chaque individu de la population.
Plus tard, nous aurons aussi besoin de la valeur moyenne de fitness de la population et d’une liste d’individus ayant abouti à la réponse optimum pour le problème donné.
Tout ceci est faisable en une fois, avec une simple boucle qui calcul la valeur moyenne de fitness, cherche les individus optimums et génère une liste triée des individus « hauts gradés », du plus haut gradé au moins gradé.

    # End the script when solution is found
    if solution:
        return population, average_grade, solution

Si un individu (ou plus) de notre population a atteint le stade ultime d’optimisation. Jackpot. On retourne la population telle quelle sans la faire évoluer, avec en prime la valeur moyenne de fitness et la liste des individus ayant atteint le niveau ultime d’optimisation.

    # Filter the top graded individuals
    parents = graded_population[:GRADED_INDIVIDUAL_RETAIN_COUNT]

Si aucun individu n’a atteint le stade ultime d’optimisation, on garde seulement les plus hauts gradés de la population actuelle.

    # Randomly add other individuals to promote genetic diversity
    for individual in graded_population[GRADED_INDIVIDUAL_RETAIN_COUNT:]:
        if random() < CHANCE_RETAIN_NONGRATED:
            parents.append(individual)

Et on ajoute quelques individus chanceux dans le lot.
La liste d’individus ainsi obtenue constituera la base de la prochaine génération d’individus.

N.B. Pour les débutants en syntaxe Python : « azerty »[2:] retourne « erty » (de l’index 2 jusqu’à la fin), « azerty »[:2] retourne « az » (de l’index 0 jusqu’à 2) et « azerty »[2:4] retourne « er » (de l’index 2 jusqu’à 4). En Python, on appelle cela du slicing (= « découpage »).

    # Mutate some individuals
    for individual in parents:
        if random() < CHANCE_TO_MUTATE:
            place_to_modify = int(random() * LENGTH_OF_EXPECTED_STR)
            individual[place_to_modify] = get_random_char()

Une fois que nous avons notre liste d’heureux élus, nous faisons subir des mutations aléatoires à certains des individus dans la liste.

    # Crossover parents to create children
    parents_len = len(parents)
    desired_len = POPULATION_COUNT - parents_len
    children = []
    while len(children) < desired_len:
        father = choice(parents)
        mother = choice(parents)
        if True: #father != mother:
            child = father[:MIDDLE_LENGTH_OF_EXPECTED_STR] + mother[MIDDLE_LENGTH_OF_EXPECTED_STR:]
            children.append(child)

La dernière étape consiste à remplir notre population avec de nouveaux individus, obtenus en croisant aléatoirement les individus de la liste afin d’obtenir une population de taille fixe.

N.B. J’ai commenté le « if father != mother », car celui-ci génère une boucle infinie. C’est normalement le signe que la population est trop petite ou que le pourcentage de « hauts gradés » conservés entre chaque génération est trop élevé. Mais comme j’avais la flemme de trouver le bon pourcentage/nombre d’individus pour cet exemple … voilà.

PS Théoriquement, l’étape de mutation devrait se faire après l’étape de croisement, mais dans la pratique, cela ralentit considérablement la recherche de la solution optimum. Pourquoi, je ne sais pas.

    # The next generation is ready
    parents.extend(children)
    return parents, average_grade, solution

On conclut la fonction d’évolution par un joli return avec notre population fraîchement généré et voilà.

def main():
    """ Main function. """

    # Create a population and compute starting grade
    population = get_random_population()
    average_grade = average_population_grade(population)
    print('Starting grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

    # Make the population evolve
    i = 0
    solution = None
    log_avg = []
    while not solution and i < GENERATION_COUNT_MAX:
        population, average_grade, solution = evolve_population(population)
        if i & 255 == 255:
            print('Current grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS, '(%d generation)' % i)
        if i & 31 == 31:
            log_avg.append(average_grade)
        i += 1

    import pygal
    line_chart = pygal.Line(show_dots=False, show_legend=False)
    line_chart.title = 'Fitness evolution'
    line_chart.x_title = 'Generations'
    line_chart.y_title = 'Fitness'
    line_chart.add('Fitness', log_avg)
    line_chart.render_to_file('bar_chart.svg')
    
    # Print the final stats
    average_grade = average_population_grade(population)
    print('Final grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

    # Print the solution
    if solution:
        print('Solution found (%d times) after %d generations.' % (len(solution), i))
    else:
        print('No solution found after %d generations.' % i)
        print('- Last population was:')
        for number, individual in enumerate(population):
            print(number, '->',  ''.join(individual))

Il ne reste plus qu’à mettre toutes ces jolies fonctions en marche avec un morceau de code pour l’affichage.
Comme c’est là aussi une fonction assez lourde, je vais commenter le code bloc par bloc.

    # Create a population and compute starting grade
    population = get_random_population()
    average_grade = average_population_grade(population)
    print('Starting grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

Tout d’abord on génère une nouvelle population et on calcule sa valeur moyenne de fitness au départ.

    # Make the population evolve
    i = 0
    solution = None
    log_avg = []
    while not solution and i < GENERATION_COUNT_MAX:
        population, average_grade, solution = evolve_population(population)
        if i & 255 == 255:
            print('Current grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS, '(%d generation)' % i)
        if i & 31 == 31:
            log_avg.append(average_grade)
        i += 1

On fait ensuite une boucle tant qu’aucune solution n’a été découverte et que le nombre de générations est inférieur à la limite fixée en début de script.

Vous remarquerez que toutes les 255 générations, j’affiche la valeur moyenne de fitness de la population sur la console pour pouvoir suivre l’évolution de l’algorithme.
Vous remarquerez aussi que toutes les 31 générations, je stocke en mémoire la valeur moyenne de fitness de la population pour tracer un graphique d’évolution dans le bloc de code suivant.

    import pygal
    line_chart = pygal.Line(show_dots=False, show_legend=False)
    line_chart.title = 'Fitness evolution'
    line_chart.x_title = 'Generations'
    line_chart.y_title = 'Fitness'
    line_chart.add('Fitness', log_avg)
    line_chart.render_to_file('bar_chart.svg')

Pour tracer le graphique en question, j’utilise la bibliothèque Python pygal, qui génère des fichiers SVG interactif vraiment sympathique.
Je recommande cette bibliothèque à tous ceux qui veulent tracer des graphiques pour le web (mais pas seulement, pygal peut aussi générer des images PNG).

    # Print the final stats
    average_grade = average_population_grade(population)
    print('Final grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

J’affiche ensuite sur la console la valeur moyenne de fitness de la dernière population en fin d’exécution du script.

    # Print the solution
    if solution:
        print('Solution found (%d times) after %d generations.' % (len(solution), i))
    else:
        print('No solution found after %d generations.' % i)
        print('- Last population was:')
        for number, individual in enumerate(population):
            print(number, '->',  ''.join(individual))

J’affiche aussi le nombre de fois que la chaîne de caractères a été devinée.
Et dans le cas ou le script n’aurait pas deviné la phrase, j’affiche la dernière population générée pour voir si le script été proche ou non de la solution.

if __name__ == '__main__':
    main()

Le script se termine avec le classique if __name__ == ‘__main__’, qui permet l’exécution du script en console, ou son utilisation directe en tant que bibliothèque logicielle.

Code complet de l’exemple

"""
Simple genetic algorithm guessing a string.
"""

# ----- Dependencies

from random import random
from string import ascii_letters

# One-linner for randomly choose a element in an array
# This one-linner is fastest than random.choice(x).
choice = lambda x: x[int(random() * len(x))]

# ----- Runtime configuration (edit at your convenience)

# Enter here the string to be searched
EXPECTED_STR = "Fuck fucking fucked fucker fucking fuckups fuck fucking fucked fucking fuckup fucking fucker's fucking fuckup."

# Enter here the chance for an individual to mutate (range 0-1)
CHANCE_TO_MUTATE = 0.1

# Enter here the percent of top-grated individuals to be retained for the next generation (range 0-1)
GRADED_RETAIN_PERCENT = 0.2

# Enter here the chance for a non top-grated individual to be retained for the next generation (range 0-1)
CHANCE_RETAIN_NONGRATED = 0.05

# Number of individual in the population
POPULATION_COUNT = 100

# Maximum number of generation before stopping the script
GENERATION_COUNT_MAX = 100000

# ----- Do not touch anything after this line

# Number of top-grated individuals to be retained for the next generation
GRADED_INDIVIDUAL_RETAIN_COUNT = int(POPULATION_COUNT * GRADED_RETAIN_PERCENT)

# Precompute the length of the expected string (individual are always fixed size objects)
LENGTH_OF_EXPECTED_STR = len(EXPECTED_STR)

# Precompute LENGTH_OF_EXPECTED_STR // 2
MIDDLE_LENGTH_OF_EXPECTED_STR = LENGTH_OF_EXPECTED_STR // 2

# Charmap of all allowed characters (A-Z a-z, space and !)
ALLOWED_CHARMAP = ascii_letters + ' !\'.'

# Maximum fitness value
MAXIMUM_FITNESS = LENGTH_OF_EXPECTED_STR

# ----- Genetic Algorithm code
# Note: An individual is simply an array of LENGTH_OF_EXPECTED_STR characters.
# And a population is nothing more than an array of individuals.

def get_random_char():
    """ Return a random char from the allowed charmap. """
    return choice(ALLOWED_CHARMAP)
    

def get_random_individual():
    """ Create a new random individual. """
    return [get_random_char() for _ in range(LENGTH_OF_EXPECTED_STR)]


def get_random_population():
    """ Create a new random population, made of `POPULATION_COUNT` individual. """
    return [get_random_individual() for _ in range(POPULATION_COUNT)]


def get_individual_fitness(individual):
    """ Compute the fitness of the given individual. """
    fitness = 0
    for c, expected_c in zip(individual, EXPECTED_STR):
        if c == expected_c:
            fitness += 1
    return fitness


def average_population_grade(population):
    """ Return the average fitness of all individual in the population. """
    total = 0
    for individual in population:
        total += get_individual_fitness(individual)
    return total / POPULATION_COUNT


def grade_population(population):
    """ Grade the population. Return a list of tuple (individual, fitness) sorted from most graded to less graded. """
    graded_individual = []
    for individual in population:
        graded_individual.append((individual, get_individual_fitness(individual)))
    return sorted(graded_individual, key=lambda x: x[1], reverse=True)


def evolve_population(population):
    """ Make the given population evolving to his next generation. """

    # Get individual sorted by grade (top first), the average grade and the solution (if any)
    raw_graded_population = grade_population(population)
    average_grade = 0
    solution = []
    graded_population = []
    for individual, fitness in raw_graded_population:
        average_grade += fitness
        graded_population.append(individual)
        if fitness == MAXIMUM_FITNESS:
            solution.append(individual)
    average_grade /= POPULATION_COUNT

    # End the script when solution is found
    if solution:
        return population, average_grade, solution    

    # Filter the top graded individuals
    parents = graded_population[:GRADED_INDIVIDUAL_RETAIN_COUNT]

    # Randomly add other individuals to promote genetic diversity
    for individual in graded_population[GRADED_INDIVIDUAL_RETAIN_COUNT:]:
        if random() < CHANCE_RETAIN_NONGRATED:
            parents.append(individual)

    # Mutate some individuals
    for individual in parents:
        if random() < CHANCE_TO_MUTATE:
            place_to_modify = int(random() * LENGTH_OF_EXPECTED_STR)
            individual[place_to_modify] = get_random_char()

    # Crossover parents to create children
    parents_len = len(parents)
    desired_len = POPULATION_COUNT - parents_len
    children = []
    while len(children) < desired_len:
        father = choice(parents)
        mother = choice(parents)
        if True: #father != mother:
            child = father[:MIDDLE_LENGTH_OF_EXPECTED_STR] + mother[MIDDLE_LENGTH_OF_EXPECTED_STR:]
            children.append(child)

    # The next generation is ready
    parents.extend(children)
    return parents, average_grade, solution


# ----- Runtime code

def main():
    """ Main function. """

    # Create a population and compute starting grade
    population = get_random_population()
    average_grade = average_population_grade(population)
    print('Starting grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

    # Make the population evolve
    i = 0
    solution = None
    log_avg = []
    while not solution and i < GENERATION_COUNT_MAX:
        population, average_grade, solution = evolve_population(population)
        if i & 255 == 255:
            print('Current grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS, '(%d generation)' % i)
        if i & 31 == 31:
            log_avg.append(average_grade)
        i += 1

    import pygal
    line_chart = pygal.Line(show_dots=False, show_legend=False)
    line_chart.title = 'Fitness evolution'
    line_chart.x_title = 'Generations'
    line_chart.y_title = 'Fitness'
    line_chart.add('Fitness', log_avg)
    line_chart.render_to_file('bar_chart.svg')
    
    # Print the final stats
    average_grade = average_population_grade(population)
    print('Final grade: %.2f' % average_grade, '/ %d' % MAXIMUM_FITNESS)

    # Print the solution
    if solution:
        print('Solution found (%d times) after %d generations.' % (len(solution), i))
    else:
        print('No solution found after %d generations.' % i)
        print('- Last population was:')
        for number, individual in enumerate(population):
            print(number, '->',  ''.join(individual))


if __name__ == '__main__':
    main()

Conclusion

Je vais conclure cet article sur les algorithmes génétiques avec un exemple d’exécution du script ci dessus.
J’espère que cet article vous en aura appris un peu plus sur les algorithmes génétiques et aura attisé votre curiosité sur le sujet 😉

PS Si jamais une boulette s’est glissé dans mon code ou dans l’article, n’hésitez pas à me le faire savoir dans les commentaires.

Starting grade: 1.71 / 110
Current grade: 17.00 / 110 (255 generation)
Current grade: 23.21 / 110 (511 generation)
Current grade: 36.98 / 110 (767 generation)
Current grade: 43.91 / 110 (1023 generation)
Current grade: 50.95 / 110 (1279 generation)
Current grade: 57.00 / 110 (1535 generation)
Current grade: 61.95 / 110 (1791 generation)
Current grade: 65.90 / 110 (2047 generation)
Current grade: 68.76 / 110 (2303 generation)
Current grade: 77.87 / 110 (2559 generation)
Current grade: 82.89 / 110 (2815 generation)
Current grade: 85.91 / 110 (3071 generation)
Current grade: 86.81 / 110 (3327 generation)
Current grade: 86.80 / 110 (3583 generation)
Current grade: 88.94 / 110 (3839 generation)
Current grade: 89.95 / 110 (4095 generation)
Current grade: 90.92 / 110 (4351 generation)
Current grade: 93.83 / 110 (4607 generation)
Current grade: 94.83 / 110 (4863 generation)
Current grade: 95.95 / 110 (5119 generation)
Current grade: 97.97 / 110 (5375 generation)
Current grade: 98.80 / 110 (5631 generation)
Current grade: 99.00 / 110 (5887 generation)
Current grade: 101.76 / 110 (6143 generation)
Current grade: 101.84 / 110 (6399 generation)
Current grade: 102.90 / 110 (6655 generation)
Current grade: 102.88 / 110 (6911 generation)
Current grade: 103.75 / 110 (7167 generation)
Current grade: 103.93 / 110 (7423 generation)
Current grade: 103.95 / 110 (7679 generation)
Current grade: 105.90 / 110 (7935 generation)
Current grade: 105.78 / 110 (8191 generation)
Current grade: 105.85 / 110 (8447 generation)
Current grade: 106.88 / 110 (8703 generation)
Current grade: 107.00 / 110 (8959 generation)
Current grade: 106.85 / 110 (9215 generation)
Current grade: 106.85 / 110 (9471 generation)
Current grade: 107.00 / 110 (9727 generation)
Current grade: 107.95 / 110 (9983 generation)
Current grade: 107.85 / 110 (10239 generation)
Current grade: 107.85 / 110 (10495 generation)
Current grade: 107.83 / 110 (10751 generation)
Current grade: 108.97 / 110 (11007 generation)
Current grade: 108.92 / 110 (11263 generation)
Current grade: 108.94 / 110 (11519 generation)
Current grade: 108.84 / 110 (11775 generation)
Final grade: 109.02 / 110
Solution found (7 times) after 11962 generations.

Seulement 11 962 générations pour deviner (sept fois !) la chaîne de caractères. Ce n’est vraiment pas mal comparé au 2.7535682435584903e+191 essais qu’aurait demandé un algorithme de type force brute.

On voit clairement l’intérêt des GA en regardant le graphique de la valeur moyenne de fitness en fonction du temps 😉