Algorithmes génétiques

9.1 Introduction aux algorithmes génétiques.

Les algorithmes génétiques (GA) sont une méthode d'optimisation et de recherche inspirée du processus de sélection naturelle, qui simule les processus biologiques évolutionnaires.

Les algorithmes génétiques sont utilisés pour résoudre des problèmes complexes où les méthodes traditionnelles peuvent être inefficaces. Ces algorithmes utilisent des mécanismes de sélection, de croisement et de mutation pour faire évoluer des solutions.

Principes de fonctionnement :

1. Initialisation :

Une population initiale de solutions possibles (chromosomes) est créée. Chaque solution est encodée sous forme de chaîne (chaîne de bits, chaîne de caractères ou autres structures).

2. Fonction d'adaptation (fitness function) :

Évalue la qualité de chaque solution dans la population.

3. Évaluation :

Chaque solution (individu) est évaluée à l'aide de la fonction d'adaptation, qui détermine à quel point une solution résout le problème.

4. Sélection :

Les solutions avec une meilleure adaptation ont plus de chances d'être sélectionnées pour la reproduction. Des méthodes telles que la sélection à la roulette, la sélection par tournoi et la sélection par classement sont souvent utilisées.

5. Croisement :

Les solutions sélectionnées (parents) sont combinées pour créer de nouvelles solutions (descendants). Le croisement peut être à un point, à deux points ou à plusieurs points.

6. Mutation :

Des modifications aléatoires des nouvelles solutions (mutations) sont appliquées pour introduire de la diversité. Cela aide l'algorithme à éviter les minimums locaux.

7. Remplacement :

La nouvelle population remplace l'ancienne, et le processus se répète jusqu'à ce qu'une condition d'arrêt soit remplie (par exemple, atteindre un certain nombre de générations ou un certain niveau d'adaptation).

Avantages et inconvénients

Avantages :

• Large gamme d'applications : Peuvent être utilisés pour résoudre divers problèmes, y compris ceux où les méthodes analytiques ne fonctionnent pas.
• Optimisation globale : Capables de trouver des optima globaux dans des espaces multidimensionnels et complexes.
• Flexibilité : Peuvent être utilisés avec n'importe quelle fonction d'adaptation.

Inconvénients :

• Coût computationnel élevé : Nécessitent des ressources computationnelles importantes, surtout pour de grandes populations et des problèmes complexes.
• Difficultés à régler les paramètres : L'ajustement des paramètres (taille de la population, probabilité de mutation et de croisement) peut être complexe et affecte fortement les performances.
• Pas de garantie de solution optimale : Pas de garantie que la solution trouvée sera globalement optimale.

En fait, l'algorithme génétique est une heuristique très efficace. Il ne garantit pas qu'il trouvera la meilleure solution, même s'il a accès à toutes les données. Mais pour des situations complexes et de grandes quantités de données, il fournit rapidement une solution proche de l'idéal.

9.2 Exemple d'application

Considérons un exemple d'application d'un algorithme génétique pour l'optimisation d'une fonction.

import random

# Paramètres de l'algorithme génétique
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Définition de la fonction d'adaptation
def fitness_function(x):
    return -x**2 + 10*x
            
# Initialisation de la population
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Sélection (sélection par tournoi)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Croisement (à un point)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutation
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Boucle principale de l'algorithme génétique
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Affichage de la meilleure solution
best_individual = max(population, key=fitness_function)
print("Meilleure solution :", best_individual)
print("Valeur de la fonction :", fitness_function(best_individual))
            
        

Avantages et inconvénients

9.3 Optimisation d'une fonction multidimensionnelle

Tâche :

Trouver la valeur minimale d'une fonction multidimensionnelle.

Solution :

Utilisons le modèle précédent

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Exemple d'utilisation :
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Meilleure solution: {best_solution}")