Accéder au contenu principal

Algorithme génétique : Guide complet avec mise en œuvre de Python

Un algorithme génétique est une technique de recherche qui imite la sélection naturelle pour trouver des solutions optimales en affinant de manière itérative une population de solutions candidates.
Actualisé 15 janv. 2025  · 18 min de lecture

Imaginez que vous essayez d'optimiser les itinéraires de livraison des camions. Chaque camion a de nombreux itinéraires possibles et vous avez de nombreux camions avec de nombreux arrêts. Le nombre de combinaisons possibles peut être écrasant, et trouver la meilleure solution peut s'apparenter à la recherche d'une aiguille dans une botte de foin.

Pour résoudre de tels problèmes, nous pouvons emprunter un concept à la biologie : l'évolution. En biologie, la sélection naturelle est un moteur de l'évolution. Le problème de la nature est de trouver les combinaisons optimales de caractéristiques qui permettent à un organisme de survivre et de se reproduire. Il utilise la sélection naturelle pour mettre en concurrence différents ensembles de caractéristiques et choisir les meilleures combinaisons. 

De même, nous pouvons utiliser ce concept pour créer un algorithme qui oppose différentes solutions et utilise la sélection pour les faire "évoluer" vers la meilleure solution. Les algorithmes qui font cela sont appelés algorithmes génétiques (AG).

Développer des applications d'IA

Apprenez à créer des applications d'IA à l'aide de l'API OpenAI.
Commencez à Upskiller gratuitement

Inspirés par l'évolution naturelle, les AG explorent efficacement l'espace des solutions pour découvrir des solutions optimales ou quasi optimales, même pour des problèmes complexes comportant de nombreux éléments mobiles. En imitant le processus de sélection naturelle, les AG peuvent faire évoluer les solutions au fil du temps, en améliorant leurs performances de manière itérative.

Contexte biologique des algorithmes génétiques

Les algorithmes génétiques s'inspirent du processus de sélection naturelle et de la génétique. Ils imitent la façon dont les organismes vivants évoluent au fil des générations pour s'adapter et survivre dans leur environnement. Comprendre les principes biologiques de base des AG peut nous aider à comprendre le fonctionnement de ces algorithmes et à les utiliser de manière plus stratégique.

La sélection naturelle

La sélection naturelle est le processus qui fait que les individus présentant les meilleures combinaisons de caractéristiques favorables ont plus de chances de survivre et de se reproduire. Avec le temps, ces caractéristiques avantageuses deviennent plus courantes dans la population.

Dans le contexte des AG, ce concept est reflété par la sélection d'individus ayant des scores de fitness plus élevés pour la reproduction. Ils transmettent ainsi leurs caractéristiques favorables, ou "gènes", à la génération suivante.

Gènes, croisements et mutations

Les caractéristiques d'un organisme biologique sont codées par ses gènes. Les gènes font partie de l'ADN, qui est organisé en chromosomes.

Les AG empruntent en grande partie les mêmes concepts et la même terminologie. Les solutions potentielles à un problème sont représentées sous forme de "chromosomes", qui sont généralement codés sous forme de chaînes ou de tableaux. Chaque élément du chromosome correspond à un gène qui détermine un caractère spécifique de la solution.

Le croisement, ou recombinaison, est une opération génétique qui combine des parties du matériel génétique de deux chromosomes parents en un nouveau chromosome qui contient des parties de chaque parent. Ce nouveau mélange de chromosomes est transmis à l'enfant. C'est l'une des raisons pour lesquelles vous pouvez obtenir la couleur des yeux de votre mère et la couleur des cheveux de votre père.

Dans les AG, le croisement consiste à échanger des segments des chromosomes parents pour créer de nouveaux individus. Cette opération introduit de la variabilité et permet à la progéniture d'hériter des traits bénéfiques des deux parents.

La mutation introduit des changements aléatoires dans les gènes d'un organisme, qui peuvent conduire à de nouvelles caractéristiques.

Explication visuelle de trois concepts d'évolution : la sélection, la mutation et le croisement.

Dans les algorithmes génétiques, la mutation consiste à modifier aléatoirement un ou plusieurs gènes d'un chromosome. Cela permet de maintenir la diversité génétique au sein de la population et permet à l'algorithme d'explorer de nouvelles zones de l'espace de solution.

Évaluation de la condition physique

Dans la nature, l'aptitude d'un individu est déterminée par sa capacité à survivre et à se reproduire. Si vous mourez avant de vous reproduire, votre aptitude est nulle. Si vous avez 12 petits-enfants, votre forme physique sera plus élevée que celle d'une personne ayant 2 petits-enfants.

Dans les AG, l'aptitude est similaire, mais un peu différente. Une fonction d'aptitude évalue dans quelle mesure une solution résout le problème posé. Les solutions ayant des scores de fitness plus élevés sont plus susceptibles d'être sélectionnées pour la reproduction, ce qui garantit que les meilleures solutions se propagent au fil des générations.

Composantes d'un algorithme génétique

Les algorithmes génétiques s'inspirent de l'évolution. Par conséquent, les composants d'un AG ont des noms et des fonctions similaires à ceux de leurs homologues biologiques. Chacun de ces composants est généralement codé comme sa propre fonction.

Population

