Impara Selezione, Crossover e Mutazione

Strategie di selezione

La selezione è un processo cruciale negli algoritmi genetici, determina quali individui contribuiscono alla generazione successiva, bilanciando fitness e diversità. Esistono diverse strategie di selezione ampiamente utilizzate:

Selezione a ruota della roulette: Assegna a ciascun individuo una probabilità di selezione proporzionale alla sua fitness. Immagina una ruota in cui la dimensione di ogni fetta corrisponde alla fitness; gli individui con fitness più elevata hanno una maggiore probabilità di essere selezionati;
Selezione tramite torneo: Seleziona casualmente un gruppo (torneo) di individui e sceglie il migliore tra loro come genitore. Questo metodo è semplice ed efficace, e la dimensione del torneo può controllare la pressione selettiva;
Selezione basata sul rango: Ordina gli individui in base alla fitness e assegna le probabilità di selezione in base al loro rango piuttosto che alla fitness assoluta. Questo aiuta a evitare la dominanza di pochi individui con fitness elevata, specialmente in problemi con grandi differenze di fitness.


              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)

Operatori di crossover

Dopo la selezione, gli algoritmi genetici utilizzano il crossover per creare nuovi individui combinando informazioni da due genitori. Il crossover introduce variazione e consente all'algoritmo di esplorare nuove combinazioni di tratti all'interno della popolazione.

Tipi comuni di crossover:

Crossover a punto singolo: Un punto di crossover viene scelto casualmente. La prima parte di un genitore viene combinata con la parte rimanente dell'altro.
Crossover a due punti: Due punti vengono selezionati casualmente. Il segmento tra di essi viene scambiato tra i genitori per produrre la prole.
Crossover uniforme: Ogni gene della prole viene scelto casualmente da uno dei due genitori con uguale probabilità.


              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)

Ruolo della Mutazione

La mutazione è uno dei meccanismi chiave negli algoritmi genetici. Introduce nuovo materiale genetico nella popolazione, aiutando l'algoritmo a evitare la stagnazione e a continuare l'esplorazione di nuove soluzioni. Senza la mutazione, la popolazione potrebbe diventare troppo simile, causando il blocco della ricerca in ottimi locali.

Perché la Mutazione è Importante

Previene la convergenza prematura: la mutazione assicura che la popolazione non diventi troppo uniforme, evitando una convergenza subottimale;
Mantiene la diversità: introducendo alterazioni casuali, la mutazione mantiene una vasta gamma di variazioni genetiche disponibili per le generazioni future;
Permette di sfuggire agli ottimi locali: piccoli cambiamenti casuali consentono all'algoritmo di esplorare nuove aree dello spazio di ricerca che potrebbero portare a soluzioni migliori;
Bilancia il crossover: mentre il crossover combina tratti esistenti, la mutazione ne introduce di nuovi, garantendo che l'algoritmo continui a generare possibilità inedite.

Insieme, queste proprietà rendono la mutazione essenziale per un processo di ricerca robusto e adattivo.

Operatori di Mutazione Comuni

Diverse rappresentazioni del problema richiedono tecniche di mutazione differenti. I due operatori più utilizzati sono:

Mutazione bit-flip: per rappresentazioni binarie — inverte un bit da 0 a 1 o da 1 a 0, introducendo cambiamenti piccoli e controllati;
Mutazione di scambio: per rappresentazioni basate su permutazioni (ad esempio, problemi di ordinamento) — scambia due elementi all'interno di un individuo per generare una nuova configurazione.


              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)

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 2. Capitolo 2

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

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

Scorri per mostrare il menu