Apprendre Sélection, Croisement et Mutation

Stratégies de sélection

La sélection est un processus crucial dans les algorithmes génétiques, déterminant quels individus contribuent à la génération suivante, en équilibrant l'adaptation et la diversité. Plusieurs stratégies de sélection sont largement utilisées :

Sélection par roulette (Roulette Wheel Selection) : Attribue à chaque individu une probabilité de sélection proportionnelle à son adaptation. Imaginez une roue où la taille de chaque segment correspond à l'adaptation ; les individus les plus adaptés ont une plus grande chance d'être sélectionnés ;
Sélection par tournoi (Tournament Selection) : Sélectionne aléatoirement un groupe (tournoi) d'individus et choisit le meilleur parmi eux comme parent. Cette méthode est simple et efficace, et la taille du tournoi permet de contrôler la pression de sélection ;
Sélection par classement (Rank-Based Selection) : Classe les individus selon leur adaptation et attribue les probabilités de sélection en fonction de leur rang plutôt que de leur adaptation absolue. Cela permet d'éviter la domination de quelques individus très adaptés, notamment dans les problèmes présentant de grandes différences d'adaptation.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Opérateurs de croisement

Après la sélection, les algorithmes génétiques utilisent le croisement pour créer de nouveaux individus en combinant les informations de deux parents. Le croisement introduit de la variation et permet à l'algorithme d'explorer de nouvelles combinaisons de caractéristiques au sein de la population.

Types courants de croisement :

Croisement à un point (Single-Point Crossover) : Un point de croisement est choisi aléatoirement. La première partie d'un parent est combinée avec la partie restante de l'autre.
Croisement à deux points (Two-Point Crossover) : Deux points sont sélectionnés aléatoirement. Le segment entre ces deux points est échangé entre les parents pour produire la descendance.
Croisement uniforme (Uniform Crossover) : Chaque gène de la descendance est choisi aléatoirement chez l'un des deux parents avec une probabilité égale.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Rôle de la mutation

La mutation constitue l’un des mécanismes clés dans les algorithmes génétiques. Elle introduit de nouveaux matériaux génétiques dans la population, ce qui aide l’algorithme à éviter la stagnation et à continuer d’explorer de nouvelles solutions. Sans mutation, la population peut devenir trop homogène, ce qui conduit la recherche à se bloquer dans des optima locaux.

Pourquoi la mutation est-elle importante ?

Prévention de la convergence prématurée : la mutation garantit que la population ne devienne pas trop uniforme, évitant ainsi une convergence sous-optimale ;
Maintien de la diversité : en introduisant des modifications aléatoires, la mutation conserve une large gamme de variations génétiques pour les générations futures ;
Possibilité d’échapper aux optima locaux : de petits changements aléatoires permettent à l’algorithme d’explorer de nouvelles zones de l’espace de recherche susceptibles de conduire à de meilleures solutions ;
Équilibre avec le croisement : tandis que le croisement combine des caractéristiques existantes, la mutation en injecte de nouvelles, assurant ainsi la génération continue de possibilités inédites.

Ensemble, ces propriétés rendent la mutation essentielle pour un processus de recherche robuste et adaptatif.

Opérateurs de mutation courants

Différentes représentations de problèmes nécessitent des techniques de mutation spécifiques. Les deux opérateurs les plus utilisés sont :

Mutation par inversion de bit : pour les représentations binaires — inverse un bit de 0 à 1 ou de 1 à 0, introduisant ainsi des modifications petites et contrôlées ;
Mutation par échange : pour les représentations basées sur les permutations (par exemple, les problèmes d’ordonnancement) — échange deux éléments au sein d’un individu pour générer une nouvelle configuration.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 2

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Suggested prompts:

Can you explain how tournament size affects selection pressure?

What are the advantages and disadvantages of each selection strategy?

How do I choose the right selection strategy for my problem?

Awesome!

Completion rate improved to 6.25

Glissez pour afficher le menu