La population d'un algorithme génétique est un ensemble de solutions candidates, souvent appelées individus. Chaque individu est représenté par un chromosome, qui peut être codé sous forme de chaînes binaires, tableauxou d'autres structures de données.

Par exemple, chaque chromosome peut représenter un ensemble de valeurs d'entrée pour une fonction que nous devons optimiser. Ou encore, chaque chromosome pourrait représenter un itinéraire de camion pour les chauffeurs-livreurs.

Fonction d'aptitude

La fonction d'aptitude évalue la capacité de chaque individu à résoudre le problème qui nous intéresse. Il attribue une valeur d'aptitude à chaque individu, les valeurs les plus élevées correspondant aux meilleures solutions. La fonction d'aptitude guide l'algorithme vers de meilleures solutions.

Par exemple, dans notre exemple d'optimisation d'une fonction mathématique, la fonction d'aptitude peut renvoyer la valeur de la fonction pour les entrées données. Pour notre exemple d'itinéraires de camions, la fonction d'aptitude pourrait renvoyer la vitesse d'achèvement de la livraison.

Fonction de sélection

La fonction de sélection choisit les individus de la population à reproduire en fonction de leur aptitude. Les individus ayant une meilleure aptitude physique sont plus susceptibles d'être choisis pour la reproduction. Cela imite la sélection naturelle, où les individus les mieux adaptés ont plus de chances de survivre et de se reproduire.

Il existe plusieurs méthodes de sélection. Les méthodes de sélection les plus courantes sont la sélection par la roulette, la sélection par le tournoi et la sélection par le rang.

La sélection par la roulette consiste à sélectionner des individus sur la base d'une probabilité proportionnelle à leur aptitude, un peu comme si l'on faisait tourner une roulette.

Dans la sélection par tournoi, un sous-ensemble d'individus est choisi au hasard et l'individu le plus adapté de ce sous-ensemble est sélectionné.

La sélection basée sur le rang classe les individus en fonction de leur aptitude. Les probabilités de sélection sont ensuite attribuées sur la base de ces classements plutôt que sur la base des valeurs brutes d'aptitude.

Chaque méthode a ses propres avantages et doit être choisie en fonction des exigences spécifiques du problème posé.

Fonction de croisement

Le croisement combine les informations de deux individus pour créer une descendance. L'objectif est d'hériter des caractéristiques bénéfiques des deux parents. Les techniques de croisement les plus courantes sont le croisement en un point, le croisement en plusieurs points, le croisement uniforme et le croisement mixte.

Le croisement en un point consiste à choisir un point aléatoire et à échanger le matériel génétique de deux parents en ce point pour créer deux descendants. Le croisement multipoint utilise plusieurs points pour échanger des segments entre les parents, ce qui permet des combinaisons génétiques plus complexes.

Le croisement uniforme décide de manière aléatoire quel parent apportera chaque gène, ce qui permet d'obtenir un niveau élevé de diversité génétique. Le croisement mixte génère une progéniture en mélangeant les gènes des parents à l'aide d'un facteur de mélange aléatoire. Le choix de la technique à utiliser doit être basé sur la complexité du problème et le niveau de diversité souhaité dans la descendance.

Fonction de mutation

La mutation introduit des changements aléatoires dans le matériel génétique de la progéniture. Cela permet de maintenir la diversité de la population et d'explorer de nouveaux domaines de l'espace de solution. Les mutations peuvent être aussi simples que le basculement d'un bit dans une chaîne binaire ou impliquer des changements plus complexes en fonction du schéma d'encodage. 

Le processus de l'algorithme génétique

Un algorithme génétique passe par une série d'étapes qui imitent les processus évolutifs naturels afin de trouver des solutions optimales. Ces étapes permettent à la population d'évoluer au fil des générations, améliorant ainsi la qualité des solutions. Voici une ligne directrice générale sur le déroulement d'un algorithme génétique :

Étape 1 : Initialisation

Tout d'abord, nous générons une population initiale d'individus aléatoires. Cette étape crée un ensemble diversifié de solutions potentielles pour lancer l'algorithme. 

Étape 2 : L'évaluation

Ensuite, nous devons calculer l'aptitude de chaque individu de la population. Nous utilisons ici la fonction d'aptitude pour évaluer la qualité de chaque solution.

Étape 3 : Sélection

En utilisant les critères de sélection, nous sélectionnons les individus pour la reproduction en fonction de leur aptitude. Cette étape permet de déterminer quelles personnes seront les parents.

Étape 4 : Crossover

Crossover vient ensuite. En combinant le matériel génétique des parents sélectionnés, nous appliquons des techniques de croisement pour générer de nouvelles solutions ou descendants.

Étape 5 : Mutation

Pour maintenir la diversité dans notre population, nous devons introduire des mutations aléatoires dans la descendance.

Étape 6 : Remplacement

Nous remplaçons ensuite une partie ou la totalité de l'ancienne population par la nouvelle progéniture, en déterminant les individus qui passent à la génération suivante.

Étape 7 : Répéter

Les étapes 2 à 6 précédentes sont répétées en boucle pendant un nombre déterminé de générations ou jusqu'à ce qu'une condition d'arrêt soit remplie. Cette boucle permet à la population d'évoluer au fil du temps, avec l'espoir d'aboutir à une bonne solution.

Exemple en Python

