Gli algoritmi genetici: La selezione della soluzione più adatta

Gli algoritmi genetici: La selezione della soluzione più adatta

Condividi con i tuoi amici...

Gli algoritmi genetici sono un tipo di algoritmi di ottimizzazione ispirati al processo evolutivo biologico. Essi utilizzano un approccio generazionale, simile alla riproduzione naturale, per trovare una soluzione ottimale a un problema specifico.

Un rapido richiamo ai basilari concetti dell’evoluzione biologica

Il processo evolutivo in ambito biologico riguarda una popolazione di individui dotati ognuno di caratteristiche diverse grazie alle quali essi si adattano più o meno bene alle condizioni ambientali. Gli individui che meglio si adattano a tali condizioni hanno più probabilità di riprodursi e quindi di trasmettere le loro caratteristiche alla generazione successiva (fitness migliore).

Durante la meiosi, il processo di divisione cellulare che da origine ai gameti, le cellule riproduttive, avvengono due importanti fenomeni: Il crossing-over e le mutazioni.

Il crossing-over è lo scambio di parti omologhe dei cromosomi che fa si che la prole erediti delle caratteristiche da ambo i genitori in modo casuale.

mentre le mutazioni sono cambiamenti casuali dei geni responsabili della comparsa di nuove caratteristiche inaspettate. Schematizzando possiamo affermare che gli aspetti salienti del processo sono:

-la presenza di una popolazione di individui ben rappresentata dal loro patrimonio genetico
-la presenza di condizioni ambientali che operano una selezione sugli individui e quindi sui loro geni
-il processo di crossing-over responsabile del mescolamento del materiale genetico
-le mutazioni responsabili della “comparsa” di nuovi geni (geni mutati)
-l’insorgenza di una nuova generazione di individui con il nuovo patrimonio genetico

Rappresentiamo in modo semplificato una popolazione di cromosomi diversi

La nuova generazione costituisce la popolazione di individui su cui il processo identico agisce nuovamente se le condizioni ambientali rimangono le medesime. Dopo numerose generazioni ci si aspetta di osservare una popolazione molto ben adattata alle condizioni ambientali.

Se ci focalizziamo sul procedimento insito in questo processo naturale ci accorgiamo che è generalizzabile ai casi in cui si vogliono individuare “elementi ottimali” rispetto ad una data “condizione”.

Esempio: il massimo di una funzione

Vediamo, per esempio, come il procedimento ben si adatta a determinare il massimo di una funzione matematica.

Consideriamo un caso semplice in cui dobbiamo trovare il valore massimo di una funzione matematica univariata, ad esempio

f(x) = -x2 + 5x.

Gli individui o elementi della popolazione vengono chiamati semplicemente “cromosomi” per mantenere una certa analogia con il processo biologico. Nel caso della funzione matematica, essi sono numeri, mentre quella che biologicamente era la condizione ambientale ora diventa la condizione di massimo valore numerico che la funzione assume in corrispondenza di quei numeri.

  • Iniziamo generando una popolazione iniziale di cromosomi casuali rappresentanti, per esempio, i valori di x: [1.2, 3.5, -0.8, 2.1].
  • Calcoliamo il valore della funzione per ciascun cromosoma della popolazione iniziale e otteniamo i punteggi di valutazione: [3.88, 10.25, 3.56, 4.41].
  • Creiamo una distribuzione di probabilità che segue questa valutazione: [3.88/somma, 10.25/somma, 3.56/somma, 4.41/somma] = [0.18, 0.46, 0.16, 0.20] dove somma = 3.88 + 10.25 + 3.56 + 4.41 e facciamo si che l’algoritmo scelga tra gli individui in base alle probabilità indicate (18% di probabilità per il primo, 46% per il secondo e così via). In questo modo avviene la selezione dei migliori individui che devono riprodursi.
  • Applichiamo l’operatore di crossing-over alle coppie di cromosomi selezionati per generare dei figli.
  • Introduciamo una mutazione casuale in modo che appaia un nuovo individuo o cromosoma
  • Sostituiamo i cromosomi con valori più bassi della vecchia popolazione con i nuovi cromosomi.

Ripetiamo i passaggi da 2 a 6 per un numero prefissato di generazioni o finché la soluzione ottima non viene raggiunta. Con ogni generazione successiva, la popolazione subirà selezione, incrocio e mutazione, permettendo alle caratteristiche migliori di essere trasmesse e mescolate per avvicinarsi a una soluzione ottima.

