Figura A.1: Funzionamento schematico di un algoritmo genetico elementare Sia data una funzione oggetto da ottimizzare f : S ⊆ Rn −→ R.
Si può dunque estrarre da S un numero Nind di elementi che costitui- ranno i cromosomi della prima generazione. Ognuno di tali elementi sarà caratterizzato dal proprio codice genetico (alleli), ovvero le n componenti del vettore chrome ∈ Rn.
Si valuta la funzione oggetto su ciascun cromosoma della popolazione, associando di conseguenza un valore di tness ad ogni individuo.
Se i criteri di ottimizzazione non sono soddisfatti si passa allo sviluppo di una nuova generazione selezionando gli individui da riprodurre. Dun- que una o più coppie di cromosomi vengono ricombinati per generare uno o più ospring. Tali ospring, dopo un'eventuale fase di mutazione, andran- no a formare la nuova generazione della popolazione, su cui verrà valutata nuovamente la f e si itererà l'algoritmo no a convergenza.
Selezione
Un parametro fondamentale per quanto riguarda la selezione è la pressione evolutiva (Selective Pressure, SP). Questo è un parametro globale (a prio- ri non varia con le generazioni) e determina la probabilità di selezionare i cromosomi migliori della popolazione.
Il valore di tness viene assegnato in base al valore della funzione oggetto calcolata per quell'individuo. I principali metodi di assegnazione sono quelli per ranking e proporzionale. Il primo metodo assegna ai cromosomi un valore di tness dipendente esclusivamente dalla loro posizione (dopo un sorting sui valori della f) e dal valore della SP.
L'attribuzione proporzionale avviene in base al valore della funzione og- getto. Così facendo il tness di individui con un valore della f piccolo sa- rà estremamente basso, ed è stato osservato [28, 29] che il metodo è me- no robusto rispetto al ranking ed è soggetto a stagnazione e convergenza prematura.
Esistono diversi metodi per selezionare gli individui da riprodurre in base al loro ranking:
• Truncation Selection: si scelgono solo gli individui col migliore tness. • Roulette Wheel Sampling [28]: si associano gli individui ad intervalli di un segmento unitario, ognuno proporzionale al proprio valore di tness. Si genera un numero di valori random uniformemente distribuiti in [0, 1] pari al numero di individui da selezionare, quindi si scelgono i cromosomi associati agli intervalli in cui cadono i numeri scelti.
• Stochastic Universal Sampling [28]: si distribuiscono gli individui in maniera analoga al caso precedente ma si seleziona un solo valore ran- dom nell'intervallo [0, 1/numero di individui da selezionare], dunque si collocano i puntatori in maniera equispaziata sul segmento partendo dal valore random.
• Local Selection: si seleziona la prima metà degli individui da selezionare con uno dei metodi descritti precedentemente, quindi si permette loro di interagire solo con gli individui ad essi circostanti. Negli intorni de niti attorno ai cromosomi selezionati si scelgono gli elementi migliori da ricombinare, ottenendo così l'altra metà degli individui selezionati. • Tournament Selection [30]: si estrae un gruppo di individui dalla po- polazione, quindi si sceglie quello col miglior tness. Si ripete quindi tale procedimento no ad avere il numero di cromosomi selezionati desiderato.
Negli algoritmi implementati durante questo lavoro è stato utilizzato un criterio di selezione tramite stochastic universal sampling, in quanto garanti- sce una maggiore variabilità genetica della truncate selection, a prezzo di una ridotta velocità di convergenza, e riduce il numero di ripetizioni fra gli indi- vidui selezionati rispetto al roulette wheel sampling, a prezzo di una minore aleatorietà del processo di selezione.
Ricombinazione
La ricombinazione è un'operazione che produce un nuovo cromosoma (o- spring) ricombinando casualmente gli alleli di due o più cromosomi selezionati dalla popolazione.
I metodi di ricombinazione [31] dipendono dal tipo di variabili che com- pongono il cromosoma:
• Ricombinazione Discreta: i gli (Ospring, V aro) vengono scelti ca-
sualmente ai vertici di un ipercubo de nito dai genitori (Parents, V arPi).
metodo si può ricombinare qualsiasi tipo di variabili: V ario = V arP1
i · ai+ V ariP2 · (1 − ai), i ∈ {1, 2, . . . , N var}
con ai ∈ {0, 1} uniformemente distribuita ∀i.
• Ricombinazione a Valori Reali: gli individui vengono scelti casualmente in un luogo di punti de nito dai genitori. Sono permesse solo variabili reali:
Ricombinazione Intermedia: ospring scelti casualmente nell'iper- cubo de nito dai genitori.
V aroi = V arP1
i · ai+ V ariP2 · (1 − ai), i ∈ {1, 2, . . . , N var}
con ai ∈ [−d, 1 + d], con d = 0.25, uniformemente distribuita ∀i.
Ricombinazione Lineare:spring scelti casualmente nel segmento congiungente i due genitori.
V aroi = V arP1
i · a + V ar P2
i · (1 − a), i ∈ {1, 2, . . . , N var}
con a ∈ [−d, 1 + d], con d = 0.25, uniformemente distribuita. In questo caso viene scelto un solo valore di a per tutti gli indici i. Ricombinazione Lineare Estesa [32]: simile alla precedente, ma
gli ospring possono essere generati, con dierente probabilità, in ogni punto della retta de nita dai due genitori.
• Crossover: ricombina cromosomi binari giustapponendo intervalli di codice genetico dei genitori selezionati random.
Nel lavoro di tesi sono state eseguite ricombinazioni tramite ricombinazio- ne intermedia, così da massimizzare lo spazio di generazione degli ospring.
Mutazione
La mutazione è un fenomeno che altera uno o più alleli di un cromosoma [31]. La frequenza con cui avviene una mutazione è determinata dal tasso di mutazione, che normalmente è molto basso.
Esistono sostanzialmente due classi di metodi:
• a valori reali: si applica un algoritmo che determina una variazione di alcuni degli alleli del cromosoma mutato. Il valore della variazione è determinato dal passo di mutazione. L'algoritmo garantisce un'alta frequenza di piccole mutazioni e una bassa probabilità di alleli che si discostano molto dai valori originari.
• a valori binari: l'algoritmo seleziona qualcuno degli alleli e cambia il suo valore (1 → 0 oppure 0 → 1).
Nel lavoro di tesi, avendo utilizzato cromosomi reali, è stato usato un criterio di mutazione a valori reali.
Reinserimento
Una volta generati gli ospring con i procedimenti descritti in precedenza, sa- rà necessario inserirli nella vecchia popolazione, eventualmente mantenendo alcuni individui della vecchia generazione e rimpiazzandone altri. La popo- lazione risultante costituirà la nuova generazione su cui applicare l'iterazione successiva dell'algoritmo.
Esistono diversi schemi di reinserimento:
• Reinserimento Globale: gli ospring vengono reinseriti all'interno della popolazione senza tenere memoria della provenienza dei genitori. Si possono attuare dierenti strategie di reinserimento:
Reinserimento Puro: si generano tanti ospring quanti sono i genitori selezionati, dunque la nuova generazione sarà costituita esclusivamente dai nuovi individui,
Reinserimento Uniforme: si generano meno ospring dei genitori e si sostituiscono casualmente al posto di alcuni genitori,
Reinserimento Elitario: come nel caso uniforme gli ospring sono meno dei genitori ma rimpiazzano i genitori col peggior tness. È molto e cace in quanto si preservano individui con tness molto elevati delle generazioni precedenti,
Reinserimento Fitness-Based: duale dell'elitario, si producono più ospring di quanti sarebbero necessari e se ne selezionano solo i migliori,
• Reinserimento Locale: si attuano meccanismi di reinserimento dipen- denti dall'intorno da cui sono stati selezionati i genitori. Si utilizza solo nel caso di selezione locale. Anche in questo caso le strategie di reinserimento sono dierenti:
si reinseriscono tutti gli ospring negli intorni in cui sono stati generati rimpiazzando individui random,
si reinseriscono tutti gli ospring negli intorni in cui sono stati generati rimpiazzando gli individui meno adattati,
si reinseriscono gli ospring con valori di tness migliori dei peg- giori individui presenti negli intorni in cui sono stati generati rimpiazzando gli individui meno adattati,
si reinseriscono gli ospring con valori di tness migliori dei peg- giori individui presenti negli intorni in cui sono stati generati rimpiazzando i genitori,
si reinseriscono gli ospring con valori di tness migliori dei peg- giori individui presenti negli intorni in cui sono stati generati rimpiazzando individui random,
si reinseriscono gli ospring con valori di tness migliori dei geni- tori, andandoli a rimpiazzare.
Negli algoritmi implementati è stato applicato un metodo di reinserimento elitario, così da massimizzare la presenza di modelli con alti valori di tness all'interno di ogni generazione.