Maintenant que nous avons une bonne idée de ce que sont les algorithmes génétiques et de leur fonctionnement général, construisons notre propre algorithme génétique pour résoudre un problème d'optimisation simple.

L'équation y=ax2+bx+c, lorsqu'elle est représentée graphiquement, crée une parabole. Nous utiliserons un algorithme génétique pour trouver la combinaison de valeurs pour a, b et c qui donne la parabole la plus plate. Voici un aperçu de ce que nous allons réaliser :

Graphique des équations avec solutions de l'exemple codé.

Importer des bibliothèques

Au début de notre fonction, nous importerons les bibliothèques nécessaires. Nous utiliserons "random" pour générer des valeurs aléatoires pour notre population de départ. Numpy est généralement utile pour effectuer des calculs, à mon avis.

Et je crois fermement qu'il faut toujours faire des tracés pour s'assurer que votre code fait bien ce que vous pensez qu'il fait. Nous allons donc importer "matplotlib.pyplot" pour créer des graphiques.

J'aime aussi imprimer les résultats importants de chaque génération (en supposant un nombre relativement faible de générations) pour mieux comprendre ce qui s'est passé pendant la simulation. Nous allons donc importer "PrettyTable" pour cela.

import random
import matplotlib.pyplot as plt
import numpy as np
from prettytable import PrettyTable

Définir la fonction d'aptitude

Ensuite, nous devons définir la fonction d'aptitude qui évaluera l'aptitude de chaque solution. Dans ce cas, nous voulons trouver la forme en U la plus plate. J'ai donc calculé la valeur y au sommet et aux points x=-1 et x=1.

J'ai ensuite calculé la courbure du graphique comme étant la différence de valeur dey en ces trois points. Comme nous voulons obtenir la courbe la plus plate, j'ai annulé la courbure pour terminer la fonction d'aptitude.

# Define the fitness function (objective is to create the flattest U-shape)
def fitness_function(params):
    a, b, c = params
    if a <= 0:
        return -float('inf')  # Penalize downward facing u-shapes heavily
    vertex_x = -b / (2 * a) #x value at vertex
    vertex_y = a * (vertex_x ** 2) + b * vertex_x + c #y value at vertex
    y_left = a * (-1) ** 2 + b * (-1) + c #y-coordinate at x = -1
    y_right = a * (1) ** 2 + b * (1) + c #y-coordinate at x = 1
    curviness = abs(y_left - vertex_y) + abs(y_right - vertex_y)
    return -curviness  # Negate to minimize curviness

Créer une population initiale

Nous utiliserons la bibliothèque "random" pour générer une population de solutions aléatoires. Chaque individu de cette population est un ensemble de valeurs pour a, b et c.

# Create the initial population
def create_initial_population(size, lower_bound, upper_bound):
    population = []
    for _ in range(size):
        individual = (random.uniform(lower_bound, upper_bound),
                      random.uniform(lower_bound, upper_bound),
                      random.uniform(lower_bound, upper_bound))
        population.append(individual)
    return population

Créer une fonction de sélection

La fonction de sélection détermine quels individus se reproduisent pour créer la population suivante. Dans cet exemple, nous utiliserons un processus de sélection par tournoi, dans lequel un sous-ensemble aléatoire d'individus de la population sera pris, et les individus ayant la meilleure aptitude dans ce sous-ensemble seront sélectionnés pour la reproduction.

# Selection function using tournament selection
def selection(population, fitnesses, tournament_size=3):
    selected = []
    for _ in range(len(population)):
        tournament = random.sample(list(zip(population, fitnesses)), tournament_size)
        winner = max(tournament, key=lambda x: x[1])[0]
        selected.append(winner)
    return selected

Créer une fonction de croisement

Ensuite, nous allons écrire une fonction rapide pour utiliser le croisement afin de créer de nouvelles solutions basées sur des solutions existantes.

# Crossover function
def crossover(parent1, parent2):
    alpha = random.random()
    child1 = tuple(alpha * p1 + (1 - alpha) * p2 for p1, p2 in zip(parent1, parent2))
    child2 = tuple(alpha * p2 + (1 - alpha) * p1 for p1, p2 in zip(parent1, parent2))
    return child1, child2

Concevoir une fonction de mutation

Nous avons également besoin d'une fonction de mutation pour introduire le hasard dans les générations suivantes. Ceci est important pour s'assurer qu'il y a suffisamment de diversité dans chaque génération pour faire une sélection.

# Mutation function
def mutation(individual, mutation_rate, lower_bound, upper_bound):
    individual = list(individual)
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            mutation_amount = random.uniform(-1, 1)
            individual[i] += mutation_amount
            # Ensure the individual stays within bounds
            individual[i] = max(min(individual[i], upper_bound), lower_bound)
    return tuple(individual)

Boucle principale

Ensuite, nous devons créer la boucle principale qui rassemblera tous ces éléments pour exécuter notre algorithme. Étant donné que nous devons également tracer nos résultats, j'ajouterai le code de traçage dans cette section, ainsi que le code nécessaire à la création de notre tableau final.