Codice python d’esempio di un algoritmo genetico


import random
import numpy as np

# Funzione obiettivo
def objective_function(x):
    return -x**2 + 5*x

# Inizializzazione della popolazione
def initialize_population(population_size):
    population = [random.uniform(0, 5) for _ in range(population_size)]
    return population

# Valutazione della popolazione
def evaluate_population(population):
    fitness_scores = np.array([objective_function(chromosome) for chromosome in population])
    return fitness_scores

# Selezione dei genitori
def select_parents(population, fitness_scores, num_parents):
    probabilities = fitness_scores / np.sum(fitness_scores)
    parents = np.random.choice(population, size=num_parents, replace=True, p=probabilities)
    return parents

# Operatore di incrocio (Crossover)
def crossover(parents, num_offsprings):
    offsprings = []
    for _ in range(num_offsprings):
        parent1, parent2 = np.random.choice(parents, size=2, replace=False)
        offspring = (parent1 + parent2) / 2  # Incrocio semplice: media dei genitori
        offsprings.append(offspring)
    return offsprings

# Operatore di mutazione
def mutate(offsprings, mutation_rate):
    mutated_offsprings = []
    for offspring in offsprings:
        if random.random() < mutation_rate:
            mutated_offspring = random.uniform(0, 5)  # Generazione di un nuovo cromosoma casuale
        else:
            mutated_offspring = offspring
        mutated_offsprings.append(mutated_offspring)
    return mutated_offsprings

# Esecuzione dell'Algoritmo Genetico
def genetic_algorithm(population_size, num_generations, num_parents, num_offsprings, mutation_rate):
    population = initialize_population(population_size)

    best_solution = None
    best_fitness = float('-inf')

    for generation in range(num_generations):
        print("Generazione", generation)
        fitness_scores = evaluate_population(population)
        

        current_best_fitness = np.max(fitness_scores)
        if current_best_fitness > best_fitness:
            best_fitness = current_best_fitness
            best_solution_index = np.argmax(fitness_scores)
            best_solution = population[best_solution_index]
            print("Migliore soluzione:",best_solution  ,"con fitness:", current_best_fitness)
            
        parents = select_parents(population, fitness_scores, num_parents)
        offsprings = crossover(parents, num_offsprings)
        mutated_offsprings = mutate(offsprings, mutation_rate)

        # Sostituiamo i cromosomi meno adatti con i nuovi cromosomi mutati
        population = mutated_offsprings

    return best_solution

# Utilizzo dell'Algoritmo Genetico
population_size = 50
num_generations = 10
num_parents = 20
num_offsprings = 30
mutation_rate = 0.1

best_solution = genetic_algorithm(population_size, num_generations, num_parents, num_offsprings, mutation_rate)
print("Soluzione migliore trovata:", best_solution)

DIAGRAMMA DELL’ALGORITMO

Spieghiamo il codice

CLICCA SULL’IMMAGINE PER INGRANDIRE

Applicazioni dell’algoritmo genetico

Questo procedimento ben si adatta a problemi di massimo o di minimo di funzioni ben più complesse, ma può adattarsi anche ai casi in cui non esiste una funzione matematica a motivo dell’alta complessità del problema. La “condizione ambientale” che permette di valutare ogni individuo può essere rappresentata dalla risposta che si ottiene inviando certi input ad un sistema predefinito. L’importante è che per ogni input (individuo) sia possibile ottenere un valore numerico in modo da realizzare una funzione di fitness.

Gli Algoritmi Genetici possono essere utilizzati per ottimizzare i parametri di un modello o di un algoritmo, ad esempio per trovare la combinazione di parametri che massimizza l’accuratezza di un modello di machine learning. Possono essere utilizzati per ottimizzare l’architettura di una rete neurale artificiale. Possono essere impiegati per determinare il numero e la disposizione degli strati, nonché i pesi dei collegamenti tra i neuroni. Gli AG si possono impiegare anche per risolvere problemi di pianificazione e scheduling, ad esempio per ottimizzare l’allocazione delle risorse in un’azienda o per pianificare e ottimizzare gli orari di esame per gli studenti.

Un’altra applicazione è l’ottimizzazione di strategie di trading algoritmico, cercando la combinazione di parametri che massimizza il rendimento degli investimenti.

Nel campo dell’ingegneria servono per ottimizzare il design di componenti, come ad esempio la forma di un’ala di un aereo o il profilo di una turbina.

Ottimizzazione della strategia di trading

