Skip to content
Torna ai risultati

Algoritmo Genetico — Ottimizzazione Evolutiva

Introdotto da
John Henry Holland
Anno
1975
Tipo
Population-based metaheuristic

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Un algoritmo genetico (GA) è un metodo di ottimizzazione meta-euristico basato su popolazioni, introdotto da John Henry Holland (1975), che mima i principi della selezione naturale.

Mantiene una popolazione di soluzioni candidate e le migliora iterativamente attraverso operatori di selezione, crossover e mutazione, rendendolo particolarmente potente su spazi di ricerca discontinui, non convessi e multimodali dove i metodi classici basati sul gradiente falliscono.

L’intuizione alla base del metodo

Immagina di avere migliaia di possibili risposte a un problema difficile e nessuna formula per trovare la migliore. Un algoritmo genetico tratta ogni risposta candidata come un individuo in una popolazione. In ogni generazione conserva gli individui più adatti, li incrocia per mescolare i loro buoni tratti e occasionalmente muta la prole per introdurre novità. Nel corso di molte generazioni, la popolazione si sposta verso soluzioni sempre migliori — non seguendo un gradiente, ma mimando il modo in cui l'evoluzione modella gli organismi nel tempo.

Storia

L'algoritmo genetico è stato introdotto da John Henry Holland nel suo libro del 1975 Adaptation in Natural and Artificial Systems, che ha formalizzato la nozione di schema (building block) e ha fornito l'analisi teorica fondamentale del perché crossover e selezione guidano la ricerca verso regioni più adatte. Gli studenti di Holland — in particolare David Goldberg — hanno reso popolari i GA attraverso applicazioni ingegneristiche negli anni '80. Kalyanmoy Deb ha successivamente esteso il framework a contesti multi-obiettivo, culminando nell'algoritmo NSGA-II ampiamente adottato (2002). Oggi i GA rimangono uno strumento standard nell'ambito del calcolo evolutivo, con ricerche attive sui metodi ibridi che combinano la ricerca evolutiva con il raffinamento locale.

Quando usarlo

Gli algoritmi genetici sono appropriati quando lo spazio di ricerca è ampio, discontinuo, non differenziabile o altamente multimodale — condizioni in cui i risolutori basati sul gradiente non possono operare o rimangono intrappolati in ottimi locali. Si applicano a tipi di variabili continue, categoriche, binarie e ordinali e non impongono assunzioni di normalità o distribuzionali. L'unico requisito è una funzione di fitness computabile. Per problemi in cui esiste una formulazione analitica o convessa, i metodi classici (programmazione lineare, discesa del gradiente) sono più veloci e dovrebbero essere preferiti. Sono necessarie iterazioni sufficienti (tipicamente ben oltre 1.000 generazioni) per una convergenza significativa; eseguire troppo poche generazioni è la modalità di fallimento più comune.

Limiti e considerazioni

  • Nessuna garanzia di convergenza all'ottimo globale; i risultati possono variare tra le esecuzioni.
  • Computazionalmente costoso: ogni generazione richiede la valutazione dell'intera popolazione, il che è proibitivo quando la funzione di fitness è lenta.
  • Le prestazioni sono sensibili alle scelte degli iperparametri — dimensione della popolazione, probabilità di crossover e tasso di mutazione — che spesso richiedono una messa a punto specifica per il problema.
  • Per problemi lisci, convessi o ben strutturati, i metodi classici basati sul gradiente o lineari saranno più veloci e affidabili.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Funziona su paesaggi obiettivi discontinui, non differenziabili e multimodali dove i metodi basati sul gradiente falliscono.
  • Non impone assunzioni distribuzionali — l'unico input richiesto è una funzione di fitness computabile.
  • Gestisce naturalmente un'ampia gamma di tipi di variabili: continue, binarie, categoriche e ordinali.
  • La diversità della popolazione consente l'esplorazione simultanea di più regioni dello spazio di ricerca, riducendo il rischio di intrappolamento prematuro in ottimi locali.
  • Altamente estensibile: operatori di crossover e mutazione specifici del dominio, gestione dei vincoli e varianti multi-obiettivo (ad esempio, NSGA-II) sono ben stabiliti in letteratura.

Applicazioni

  • Ottimizzazione del design ingegneristico: trovare configurazioni di parametri ottimali per strutture, circuiti o sistemi meccanici.
  • Problemi di pianificazione e routing: pianificazione di job-shop, routing di veicoli e orari dove lo spazio di ricerca combinatorio è troppo grande per una ricerca esaustiva.
  • Apprendimento automatico: ottimizzazione degli iperparametri, ricerca dell'architettura neurale e selezione delle caratteristiche.
  • Ricerca operativa: ottimizzazione della catena di approvvigionamento, allocazione di portafoglio e assegnazione di risorse sotto vincoli complessi.
  • Bioinformatica: allineamento di sequenze, predizione della struttura proteica e inferenza di reti di regolazione genica.

Come funziona

Come funziona

1

Viene creata una popolazione di soluzioni candidate (individui), tipicamente in modo casuale all'interno dello spazio di ricerca. Ogni individuo codifica una soluzione potenziale — ad esempio come una stringa binaria, un vettore di valori reali o una permutazione — e la dimensione della popolazione è un parametro chiave che determina quanto ampiamente lo spazio di ricerca viene campionato fin dall'inizio.