# Main genetic algorithm function
def genetic_algorithm(population_size, lower_bound, upper_bound, generations, mutation_rate):
    population = create_initial_population(population_size, lower_bound, upper_bound)
    
    # Prepare for plotting
    fig, axs = plt.subplots(3, 1, figsize=(12, 18))  # 3 rows, 1 column for subplots
    best_performers = []
    all_populations = []

    # Prepare for table
    table = PrettyTable()
    table.field_names = ["Generation", "a", "b", "c", "Fitness"]

    for generation in range(generations):
        fitnesses = [fitness_function(ind) for ind in population]

        # Store the best performer of the current generation
        best_individual = max(population, key=fitness_function)
        best_fitness = fitness_function(best_individual)
        best_performers.append((best_individual, best_fitness))
        all_populations.append(population[:])
        table.add_row([generation + 1, best_individual[0], best_individual[1], best_individual[2], best_fitness])

        population = selection(population, fitnesses)

        next_population = []
        for i in range(0, len(population), 2):
            parent1 = population[i]
            parent2 = population[i + 1]

            child1, child2 = crossover(parent1, parent2)

            next_population.append(mutation(child1, mutation_rate, lower_bound, upper_bound))
            next_population.append(mutation(child2, mutation_rate, lower_bound, upper_bound))

        # Replace the old population with the new one, preserving the best individual
        next_population[0] = best_individual
        population = next_population

    # Print the table
    print(table)

    # Plot the population of one generation (last generation)
    final_population = all_populations[-1]
    final_fitnesses = [fitness_function(ind) for ind in final_population]

    axs[0].scatter(range(len(final_population)), [ind[0] for ind in final_population], color='blue', label='a')
    axs[0].scatter([final_population.index(best_individual)], [best_individual[0]], color='cyan', s=100, label='Best Individual a')
    axs[0].set_ylabel('a', color='blue')
    axs[0].legend(loc='upper left')
    
    axs[1].scatter(range(len(final_population)), [ind[1] for ind in final_population], color='green', label='b')
    axs[1].scatter([final_population.index(best_individual)], [best_individual[1]], color='magenta', s=100, label='Best Individual b')
    axs[1].set_ylabel('b', color='green')
    axs[1].legend(loc='upper left')
    
    axs[2].scatter(range(len(final_population)), [ind[2] for ind in final_population], color='red', label='c')
    axs[2].scatter([final_population.index(best_individual)], [best_individual[2]], color='yellow', s=100, label='Best Individual c')
    axs[2].set_ylabel('c', color='red')
    axs[2].set_xlabel('Individual Index')
    axs[2].legend(loc='upper left')
    
    axs[0].set_title(f'Final Generation ({generations}) Population Solutions')

    # Plot the values of a, b, and c over generations
    generations_list = range(1, len(best_performers) + 1)
    a_values = [ind[0][0] for ind in best_performers]
    b_values = [ind[0][1] for ind in best_performers]
    c_values = [ind[0][2] for ind in best_performers]
    fig, ax = plt.subplots()
    ax.plot(generations_list, a_values, label='a', color='blue')
    ax.plot(generations_list, b_values, label='b', color='green')
    ax.plot(generations_list, c_values, label='c', color='red')
    ax.set_xlabel('Generation')
    ax.set_ylabel('Parameter Values')
    ax.set_title('Parameter Values Over Generations')
    ax.legend()

    # Plot the fitness values over generations
    best_fitness_values = [fit[1] for fit in best_performers]
    min_fitness_values = [min([fitness_function(ind) for ind in population]) for population in all_populations]
    max_fitness_values = [max([fitness_function(ind) for ind in population]) for population in all_populations]
    fig, ax = plt.subplots()
    ax.plot(generations_list, best_fitness_values, label='Best Fitness', color='black')
    ax.fill_between(generations_list, min_fitness_values, max_fitness_values, color='gray', alpha=0.5, label='Fitness Range')
    ax.set_xlabel('Generation')
    ax.set_ylabel('Fitness')
    ax.set_title('Fitness Over Generations')
    ax.legend()

    # Plot the quadratic function for each generation
    fig, ax = plt.subplots()
    colors = plt.cm.viridis(np.linspace(0, 1, generations))
    for i, (best_ind, best_fit) in enumerate(best_performers):
        color = colors[i]
        a, b, c = best_ind
        x_range = np.linspace(lower_bound, upper_bound, 400)
        y_values = a * (x_range ** 2) + b * x_range + c
        ax.plot(x_range, y_values, color=color)

    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_title('Quadratic Function')

    # Create a subplot for the colorbar
    cax = fig.add_axes([0.92, 0.2, 0.02, 0.6])  # [left, bottom, width, height]
    norm = plt.cm.colors.Normalize(vmin=0, vmax=generations)
    sm = plt.cm.ScalarMappable(cmap='viridis', norm=norm)
    sm.set_array([])
    fig.colorbar(sm, ax=ax, cax=cax, orientation='vertical', label='Generation')

    plt.show()

    return max(population, key=fitness_function)

Faire fonctionner l'ensemble

Enfin, nous devons définir les paramètres de notre algorithme et l'exécuter.

# Parameters for the genetic algorithm
population_size = 100
lower_bound = -50
upper_bound = 50
generations = 20
mutation_rate = 1

# Run the genetic algorithm
best_solution = genetic_algorithm(population_size, lower_bound, upper_bound, generations, mutation_rate)
print(f"Best solution found: a = {best_solution[0]}, b = {best_solution[1]}, c = {best_solution[2]}")

