L'algorithme génétique est un algorithme d'optimisation.

Dans un problème d'optimisation, on cherche la meilleure solution à un problème. Dans l'exemple de ce TD, il s'agit de trouver un chemin le plus court. Certains algorithmes d'optimisation consistent à choisir une solution au hasard et à l'améliorer de proche en proche. Mais pour les problèmes complexes, en faisant cela on risque d'arriver à une solution qui réalise un minimum local, c'est à dire qu'on ne peut pas modifier par une petite adaptation.

Il existe diverses technique permettant d'explorer les solutions possibles au hasard et de converger vers une bonne solution sans rester coincé dans un optimum local. L'algorithme génétique en fait partie.

Afin d'expliquer plus facilement, je vais m'appuyer sur un exemple de problème. Nous allons traiter le problème du voyageur de commerce : il s'agit de chercher le parcours le plus court passant par une liste de villes.

Nous utiliserons le fichier communes-departement-region.csv contenant des communes françaises.

Pour extraire les données, je propose ce module court :

# data.py

import csv

def format(city):
    return {
        "insee":city['code_commune_INSEE'],
        "nom":city['nom_commune_complet'],
        "lat":float(city['latitude']),
        "lng":float(city['longitude'])
    }

def load_cities():
    with open("communes-departement-region.csv", "r", encoding="utf8") as f:
        reader = csv.DictReader(f, delimiter=',')
        cities = []
        for city in reader:
            try:
                cities.append(format(city))
            except:
                pass
    return cities

cities = load_cities()

Et dans notre exemple de démonstration nous aurons :

# demo.py

from data import cities
import random

random.seed(452)
N = 100

selected_cities = [random.choice(cities) for i in range(N)]

Ainsi, notre démo a permis de sélectionner au hasard une centaine de villes françaises.

Dans l'algorithme génétique, une solution possible se présentera sous la forme d'une séquence (bien sûr il est toujours possible d'adapter à d'autres formes)

Dans notre exemple, nous avons 100 villes que nous pouvons numéroter de 0 à 99. Une solution est donc une séquence d'indices parcourant toutes les valeurs de 0 à 99. Par exemple [15, 28, 17, 69, 36, ... ,84, 2].

Cette séquence constitue l'adn de cette solution.

Dans un algorithme évolutionniste, il faut bien choisir la forme de l'adn.

En biologie évolutionniste, on appelle fitness la mesure de l'efficacité d'un individu du point de vue évolutionniste. Un individu avec un bon fitness aura tendance à se reproduire et donc à survivre, à occuper le territoire, à remplacer les autres, à s'imposer.

Dans notre cas, le fitness sera la longueur totale du parcours correspondant à un adn donné.

Par exemple si adn = [1, 8, 15, 2], la fitness sera la longueur du parcours partant de la ville d'indice 1, puis passant par la ville d'indice 8, puis… jusqu'à la ville d'indice 2. Ces indices correspondent aux villes placées dans selected_cities.

Dans ce cas, un bon fitness est un fitness proche de 0. On sélectionne donc les individus avec un fitness minimum.

On constitue une population remplie d'individus choisis au hasard. Une plus grande population entraîne plus de diversité mais aussi plus de calculs. Il faut donc bien choisir la taille de la population.

L'évolution repose sur la sélection des individus les plus adaptés et leur reproduction.

Mais pour que l'on puisse progresser vers une solution, il faut un mécanisme qui modifie peu à peu les adn des individus. On imite donc les mécanismes naturels :

• cross over : quand deux individus se reproduisent, leur enfant a un adn composé d'une partie des gène du parent 1 et d'une partie des gène du parent 2. De nombreux choix sont possibles mais il faut veiller à ce que la procédure choisie produise un adn viable.
  Dans notre cas, l'adn de l'enfant doit toujours être un mélange de la liste [0, 1, 2, ..., 99].

Dans notre problème nous faisons le choix suivant :

• la première moitié des gènes de l'enfant est une simple copie de la première moitié des gène du parent 1 ;
• la 2e moitié des gènes de l'enfant sont les valeurs manquantes prises dans l'ordre du parent 2

