La fase di riproduzione degli individui rappresenta il momento in cui la popolazione evolve ovvero viene creata una nuova generazione di individui grazie alla applicazione di due operazioni ispirate dall’evoluzionismo biologico: il crossover e la mutazione.
Questi operatori non sono sempre necessariamente applicati a tutte le coppie di cromosomi selezionati, ma vengono applicati rispettivamente con probabilità di crossover Pc e probabilità di mutazione Pm. Per ogni coppia di individui selezionati viene generato un numero casuale, se questo è minore delle probabilità Pc e/o Pm allora vengono applicati i relativi operatori genetici altrimenti i cromosomi genitori vengono copiati direttamente nella generazione successiva. Nella maggior parte dei casi si stabilisce la probabilità di accadimento Pc molto superiore a quella stabilita per la mutazione Pm.
Crossover
Il crossover rappresenta l’operatore genetico base per la riproduzione di nuovi cromosomi; partendo da due cromosomi precedentemente selezionati (genitori) ne ricombina il patrimonio genetico (geni) dando origini a due nuovi individui detti
L’influenza dei fattori ergonomici nelle linee di montaggio:
sviluppo di un algoritmo genetico per il loro dimensionamento e bilanciamento 68 figli. In letteratura sono presenti diversi metodi di crossover; di seguito saranno descritti solo le tipologie più conosciute [21].
K-point Crossover
I crossover appartenenti a questa tipologia effettuano la ricombinazione degli individui selezionando, in maniera casuale e senza ripetizioni, k punti all’interno dei cromosomi - genitori e scambiandone il contenuto.
Tra questi, i metodi più utilizzati sono:
- one-point crossover: viene scelto un solo punto all’interno dei cromosomi
genitori e tutti i geni successivi a tale posizione vengono scambiati tra di due genitori dando origine a due cromosomi figli. Il punto selezionato divide il cromosoma genitore in due parti chiamate testa e coda; i cromosomi figli saranno formati rispettivamente dalla testa di un genitore e dalla coda dell’altro.
- two-point crossover: attraverso questo metodo vengono selezionati due punti in cui effettuare la ricombinazione. Stavolta i cromosomi genitori sono divisi tre parti: testa, centro e coda. I nuovi individui saranno formati scambiando la testa e la coda tra i genitori ma mantenendo la parte centrale inalterata. testa 1 testa 1 testa 2 coda 1 coda 1 coda 2 coda 2 testa 2 Figura 3.10 One point crossover
L’influenza dei fattori ergonomici nelle linee di montaggio:
sviluppo di un algoritmo genetico per il loro dimensionamento e bilanciamento 69 Order based crossover
L’idea di fondo di questo metodo è preservare l'ordine relativo in cui si presentano gli elementi del cromosoma. Si sceglie una parte arbitraria dal primo genitore e la si copia nel figlio. Successivamente si inserisco i geni appartenenti al secondo genitore, partendo dal primo numero dopo il punto di taglio escludendo quelli già presenti all’interno del cromosoma. Per la creazione del secondo cromosoma figlio si esegue lo stesso procedimento invertendo i genitori.
Uniform based order crossover
In questo metodo dopo aver selezionato i due genitori, viene creato un vettore modello contenente valori binari casuali. Il primo cromosoma figlio eredita dal primo genitore i geni che presentano, nelle corrispondenti posizioni del vettore modello creato, il valore 1. A questo punto il cromosoma figlio è parzialmente
testa 1 testa 2 testa 1 testa 2 coda 1 coda 2 coda 1 coda 2 centro 1 centro 1 centro 2 centro 2 Figura 3.11 Two point crossover Genitore 1 Genitore 2 Figlio 1 Figlio 2 Figura 3.12 Order based crossover
L’influenza dei fattori ergonomici nelle linee di montaggio:
sviluppo di un algoritmo genetico per il loro dimensionamento e bilanciamento 70 riempito, ma presenta ancora dei geni vuoti che vengono riempiti con i geni
mancanti inseriti nell'ordine in cui appaiono nell'altro genitore. Il secondo figlio viene creato con lo stesso processo invertendo i genitori.
Esiste un’ampia varietà di crossover alcuni dei quali non sono trattati in questo elaborato ma che vengono citati per maggiore completezza sull’argomento: Partially Mapped Crossover, Cycle crossover, Simulated Binary Crossover [21].
Mutazione
La mutazione avviene in seguito alla fase di riproduzione. Applicato dopo il crossover, questo operatore genetico altera in modo casuale alcuni dei geni dei figli appena creati allo scopo di evitare che l’evoluzione ricada in ottimi locali, cercando di preservare la diversità del patrimonio genetico di popolazione in popolazione.
Si illustrano (fig. 3.14) ora alcune delle tecniche di mutazione tra le più note: - Swap Mutation: con questa metodologia vengono selezionati e
semplicemente scambiati di posto due geni appartenenti al cromosoma. - Insert mutation: prevede la selezione di due geni e uno di questi è spostato
accanto all’altro spostando così di una posizione tutti gli altri.
Genitore 1 Genitore 2 Modello
Figlio 1 Figlio 2
Si copiano i geni delle posizioni 2,3,6
L’influenza dei fattori ergonomici nelle linee di montaggio:
sviluppo di un algoritmo genetico per il loro dimensionamento e bilanciamento 71 - Scramble mutation: in questo tipo di tecnica viene selezionata casualmente
una porzione del cromosoma e si modifica l’ordine dei geni che la compongono.
- Inversion mutation: seleziona casualmente due geni e si invertono l’ordine dei valori che compaiono tra essi.
Applicando gli algoritmi genetici ai problemi di bilanciamento, che presentano vincoli tecnologici e temporali, può accadere talvolta che i cromosomi generati non risultino fattibili, occorre quindi decidere come comportarsi con tali individui. Alcune possibili soluzioni a questo inconveniente possono essere:
- riparare i geni dei cromosomi nei punti che risultano violare i vincoli; - creare fin dall’inizio solo cromosomi fattibili attraverso procedure mirate;
- assegnare ai cromosomi che risultino infattibili una penalità durante il calcolo della fitness affinché questi ottengano probabilità quasi nulla di essere selezionati ed essere così scartarti dalla popolazione successiva.
5. Creazione della nuova popolazione tramite inserimento dei