Test 8

Ora, proviamo la tecnica Linear Normalization.
Riportiamo la probabilità di mutazione a 0.005, il valore di elitismo è settato a 1, la tecnica di valutazione è settata a  Windowing e il valore di decremento lineare è assegnato a 1.5.

Population size: 100
Generations: 75
Crossover probability: 0.4
Crossover type: 0 (0 = Fixed Position, 1 = Fixed Position Sequential)
Mutation probabilaty: 0.005
Fitness technique: 2 (0 = Evaluation, 1 = Windowing, 2 = Linear Normalization)
Population Deletion technique: 0 (0 = Delete All, 1 = Steady Delete)
Elitism value: 1
Deletion parameter: 1.5
Seed: 799500870

Risultato
Distanza: 130.482

 

Analisi

Una convergenza molto veloce ma a un valore abbastanza brutto di evaluation. Abbiamo provato altri valori  di elitismo ma sembra che L.N. sia molto sensibile a questi valori. Uno zero quasi sempre implica che il miglior  cromosoma viene sostituito e un valore più grande va a finire  in una performance molto cattiva.
Torniamo a una veloce convergenza. Forse il fattore lineare di decremento è troppo grande? A Un valore più piccolo produrrebbe una convergenza più lenta in a ma, speriamo, una soluzione migliore.
 
 

Test 9

Tutti i parametri sono impostati come nel test 8, eccetto il fattore di decremento lineare che decresce a  0.15. Inoltre, a causa della più bassa probabilità di convergenza, il numero di generazioni è raddoppiato a 150.

Population size: 100
Generations: 150
Crossover probability: 0.4
Crossover type: 0 (0 = Fixed Position, 1 = Fixed Position Sequential)
Mutation probabilaty: 0.005
Fitness technique: 2 (0 = Evaluation, 1 = Windowing, 2 = Linear Normalization)
Population Deletion technique: 0 (0 = Delete All, 1 = Steady Delete)
Elitism value: 1
Deletion parameter: 0.15
Seed: 799500870

Risultato

Distanza: 98.7325
 

Analisi

Miglioramento. Con queste impostazioni dei parametri, la tecnica L.N. riesce a trovare la soluzione migliore possibile come la tecnica windowing ha fatto. Ma ha bisogno di molto tempo (o piuttosto: rimpiazzamento di generazioni).

Il fattore di decremento gioca il maggior ruolo nei risultati dati nei test 8 e 9. Nel test 8, c’è un grande sparpagliamento dei valori di valutazione tra i e cromosomi che dà ai migliori  cromosomi un grande vantaggio. In test 9, le differenze tra i cromosomi sono molto più piccole e così, dà agli altri cromosomi una migliore chance di vivere e riprodursi.
 

Test 10

Tutti i test sopra sono stati fatti con la tecnica Delete All. E’ tempo di provare quanto buona è la tecnica Steady Delete in paragone. Questa tecnica è considerevolmente più lenta a ogni passo generazionale a causa della selezione necessaria a ogni inserimento di un nuovo membro della popolazione. Il vantaggio dovrebbe essere una veloce convergenza riguardo quante generazioni sono necessarie.

Non rifaremo tutti i test precedenti, invece mostreremo il risultato migliore, e discuteremo come l’algoritmo Steady Delete funziona in generale, confrontandolo con Delete All.

I valori dei parametri sono sotto:

Population size: 100
Generations: 75
Crossover probability: 1
Crossover type: 0 (0 = Fixed Position, 1 = Fixed Position Sequential)
Mutation probabilaty: 0.2
Fitness technique: 0 (0 = Evaluation, 1 = Windowing, 2 = Linear Normalization)
Population Deletion technique: 1 (0 = Delete All, 1 = Steady Delete)
Elitism value: 5
Deletion parameter: 45
Seed: 799500870

Risultato
Distanza: 98.7325

Analisi

Questo algoritmo  di cancellazione è capace di trovare la soluzione migliore possibile, e con i parametri sopra, lo fa molto velocemente (parlando in termini di generazioni). Raggiunge la soluzione migliore dopo sole 27 generazioni.

Com’è possibile? La cosa più importante è che, se viene generato un buon cromosoma, fin dall’inizio di un rimpiazzamento generazionale può essere usato come genitore all’interno dello stesso rimpiazzamento generazionale. Questo rende l’algoritmo molto più  'intenso' del Delete All dove un buon cromosoma deve aspettare la generazione successiva prima che possa essere usato come materiale per nuovi cromosomi.

Abbiamo fatto alcuni test con questo algoritmo e quasi  sempre converge velocemente, quasi sempre  converge a una soluzione abbastanza buona quando usato insieme  a un’alta probabilità di mutazione. Questo è naturale poiché ha bisogno di un ambiente instabile per evitare i massimi locali.

In generale, sembra che questo algoritmo ha una statistica un po’ migliore nel trovare una soluzione abbastanza buona, quando usato correttamente (cioè con un’alta probabilità di mutazione), rispetto all’algoritmo Delete All. Questo per tutte le combinazioni di tecniche di valutazione del fitness etc. Tuttavia per confermare quanto detto sono necessari più test.