Condition de résiliation (facultatif)

Dans cet exemple, nous avons fixé un nombre spécifique de générations pour l'exécution de notre algorithme. Cependant, nous aurions pu mettre en place une condition de terminaison qui aurait arrêté le programme lorsque nous avons atteint une valeur d'aptitude cible. Cela pourrait ressembler à ceci :

def termination_condition(fitnesses, target_fitness):
    return max(fitnesses) >= target_fitness

La mise en place de l'ensemble

Voici le code complet.

import random
import matplotlib.pyplot as plt
import numpy as np
from prettytable import PrettyTable

# Define the fitness function (objective is to create the flattest U-shape)
def fitness_function(params):
    a, b, c = params
    if a <= 0:
        return -float('inf')  # Penalize downward facing u-shapes heavily
    vertex_x = -b / (2 * a) #x value at vertex
    vertex_y = a * (vertex_x ** 2) + b * vertex_x + c #y value at vertex
    y_left = a * (-1) ** 2 + b * (-1) + c #y-coordinate at x = -1
    y_right = a * (1) ** 2 + b * (1) + c #y-coordinate at x = 1
    curviness = abs(y_left - vertex_y) + abs(y_right - vertex_y)
    return -curviness  # Negate to minimize curviness

# Create the initial population
def create_initial_population(size, lower_bound, upper_bound):
    population = []
    for _ in range(size):
        individual = (random.uniform(lower_bound, upper_bound),
                      random.uniform(lower_bound, upper_bound),
                      random.uniform(lower_bound, upper_bound))
        population.append(individual)
    return population

# Selection function using tournament selection
def selection(population, fitnesses, tournament_size=3):
    selected = []
    for _ in range(len(population)):
        tournament = random.sample(list(zip(population, fitnesses)), tournament_size)
        winner = max(tournament, key=lambda x: x[1])[0]
        selected.append(winner)
    return selected

# Crossover function
def crossover(parent1, parent2):
    alpha = random.random()
    child1 = tuple(alpha * p1 + (1 - alpha) * p2 for p1, p2 in zip(parent1, parent2))
    child2 = tuple(alpha * p2 + (1 - alpha) * p1 for p1, p2 in zip(parent1, parent2))
    return child1, child2

# Mutation function
def mutation(individual, mutation_rate, lower_bound, upper_bound):
    individual = list(individual)
    for i in range(len(individual)):
        if random.random() < mutation_rate:
            mutation_amount = random.uniform(-1, 1)
            individual[i] += mutation_amount
            # Ensure the individual stays within bounds
            individual[i] = max(min(individual[i], upper_bound), lower_bound)
    return tuple(individual)

# Main genetic algorithm function
def genetic_algorithm(population_size, lower_bound, upper_bound, generations, mutation_rate):
    population = create_initial_population(population_size, lower_bound, upper_bound)
    
    # Prepare for plotting
    fig, axs = plt.subplots(3, 1, figsize=(12, 18))  # 3 rows, 1 column for subplots
    best_performers = []
    all_populations = []

    # Prepare for table
    table = PrettyTable()
    table.field_names = ["Generation", "a", "b", "c", "Fitness"]

    for generation in range(generations):
        fitnesses = [fitness_function(ind) for ind in population]

        # Store the best performer of the current generation
        best_individual = max(population, key=fitness_function)
        best_fitness = fitness_function(best_individual)
        best_performers.append((best_individual, best_fitness))
        all_populations.append(population[:])
        table.add_row([generation + 1, best_individual[0], best_individual[1], best_individual[2], best_fitness])

        population = selection(population, fitnesses)

        next_population = []
        for i in range(0, len(population), 2):
            parent1 = population[i]
            parent2 = population[i + 1]

            child1, child2 = crossover(parent1, parent2)

            next_population.append(mutation(child1, mutation_rate, lower_bound, upper_bound))
            next_population.append(mutation(child2, mutation_rate, lower_bound, upper_bound))

        # Replace the old population with the new one, preserving the best individual
        next_population[0] = best_individual
        population = next_population

    # Print the table
    print(table)

    # Plot the population of one generation (last generation)
    final_population = all_populations[-1]
    final_fitnesses = [fitness_function(ind) for ind in final_population]

    axs[0].scatter(range(len(final_population)), [ind[0] for ind in final_population], color='blue', label='a')
    axs[0].scatter([final_population.index(best_individual)], [best_individual[0]], color='cyan', s=100, label='Best Individual a')
    axs[0].set_ylabel('a', color='blue')
    axs[0].legend(loc='upper left')
    
    axs[1].scatter(range(len(final_population)), [ind[1] for ind in final_population], color='green', label='b')
    axs[1].scatter([final_population.index(best_individual)], [best_individual[1]], color='magenta', s=100, label='Best Individual b')
    axs[1].set_ylabel('b', color='green')
    axs[1].legend(loc='upper left')
    
    axs[2].scatter(range(len(final_population)), [ind[2] for ind in final_population], color='red', label='c')
    axs[2].scatter([final_population.index(best_individual)], [best_individual[2]], color='yellow', s=100, label='Best Individual c')
    axs[2].set_ylabel('c', color='red')
    axs[2].set_xlabel('Individual Index')
    axs[2].legend(loc='upper left')
    
    axs[0].set_title(f'Final Generation ({generations}) Population Solutions')

    # Plot the values of a, b, and c over generations
    generations_list = range(1, len(best_performers) + 1)
    a_values = [ind[0][0] for ind in best_performers]
    b_values = [ind[0][1] for ind in best_performers]
    c_values = [ind[0][2] for ind in best_performers]
    fig, ax = plt.subplots()
    ax.plot(generations_list, a_values, label='a', color='blue')
    ax.plot(generations_list, b_values, label='b', color='green')
    ax.plot(generations_list, c_values, label='c', color='red')
    ax.set_xlabel('Generation')
    ax.set_ylabel('Parameter Values')
    ax.set_title('Parameter Values Over Generations')
    ax.legend()

    # Plot the fitness values over generations
    best_fitness_values = [fit[1] for fit in best_performers]
    min_fitness_values = [min([fitness_function(ind) for ind in population]) for population in all_populations]
    max_fitness_values = [max([fitness_function(ind) for ind in population]) for population in all_populations]
    fig, ax = plt.subplots()
    ax.plot(generations_list, best_fitness_values, label='Best Fitness', color='black')
    ax.fill_between(generations_list, min_fitness_values, max_fitness_values, color='gray', alpha=0.5, label='Fitness Range')
    ax.set_xlabel('Generation')
    ax.set_ylabel('Fitness')
    ax.set_title('Fitness Over Generations')
    ax.legend()

    # Plot the quadratic function for each generation
    fig, ax = plt.subplots()
    colors = plt.cm.viridis(np.linspace(0, 1, generations))
    for i, (best_ind, best_fit) in enumerate(best_performers):
        color = colors[i]
        a, b, c = best_ind
        x_range = np.linspace(lower_bound, upper_bound, 400)
        y_values = a * (x_range ** 2) + b * x_range + c
        ax.plot(x_range, y_values, color=color)

    ax.set_xlabel('x')
    ax.set_ylabel('y')
    ax.set_title('Quadratic Function')

    # Create a subplot for the colorbar
    cax = fig.add_axes([0.92, 0.2, 0.02, 0.6])  # [left, bottom, width, height]
    norm = plt.cm.colors.Normalize(vmin=0, vmax=generations)
    sm = plt.cm.ScalarMappable(cmap='viridis', norm=norm)
    sm.set_array([])
    fig.colorbar(sm, ax=ax, cax=cax, orientation='vertical', label='Generation')

    plt.show()

    return max(population, key=fitness_function)

