Algoritmi genetici

9.1 Introduzione agli algoritmi genetici.

Gli algoritmi genetici (GA) sono un metodo di ottimizzazione e ricerca ispirato al processo di selezione naturale, che imita i processi evolutivi biologici.

Gli algoritmi genetici vengono applicati per risolvere compiti complessi dove i metodi tradizionali potrebbero essere inefficaci. Questi algoritmi utilizzano meccanismi di selezione, incrocio (crossover) e mutazione per l'evoluzione delle soluzioni.

Principi di funzionamento:

1. Inizializzazione:

Viene creata una popolazione iniziale di possibili soluzioni (cromosomi). Ogni soluzione è codificata sotto forma di stringa (stringa binaria, stringa di caratteri o altre strutture).

2 Funzione di fitness (fitness function):

Valuta la qualità di ciascuna soluzione nella popolazione.

3. Valutazione:

Ogni soluzione (individuo) viene valutata attraverso la funzione di fitness (fitness function), che determina quanto bene la soluzione risolve il compito.

4. Selezione:

Le soluzioni con la migliore fitness hanno maggiori probabilità di essere selezionate per la riproduzione. Spesso vengono utilizzati metodi come la selezione a ruota di roulette (roulette wheel selection), la selezione a torneo (tournament selection) e la selezione a ranking (rank selection).

5. Incrocio (crossover):

Le soluzioni selezionate (genitori) vengono combinate per creare nuove soluzioni (discendenti). Il crossover può essere a singolo punto, a doppio punto o multipunto.

6. Mutazione:

Vengono applicati cambiamenti casuali nelle nuove soluzioni (mutazioni) per introdurre diversità. Questo aiuta l'algoritmo a evitare minimi locali.

7. Sostituzione:

La nuova popolazione sostituisce la vecchia e il processo si ripete finché non viene soddisfatta una condizione di arresto (ad esempio, raggiungimento di un numero di generazioni specifico o raggiungimento di una certa fitness).

Vantaggi e svantaggi

Vantaggi:

• Ampia gamma di applicazioni: Possono essere applicati per risolvere vari compiti, inclusi quelli dove i metodi analitici non funzionano.
• Ottimizzazione globale: Sono in grado di trovare ottimi globali in spazi complessi e multidimensionali.
• Flessibilità: Possono essere utilizzati con qualsiasi funzione di fitness.

Svantaggi:

• Alti costi computazionali: Richiedono significative risorse computazionali, specialmente per grandi popolazioni e compiti complessi.
• Difficoltà nella configurazione dei parametri: La messa a punto dei parametri (dimensione della popolazione, probabilità di mutazione e crossover) può essere complessa e influenzare notevolmente le prestazioni.
• Assenza di garanzia della soluzione ottimale: Non c'è garanzia che la soluzione trovata sia l'ottimo globale.

In effetti, l'algoritmo genetico è un'euristica altamente efficiente. Non garantisce di trovare la soluzione migliore, anche se ha accesso a tutti i dati. Ma per situazioni complesse e grandi volumi di dati, fornisce rapidamente una soluzione vicina all'ideale.

9.2 Esempio di applicazione

Consideriamo un esempio di applicazione di un algoritmo genetico per l'ottimizzazione di una funzione.

import random

# Parametri dell'algoritmo genetico
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Definizione della funzione di fitness
def fitness_function(x):
    return -x**2 + 10*x
            
# Inizializzazione della popolazione
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Selezione (selezione a torneo)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Incrocio (singolo punto)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutazione
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Ciclo principale dell'algoritmo genetico
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
            
# Output della migliore soluzione
best_individual = max(population, key=fitness_function)
print("Migliore soluzione:", best_individual)
print("Valore della funzione:", fitness_function(best_individual))
            
        

Vantaggi e svantaggi

9.3 Ottimizzazione di una funzione multidimensionale

Compito:

Trovare il valore minimo di una funzione multidimensionale.

Soluzione:

Prendiamo il modello precedente

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
# Esempio di utilizzo:
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"Migliore soluzione: {best_solution}")