Les algorithmes génétiques pour les nuls

Les algorithmes génétiques sont des méthodes informatiques qui sont utilisées pour trouver des solutions à des problèmes complexes. Ils s'inspirent du processus de sélection naturelle qui a lieu dans la nature, où les êtres vivants qui sont les plus adaptés à leur environnement sont les plus susceptibles de survie et de reproduction.

Voici comment cela fonctionne :

1. On commence par créer une "population" de solutions possibles au problème. Par exemple, si on veut trouver le meilleur itinéraire pour aller d'un point A à un point B, on peut créer une population de différents itinéraires possibles.
2. On évalue chaque solution de la population en utilisant une "fonction de fitness", qui mesure à quel point une solution est bonne. Par exemple, si on cherche le meilleur itinéraire, la fonction de fitness pourrait mesurer combien de temps il faut pour aller d'un point A à un point B en suivant chaque itinéraire.
3. On sélectionne les meilleures solutions de la population en utilisant la fonction de fitness. Par exemple, on pourrait choisir les itinéraires qui sont les plus rapides.
4. On "croise" ces solutions en les combinant de différentes manières pour créer de nouvelles solutions. Par exemple, on pourrait prendre le début de l'itinéraire le plus rapide et le finir avec la fin de l'itinéraire le plus court.
5. On ajoute de l'aléatoire en "mutant" certaines solutions. Par exemple, on pourrait changer un tronçon d'un itinéraire pour voir si cela peut le rendre encore meilleur.
6. On recommence le processus en évaluant la nouvelle population de solutions et en sélectionnant les meilleures. On continue ce processus jusqu'à ce qu'on trouve la solution optimale.

Les algorithmes génétiques sont utilisés pour résoudre de nombreux types de problèmes, comme la recherche d'itinéraires les plus courts, la conception de produits, la prédiction des résultats de matchs de sport, et bien d'autres encore.

Exemple

Voici comment on pourrait écrire un algorithme génétique pour trier une liste de mots en Python :

import random

# On définit une fonction de fitness qui mesure à quel point une liste est triée
def fitness(words):
  score = 0
  for i in range(len(words) - 1):
    if words[i] <= words[i + 1]:
      score += 1
  return score

# On définit une fonction pour "croiser" deux listes en les combinant de différentes manières
def crossover(words1, words2):
  # On choisit un point de "crossover" au hasard
  crossover_point = random.randint(1, len(words1) - 1)
  # On crée deux nouvelles listes en combinant les deux listes originales
  new_words1 = words1[:crossover_point] + words2[crossover_point:]
  new_words2 = words2[:crossover_point] + words1[crossover_point:]
  return new_words1, new_words2

# On définit une fonction pour "mutater" une liste en modifiant un mot au hasard
def mutate(words):
  # On choisit un mot au hasard
  index = random.randint(0, len(words) - 1)
  # On modifie le mot en le remplaçant par un mot au hasard dans la liste
  words[index] = random.choice(words)
  return words

# On définit la fonction principale de l'algorithme génétique
def genetic_sort(words, n_iterations):
  # On crée une population de listes de mots qui sont mélangées de différentes manières
  population = []
  for i in range(20):
    population.append(random.sample(words, len(words)))
  
  # On exécute l'algorithme génétique pendant un certain nombre d'itérations
  for i in range(n_iterations):
    # On évalue chaque liste de la population en utilisant la fonction de fitness
    scores = [fitness(words) for words in population]
    # On sélectionne les meilleures listes en utilisant la fonction de fitness
    top_words = [words for _, words in sorted(zip(scores, population), reverse=True)[:10]]
    # On crée de nouvelles listes en "croisant" les meilleures listes
    new_words = []
    for i in range(10):
      for j in range(i + 1, 10):
        new_words.extend(crossover(top_words[i], top_words[j]))
    # On "mutate" certaines listes de la nouvelle population
    for i in range(10):
      new_words[i] = mutate(new_words[i])
    # On remplace la population par la nouvelle population
    population = new_words