# Parameters for the genetic algorithm
population_size = 100
lower_bound = -50
upper_bound = 50
generations = 20
mutation_rate = 1

# Run the genetic algorithm
best_solution = genetic_algorithm(population_size, lower_bound, upper_bound, generations, mutation_rate)
print(f"Best solution found: a = {best_solution[0]}, b = {best_solution[1]}, c = {best_solution[2]}")

Évaluation des résultats

Utilisons nos résultats pour voir comment notre fonction s'est comportée.

Tableau des données brutes issues de l'exemple codé.

Tout d'abord, nous pouvons voir dans notre tableau que nous avons effectué 20 générations et que la condition physique semble passer d'une condition physique relativement négative à une condition physique moins négative à chaque génération. Excellent !

Graphique de l'aptitude au fil des générations de l'exemple codé.

Notre graphique d'aptitude nous permet de confirmer nos soupçons : l'aptitude s'est améliorée au fil du temps et semble s'être quelque peu stabilisée dans les générations ultérieures. Mais nous pouvons également constater que, dans certaines des premières générations, il y avait de très mauvaises solutions que notre modèle a rejetées à juste titre.

Nous pouvons également constater que, sur plusieurs générations, il n'y avait pas beaucoup de diversité dans l'éventail des aptitudes. Ce n'est pas nécessairement une mauvaise chose, mais il faut s'en méfier. Dans certains cas, il peut s'agir d'un indicateur de convergence prématurée, un problème qui survient lorsqu'il n'y a pas assez de diversité dans votre population.

Ensuite, traçons nos équations de chaque génération pour voir si nous avons vraiment aplani les choses.

Graphique des équations avec solutions de l'exemple codé.

Nous pouvons constater que nos solutions de première génération sont très incurvées, ce qui est logique. Cette équation produit un graphique en forme de U. Mais nous pouvons également constater que les générations suivantes sont devenues de plus en plus plates. C'est exactement ce que nous recherchions !

Il convient de noter que nous ne cherchons explicitement qu'à l'intérieur de nos limites de -50 - 50. Si l'on agrandissait ce graphique, on verrait que même ces lignes apparemment plates sont toujours des formes en U, mais avec des bases plus larges.

Cet exemple souligne l'importance d'être prudent avec nos hypothèses dans les analyses afin de s'assurer qu'elles soutiennent nos prédictions. Notre modèle a fait exactement ce que nous voulions qu'il fasse, mais seulement dans les limites que nous lui avons données. Si nous voulions trouver une combinaison de variables qui créerait une forme plate plus éloignée, nous devrions réexécuter le modèle avec des limites plus larges.

Graphique de l'évolution de chaque paramètre à chaque génération de l'exemple codé.

