👁️‍🗨️ Coup d’oeil sur l’algorithme génétique

Initiation à l’algorithme génétique : présentation des principes et petit cas pratique

En recherche opérationnelle, les méthodes de résolution exactes (comme le simplexe) étant de complexité exponentielle, donc relativement chronophage, parfois il plus judicieux de faire appel à des méthodes heuristiques pour des problèmes difficiles.

• Un heuristique est un algorithme qui permet afin de trouver une solution approchée, pas nécessairement optimale, pour un problème d’optimisation difficile ; dans un délai de temps raisonnable.

Les heuristiques sont dépendantes du problème à résoudre, toutefois des heuristiques plus poussées ont été mises au point — un niveau d’abstraction plus élevé que les heuristiques puisqu’il s’agit de méthode pouvant s’adapter à un problème donné — et ont données naissance à une nouvelle famille d’algorithmes : les méta-heuristiques.

• L’idée principale des métaheuristiques est d’explorer l’espace des solutions en essayant de converger vers l’optimum global (la meilleure solution dans l’ensemble) ; sans être « piégé » par un optimum local (la meilleure solution dans une zone restreinte).

Les métaheuristiques (M) tentent de trouver l’optimum global (G) d’un problème d’optimisation difficile (avec des discontinuités — D — , par exemple), sans être piégé par les optima locaux (L).

Généralement de nature stochastiques et itératifs, ces algorithmes se veulent être des méthodes génériques pouvant optimiser une large gamme de problèmes différents :

• Les plus simples : Problème du voyageur, problème du sac à dos, etc.
• Comme les plus compliqués : Choix optimal des paramètres du modèle K-Nearest Neighbors (KNN) ou K-Means, réduction de la complexité des réseaux de neurones, etc.

Les métaheuristiques sont souvent inspirées par des systèmes naturels, et sont de plus en plus hybridées avec d’autres méthodes de recherche opérationnelle.

Parmi les principales métaheuristiques utilisées pour résoudre des problèmes à variables discrètes, on retrouve les algorithme génétiques.

Algorithme génétique : principes et fonctionnement

Inspiration de la nature

Les algorithmes génétiques (AG) sont de la famille des algorithmes évolutionnaires ; des algorithmes d’optimisation stochastique fondés sur les mécanismes de la sélection naturelle et de la génétique.

Les principes de base des AG, développés par le scientifique américain John Henry Holland dans les années 1970, s’inspirent directement des travaux du naturaliste anglais Charles Darwin. En effet, la théorie de l’évolution, développée dans le célèbre ouvrage De l’origine des espèces de Darwin, postule que le principal moteur de l’évolution est le processus de sélection naturelle.

Illustration de la théorie de Darwin

Cette notion, que l’on qualifie parfois comme la survie du plus apte (survival of the fittest, en anglais), repose sur trois principes : le principe de variation, le principe d’adaptation et le principe d’hérédité. :

• Le principe de variation : Chaque individu au sein d’une population est unique. Ces différences, plus ou moins importantes, vont être décisives dans le processus de sélection.

Chez les girafes, la couleur de la peau, le nombre de taches ou la taille du cou sont des caractères pour lesquels il existe de multiples variations ou traits.

• Le principe d’adaptation : Les individus ayant les variations les plus favorables par rapport à leur environnement sont plus adaptés et atteignent plus facilement l’âge adulte. Ceux ayant une meilleure capacité de survie pourront donc se reproduire davantage.

Chez les ancêtres de la girafe, les individus dotés d’un cou plus long ont eu un avantage sur les autres. Cette variation a affecter positivement la survie de l’espèce dans son environnement

• Le principe d’hérédité : Les caractéristiques et variations des individus sont héréditaires, c’est-à-dire héritées des parents et transmises aux descendants. Ainsi, après plusieurs générations, on verra les variations favorables se retrouver chez tous les individus de la population et la fréquence des gènes désavantageux diminuer jusqu’à éventuellement disparaître.

Chez les girafes, lors de la reproduction, les individus transmettent leurs gènes aux descendants

Le fonctionnement de base de l’algorithme génétique

À l’image de la sélection naturelle, le fonctionnement des algorithmes évolutionnaires est axé sur un processus itératif que nous pouvons de diviser en cinq phases :

