Rete neurale artificiale - Algoritmo genetico

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. Gli GA sono un sottoinsieme di un ramo di calcolo molto più ampio noto comeEvolutionary Computation.

GAs è stato sviluppato da John Holland e dai suoi studenti e colleghi presso l'Università del Michigan, in particolare David E. Goldberg, e da allora è stato provato su vari problemi di ottimizzazione con un alto grado di successo.

In GA, abbiamo un pool o una popolazione di possibili soluzioni al problema dato. Queste soluzioni subiscono quindi 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 “far evolvere” individui o soluzioni migliori nel corso delle generazioni, fino a raggiungere un criterio di arresto.

Gli algoritmi genetici sono di natura sufficientemente casuale, tuttavia si comportano 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 sia le funzioni continue e discrete che i 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 il numero di parametri coinvolti è elevato.

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 della forma fisica viene calcolato ripetutamente, il che potrebbe essere costoso dal punto di vista computazionale 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 il gas interessante per la 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 le funzioni obiettivo a picco singolo come la funzione di costo nella regressione lineare. Tuttavia, nella maggior parte delle situazioni del mondo reale, abbiamo un problema molto complesso chiamato paesaggi, fatto di molti picchi e molte valli, che fa sì che tali metodi falliscano, 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 di percorsi 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.

Come utilizzare GA per problemi di ottimizzazione?

Sappiamo già che l'ottimizzazione è un'azione per rendere qualcosa come il design, la situazione, le risorse e il sistema il più efficaci possibile. Il processo di ottimizzazione è mostrato nel diagramma seguente.

Fasi del meccanismo GA per il processo di ottimizzazione

Le seguenti sono le fasi del meccanismo GA quando viene utilizzato per l'ottimizzazione dei problemi.

  • Genera la popolazione iniziale in modo casuale.

  • Seleziona la soluzione iniziale con i migliori valori di fitness.

  • Ricombinare le soluzioni selezionate utilizzando operatori di mutazione e crossover.

  • Inserire la prole nella popolazione.

  • Ora, se la condizione di arresto è soddisfatta, restituisci la soluzione con il miglior valore di fitness. Altrimenti, vai al passaggio 2.