Algorithme Génétique

En Machine Learning, il est fréquent d’utiliser des modèles pour résoudre les problèmes de régression ou de classification. Des modèles tels que K-Nearest Neighbors (KNN), K-Means (Clustering) utilisent des paramètres qui impactent fortement la solution du modèle utilisé.
Afin de mieux choisir ces paramètres et avoir ainsi des performances optimales pour nos modèles, nous utilisons des algorithmes d’optimisation dont l’Algorithme Génétique (Genetic Algorithm pour les anglo-saxons 🙃).
Dans cet article, je décris d’une part l’Algorithme Génétique, d’autre part je présente un exemple de son utilisation.

C’est quoi l’Algorithme Génétique ? 🧬

L’Algorithme Génétique est un algorithme d’optimisation qui s’inspire du processus d’évolution des êtres vivants (coucou 👋 les dinosaures 🦕). Il fut développé par le scientifique américain John Henry Holland dans les années 1970.

En recherche opérationnelle, l’Algorithme Génétique est une métaheuristique de la grande famille des algorithmes d’évolution (Evolutionary Algorithms) qui offrent l’avantage de fournir des solutions de très grande qualité en un temps raisonnable ; l’inconvénient est qu’il n’y a aucune garantie que la solution soit l’optimum global.

Les principes de l’Algorithme Génétique ⚙️

• L’Algorithme Génétique se base au départ sur une population de solutions candidates appelées parfois individus, créatures, phénotypes qui va évoluer de génération en génération jusqu’à la génération qui contient les meilleures solutions.
• Chaque individu comprend des propriétés et il peut être sujet à des transformations génétiques (mutation, croisement par exemple).
• Chaque individu est évalué et cette valeur d’aptitude (fitness value) est un critère pour sa survie d’une génération à une autre.

Voyons tout cela par un exemple (🤠 c’est encore plus simple comme ça). Prenons l’exemple du problème célèbre de l’emplacement de hubs (Hub Location Problem HLP dans la littérature).

C’est quoi le HLP ? 🤔

Le HLP est un problème que rencontre la plupart des entreprises qui font de la logistique.

Nous avons un graphe formé de sites de stockage dans lequel des marchandises transitent d’un site A vers un site B. Chaque site a une capacité de stockage et il y a des coûts d’acheminement d’un site A vers un site B.
Dans ce problème (suivre ce lien), l’objectif est de minimiser les coûts de logistique (transit + stockage) en définissant certains sites comme des hubs (les autres sont considérés évidemment comme des spokes).

Pour résoudre ce problème, nous suivrons les principes de l’Algorithme Génétique suivant les étapes du schéma ci-dessous :

0. Représentation de la solution 💡

Pour le problème auquel nous faisons face, il convient de faire un représentation de la solution. Nous pouvons avoir des solutions de type vecteurs, matrices, ou encore d’autres structures de données.
Dans notre cas, nous optons pour une séquence de Prüfer de type vecteur qui convient pour représenter les structures d’arbres où les nœuds sont numérotés.

1. Définition de la population 👥👥👥

Une méthode simple consiste à définir la population par la permutation. Afin de prendre en compte tous les individus possibles, cette population se compose de toutes les permutations de la séquence de Prüfer de longueur 6. Donc on aura 6⁸ (8 nœuds) soit plus d’un million d’individus dès le départ.

2. Évaluation : calcul de la valeur du fitness 🧮

Cette étape consiste à définir la fonction objective de notre problème. L’objectif étant de minimiser le coût total, ainsi la fonction objective s’écrit comme suit :

3. Sélection 🎲

Après avoir constitué notre population (plus d’un million d’individus), il serait impossible à l’échelle (pour un grand réseau : complexité O(n^m)) d’utiliser toute cette population pour l’algorithme. Nous définissons donc un nombre d’individus que nous voulons avoir par génération. Pour ce faire, nous utilisons des méthodes aléatoires comme le Tournament Selection.
Cette méthode consiste à sélectionner, parmi une liste d’individus extraits de la population, l’individu ayant le meilleur fitness.

def tournamentSelection(generation, Ntour):
    """
    Permet le choix aléatoire de meilleurs individus de la génération.

    @parameters:
        generation: une liste de tuples (individu, fitnessValue)
        Ntour: un entier (integer)

    @return:
        populationSelection: une liste
    """

    populationSelection = [] # Création de notre variable de sortie

    for i in range(len(generation)):
        populationRandom = [] # Création de notre liste de sélection aléatoire

        for j in range(Ntour):
            populationRandom.append(generation[random.randrange(len(generation))]) # On choisit aléatoirement des 