1. Initialisation
2. Évaluation
3. Sélection
4. Croisement
5. Mutation
Ensuite, il y a un Retour à la phase d’évaluation jusqu’à l’arrêt de l’algorithme.

Fonctionnement d’un algorithme génétique simple

Grossièrement, les AG se basent au départ sur une population de solutions candidates appelées parfois individus, celles-ci comprennent des propriétés et elles peuvent être sujettes à des transformations génétiques (mutation, croisement par exemple) qui vont faire évoluer la population de génération en génération, jusqu’à la génération qui contient les meilleures solutions.

Pour mieux appréhender le fonctionnement des AG, quoi de mieux qu’un cas pratique ?

Cas pratique : Maximisation de la somme des gènes d’un octet

Objectif du cas pratique

Pour ce cas pratique, nous allons avoir au départ une liste aléatoire d’individus en représentation binaire. Nous travaillerons avec une liste contenant 10 individus.

Liste typique d’octets

L’objectif va être d’utiliser un algorithme génétique afin d’avoir des individus dont la somme des gènes est maximisé.

Par exemple, la somme des gènes de l’individu 10101000 vaut 3

Bien que ce problème soit trivial, le but de ce cas pratique est de comprendre pas à pas les notions, comment utiliser et implémenter les algorithmes génétiques.

Initialisation de la population

Pour commencer, il est important de définir quelques notions de bases :

• La population est l’ensemble des solutions envisageables.
• L’individu représente une solution.
• Le gène est une caractéristique, une particularité de la solution.

Dans notre problème, cela équivaut à cela :

Identification de la population, d’un individu et d’un gène

Pour notre problème, étant donné qu’un octet est composer de 8 bits, nous représenterons un individu par un array de taille 8, rempli de 1 et de 0.

import numpy as np
import random

# Generate randomly an individual
def generate_individual():
    individu = np.random.randint(0,2, size=(1,8))
    return individu

generate_individual()

# Output : array([[1, 1, 0, 1, 1, 1, 0, 0]])

Dès lors, nous pouvons générer aléatoirement la population d’octets sur laquelle nous allons travailler.

# Generate a population of individual generated randomly
def generate_population(size):
    pop = np.empty(shape=[0, 8])
    for i in range(size):
        pop = np.vstack([pop, generate_individual()])
    return pop

# Output : array([[0., 1., 0., 0., 1., 1., 0., 0.],
#                 [0., 0., 1., 1., 0., 0., 1., 1.],
#                 ...,
#                 [0., 0., 0., 0., 1., 0., 0., 0.]])

Evaluation de la population

Maintenant que notre population est généré, il faut l’évaluer. Nous allons attribuer à chaque individu un score (aussi appelé fitness). En effet, les individus ayant une bonne qualité seront ceux avec un score élevé. Ils auront plus de chance d’être sélectionnés et donc il y a plus de chance que la populati Pour notre problème, c’est relativement simple, nous définissons la fitness comme la somme des variables (0 ou 1) de l’individu. on suivante hérite de leur matériel génétique.

Pour notre problème, c’est relativement simple, nous définissons la fitness comme la somme des variables (0 ou 1) de l’individu.

# Attribute a score to each individual of the population : sum of their genes
def compute_fitness(population):
    matriceScores = population.sum(axis=1)
    return matriceScores

# Work on population : Sort the population in ascending order
def evaluate_population(population):
    pop = population.copy() # get the population
    listScores = compute_fitness(pop) # get the list of scores
    listScores = listScores.argsort(axis=0) # sort the list of scores
    population_evaluated = pop[listScores] # put the mask in population to sort population 
    return population_evaluated

Opérateurs génétique

Pour la suite, il est important de comprendre qu’il y a trois opérateurs d’évolution dans les algorithmes génétiques :

• La sélection qui permet de choisir les individus les mieux adaptés.
• Le croisement qui permet de mélanger des individus choisis par la reproduction de certaines de leurs propriétés.
• La mutation qui permet d’altérer / faire varier aléatoirement les propriétés d’un individu.

Opérateur de sélection sur la population

La sélection consiste à choisir les individus les mieux adaptés (i.e. avec les meilleurs fitness) afin d’avoir une population de solution la plus proche de converger vers l’optimum global. Cet opérateur est l’application du principe d’adaptation de la théorie de Darwin.