2

Ogni individuo nella popolazione viene valutato da una funzione di fitness che quantifica quanto sia buona quella soluzione rispetto all'obiettivo del problema. La funzione di fitness è l'unico componente specifico del dominio che l'utente deve fornire; può essere qualsiasi misura computabile — l'output di una simulazione, una formula di costo o una metrica di errore di un modello.

3

Gli individui con fitness più elevata vengono scelti preferenzialmente per diventare genitori della generazione successiva. I meccanismi di selezione comuni includono la selezione a torneo, la selezione a roulette (proporzionale alla fitness) e la selezione basata sul rango. La pressione selettiva controlla il compromesso tra lo sfruttamento di soluzioni di alta qualità e il mantenimento della diversità della popolazione.

4

I genitori selezionati producono prole attraverso il crossover (ricombinazione), dove segmenti delle codifiche di due genitori vengono combinati per formare un nuovo individuo, e attraverso la mutazione, dove piccole modifiche casuali vengono applicate ai singoli geni. La probabilità di crossover e il tasso di mutazione sono parametri critici di messa a punto: troppo poca mutazione causa convergenza prematura, troppa trasforma la ricerca in una passeggiata casuale.

5

Il ciclo di valutazione → selezione → riproduzione continua per un numero prefissato di generazioni o fino a quando non viene soddisfatto un criterio di convergenza (ad esempio, nessun miglioramento in una finestra di generazioni). L'individuo migliore trovato in tutte le generazioni viene restituito come soluzione. Poiché la convergenza all'ottimo globale non è garantita, si raccomandano più esecuzioni indipendenti per problemi ad alto rischio.

Errori comuni

  • Eseguire troppo poche generazioni è l'errore più comune: con generazioni insufficienti l'algoritmo non converge, quindi i metodi analitici o basati sul gradiente dovrebbero essere preferiti quando è disponibile solo un piccolo budget di iterazioni.
  • La convergenza prematura — la perdita di diversità della popolazione troppo presto — produce un risultato localmente ottimale ma globalmente subottimale; mantenere una dimensione della popolazione e un tasso di mutazione adeguati per contrastare questo fenomeno.
  • L'uso di una funzione di fitness mal definita o errata produce risultati fuorvianti indipendentemente dalla correttezza algoritmica; validare la funzione di fitness in modo indipendente prima di eseguire il GA.
  • Applicare un GA a un problema liscio e convesso dove la discesa del gradiente o la programmazione lineare sarebbero sufficienti spreca risorse computazionali e introduce una stocasticità non necessaria.
  • Riportare una singola esecuzione come soluzione senza verificarne la riproducibilità; per applicazioni ad alto rischio eseguire l'algoritmo più volte e riportare la distribuzione dei risultati.

Domande frequenti

In che modo un algoritmo genetico è diverso dalla discesa del gradiente?

La discesa del gradiente richiede un obiettivo differenziabile e segue il gradiente locale verso il basso. Un algoritmo genetico richiede solo che la fitness possa essere calcolata per qualsiasi soluzione candidata; cerca evolvendo una popolazione piuttosto che seguendo un gradiente, quindi può gestire paesaggi discontinui, non differenziabili e multimodali dove la discesa del gradiente fallisce o si blocca.

Quante generazioni e quanto grande una popolazione mi serve?

Non ci sono regole universali; entrambi dipendono dalla complessità dello spazio di ricerca. Una popolazione troppo piccola o un'esecuzione troppo breve rischiano la convergenza prematura. Come punto di partenza pratico, dimensioni della popolazione di 50-200 e conteggi di generazioni di 100-1.000 sono comuni in letteratura, ma problemi impegnativi richiedono regolarmente di più. Ispezionare sempre le curve di convergenza piuttosto che fissare criteri di arresto arbitrari.

Un algoritmo genetico è garantito per trovare l'ottimo globale?

No. I GA sono euristiche e non forniscono alcuna garanzia di convergenza all'ottimo globale in tempo finito. Per garanzie deterministiche sono necessari metodi esatti come risolutori di programmazione intera. Per decisioni ad alto rischio, eseguire il GA più volte, riportare la distribuzione dei risultati e confrontare la migliore soluzione con eventuali limiti noti.

Quando dovrei scegliere un GA rispetto al simulated annealing o all'ottimizzazione per sciami di particelle?

I GA tendono ad essere preferiti quando la soluzione è codificata naturalmente come una struttura combinatoria (permutazioni, stringhe binarie) o quando sono necessarie estensioni multi-obiettivo. L'ottimizzazione per sciami di particelle è spesso più veloce su problemi continui unimodali. Il simulated annealing è più semplice da implementare per problemi combinatori con un vicinato ben definito. In pratica, è consigliabile confrontare due o tre metodi su una piccola istanza di problema prima di impegnarsi in uno.

Metodi correlati

Fonti

  1. Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.

    Apri il riferimento della pubblicazione
    Copiato.
  2. Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.

    ISBN: 9780471873396
    Copiato.