ALGORITMI GATSS

In questa sezione discuteremo gli algoritmi specifici GATSS. Dato che GATSS è un vero e proprio GA, l'algoritmo funziona come descritto nella sezione generale sui GA.

Crossover
I tipi di crossover usati  in GATSS sono chiamati Fixed Position e Fixed Position Sequential:
Fixed Position
I geni del genitore 1 sono selezionati  a caso e copiati nel discendente esattamente nella stessa ubicazione come appaiono nel gene del genitore. Così, sia ordine che posizione dei geni del genitore 1 sono conservati.

I geni che non sono selezionati dal genitore 1 sono copiati dal genitore 2 per riempire gli i spazi vuoti nel discendente. L'ordine dei geni nel genitore 2 è conservato ma le ubicazioni esatte, per ragioni ovvie, no.

Fixed Position Sequential
Una parte selezionata caso (consistente di geni consecutivi) del cromosoma del genitore 1 è copiata nel discendente esattamente nella stessa ubicazione. L'ordine ed l’ubicazione sono conservati.

Come nel 'Fixed Position' descritto sopra, il cromosoma del genitore 2 è usato per riempire le posizione vuote nel figlio. L’ordine è conservato ma non la posizione.

Mutazione
Una parte selezionata (consistente di geni consecutivi) del cromosoma è permutata. In pratica questo è fatto  commutando l’ubicazione dei geni dentro la parte selezionata
 

Fitness Evaluation

Il fitness è calcolato in due passi. Prima, tutti i cromosomi nella popolazione sono valutati. Poi, uno dei tre algoritmi di fitness viene applicato.
1.Valutazione: I geni in questa applicazione GA sono nodi in un grafo, ed un cromosoma può essere ritenuto come un percorso attraverso questo grafo. Per valutare quanta buona è la soluzione, la lunghezza totale del percorso è calcolato sommando le distanze tra ciascuno nodo (gene).
 

2.Fitness: Il calcolo del fitness è basato sulla valutazione descritta sopra.  Poiché il sistema usa una tecnica di selezione del genitore  chiamata 'Roulette Wheel Selection,' tutte tecniche del calcolo del fitness cominciano con assegnare il valore di fitness iniziale  per invertire il valore stimato. Per fare questo, il cromosoma con la soluzione più corta ottiene inizialmente il valore di fitness più alto, ed una probabilità più alta di divenire genitore del nuovo cromosoma.
 
 

 Evaluation
Questo algoritmo non fa niente tranne assegnare al fitness lo stesso valore di quello stimato (ma invertito, vedi il paragrafo sopra).

Esempio di una popolazione con 10 Cromosomi

Windowing
Questo algoritmo ricalcola il fitness dell’intera popolazione così che il cromosoma più debole ottiene fitness 1, ed l'altro ottiene un fitness uguale al valore di quanto superano la valutazione del cromosoma più debole.


 

Il valore di guardia può essere pensato a come un algoritmo della Previdenza Sociale per i cromosomi più deboli. A ogni cromosoma con un valore di fitness minore del  valore di guardia è assegnato il valore di guardia.

Linear Normalization

Al migliore cromosoma è assegnato fitness = 100. Il fitness di tutti gli altri cromosomi ottiene valori decrescenti dal valore migliore . Il fattore della diminuzione è messo [x] percento (assegnato nel modulo "Parametro") della migliore fitness che di solito ha come conseguenza una lenta ma stabile convergenza del fitness della popolazione.

Population Deletion
In questo sistema, due differenti tipi sono implementati:
Delete All
Viene creata una nuova popolazione vuota e poi riempita con nuovi cromosomi. I nuovi figli sono creati solo dai cromosomi dei genitori della vecchia popolazione (al contrario del "Steady Delete"). Questa è una tecnica molto comune chiamata "one generational replacement" nella terminologia dei GA.

L’"Elitism Value" è usato per assicurarsi che il miglior cromosoma x  sopravviverà alla generazione successiva.

Steady Delete
In questo algoritmo, ogni discendente nuovo sostituisce il peggiore cromosoma nella popolazione. I cromosomi che sono membri della stessa generazione possono essere genitori l’uno dell’altro! Questo è, naturalmente, non biologicamente attuabile ma può avere un buon effetto nell'accelerare la convergenza del fitness della popolazione durante evoluzione