Il existe plusieurs techniques de sélection. Voici les principales utilisées :

• Sélection par rang : on choisit toujours les individus possédant les meilleurs scores d’adaptation (fitness).
• Sélection par tournoi : on sélectionne proportionnellement des paires d’individus, puis choisit parmi ces paires l’individu qui a le meilleur score d’adaptation.
• Sélection uniforme : on sélectionne aléatoirement, uniformément et sans intervention de la valeur d’adaptation.

Pour notre problème, les individus de la population ont été évaluées très facilement ; ceux ayant un score élevé ont été classé en fin du tableau. Nous opterons alors pour une sélection par rang, et nous sélectionnerons les meilleurs individus de la population en indexant le tableau par la fin.

# Work on population : Select a percentage of the population
def select_population(population, percent):
    pop = population.copy() # get the population

    howmany = int(round(len(pop)*(percent))) # the number of individu to select
    population_selected = pop[-howmany:]
    return population_selected

Opérateur de croisement sur la population

Le croisement (ou crossing-over en anglais), est le résultat obtenue lorsque deux chromosomes partage leurs particularités. Cet opérateur est l’application du principe d’hérédité de la théorie de Darwin, et permet le brassage génétique de la population.

Il existe plusieurs techniques de croisement. Voici les principales utilisées :

• Le croisement simple : on fusionne les particularités de deux individus à partir d’un point de coupure, afin d’obtenir un ou deux enfants.”

Croisement simple — Un point de coupure

• Le croisement multiple : même principe que le précédant, sauf qu’il y a plusieurs points de coupure.

Croisement double — Deux points de coupures

• Le croisement uniforme : on fusionne les particularités de deux individus à partir d’un masque de croisement généré aléatoirement, afin d’obtenir un ou deux enfants.

Pour notre problème, nous opterons pour un croisement simple ; les individus-enfants hériterons de la moitié des caractéristiques respectives des parents.

# Work on individual : Create an individual crossed simply with 2 individuals 
def crossover(parent1, parent2):
    genes1, genes2 = parent1[:4], parent2[-4:]
    child = np.hstack([genes1, genes2])
    return child

Dès lors, nous implémentons une fonction permettant d’appliquer l’opérateur de croisement dans une population et pouvoir en faire croiser une partie (un pourcentage).

# Work on population : Cross a percentage (taken as a parameter) of the population
def cross_population(population, percent):
    pop = population.copy() # get the population

    children = np.empty(shape=[0, 8])
    howmany = int(round(len(pop)*(percent))) # the number of child to create
    for k in range(howmany):
        ind1 = random.choice(pop)
        ind2 = random.choice(pop)
        # create the child
        child = crossover(ind1, ind2)
        # store the child 
        children = np.vstack([children, child])
    
    # Add children to population
    population_crossed = np.vstack([pop, children])
    return population_crossed

Opérateur de mutation sur la population

La mutation consiste à altérer un gène dans un chromosome (individu) selon un facteur de mutation. Ce facteur est soit la probabilité qu’une mutation soit effectuée sur un individu, soit le pourcentage d’individus mutés dans une population.

Cet opérateur est l’application du principe de variation de la théorie de Darwin et permet, par la même occasion, d’éviter une convergence prématurée de l’algorithme vers un extremum local.

Il existe plusieurs techniques de mutation. Mais pour notre cas simple nous n’utiliserons que celle-ci :

• La mutation aléatoire : consiste à modifier une des particularités déterminées aléatoirement d’un individu

Pour notre problème, nous opterons pour cette technique ; lorsque la valeur du gène à muter est égale à 1 alors elle est inversée à 0 et lorsqu’elle est égale à 0 alors elle est inversée à 1.

# Work on individual : Mutate an individual / randomly change a bit
def mutation(individu):
    a = random.randrange(len(individu)) # choose a random gene to mutate
    if individu[a]==0:
        individu[a]=1
    else:
        individu[a]=0
    return individu

Dès lors, nous implémentons une fonction permettant d’appliquer l’opérateur mutation dans une population et pouvoir en faire muter une partie (un pourcentage).

