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 laffidabilità 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 levoluzione 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 dallottimo. 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
allinizio migliori cromosomi. Questo ha prodotto una
soluzione convergente a 187.015. Questo è lontano dallottimo.
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
Luso 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
Lintroduzione della mutazione ha prodotto un piccolo, ma significante miglioramento. Si vede chiaramente leffetto 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 levoluzione 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 lalto 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 dellalgoritmo
windowing è probabilmente un caso fortunato, ma pensiamo che sia
comunque degno di nota.