Come funziona l'algoritmo genetico
Schema dell'algoritmo
La seguente panoramica riassume il funzionamento dell'algoritmo genetico:
L'algoritmo inizia creando una popolazione iniziale casuale.
L'algoritmo crea quindi una sequenza di nuove popolazioni. A ogni passaggio, l'algoritmo utilizza gli individui della generazione corrente per creare la popolazione successiva. Per creare la nuova popolazione, l'algoritmo esegue i seguenti passaggi:
Assegna un punteggio a ciascun membro della popolazione attuale calcolandone il valore di idoneità. Questi valori sono chiamati punteggi di fitness grezzi.
Adatta i punteggi di fitness grezzi per convertirli in un intervallo di valori più utilizzabile. Questi valori scalati sono chiamati valori attesi.
Seleziona i membri, chiamati genitori, in base alle loro aspettative.
Alcuni degli individui della popolazione attuale che hanno una forma fisica inferiore vengono scelti come élite. Questi individui d'élite vengono passati alla popolazione successiva.
Genera figli dai genitori. I figli vengono prodotti apportando modifiche casuali a un singolo genitore (mutation) oppure combinando le voci del vettore di una coppia di genitori (crossover).
Sostituisce la popolazione attuale con i children per formare la generazione successiva.
L'algoritmo si arresta quando viene soddisfatto uno dei criteri di arresto. Vedi Condizioni di arresto per l'algoritmo .
L'algoritmo adotta passaggi modificati per vincoli lineari e interi. Vedi Vincoli interi e lineari .
L'algoritmo è ulteriormente modificato per vincoli non lineari. Vedi Nonlinear Constraint Solver Algorithms for Genetic Algorithm .
Popolazione iniziale
L'algoritmo inizia creando una popolazione iniziale casuale, come mostrato nella figura seguente.
In questo esempio, la popolazione iniziale contiene 20 individui. Si noti che tutti gli individui della popolazione iniziale si trovano nel quadrante in alto a destra dell'immagine, ovvero le loro coordinate sono comprese tra 0 e 1. Per questo esempio, l'opzione InitialPopulationRange è [0;1] .
Se si conosce approssimativamente dove si trova il punto minimo di una funzione, si dovrebbe impostare InitialPopulationRange in modo che il punto si trovi vicino al centro di tale intervallo. Ad esempio, se si ritiene che il punto minimo per la funzione di Rastrigin sia vicino al punto [0 0], è possibile impostare InitialPopulationRange su [-1;1]. Tuttavia, come mostra questo esempio, l'algoritmo genetico riesce a trovare il minimo anche con una scelta non ottimale per InitialPopulationRange .
Creare la prossima generazione
A ogni passaggio, l'algoritmo genetico utilizza la popolazione attuale per creare i children che comporranno la generazione successiva. L'algoritmo seleziona un gruppo di individui nella popolazione attuale, chiamati genitori, che forniscono i loro geni (le voci dei loro vettori) ai loro figli. Di solito l'algoritmo seleziona come genitori gli individui che hanno valori di fitness migliori. È possibile specificare la funzione che l'algoritmo utilizza per selezionare i genitori nell'opzione SelectionFcn. Vedi Selection Options .
L'algoritmo genetico crea tre tipi di children per la prossima generazione:
I bambini di élite sono gli individui della generazione attuale con i migliori valori di fitness. Questi individui sopravvivono automaticamente alla generazione successiva.
I children di crossover vengono creati combinando i vettori di una coppia di genitori.
Mutation I children vengono creati introducendo cambiamenti casuali, o mutazioni, in un singolo genitore.
Il seguente diagramma schematico illustra i tre tipi di children.
Mutation e Crossover spiega come specificare il numero di figli di ciascun tipo generato dall'algoritmo e le funzioni che utilizza per eseguire il crossover e la mutation.
Le sezioni seguenti spiegano come l'algoritmo crea children di crossover e mutation.
Crossover Children
L'algoritmo crea figli incrociati combinando coppie di genitori nella popolazione attuale. A ogni coordinata del vettore figlio, la funzione di crossover predefinita seleziona casualmente una voce, o gene, alla stessa coordinata da uno dei due genitori e la assegna al figlio. Per problemi con vincoli lineari, la funzione di crossover predefinita crea il figlio come media ponderata casuale dei genitori.
Children Mutanti
L'algoritmo crea mutation children modificando casualmente i geni dei singoli genitori. Per impostazione predefinita, per i problemi non vincolati, l'algoritmo aggiunge un vettore casuale da una distribuzione gaussiana al genitore. Per problemi limitati o linearmente vincolati, il figlio rimane fattibile.
La figura seguente mostra i figli della popolazione iniziale, cioè la popolazione alla seconda generazione, e indica se sono figli d'élite, figli di crossover o figli di mutation.
Trame delle generazioni successive
La figura seguente mostra le popolazioni alle iterazioni 60, 80, 95 e 100.
|
|
|
|
|
|
Con l'aumentare del numero di generazioni, gli individui della popolazione si avvicinano sempre di più e si avvicinano al punto minimo [0 0].
Condizioni di arresto per l'algoritmo
L'algoritmo genetico utilizza le seguenti opzioni per determinare quando fermarsi. Per visualizzare i valori predefiniti per ciascuna opzione, eseguire opts = optimoptions('ga') .
MaxGenerations— L'algoritmo si arresta quando il numero di generazioni raggiungeMaxGenerations.MaxTime— L'algoritmo si arresta dopo un periodo di esecuzione in secondi pari aMaxTime.FitnessLimit— L'algoritmo si arresta quando il valore della funzione di idoneità per il punto migliore nella popolazione corrente è minore o uguale aFitnessLimit.MaxStallGenerations— L'algoritmo si arresta quando la variazione relativa media del valore della funzione di fitness suMaxStallGenerationsè inferiore aFunction tolerance.MaxStallTime— L'algoritmo si arresta se non si verifica alcun miglioramento nella funzione obiettivo durante un intervallo di tempo in secondi pari aMaxStallTime.FunctionTolerance— L'algoritmo viene eseguito finché la variazione relativa media del valore della funzione di fitness suMaxStallGenerationsè inferiore aFunction tolerance.ConstraintTolerance—ConstraintTolerancenon viene utilizzato come criterio di arresto. Viene utilizzato per determinare la fattibilità rispetto ai vincoli non lineari. Inoltre,max(sqrt(eps),ConstraintTolerance)determina la fattibilità rispetto ai vincoli lineari.
L'algoritmo si arresta non appena viene soddisfatta una qualsiasi di queste condizioni.
Selezione
La funzione di selezione sceglie i genitori per la generazione successiva in base ai loro valori scalati dalla funzione di scala di fitness. I valori di fitness scalati sono chiamati valori attesi. Un individuo può essere selezionato più di una volta come genitore, nel qual caso trasmette i suoi geni a più di un figlio. L'opzione di selezione predefinita, @selectionstochunif, traccia una linea in cui ciascun genitore corrisponde a una sezione della linea di lunghezza proporzionale al suo valore in scala. L'algoritmo si muove lungo la linea in passi di uguale entità. A ogni passaggio, l'algoritmo assegna un elemento genitore dalla sezione in cui atterra.
Un'opzione di selezione più deterministica è @selectionremainder, che esegue due passaggi:
Nel primo passaggio, la funzione seleziona i genitori in modo deterministico in base alla parte intera del valore scalato per ciascun individuo. Ad esempio, se il valore scalare di un individuo è 2,3, la funzione seleziona quell'individuo due volte come genitore.
Nel secondo passaggio, la funzione di selezione seleziona ulteriori genitori utilizzando le parti frazionarie dei valori scalati, come nella selezione uniforme stocastica. La funzione traccia una linea in sezioni, le cui lunghezze sono proporzionali alla parte frazionaria del valore in scala degli individui, e si sposta lungo la linea con passi uguali per selezionare i genitori.
Si noti che se le parti frazionarie dei valori ridimensionati sono tutte uguali a 0, come può accadere utilizzando la scala
Top, la selezione è del tutto deterministica.
Per maggiori dettagli e ulteriori opzioni di selezione, vedere Selection Options .
Opzioni di riproduzione
Le opzioni di riproduzione controllano il modo in cui l'algoritmo genetico crea la generazione successiva. Le opzioni sono
EliteCount— Numero di individui con i migliori valori di fitness nella generazione attuale che hanno la garanzia di sopravvivere alla generazione successiva. Questi individui vengono chiamati bambini d'élite.Quando
EliteCountè almeno 1, il valore di fitness migliore può solo diminuire da una generazione all'altra. Questo è ciò che si desidera che accada, poiché l'algoritmo genetico riduce al minimo la funzione di idoneità. ImpostandoEliteCountsu un valore elevato, gli individui più adatti tendono a dominare la popolazione, il che può rendere la ricerca meno efficace.CrossoverFraction— La frazione di individui nella generazione successiva, diversi dai children d'élite, creati tramite incrocio. L'argomento "Impostazione della frazione di crossover" in Vary Mutation and Crossover descrive come il valore diCrossoverFractioninfluisce sulle prestazioni dell'algoritmo genetico.
Poiché gli individui d'élite sono già stati valutati, ga non rivaluta la funzione di fitness degli individui d'élite durante la riproduzione. Questo comportamento presuppone che la funzione di fitness di un individuo non sia casuale, ma una funzione deterministica. Per modificare questo comportamento, utilizzare una funzione di output. Vedi EvalElites in The State Structure .
Mutation e Crossover
L'algoritmo genetico utilizza gli individui della generazione attuale per creare i children che comporranno la generazione successiva. Oltre ai children d'élite, che corrispondono agli individui della generazione attuale con i migliori valori di fitness, l'algoritmo crea
Eseguire il crossover dei children selezionando le voci del vettore, o geni, da una coppia di individui nella generazione corrente e combinandoli per formare un child.
Mutazione dei children applicando cambiamenti casuali a un singolo individuo nella generazione attuale per creare un child.
Entrambi i processi sono essenziali per l'algoritmo genetico. Il crossover consente all'algoritmo di estrarre i geni migliori da individui diversi e di ricombinarli per ottenere children potenzialmente superiori. La mutazione aumenta la diversità di una popolazione e quindi aumenta la probabilità che l'algoritmo generi individui con valori di fitness migliori.
Vedere Creare la prossima generazione per un esempio di come l'algoritmo genetico applica la mutation e il crossover.
È possibile specificare quanti figli di ogni tipo l'algoritmo crea come segue:
EliteCountspecifica il numero di children d'élite.CrossoverFractionspecifica la frazione della popolazione, diversi dai children d'élite, che sono crossover children.
Ad esempio, se PopulationSize è 20, EliteCount è 2 e CrossoverFraction è 0.8, il numero di ciascun tipo di children nella generazione successiva è il seguente:
Ci sono due children d'élite.
Ci sono 18 individui diversi dai children d'élite, quindi l'algoritmo arrotonda 0,8*18 = 14,4 a 14 per ottenere il numero di crossover children.
I restanti quattro individui, diversi dai elite children, sono mutation children.
Vincoli interi e lineari
Quando un problema ha vincoli interi o lineari (inclusi i limiti), l'algoritmo modifica l'evoluzione della popolazione.
Quando il problema presenta vincoli sia interi che lineari, il software modifica tutti gli individui generati in modo che siano fattibili rispetto a tali vincoli. È possibile utilizzare qualsiasi funzione di creazione, mutation o crossover e l'intera popolazione rimane fattibile rispetto ai vincoli interi e lineari.
Quando il problema ha solo vincoli lineari, il software non modifica gli individui in modo che siano fattibili rispetto a tali vincoli. È necessario utilizzare funzioni di creazione, mutation e crossover che mantengano la fattibilità rispetto ai vincoli lineari. Altrimenti la popolazione potrebbe diventare irrealizzabile e il risultato potrebbe essere irrealizzabile. Gli operatori predefiniti mantengono la fattibilità lineare:
gacreationlinearfeasibleogacreationnonlinearfeasibleper la creazione,mutationadaptfeasibleper la mutation ecrossoverintermediateper il crossover.
Gli algoritmi interni per la fattibilità intera e lineare sono simili a quelli per surrogateopt . Quando un problema presenta vincoli interi e lineari, l'algoritmo crea innanzitutto punti linearmente realizzabili. Quindi l'algoritmo cerca di soddisfare i vincoli sugli interi arrotondando i punti linearmente fattibili a numeri interi utilizzando un'euristica che tenta di mantenere i punti linearmente fattibili. Quando questo processo non riesce a ottenere abbastanza punti fattibili per costruire una popolazione, l'algoritmo chiama intlinprog per provare a trovare più punti fattibili rispetto ai limiti, ai vincoli lineari e ai vincoli interi.
Successivamente, quando una mutation o un incrocio creano nuovi membri della popolazione, gli algoritmi assicurano che i nuovi membri siano interi e lineari realizzabili adottando misure simili. Ogni nuovo membro viene modificato, se necessario, per avvicinarsi il più possibile al suo valore originale, soddisfacendo al contempo i vincoli e i limiti interi e lineari.
