Algorytm Genetyczny
Funkcja: 10*n + Suma[x^n -10*cos(2*pi*x)] od 1 do n
Parametry funkcji:
n = 2
<a; b> = -10; 10
dx = 0.001
Wyliczona liczba bitów: 15*n = 30
Parametry populacji:
p – ilość osobników
h – ilość pokoleń
pk – prawdopodobieństwo krzyżowania
pm – prawdopodobieństwo mutacji
oraz
średnia ocena pokolenia – średnia z wartości funkcji celu dla wszystkich osobników danego
pokolenia
najlepszy osobnik populacji – najlepsza wartość funkcji celu jaka pojawiła się na przestrzeni
pokoleń
Wpływ parametrów startowych populacji na średnią ocenę pokolenia
Prawdopodobieństwo krzyżowania:
Krzyżowanie osobników powoduje uśrednianie oceny populacji
W przedziale od 0 do 100 pokolenia widać że niska szansa na krzyżowanie pozwala osiągnąć
szybszy wzrost oceny populacji.
Przedział od 500 do 1000 pokazuje zaś, że wysoki współczynnik krzyżowania zmniejsza
fluktacje (wahania przypadkowe).
Parametr ten powinien być dobierany do ilości pokoleń.
1
10
100
0
100
200
300
400
500
600
700
800
900
1000
Śr
e
d
n
ia
oc
e
n
a
p
ok
ol
e
n
ia
p = 1000; h = 1000; pm = 0.05
pk = 0.20
pk = 0.50
pk = 0.80
Prawdopodobieństwo mutacji:
Mutacja powoduje wprowadzanie losowych zaburzeń w genach osobników, przez co może
stworzyć nowego osobnika o lepszym przystosowaniu.
Współczynnik ten powinien być dobierany do wielkości populacji i ilości pokoleń. Dla 1000
osobników 2,5% jest wartością silnie wpływającą (3 rzędy wielkości) na średnią ocenę
populacji.
Szansa mutacji równa 1,25% dała najlepsze rezultaty od 0 do 150 pokolenia.
Wyłącznie mutacji powoduje jednostronne fluktacje.
0,0001
0,001
0,01
0,1
1
10
100
0
100
200
300
400
500
600
700
800
900
1000
Śr
e
d
n
ia
oc
e
n
a
p
ok
ol
e
n
ia
p = 1000; h = 1000; pk= 0.50
pm = 0.00
pm = 0.0125
pm = 0.025
pm = 0.05
Przykładowe wyniki algorytmu z włączoną mutacją.
Najlepsze wyniki oceny populacji i wartości funkcji najlepszego osobnika osiągnąłem dla wysokiego
prawdopodobieństwa krzyżowania (80%) i niskiego prawdopodobieństwa mutacji (1%).
0,00001
0,0001
0,001
0,01
0,1
1
10
100
0
100
200
300
400
500
600
700
800
900
1000
p = 1000; h = 1000; pk= 0.80; pm = 0.01
srednia ocena pokolenia
najlepszy osobnik populacji
0,00001
0,0001
0,001
0,01
0,1
1
10
100
0
100
200
300
400
500
600
700
800
900
1000
p = 1000; h = 1000; pk= 0.60; pm = 0.02
srednia ocena pokolenia
najlepszy osobnik populacji
Przykładowe wyniki algorytmu z wyłączoną mutacją.
Wyłącznie mutacji powoduje, że algorytm w 8 na 10 przypadków znajduje ocenę funkcji celu równą
3,700008*10^-5 dla parametrów startowych podanych na początku sprawozdania. Mutacja nie
większa niż 1% poprawia ten wynik, kosztem średniej oceny populacji.
0,00001
0,0001
0,001
0,01
0,1
1
10
100
0
100
200
300
400
500
600
700
800
900
1000
p = 1000; h = 1000; pk= 0.80; pm = 0.00
srednia ocena pokolenia
najlepszy osobnik populacji