Nous pouvons représenter graphiquement chacune des variables pour voir dans quelle mesure elles ont changé au fil des générations. Nous pouvons constater que dans cette simulation, c a connu des variations importantes au début, tandis que a et b ont connu des variations beaucoup moins importantes. Ce graphique sera différent à chaque fois que nous effectuerons cette simulation, même si nous ne modifions aucun paramètre, car notre population de départ est aléatoire.

Trois sous-graphes représentant chacun l'ensemble de la population d'individus de la génération finale de l'exemple codé.

Le dernier graphique que je souhaite examiner est un instantané de l'ensemble de la population en une seule génération : la dernière génération. Étant donné que chaque individu de la population possède trois paramètres, j'ai décidé de les séparer en trois sous-graphes au lieu de m'embarrasser de graphes tridimensionnels. 

Ce que je veux vraiment voir dans ces graphiques, c'est s'il y a une bonne diversité au sein de cette génération. Sans une bonne dose de diversité, nous pourrions nous retrouver dans une situation où les seules solutions disponibles sont celles qui présentent de faibles valeurs d'aptitude, ce qui entraînerait une convergence prématurée. Mais il semble que ce graphique présente une bonne diversité, et je suis donc satisfait de ce résultat.

Considérations et conseils

Les algorithmes génétiques peuvent être utilisés dans une grande variété de situations. Mais il y a quelques considérations à garder à l'esprit.

Réglage des paramètres

Comme pour tout modèle, les performances d'un algorithme génétique dépendent de divers paramètres, notamment la taille de la population, le taux de croisement, le taux de mutation et les paramètres limites. La modification de ces paramètres changera les performances de votre modèle.

En règle générale, une population plus importante vous permettra de trouver plus rapidement la solution optimale, car il y a plus d'options parmi lesquelles choisir. Cependant, l'augmentation de la taille des populations nécessite plus de temps et de ressources pour fonctionner.

Un taux de croisement plus élevé peut conduire à une convergence plus rapide en combinant plus fréquemment les caractéristiques bénéfiques de différents individus. Toutefois, un taux de croisement trop élevé peut perturber la structure de la population et entraîner une convergence prématurée.

Un taux de mutation plus élevé permet de maintenir la diversité génétique, ce qui empêche l'algorithme de rester bloqué à un optimum local. Toutefois, si le taux de mutation est trop élevé, il peut perturber le processus de convergence en introduisant trop d'aléa, ce qui rend difficile l'affinement des solutions par l'algorithme.

Les paramètres de délimitation définissent la plage dans laquelle l'algorithme recherche des solutions. Il est important de les adapter au problème particulier de votre entreprise. Une zone de délimitation trop étroite peut ne pas permettre de trouver des solutions optimales à votre problème. Une zone de délimitation trop large nécessitera plus de temps et de ressources. Mais il y a aussi d'autres considérations. 

Par exemple, dans notre exemple codé ci-dessus, cette équation n'a théoriquement aucune limite. Mais en pratique, nous ne pouvons pas demander à l'ordinateur de trouver l'arc le plus plat dans un graphe infiniment grand. Des limites sont donc nécessaires. Mais la modification de ces limites modifiera également la réponse optimale. À mon avis, il est impératif, quel que soit le modèle, d'établir des limites appropriées à votre cas d'utilisation spécifique.

Il peut y avoir d'autres paramètres importants à régler dans votre modèle particulier. Expérimentez avec différentes valeurs pour trouver les meilleurs paramètres pour votre problème. Pour en savoir plus sur l'optimisation des AG, consultez le site Informed Methods : Algorithmes génétiques.

Encodage

Le codage est une étape importante dans la mise en place d'un algorithme génétique. Il s'agit de convertir les solutions potentielles dans un format que l'algorithme peut traiter. Par exemple, imaginons que nous concevions un algorithme génétique pour optimiser les itinéraires de livraison de nos camions. Comment transformer une liste de lieux de livraison en un chromosome à intégrer dans un AG ? Le codage transforme cette liste en une séquence que l'algorithme peut manipuler, par exemple une liste ordonnée de lieux représentant un itinéraire de livraison possible.

Un codage approprié permet à l'algorithme génétique d'explorer efficacement l'espace de solution et de combiner ou de faire muter les solutions de manière significative. Sans elle, l'algorithme ne serait pas en mesure de traiter des données complexes. Les données telles que les lieux de livraison, les problèmes de programmation ou les interactions avec le service clientèle ne sont accessibles aux ordinateurs que par le biais de l'encodage. 

Il existe plusieurs schémas d'encodage. Vous pouvez en savoir plus pour décider ce qui convient le mieux à votre situation dans Travailler avec des données catégorielles en Python ou Comment convertir des chaînes de caractères en octets en Python.

Convergence prématurée

La convergence prématurée est un problème qui survient lorsque la population devient trop similaire. L'algorithme peut ainsi rester bloqué à un optimum local au lieu de trouver l'optimum global. Essentiellement, s'il n'y a pas assez de diversité dans la population, les solutions deviennent "consanguines" et vous n'obtenez pas la meilleure solution.

Vous pouvez essayer quelques techniques pour éviter une convergence prématurée. Un taux de mutation plus élevé peut introduire davantage de diversité dans la population, ce qui permet d'explorer de nouvelles zones de l'espace de solution. Vous pouvez également essayer de commencer avec une population initiale plus diversifiée afin de garantir une large exploration de l'espace de solution dès le début.