Ainsi l'enfant reçoit une part de ses deux parents et reste viable.

En plus du mélange dû au cross-over, on envisage des modifications aléatoires, des mutations. À la naissance de chaque enfant, il y a une probabilité pour l'apparition d'une mutation.

Là encore, il y a des réglages : quel taux de mutation ? quel choix de mutation ?

On pourra choisir MUTATION_RATE = 0.3, c'est à dire que la probabilité qu'il y ait une mutation est de 30 %.

On sélectionne deux positions au hasard et on les transpose.

On sélectionne deux positions au hasard et on renverse la séquence correspondante.

On sélectionne au hasard l'indice d'insertion, l'indice de l'item à déplacer puis on place l'item à déplacer à l'indice d'insertion, décalant les autres.

Lorsqu'il y a mutation, le mieux est de choisir la mutation au hasard. On peut faire le choix suivant :

• TRANSPOSITION_RATIO = 0.4
• INSERT_RATIO = 0.4
• et donc REVERSE_RATIO = 0.2

Quels parents peuvent se reproduire ?

Pour sélectionner un parent, on prélève au hasard TOURNOI_SIZE adn au hasard dans la population et parmi ceux-là, on ne garde que celui ayant le meilleur fitness.

Pour produire un enfant, on doit donc faire 2 tournois, pour obtenir 2 parents.

On recommence autant de fois que nécessaire pour obtenir le nombre d'enfants désiré.

Dans l'algorithme génétique, la population a une taille fixe.

À chaque génération, on doit produire une nouvelle population d'une taille semblable à l'ancienne. Mais si la population précédente contenait de bons adns, on veut les conserver.

On choisit donc de conserver les meilleurs adns de la population et de compléter la population en produisant autant d'enfants que nécessaire.

nouvelle population = meilleurs de l'ancienne population + enfants

On peut se fixer un facteur : ELITE_RATIO = 0.2 qui permet de fixer à 20 % la part de meilleurs à conserver. Les 80 % restant sont complétés par les enfants.

Vous disposez déjà de data.py et du fichier communes-departement-region.csv

Pour les calculs de distances, je vous propose le module suivant :

# distance.py
from math import radians, cos, sin, acos

def cosd(angle_deg:float) -> float:
    '''
    renvoie le cosinus de angle_deg, exprimé en degrés
    '''
    return cos(radians(angle_deg))

def sind(angle_deg:float) -> float:
    '''
    renvoie le sinus de angle_deg, exprimé en degrés
    '''
    return sin(radians(angle_deg))

def distance(lat1:float, lng1:float, lat2:float, lng2:float) -> float:
    '''
    renvoie la distance en km, entre deux points positionnés selon les coordonnées gps
    '''
    R = 6378
    return R*acos(sind(lat1)*sind(lat2) + cosd(lng1-lng2)*cosd(lat1)*cosd(lat2))

def longueur_parcours(indices, data) -> float:
    '''
    indices: liste d'indices
    data: liste de dict contenant les clés lat et lng
    pour chaque i de indices, data[i] désigne un point.
    renvoie la longueur du parcours reliant ces points
    '''
    n = len(indices)
    if n <= 1:
        return 0
    somme = 0
    for i in range(n-1):
        indice1 = indices[i]
        lat1 = data[indice1]["lat"]
        lng1 = data[indice1]["lng"]
        indice2 = indices[i+1]
        lat2 = data[indice2]["lat"]
        lng2 = data[indice2]["lng"]
        somme += distance(lat1, lng1, lat2, lng2)
    return somme

C'est le cœur de votre programme. Vous allez écrire un module genetics.py contenant les fonctions suivante (complétez les fonctions) :

import random
from tqdm import tqdm

TOURNAMENT_SIZE = 10 # nombre de parents à tirer au sort pour un round de sélection
MUTATION_RATE = 0.3
TRANSPOSE_RATIO = 0.4
INSERT_RATIO = 0.4
REVERSE_RATIO = 1 - TRANSPOSE_RATIO - INSERT_RATIO
ELITE_RATIO = 0.2    # ratio d'élites conservés à chaque tour 

