Algoritmi genetici - Introduzione
Genetic Algorithm (GA) è una tecnica di ottimizzazione basata sulla ricerca basata sui principi di Genetics and Natural Selection. Viene spesso utilizzato per trovare soluzioni ottimali o quasi ottimali a problemi difficili che altrimenti richiederebbero una vita per risolverli. Viene spesso utilizzato per risolvere problemi di ottimizzazione, nella ricerca e nell'apprendimento automatico.
Introduzione all'ottimizzazione
L'ottimizzazione è il processo di making something better. In ogni processo, abbiamo una serie di input e una serie di output come mostrato nella figura seguente.
L'ottimizzazione si riferisce alla ricerca dei valori degli input in modo tale da ottenere i valori di output "migliori". La definizione di “migliore” varia da problema a problema, ma in termini matematici si riferisce alla massimizzazione o alla minimizzazione di una o più funzioni obiettivo, variando i parametri di input.
L'insieme di tutte le possibili soluzioni o valori che gli input possono assumere costituisce lo spazio di ricerca. In questo spazio di ricerca si trova un punto o un insieme di punti che fornisce la soluzione ottimale. Lo scopo dell'ottimizzazione è trovare quel punto o insieme di punti nello spazio di ricerca.
Cosa sono gli algoritmi genetici?
La natura è sempre stata una grande fonte di ispirazione per tutta l'umanità. Gli algoritmi genetici (GA) sono algoritmi basati sulla ricerca basati sui concetti di selezione naturale e genetica. I GA sono un sottoinsieme di un ramo di calcolo molto più ampio noto comeEvolutionary Computation.
Le GA sono state sviluppate da John Holland e dai suoi studenti e colleghi presso l'Università del Michigan, in particolare David E. Goldberg, e da allora sono state sperimentate su vari problemi di ottimizzazione con un alto grado di successo.
In GA, abbiamo un file pool or a population of possible solutionsal problema dato. Queste soluzioni poi subiscono ricombinazione e mutazione (come nella genetica naturale), producendo nuovi bambini, e il processo si ripete su varie generazioni. Ad ogni individuo (o soluzione candidata) viene assegnato un valore di fitness (basato sul valore della sua funzione oggettiva) e agli individui più in forma viene data una maggiore possibilità di accoppiarsi e produrre individui più “in forma”. Ciò è in linea con la teoria darwiniana della "sopravvivenza del più adatto".
In questo modo continuiamo a “evolvere” individui o soluzioni migliori nel corso delle generazioni, fino a raggiungere un criterio di arresto.
Gli algoritmi genetici sono di natura sufficientemente casuale, ma funzionano molto meglio della ricerca locale casuale (in cui proviamo solo varie soluzioni casuali, tenendo traccia delle migliori finora), poiché sfruttano anche le informazioni storiche.
Vantaggi delle GA
Gli GA hanno diversi vantaggi che li hanno resi immensamente popolari. Questi includono:
Non richiede alcuna informazione derivata (che potrebbe non essere disponibile per molti problemi del mondo reale).
È più veloce ed efficiente rispetto ai metodi tradizionali.
Ha ottime capacità parallele.
Ottimizza funzioni sia continue che discrete e anche problemi multi-obiettivo.
Fornisce un elenco di soluzioni "buone" e non solo una singola soluzione.
Ottiene sempre una risposta al problema, che migliora nel tempo.
Utile quando lo spazio di ricerca è molto ampio e sono coinvolti molti parametri.
Limitazioni di GA
Come ogni tecnica, anche le GA soffrono di alcune limitazioni. Questi includono:
Le GA non sono adatte a tutti i problemi, specialmente i problemi che sono semplici e per i quali sono disponibili informazioni derivate.
Il valore di fitness viene calcolato ripetutamente, il che potrebbe essere computazionalmente costoso per alcuni problemi.
Essendo stocastico, non ci sono garanzie sull'ottimalità o sulla qualità della soluzione.
Se non implementato correttamente, GA potrebbe non convergere verso la soluzione ottimale.
GA - Motivazione
Gli algoritmi genetici hanno la capacità di fornire una soluzione "abbastanza buona" "abbastanza veloce". Ciò rende gli algoritmi genetici attraenti per l'uso nella risoluzione dei problemi di ottimizzazione. I motivi per cui sono necessari GA sono i seguenti:
Risolvere problemi difficili
Nell'informatica, c'è una vasta serie di problemi, che sono NP-Hard. Ciò significa essenzialmente che anche i sistemi informatici più potenti impiegano molto tempo (anche anni!) Per risolvere il problema. In uno scenario del genere, le GA dimostrano di essere uno strumento efficiente da fornireusable near-optimal solutions in un breve lasso di tempo.
Fallimento dei metodi basati sul gradiente
I metodi tradizionali basati sul calcolo funzionano partendo da un punto casuale e muovendosi nella direzione del gradiente, fino a raggiungere la cima della collina. Questa tecnica è efficiente e funziona molto bene per funzioni obiettivo a picco singolo come la funzione di costo nella regressione lineare. Ma, nella maggior parte delle situazioni del mondo reale, abbiamo un problema molto complesso chiamato paesaggi, che sono fatti di molti picchi e molte valli, che fa fallire tali metodi, poiché soffrono di una tendenza intrinseca a rimanere bloccati all'ottimo locale come mostrato nella figura seguente.
Ottenere rapidamente una buona soluzione
Alcuni problemi difficili come il problema del venditore in viaggio (TSP), hanno applicazioni del mondo reale come la ricerca del percorso e la progettazione VLSI. Ora immagina di utilizzare il tuo sistema di navigazione GPS e ci vogliono pochi minuti (o anche poche ore) per calcolare il percorso "ottimale" dalla sorgente alla destinazione. Il ritardo in tali applicazioni del mondo reale non è accettabile e quindi una soluzione "abbastanza buona", che viene fornita "velocemente" è ciò che è richiesto.