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