def random_adn(size):
    '''
    renvoie un adn aléatoire
    l'adn est une séquence 0...size-1 mélangée
    '''

def mutation_reverse(adn):
    '''
    adn: séquence, par exemple (4, 9, 17, 12, 65, 416, 53)
    renvoie une copie avec une sous-séquence renversée au hasard, par exemple (4, 9, 416, 65, 12, 17, 53)
    '''

def mutation_transpose(adn):
    '''
    adn: séquence, par exemple (4, 9, 17, 12, 65, 416, 53)
    renvoie une copie avec une paire inversée, par exemple (4, 416, 17, 12, 65, 9, 53)
    '''

def mutation_insertion(adn):
    '''
    adn: séquence, par exemple (4, 9, 17, 12, 65, 416, 53)
    renvoie une copie avec un item inséré à une nouvelle position, par exemple (4, 9, 416, 17, 12, 65, 53)
    '''

def get_best(population):
    '''
    population: liste de paire (adn, fitness)
    renvoie la paire avec le meilleur fitness
    '''

def croisement(adn1, adn2):
    '''
    adn1, adn2: adns des parents, de même taille
    renvoie l'adn enfant suivant la règle :
      sélection de la première moitié de adn1, recopiée identique dans enfant
      sélection des autres valeurs, recopiées dans le même ordre que parent2 dans enfant 2
    Exemple :
      adn1   = (1, 6, 5, 0, 2, 4, 3)
      adn2   = (5, 3, 6, 2, 4, 0, 1)
      enfant = (1, 6, 5, 0, 3, 2, 4)
    '''

def make_child(population, fitness_fct):
    '''
    population: liste de paire (adn, fitness)
    Tire 2x au hasard TOURNAMENT_SIZE individus dans population,
    sélectionne les deux meilleurs et produit un enfant
    l'enfant a une probabilité de muter
    '''

def generation(population, fitness_fct):
    '''
    population: liste de paires (adn, fitness)
    fitness_fct: fonction adn -> float qui pour un adn donné calcule sont fitness
    produit la nouvelle population constituée ainsi :
      ELITE_RATIO d'élites, c'est à dire des meilleurs de l'ancienne population conservés sans changement
      enfants dont les parents sont pris par tournoi dans l'ancienne population
    la nouvelle population a la même taille que l'ancienne
    attention : la nouvelle population est toujours constituée de paires (adn ,fitness)
    '''

def process(adn_size:int, population_size:int, turns:int, fitness_fct):
    '''
    adn_size: taille d'un adn
    population_size: taille de la population
    turns: nombre de générations
    fitness_fct: fonction adn -> float permettant de calculer le fitness
    Partant d'une population générée au hasard, produit turns générations et renvoie le meilleur adn
    de la dernière génération
    '''
    
    # pour la boucle principale, écrivez :
    # for i in tqdm(range(turns)):
    # tqdm permet d'avoir une barre de progression, c'est plus confort à l'exécution !

Je propose le script de démonstration suivant :

# demo.py
from data import cities
from distance import longueur_parcours
from genetics import process
import matplotlib.pyplot as plt
import random

random.seed(452)
N = 100

selected_cities = [random.choice(cities) for i in range(N)]

def fitness_fct(adn):
    return longueur_parcours(adn, selected_cities)

best = process(N, 300, 1000, fitness_fct)

d = fitness_fct(best)
print(f"Le meilleur parcours obtenu fait {d:.1f} km.")

# représentation graphique
# remarque : la France est environ à 45° de latitude, pour avoir une carte pas trop
# écrasée, il faut multiplier les longitude par cos(45°) = 0.71

# marqueurs des villes retenues
x_cities = [city["lng"]*.71 for city in selected_cities]
y_cities = [city["lat"]     for city in selected_cities]
plt.scatter(x_cities, y_cities)

# parcours
x_values = [selected_cities[i]["lng"]*.71 for i in best]
y_values = [selected_cities[i]["lat"] for i in best]
plt.plot(x_values, y_values)

plt.show()