Analisi dei Test

Note

Questo non è certamente un test completo, abbiamo solo fatto alcuni tentativi come ci sono venuti in mente. Per uno studio più affidabile, i diversi settaggi dei parametri  devono essere ripetuti molte più volte a scelti secondo qualche modello statistico.
Abbiamo usato un valore fissato di seed (799500870) in tutti i test. Questo per dare a tutte le prove esattamente la tessa serie casuale, che migliora l’affidabilità nel comparare i test.

Test 1

Iniziamo con un semplice insieme di  parametri: niente mutazione, niente crossover, tecnica  di sostituzione delete all con elitsmo = 0.

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

Risultato: Distanza: 205.251

ANALISI

E’ interessante notare che l’evoluzione del miglior cromosoma attualmente è migliore nella popolazione iniziale che nella popolazione di convergenza. Questo cromosoma è stato ovviamente sostituito con un cromosoma debole (nota il piccolo picco negativo sulla curva rossa nel grafico). Può forse essere evitato con un valore di elitismo > 0 ?
 

TEST 2

Usiamo gli stessi parametri del test 1, eccetto il valore elitismo cambiato 1.

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

Seed: 799500870

Risultato
Distanza: 197.244
 

Analisi

Usando elitismo, il cromosoma inizialmente migliore non è stato sostituito. Questi risultati  in una soluzione convergente meglio (distanza = 197.244 invece di 205.251). Questa soluzione è comunque lontana dall’ottimo. Usando una popolazione più numerosa, forse un miglior cromosoma esisterà inizialmente?

Test 3

Usiamo gli stessi parametri del test 2, ma aumentiamo la popolazione a  300.

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

Risultato

Distanza: 187.015

Analisi

Siamo stati fortunati! Una Più grande popolazione ha prodotto all’inizio migliori cromosomi. Questo ha prodotto una soluzione convergente a 187.015. Questo è lontano dall’ottimo. Introduciamo qualche irregolarità nella popolazione usando il crossover.
 

Test 4

Usiamo gli stessi parametri del test 3, eccetto: la popolazione è nuovamente di 100, elitismo è settato a 10, la probabilità di crossover è al valore 0.4.

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

Risultato

 

Distanza: 131.562

Analisi

L’uso del crossover insieme a un alto valore di elitismo ha veramente fatto molto. La soluzione migliore è sotto 131.562. Forse questo può essere ancora migliorato? Introduciamo un po’ di  caos - nel linguaggio dei GA: mutazione.
 

Test 5

Usando gli stessi parametri del test 4, ma assegnando alla probabilità di mutazione il valore 0.005.

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: 0 (0 = Evaluation, 1 = Windowing, 2 = Linear Normalization)
Population Deletion technique: 0 (0 = Delete All, 1 = Steady Delete)
Elitism value: 10
Deletion parameter: 10
Seed: 799500870

Risultato
 

Distanza: 113.336
 

Analisi

L’introduzione della mutazione ha prodotto un piccolo, ma significante miglioramento. Si vede chiaramente  l’effetto della mutazione nella curva che mostra la valutazione media. Diventa instabile. Questo implica che c’è una chance che una soluzione migliore verrà prodotta, ma la ricerca di una soluzione migliore è fatta  'alla cieca’. Così, la convergenza è molto lenta.

Abbiamo provato le impostazioni sotto, lasciando l’evoluzione procedere in 75 generazioni. E’ risultato un miglioramento molto piccolo (111.523).

Test 6

Proviamo tecnica di valutazione del fitness chiamata windowing (strappare finestre). La teoria è che a un basso valore di guardia fa sì che i pochi migliori cromosomi dominino la popolazione, e un alto valore fa sì che tutti i cromosomi sembrino gli stessi riguardo il loro fitness. Nel primo caso , il  GA trova velocemente una soluzione migliore, ma in molti casi questa soluzione è un massimo locale. Nel secondo caso, la popolazione è omogenea e perciò converge molto lentamente.

Triste a dirsi, il GA non funziona come dovrebbe nel secondo caso. Converge, quasi con lo stesso  ritmo del primo caso! Forse c’è un bug da qualche parte nel codice…

Comunque, la tecnica windowing funziona bene quando valore di guardia è circa 45. Ogni altro parametro ha lo stesso valore come nel test 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: 1 (0 = Evaluation, 1 = Windowing, 2 = Linear Normalization)
Population Deletion technique: 0 (0 = Delete All, 1 = Steady Delete)
Elitism value: 10
Deletion parameter: 45
Seed: 799500870

Risultati

Distanza: 132.162
 
 

Analisi

La popolazione converge velocemente, ma non a un livello di evaluation molto buono. Forse ci vorrebbe più mutazione?
 

Test 7

Usando gli stessi parametri del test 6, eccetto la probabilità di mutazione che è settata a 0.4. Questa è una probabilità molto alta di mutazione, ma andrà a finire  in una buona soluzione:

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

Risultato

Distanza: 98.7325

Analisi

Si vede chiaramente che l’alto valore di mutazione fa sì che la linea di valutazione media vada  su e giù. La soluzione migliore risultante (98.7325) è la migliore che questo  GA abbia mai raggiunto.
 

Il diagramma sopra mostra che questa deve essere una delle migliori soluzioni possibili. Il successo dell’algoritmo windowing è probabilmente un caso fortunato, ma pensiamo che sia comunque degno di nota.