Algoritmo Genetico Stocastico — Ricerca Evolutiva Randomizzata per l'Ottimizzazione
- Introdotto da
- Holland, J. H.
- Anno
- 1975
- Tipo
- Stochastic evolutionary metaheuristic
- Famiglia
- Simulation / optimization
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
L'Algoritmo Genetico Stocastico (SGA) è una meta-euristica basata su popolazione che imita l'evoluzione biologica — selezione, crossover e mutazione — per cercare soluzioni quasi ottimali in spazi complessi, non lineari o combinatori.
I suoi operatori randomizzati lo rendono robusto rispetto agli ottimi locali e ampiamente applicabile in ingegneria, pianificazione, machine learning e ricerca operativa.
L’intuizione alla base del metodo
Immaginate una popolazione di soluzioni candidate che competono per la sopravvivenza. Le soluzioni migliori hanno maggiori probabilità di essere scelte come genitori; i loro discendenti ereditano e ricombinano tratti buoni, mentre occasionali mutazioni casuali introducono novità. Nel corso di molte generazioni, questo processo converge verso regioni di alta qualità dello spazio di ricerca senza richiedere informazioni sul gradiente. L'etichetta 'stocastico' sottolinea che selezione, crossover e mutazione coinvolgono tutti estrazioni probabilistiche, il che distingue il GA canonico da rare varianti deterministiche e gli conferisce capacità di ricerca globale.
Storia
John Holland introdusse le fondamenta teoriche degli algoritmi genetici all'Università del Michigan nel 1975, basandosi su lavori precedenti di Fraser (1957) sui sistemi genetici simulati. Il libro di testo di David Goldberg del 1989 rese popolari i GA per l'ottimizzazione ingegneristica. La natura stocastica della selezione fu formalizzata attraverso il teorema degli schemi, e il metodo divenne una pietra miliare dell'intelligenza evolutiva e dell'intelligenza computazionale.
Quando usarlo
Utilizzare un Algoritmo Genetico Stocastico quando: (1) lo spazio di ricerca è ampio, multimodale o discontinuo e i metodi basati sul gradiente falliscono o non sono applicabili; (2) la funzione obiettivo è una black-box, rumorosa o costosa da valutare ma trattabile per il campionamento a livello di popolazione; (3) problemi combinatori o misti-interi mancano di risolutori esatti efficienti; (4) è accettabile una soluzione quasi ottimale trovata entro un numero ragionevole di valutazioni. NON utilizzare l'SGA quando: il problema è convesso o il gradiente è disponibile e a basso costo — l'ottimizzazione classica converge più velocemente; quando le valutazioni della funzione sono estremamente costose (decine o centinaia), i metodi basati su popolazione possono esaurire il budget; o quando è richiesta una soluzione provabilmente ottimale, poiché i GA non offrono garanzie di ottimalità.
Limiti e considerazioni
- Nessuna garanzia di trovare l'ottimo globale; la qualità della soluzione dipende dalla dimensione della popolazione, dalle scelte degli operatori e dal numero di generazioni.
- Computazionalmente costoso rispetto ai metodi basati sul gradiente su problemi lisci e a bassa dimensionalità — sono necessarie molte valutazioni della funzione.
- La sintonizzazione degli iperparametri (dimensione della popolazione, tasso di crossover, tasso di mutazione) dipende dal problema e richiede spesso sperimentazione.
- La convergenza prematura può verificarsi se la pressione selettiva è troppo alta o il tasso di mutazione è troppo basso, intrappolando la ricerca in regioni subottimali.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Non richiede informazioni sul gradiente — applicabile a obiettivi black-box, discontinui o non differenziabili.
- Gestisce naturalmente spazi di ricerca combinatori, misti-interi e di permutazione con codifica appropriata.
- Parallelizzabile per progettazione: la popolazione può essere valutata in parallelo, riducendo il tempo di clock effettivo.
- Robusto contro gli ottimi locali grazie alla diversità della popolazione e all'esplorazione stocastica.
- Altamente estensibile: operatori, codifiche e schemi di selezione possono essere personalizzati per vincoli specifici del dominio.
Applicazioni
- Pianificazione job-shop e flow-shop nella produzione e nella logistica
- Selezione di feature e sintonizzazione di iperparametri nelle pipeline di machine learning
- Ottimizzazione strutturale e topologica nell'ingegneria meccanica e civile
- Problemi del commesso viaggiatore e di routing dei veicoli nella ricerca operativa
- Predizione della struttura proteica e scoperta di farmaci in bioinformatica
- Ricerca dell'architettura di reti neurali e ottimizzazione dei pesi
Come funziona
Come funziona
Generare una popolazione iniziale di N soluzioni candidate (cromosomi) casualmente o tramite seeding euristico. Ogni cromosoma codifica un punto fattibile nello spazio decisionale — stringhe binarie, vettori reali, permutazioni o alberi a seconda della rappresentazione del problema scelta.
Calcolare la fitness f(x_i) per ogni individuo nella popolazione utilizzando la funzione obiettivo (o un suo surrogato). La fitness quantifica la qualità della soluzione; una fitness maggiore indica una soluzione migliore. Per problemi di minimizzazione, la fitness è spesso definita come il reciproco o una trasformazione della funzione di costo.
Formula
f(x_i), \quad i = 1, \ldots, N
Applicare un operatore di selezione stocastico per scegliere i genitori. La selezione a roulette (proporzionale alla fitness) assegna a ciascun individuo una probabilità proporzionale alla sua fitness. La selezione a torneo, la selezione per rango e l'elitarismo sono varianti comuni che controllano la pressione selettiva.
Formula
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}Con probabilità p_c (tipicamente 0.6–0.9), ricombinare coppie di genitori selezionati per produrre discendenti. Il crossover a punto singolo, a due punti o uniforme scambia materiale genetico tra i cromosomi dei genitori, creando figli che ereditano tratti da entrambi. Questo operatore guida lo sfruttamento di buoni blocchi costitutivi.
Con una bassa probabilità p_m (tipicamente 0.001–0.05 per gene), alterare casualmente singoli geni in ciascun cromosoma discendente. La mutazione mantiene la diversità genetica, previene la convergenza prematura e assicura che l'algoritmo possa sfuggire agli ottimi locali. Il tasso di mutazione è un parametro critico calibrato sul problema.
Sostituire la popolazione corrente con i discendenti (sostituzione generazionale) o utilizzare aggiornamenti allo stato stazionario. Rivalutare la fitness e ripetere dal passo di selezione fino a quando non viene soddisfatto un criterio di arresto — numero massimo di generazioni, una soglia di fitness o nessun miglioramento per un certo numero di generazioni.
Errori comuni
- L'uso di un tasso di mutazione troppo alto riduce efficacemente l'algoritmo a una ricerca casuale e distrugge i guadagni di fitness accumulati.
- Ignorare l'elitarismo nella strategia di sostituzione può causare la perdita della migliore soluzione trovata tra le generazioni.
- Applicare operatori di crossover per valori reali a problemi codificati in binario (o viceversa) rompe la codifica e produce discendenti non fattibili.
- Arrestarsi troppo presto — generazioni insufficienti — è la ragione più comune di scarsa qualità della soluzione nella pratica.
- Trascurare la gestione dei vincoli: crossover e mutazione non vincolati violano frequentemente i vincoli del problema; funzioni di penalità o operatori di riparazione devono essere integrati esplicitamente.
Domande frequenti
In che modo un Algoritmo Genetico Stocastico differisce da un Algoritmo Genetico standard?
L'etichetta 'stocastico' enfatizza che tutti gli operatori principali — selezione, crossover e mutazione — coinvolgono estrazioni probabilistiche. Il GA canonico introdotto da Holland è intrinsecamente stocastico. L'etichetta è usata nella letteratura sulla simulazione/ottimizzazione per distinguerlo da rare varianti deterministiche (es. crowding deterministico) e per chiarire che il comportamento dell'algoritmo varia tra le esecuzioni a causa della casualità.
Quanto dovrebbe essere grande la popolazione?
Un punto di partenza comune è 50–200 individui per problemi di media dimensionalità. Popolazioni più grandi migliorano la diversità e riducono la convergenza prematura ma aumentano il costo computazionale per generazione. Esistono regole empiriche basate sulla lunghezza del cromosoma (es. 10× il numero di geni), ma spesso sono necessarie la sintonizzazione empirica o la meta-ottimizzazione.
Quando dovrei preferire l'Ottimizzazione per Sciami di Particelle o il Simulated Annealing rispetto a un Algoritmo Genetico?
L'Ottimizzazione per Sciami di Particelle (PSO) è spesso più veloce su problemi continui a valori reali perché sfrutta le informazioni sulla velocità. Il Simulated Annealing (SA) è più semplice da implementare e può essere efficace per la ricerca di traiettorie a singola soluzione. I GA sono preferiti quando lo spazio di ricerca è combinatorio, quando il crossover ricombina significativamente le strutture delle soluzioni, o quando la diversità della popolazione è preziosa per paesaggi multimodali.
L'Algoritmo Genetico Stocastico scala a problemi ad alta dimensionalità?
Le prestazioni degradano in dimensioni molto elevate (centinaia o migliaia di variabili) perché la popolazione deve essere sufficientemente grande da campionare adeguatamente lo spazio. Varianti specializzate — come GA che apprendono il linkage, algoritmi di stima della distribuzione o modelli a isole con migrazione — affrontano la scalabilità ma aggiungono complessità.
Come gestisco i vincoli in un Algoritmo Genetico?
Vengono utilizzate tre strategie principali: (1) funzioni di penalità che riducono la fitness per le violazioni dei vincoli; (2) operatori di riparazione che proiettano i discendenti non fattibili nella regione fattibile; (3) codifiche e operatori specializzati che producono solo soluzioni fattibili per costruzione. I metodi basati su penalità sono i più facili da implementare ma richiedono un'attenta calibrazione dei coefficienti di penalità.
Metodi correlati
Fonti
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
ISBN: 978-0262581110Copiato.Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
ISBN: 978-0201157673Copiato.