# Work on population : Mutate a percentage of the population
def mutate_population(population, percent):
    pop = population.copy() # get the population

    howmany = int(round(len(pop)*(percent))) # the number of individu to mutate
    for k in range(howmany):
        i = random.randrange(pop.shape[0]) # choose a random individu in population to mutate
        individu = pop[i]
        mutant = mutation(individu) # mutate the individu
        pop[i] = mutant # replace individu by mutant

    return pop

Création de la première génération

Nous testons rapidement nos fonctions avec en paramètres :
- Taille de la population : 6
- Part d’individus sélectionnés dans la population : 50%
- Part d’enfants croisés obtenus par rapport à la population : 100%
- Part d’individus mutés chez les enfants : 40%

Tout d’abord, une population est initialisée :

population = generate_population(6)

Ensuite, cette population est évaluée :

population = evaluate_population(population)

Puis, les meilleurs individus de cette population sont sélectionnés :

population = select_population(population, 0.5)

Ces derniers vont être croisées, et vont faire un nombre défini d’enfants. Les voici :

children = cross_population(population, 1.0) //// children = mutate_population(children, 0.4)

Et enfin, ces enfants vont être regrouper avec leurs magnifiques parents pour constituer une population finale

population = np.vstack([population, children])

Voilà une génération de crée ! Nos fonctions marche très bien.

Résolution du problème par l’algorithme génétique

Désormais, il ne reste plus qu’à mettre les lignes de codes précédentes dans une boucle itérative afin de simuler le renouvellement de population au fil de N génération.

def algorithme_genetique(nbPopulationStart, numberOfGeneration, percentSelected, percentCrossed, percentMutated, aff):
    # Initialisation
    population = generate_population(nbPopulationStart)
    print('Initial population\n', population) if aff>=1 else None

    for t in range(numberOfGeneration):
        print('\n#########################################################') if aff==2 else None
        print('######################################### GENERATION :', t) if aff==2 else None
        # Evaluation
        population = evaluate_population(population)
        print('\nEvaluation :\n', population) if aff==2 else None
        # Selection
        population = select_population(population, percentSelected)
        print('\nSelection :\n', population) if aff==2 else None
        # Crossover
        children = cross_population(population, percentCrossed)
        print('\nCrossover - Children :\n', children) if aff==2 else None
        # Mutation
        children = mutate_population(children, percentMutated)
        print('\nMutation - Children :\n', children) if aff==2 else None
        # store the child 
        population = np.vstack([population, children])
        print('\nSelection :\n', population) if aff==2 else None

    print('\n#########################################################') if aff==2 else None
    print('>>>> Result :\n', population) if aff>=1 else None
    return population

Ainsi, pour résoudre le problème initiale, il suffit de lancer notre algorithme en choisissant comme paramètres d’entrées :
- Taille de la population : 10
- Nombre de génération : 3
- Part d’individus sélectionnés dans la population : 50%
- Part d’enfants croisés obtenus par rapport à la population : 100%
- Part d’individus mutés chez les enfants : 30%

population = algorithme_genetique(10, 5, 0.5, 1, 0.3, 1)

On constate que cette population final est composé majoritairement d’individus dont la somme des gènes maximisée, c’est-à-dire composé de bonnes solutions. Il a fallu seulement 3 génération à notre algorithme pour résoudre ce problème.

Voilà une brève introduction à l’algorithme génétique, mais il faut garder en tête qu’en dehors du modèle que je viens de présenter, il existe plusieurs variétés de modèles d’implémentation de l’AG pour avoir des solutions qui se rapprochent beaucoup plus de l’optimum.

Mlachahe SAID SALIMO.

Sources et ressources complémentaires :
- Sélection naturelle, la page Wikipédia
- Darwin et la sélection naturelle, un cours du site alloprof.qc.ca
- Optimisation combinatoire, un article du site complex-systems-ai.com
- Maxima and minima, la page Wikipédia
- Algorithme génétique, la page Wikipédia
- Algorithme génétique, le site de l’exposé de Thomas LEROUX
- Algorithme génétique, un article du site ledatascientist.com
- Les techniques algorithmiques de l’IA | Les algorithmes évolutionnaires, article du site ajcact.org
- Présentation des algorithmes génétiques et de leurs applications en
économie, un article de Thomas Vallée et Murat Yildizoglu
- Genetic Algorithms — Quick Guide, un article du site tutorialspoint.com