Si vous êtes toujours confronté à une convergence prématurée, vous pouvez essayer d'ajuster les paramètres tels que le taux de mutation et le taux de croisement de manière dynamique en fonction de la progression de l'algorithme. Vous pouvez également utiliser plusieurs populations (imaginez des îles) qui échangent occasionnellement des individus pour maintenir la diversité.

Pour en savoir plus sur la convergence prématurée et d'autres erreurs de l'apprentissage automatique, consultez la rubrique Contrôler les concepts de l'apprentissage automatique dans le cours de suivi des concepts de l'apprentissage automatique.

L'élitisme

D'autre part, des croisements et des mutations importants ou une sélection aléatoire peuvent empêcher la reproduction de bonnes solutions. C'est là que l'élitisme peut intervenir. L'élitisme est une technique selon laquelle les meilleurs individus sont directement transmis à la génération suivante afin de préserver les bonnes solutions. Cela permet de s'assurer que les meilleures solutions ne sont pas perdues au cours du processus d'évolution.

Cependant, soyez prudent si vous utilisez l'élitisme. Si l'élitisme est utilisé sans une diversité de population suffisamment élevée, vous risquez d'obtenir une convergence prématurée. Si votre problème requiert des techniques d'élitisme, veillez à les associer à des fonctions de croisement et de mutation suffisamment puissantes et à une population de grande taille. Cette approche permet de maintenir un équilibre sain entre l'exploitation des solutions connues et l'exploration de nouvelles possibilités.

Conclusion

Les algorithmes génétiques sont un exemple fantastique de science des données s'inspirant du monde naturel. Ils offrent une méthode puissante pour résoudre des problèmes d'optimisation complexes en imitant le processus de sélection naturelle.

Si vous vous intéressez à d'autres modèles inspirés de la biologie, découvrez les réseaux neuronaux et d'autres techniques d'apprentissage profond dans la rubrique Introduction à l'apprentissage profond en Python. Vous pouvez également être intéressé par le cours de DataCamp intitulé Cours sur les concepts de l'IA générative et L'éthique de l'IA.

Si vous avez envie de réaliser un projet avec des données biologiques, consultez le site Analyse de données génomiques en R ou Analyse d'images biomédicales en Python.

Obtenez une certification de haut niveau en matière d'IA

Démontrez que vous pouvez utiliser l'IA de manière efficace et responsable.

Amberle McKee's photo
Author
Amberle McKee
LinkedIn

Je suis titulaire d'un doctorat et j'ai 13 ans d'expérience dans le traitement des données dans un environnement de recherche biologique. Je crée des logiciels dans plusieurs langages de programmation, notamment Python, MATLAB et R. Je suis passionné par le partage de mon amour de l'apprentissage avec le monde.

Sujets

Apprenez l'IA avec ces cours !

cours

Implementing AI Solutions in Business

2 hr
24.6K
Discover how to extract business value from AI. Learn to scope opportunities for AI, create POCs, implement solutions, and develop an AI strategy.
Afficher les détailsRight Arrow
Commencer le cours
Voir plusRight Arrow
Apparenté

blog

Les 32 meilleures questions d'entretien sur AWS et leurs réponses pour 2024

Un guide complet pour explorer les questions d'entretien AWS de base, intermédiaires et avancées, ainsi que des questions basées sur des situations réelles. Il couvre tous les domaines, garantissant ainsi une stratégie de préparation bien équilibrée.
Zoumana Keita 's photo

Zoumana Keita

30 min

blog

Q2 2023 DataCamp Donates Digest

DataCamp Donates a offert plus de 20k bourses d'études à nos partenaires à but non lucratif au deuxième trimestre 2023. Découvrez comment des apprenants défavorisés et assidus ont transformé ces opportunités en réussites professionnelles qui ont changé leur vie.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

blog

Les 20 meilleures questions d'entretien pour les flocons de neige, à tous les niveaux

Vous êtes actuellement à la recherche d'un emploi qui utilise Snowflake ? Préparez-vous à répondre à ces 20 questions d'entretien sur le flocon de neige pour décrocher le poste !
Nisha Arya Ahmed's photo

Nisha Arya Ahmed

20 min

blog

Célébration de Saghar Hazinyar : Une boursière de DataCamp Donates et une diplômée de Code to Inspire

Découvrez le parcours inspirant de Saghar Hazinyar, diplômée de Code to Inspire, qui a surmonté les défis en Afghanistan et s'est épanouie grâce à une bourse de DataCamp Donates.
Fereshteh Forough's photo

Fereshteh Forough

4 min

blog

2022-2023 Rapport annuel DataCamp Classrooms

À l'aube de la nouvelle année scolaire, DataCamp Classrooms est plus motivé que jamais pour démocratiser l'apprentissage des données, avec plus de 7 650 nouveaux Classrooms ajoutés au cours des 12 derniers mois.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

8 min

blog

Nous avons fait don de bourses DataCamp Premium à un million de personnes, et ce n'est pas fini.

Réparties entre nos deux programmes d'impact social, DataCamp Classrooms et #DCDonates, les bourses offrent un accès illimité à tout ce que DataCamp Premium a à offrir.
Nathaniel Taylor-Leach's photo

Nathaniel Taylor-Leach

Voir plusVoir plus