Quando si tratta di ottimizzare una strategia di trading utilizzando gli Algoritmi Genetici, può essere difficile ottenere una funzione analitica che rappresenti il comportamento e il rendimento dei mercati finanziari. Ciò è spesso dovuto alla complessità dei mercati finanziari, che sono influenzati da molteplici variabili, tra cui fattori economici, politici ed emotivi, che possono essere difficili da quantificare e modellare in modo preciso attraverso una formula analitica.

Invece, un approccio più pratico per valutare e ottimizzare le strategie di trading utilizzando gli Algoritmi Genetici consiste nell’utilizzare i dati storici e le simulazioni. Questo approccio può essere molto efficace perché consente di valutare le strategie di trading in base alle prestazioni passate, fornendo una valutazione realistica di come queste strategie avrebbero funzionato nel contesto storico dei mercati finanziari.

Utilizzando i dati storici, è possibile simulare l’applicazione di diverse strategie di trading e calcolare il rendimento e altre metriche di interesse, come il rapporto di Sharpe, la massimizzazione del rendimento o la minimizzazione del rischio. Queste metriche possono essere utilizzate come funzione di fitness nella valutazione e nell’ottimizzazione delle strategie di trading utilizzando gli Algoritmi Genetici.

Un vantaggio di utilizzare i dati storici è che ci consente di catturare l’effetto di variabili non lineari, tendenze di mercato, volatilità e altri fenomeni che possono influenzare il rendimento delle strategie di trading. Inoltre, l’utilizzo dei dati storici consente di testare la robustezza delle strategie di trading su diverse condizioni di mercato e di identificare quelle che potrebbero aver funzionato solo in determinate circostanze.

Esempio

Supponiamo di voler utilizzare gli Algoritmi Genetici per ottimizzare una strategia di trading basata su un insieme di indicatori tecnici. Per semplificare l’esempio, consideriamo due indicatori: la media mobile a 50 giorni (SMA50) e il Relative Strength Index (RSI).

L’obiettivo è massimizzare il rendimento e minimizzare il rischio della strategia di trading, utilizzando i dati storici per valutare le performance.

Iniziamo generando una popolazione iniziale di strategie di trading, rappresentate come cromosomi che contengono gli indicatori e i relativi parametri. Ad esempio, un cromosoma potrebbe essere rappresentato come [SMA50, RSI, SMA50_periodo, RSI_periodo], dove SMA50_periodo e RSI_periodo sono i periodi scelti per calcolare i due indicatori.

Successivamente, valutiamo la performance di ogni strategia nella popolazione utilizzando i dati storici. Applichiamo ciascuna strategia al dataset di dati e calcoliamo il rendimento basato sugli scambi effettuati, insieme ad altre metriche come il rapporto di Sharpe o la deviazione standard dei rendimenti. Queste metriche riflettono il rendimento e il rischio associati a ciascuna strategia.

Le metriche ottenute vengono utilizzate come funzioni di fitness per valutare la bontà delle strategie. Ad esempio, potremmo considerare come funzione di fitness il rendimento ottenuto negli ultimi sei mesi, cercando di massimizzarlo. Potremmo anche considerare il rapporto di Sharpe come funzione di fitness, cercando di massimizzare il rendimento rapportato al rischio.

In base alle valutazioni delle metriche di fitness, selezioniamo i genitori migliori per la successiva generazione di strategie. Possiamo utilizzare una selezione proporzionale alla fitness, in cui le strategie con una maggiore fitness hanno maggiori probabilità di essere selezionate come genitori per la riproduzione. Possiamo anche utilizzare l’operatore di crossing-over per combinare i genitori selezionati e generare nuove strategie, abbinando gli indicatori e i parametri.

Dopo la riproduzione, possiamo applicare l’operatore di mutazione per introdurre variazione nelle strategie. Ad esempio, potremmo modificare casualmente il periodo del SMA50 per una strategia, o cambiare l’indicatore utilizzato.

Ripetiamo questi passaggi per diverse generazioni, cercando di migliorare continuamente la fitness delle strategie. Alla fine dell’algoritmo genetico, otteniamo la strategia migliore, con i relativi indicatori e parametri ottimizzati per massimizzare il rendimento e minimizzare il rischio.

L’importanza dell’utilizzo dei dati storici risiede nel fatto che le performance delle strategie di trading sono valutate in base alle reali dinamiche di mercato e alle fluttuazioni dei prezzi nel tempo. Questo ci permette di valutare la capacità delle strategie di adattarsi e performare in diverse condizioni di mercato.