# individus de la génération
        
        populationRandom = sorted(populationRandom, key=lambda x: x[1]) # Trier en fonction de la valeur du fitness
        populationSelection.append(populationRandom[0]) # Ajouter à notre variable de sortie l'individu ayant le 
# meilleur fitness

    populationSelection = sorted(populationSelection, key=lambda x: x[1]) # Trier en fonction du fitness
    a = populationSelection[:] # Faire une copie de la variable de sortie
    for i in range(len(a)):
        populationSelection[i] = a[i][0] # On choisit l'individu sans le fitness

    return populationSelection

4. Croisement & Mutation 🦖🔬🦎

Faisons un peu de génétique (non je rigole 👻, mais c’est tout comme) : le croisement et la mutation permettent de produire la génération descendante.

Le croisement

Le croisement consiste à partir de 2 parents de donner 2 enfants en faisant s’échanger leurs propriétés. Il existe plusieurs types de croisement :

• One-point CrossOver

• Two-point CrossOver

• n-point CrossOver (nXO) : avec n > 2

La mutation

La mutation quant à elle consiste à modifier les propriétés d’un individu. Il existe 3 principaux types de mutation :

• Insertion

• Swap

• Reversion

5. Prochaine génération 👨‍👩‍👧‍👦👨‍👩‍👧‍👦👨‍👩‍👧‍👦

La dernière étape consiste à former la génération suivante (ascendants vers descendants). Durant cette phase, il consiste à appliquer les différentes transformations génétiques sur une partie de notre génération actuelle. Ici également, nous avons deux méthodes (stratégies) pour produire la prochaine génération :

• Stratégie 1 : l’élitisme
  On sélectionne les élites (individus ayant les meilleurs fitness) de notre génération actuelle et on les positionne dans l’ordre dans notre prochaine génération. Le reste de la population sera croisé et muté, puis ajouté dans l’ordre également dans la prochaine génération.

• Stratégie 2 : la fusion
  On sélectionne toute la génération actuelle et on lui ajoute des individus croisés et des individus mutés issus de la génération actuelle. Puis, on trie et on sélectionne les P (la taille de la génération de base) premiers individus de notre liste d’individus récemment créée pour former la prochaine génération.

6. Solution finale 🎊🎉🎈

Pour avoir notre solution finale, nous allons choisir notre critère de fin de cycle. Ce qui permet d’avoir notre génération finale dans laquelle se trouve notre solution finale. Le critère de fin peut être :

• Le nombre d’itérations : On définit un nombre d’itérations à atteindre ce qui revient à choisir la génération qui marque la fin de notre cycle. Pour résoudre notre problème, nous choisirons 100 itérations.
  Pour la solution de notre problème, suivre ce lien.
• Le temps de calcul CPU : On définit une limite de temps d’exécution de notre algorithme.
• S’arrêter s’il n’y a pas d’amélioration de notre fitness : Après un certain nombre d’itérations, on évalue notre fonction objective. Si celle-ci ne s’améliore pas, on arrête le cycle. Sinon, on continue avec le nombre d’itérations déjà défini.

Conclusion

Dans cet article, j’ai présenté l’Algorithme Génétique comme un moyen excellent, avant toute application de nos modèles de Machine Learning, de faire le choix des paramètres de ces modèles. Cet algorithme est une méthode d’optimisation qui s’adapte à la plupart des problèmes. Mais, ils existent d’autres algorithmes plus performants dits hybrides pour avoir des solutions qui se rapprochent beaucoup plus de l’optimum global.

Sources et ressources complémentaires

[1] WIKIPEDIA, Genetic algorithm, https://en.wikipedia.org/wiki/Genetic_algorithm
[2] WIKIPEDIA, Métaheuristique, https://fr.wikipedia.org/wiki/Métaheuristique
[3] IMT Atlantique, Lesson 05 : Approximate resolution methods, http://formations.telecom-bretagne.eu/or/courses/2018-2019-ISA/05/05.html
[4] Medium, Episode 1 — Genetic Algorithm for Reinforcement Learning, https://becominghuman.ai/genetic-algorithm-for-reinforcement-learning-a38a5612c4dc