Différences

Ci-dessous, les différences entre deux révisions de la page.

--- ia:genetique [2023/02/27 19:48] – créée goupillwiki
+++ ia:genetique [2023/02/28 14:42] (Version actuelle) – goupillwiki
@@ Ligne 108: / Ligne 108: @@
   * la 2e moitié des gènes de l'enfant sont les valeurs manquantes prises dans l'ordre du parent 2
-{{ :ia:genetique2.svg?600x200 |}}
+{{ :ia:genetique2.svg?300x100 |}}
 Ainsi l'enfant reçoit une part de ses deux parents et reste viable.
+<WRAP box>
+{{ :ia:genetique6.svg?200x50|}}
+En général, le cross-over consiste plutôt à choisir au hasard une position pour couper l'adn des deux parents et de générer deux enfants avec les morceaux.
+Mais dans notre cas, cela ne convient pas : il faut absolument que l'enfant soit viable selon la modélisation choisie. Si on faisait cela, on aurait très probablement un enfant avec un adn correspondant à un parcours passant plusieurs fois par la même ville et pas par d'autres...
+</WRAP>
 === mutation ===
@@ Ligne 117: / Ligne 125: @@
 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 %.
 == mutation par transposition ==
-{{ :ia:genetique3.svg?600x150 |}}
+{{ :ia:genetique3.svg?300x75 |}}
 On sélectionne deux positions au hasard et on les transpose.
@@ Ligne 126: / Ligne 136: @@
 == mutation par renversement ==
-{{ :ia:genetique4.svg?600x150 |}}
+{{ :ia:genetique4.svg?300x75 |}}
 On sélectionne deux positions au hasard et on renverse la séquence correspondante.
@@ Ligne 132: / Ligne 142: @@
 == mutation par insertion ==
-{{ :ia:genetique5.svg?600x150 |}}
+{{ :ia:genetique5.svg?300x75 |}}
 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.
+== choix aléatoire de la mutation ==
+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''
+=== compétitions pour la reproduction ===
+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é.
+=== élite ===
+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.
+===== Implémentation =====
+Vous disposez déjà de ''data.py'' et du fichier {{ :nsi:datasets:communes-departement-region.csv |}}
+==== module distance ====
+Pour les calculs de distances, je vous propose le module suivant :
+<code python>
+# 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
+</code>
+==== module genetics ====
+C'est le cœur de votre programme. Vous allez écrire un module ''genetics.py'' contenant les fonctions suivante (complétez les fonctions) :
+<code python>
+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 !
+</code>
+==== démonstration ====
+Je propose le script de démonstration suivant :
+<code python>
+# 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()
+</code>
+<WRAP tip>
+Dans l'exemple, avec le ''random'' calé sur ''random.seed(452)'', j'obtient un meilleur chemin d'environ 5830 km avec l'algo génétique. Pour l'exemple, je cherche un meilleur chemin avec un algorithme glouton et en testant exhaustivement tous les points de départs possibles (l'algorithme glouton est très rapide, donc ça reste faisable). On obtient alors 5920 km environ, mais beaucoup plus vite. Et en choisissant un point de départ au hasard et l'algorithme glouton, j'obtiens très très vite un chemin d'environ 6300 km. Donc...
+  * on pourrait juger que le surcroit de complexité et de coût en temps de l'algo génétique n'est pas rentable étant donné le maigre gain de performance,
+  * si de surcroit on réfléchissait à un bon choix de point de départ avec l'algorithme glouton, on aurait un bon résultat très rapidement,
+  * on pourrait réfléchir à une hybridation : constituer une population initiale avec l'algo glouton de façon à avoir de bons candidats dès le début, améliorer avec l'algo génétique. Ainsi, on limite le nombre de générations.
+</WRAP>