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