WYŻSZA SZKOŁA TECHNOLOGII INFORMATYCZNYCH

Warszawa

Laboratorium sztucznej inteligencji

SPRAWOZDANIE

Zadanie nr 1

Studia zaoczne, grupa IZ-5/V

Robert Chmielewski 766

Krzysztof Marchewa 578

Termin oddania: 05.01.2008,

Zadanie 1

Znaleźć (wykorzystując algorytm genetyczny) punkt przecięcia krzywych

f1(x)= x ² oraz f2(x)= 3*sin(x)

co odpowiada rozwiązaniu równania

x ² - 3*sin(x)=0

Rozwiązania poszukiwać w przedziale p჎[0.20, 3.14].

Poszukiwanie rozwiązania można sprowadzić do poszukiwania minimum funkcji

g(x)=abs(f1(x)-f2(x))

Ponieważ dla każdego punktu rozpatrywanego przedziału, różnica między wartości obu funkcji jest nie mniejsza od 10 (g(x)<10), problem można sprowadzić do szukania maksimum funkcji

h(x)=10 - abs(f1(x)-f2(x))

Chromosom zbudować kodując wartości należące do rozpatrywanego przedziału binarnie.

Reprezentację binarną zbudować w sposób w opisany w zadaniu przykładowym.

Przygotować sprawozdanie, prezentujące osiągnięte wyniki. Wykresy sporządzić korzystając z Excela. Do sprawozdania dołączyć kod źródłowy programu.

Rozwiązanie

W celu rozwiązania zadania został zbudowany program, który w oparciu o algorytm

genetyczny poszukuje rozwiązania przedstawionego problemu.

Dane wejściowe są reprezentowane poprzez tablicę chromosomów. Każdy z chromosomów składa się z 10 bitów, tak więc może przedstawiać 1024 punkty kontrolne.

Pozostałe parametry z którymi będziemy uruchamiać program to :

• ilość osobników w populacji - PULA

• liczba pokoleń eksperymentu - LP

• prawdopodobieństwo mutacji - PM

• prawdopodobieństwo krzyżowania - P_KRZYZ

Badania zostały przeprowadzone przy użyciu klasycznego algorytmu sztucznej inteligencji - metody koła ruletki oraz strategii elitarnej.

Program generuje wyniki dla odpowiedniej liczby pokoleń w postaci pliku wyniki.txt, na podstawie którego zostały sporządzone odpowiednie wykresy oraz wnioski.

METODA KOŁA RULETKI

Jest to jedna z podstawowych metod selekcji algorytmów sztucznej inteligencji.

Polega ona na stworzeniu koła ruletki dla poszczególnych chromosomów. Wielkość pól koła ruletki jest proporcjonalna do wartości funkcji przystosowania.

Proces selekcji oparty jest na obrocie ruletką taką ilość razy ile jest osobników w populacji. Za każdym razem wybierany jest jeden chromosom do nowej populacji, dzięki czemu niektóre chromosomy będą wybierane częściej, inne rzadziej a jeszcze inne wcale.

W naszym przypadku wykres funkcji dostosowania wygląda następująco :

h(x) = 10 - |(f1(x)-f2(x)|

Jak widać z powyższego rysunku chromosomy o fenotypie x = 1.7 są „najlepsze” ponieważ ich wartość funkcji dostosowania jest w przybliżeniu równa 10. Dlatego też będziemy poszukiwać chromosomów o fenotypie możliwie bliskim tej wartości.

W tym miejscu pojawia się pewien problem, ponieważ napisaliśmy, że chromosomy „najlepsze”, to te które mają fenotyp x=1.7, ale z wykresu funkcji wynika, że do chromosomów „bardzo dobrych” można zaliczyć wszystkie, których fenotypy reprezentują wartości x od 0.2 do mniej więcej 2.1, ponieważ dla tych wartości x wartość funkcji dostosowania jest wysoka - powyżej 8.

Gdy uruchomimy klasyczny algorytm genetyczny dla metody selekcji ruletki, to pod koniec (przy wysokich numerach pokolenia) w populacji zostają już tylko chromosomy „bardzo dobre” i „najlepsze”, a te „gorsze” zostały usunięte z populacji. Na początku napisaliśmy, że algorytm znajdzie chromosom „najlepszy” (x = 1.7), jednak w przypadku takiej funkcji ten „najlepszy” nie musi wcale mieć wartości x = 1.7, ponieważ może mieć wartość 0.2, albo 0.5 bądź też 1.5 - wszystkie one mają podobną wartość funkcji dostosowania, więc są równie „dobre”.

Dlatego też nie można się dziwić, jeśli algorytm stwierdzi, że „najlepszy” jest chromosom o

x = 0.2 - ponieważ jest on prawie tak samo dobry, jak ten o x = 1.7.

Uruchamiając klasyczny algorytm sztucznej inteligencji z parametrami :

const int lp=50; //liczba pokoleń w eksperymencie

const float a=0.2; //wartość początkowa przestrzeni poszukiwań

const float b=3.14; //wartość końcowa przestrzeni poszukiwań

const int N=10; //liczba genów w chromosomie

const int pula=30; //liczba osobników w populacji (parzysta)

const float pk=0.7; //prawdopodobieństwo krzyżowania

const float pm=0.00; //prawdopodobieństwo mutacji

Uzyskaliśmy następujące wyniki :

0 +7.357 +9.709 3 1101010001 1.793

1 +7.539 +9.746 5 0001010001 1.785

2 +8.912 +9.746 21 0001010001 1.785

3 +8.762 +9.722 16 0101010001 1.791

4 +8.777 +9.976 12 0000100001 1.716

5 +8.929 +9.976 13 0000100001 1.716

6 +8.890 +9.991 15 1100100001 1.725

7 +8.810 +9.991 26 1100100001 1.725

8 +8.785 +9.648 1 0000110001 1.808

9 +8.887 +9.648 3 0000110001 1.808

10 +8.910 +9.648 2 0000110001 1.808

11 +9.066 +9.648 2 0000110001 1.808

12 +9.149 +9.623 27 0100110001 1.814

13 +9.059 +9.611 5 1100110001 1.816

14 +9.094 +9.648 26 0000110001 1.808

15 +9.061 +9.547 2 0001110001 1.831

16 +8.916 +9.547 17 0001110001 1.831

17 +8.985 +9.547 6 0001110001 1.831

18 +9.058 +9.547 1 0001110001 1.831

19 +9.090 +9.547 0 0001110001 1.831

20 +9.175 +9.547 4 0001110001 1.831

21 +9.161 +9.547 5 0001110001 1.831

22 +9.143 +9.547 2 0001110001 1.831

23 +9.103 +9.547 4 0001110001 1.831

24 +9.083 +9.547 1 0001110001 1.831

25 +9.147 +9.547 8 0001110001 1.831

26 +9.152 +9.547 4 0001110001 1.831

27 +9.216 +9.547 7 0001110001 1.831

28 +9.210 +9.547 0 0001110001 1.831

29 +9.177 +9.547 0 0001110001 1.831

30 +9.131 +9.547 5 0001110001 1.831

31 +9.127 +9.547 1 0001110001 1.831

32 +9.123 +9.547 4 0001110001 1.831

33 +9.123 +9.547 5 0001110001 1.831

34 +9.121 +9.547 16 0001110001 1.831

35 +9.104 +9.547 3 0001110001 1.831

36 +9.209 +9.496 0 0011110001 1.842

37 +9.273 +9.522 7 0101110001 1.837

38 +9.291 +9.522 0 0101110001 1.837

39 +9.261 +9.547 10 0001110001 1.831

40 +9.187 +9.547 17 0001110001 1.831

41 +9.174 +9.547 6 0001110001 1.831

42 +9.234 +9.547 25 0001110001 1.831

43 +9.293 +9.547 8 0001110001 1.831

44 +9.367 +9.547 10 0001110001 1.831

45 +9.422 +9.547 8 0001110001 1.831

46 +9.394 +9.547 6 0001110001 1.831

47 +9.393 +9.522 6 0101110001 1.837

48 +9.362 +9.496 2 0011110001 1.842

49 +9.332 +9.496 3 0011110001 1.842

Kolejne kolumny oznaczają:

1 - numer pokolenia

2 - średnia wartość funkcji dostosowania w populacji

3 - maksymalna wartość funkcji dostosowania w populacji

4 - numer w populacji chromosomu, który ma największą wartość funkcji dostosowania

5 - chromosom, który w całej populacji ma największą wartość funkcji dostosowania

6 - wartość fenotypu chromosomu

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
45	9.422	0001110001	1.831

Czyli algorytm nie znalazł „najlepszego” chromosomu (najlepszy jest dla x=1.722), ale znalazł „bardzo dobry” (x=1.831).

Wykres średniej wartości funkcji dostosowania w populacji:

Na osi poziomej - oznaczone są nr pokoleń.

Na osi pionowej - średnia wartość funkcji dostosowania w pokoleniu.

Jak widać, na początku populacja była „średnia” (średnia wartość funkcji dostosowania = 7.5), ale szybko stała się „dobra” ( ...>= 9), a pod koniec stała się już „bardzo dobra” (...>= 9.5).

Sprawdźmy jak będzie się zachowywał algorytm dla parametrów :

lp=50, N=10, pula=30; pk=0.5; pm=0.15

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
31	9.626	1011000001	1.707

W tym wypadku wykres jest bardziej „poszarpany” w stosunku do poprzedniego, ponieważ znaczny wpływ na jego przebieg miało krzyżowanie chromosomów. Pomimo sporych wahań wartości funkcji dostosowania algorytm zwraca dobre wyniki, czego dowodem jest odnaleziony fenotyp x=1.707 posiadający wartość 9.626.

Zbadamy teraz algorytm dla parametrów sterujących :

lp=50, N=10, pula=30; pk=0.35; pm=0.10.

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
45	9.529	1101000001	1.702

W początkowych pokoleniach chromosomy są „przeciętne” (wartości ok. 8.8) jednak w późniejszych sytuacja się zmienia (średnia wartość ok. 9.4) i nie następują już znaczne zmiany wartości funkcji dostosowania.

Następnie zbadamy jak będzie się zachowywał algorytm przy zmianach mutacji :

lp=50, N=10, pula=30; pk=0.7; pm=0.01.

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
18	9.140	0111111110	1.664

Czyli znowu algorytm nie znalazł „najlepszego” chromosomu, ale znalazł „bardzo dobry”.

Widać, że populacja najpierw była całkiem dobra (8.2), potem bardzo dobra (9.1), ale potem trochę się pogorszyła (8.9). Jest to dość normalna sytuacja, ponieważ algorytm jest losowy. Sporządzony wykres funkcji jest bardziej poszarpany pod koniec, co zapewne wynika z mutacji chromosomów w kolejnych pokoleniach.

lp=50, N=10, pula=30; pk=0.7; pm=0.3.

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
11	9.058	1100100001	1.725

Z pośród zaprezentowanych poprzednio wykresów, ten wydaje się najbardziej „poszarpany” co tylko potwierdza słuszność, iż mutacja odgrywa tutaj zasadniczą rolę.

Na wykresie występują znaczne spadki średniej wartości funkcji dostosowania dla niektórych pokoleń (najbardziej widoczne między 15-20 pokoleniem, oraz między 40 - 43).

lp=50, N=10, pula=30; pk=0.7; pm=0.5.

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
42	9.228	1100100001	1.725

Zmiana prawdopodobieństwa mutacji z 0.3 do 0.5 nie przyniosła już tak gwałtownych zmian jak we wcześniejszych przypadkach. Algorytm zwrócił w miarę dobry chromosom o fenotypie 1.725 i wartości dostosowania 9.228.

Warto również sprawdzić jak będą przebiegały zmiany dla większej liczby pokoleń.

lp=300, N=10, pula=30; pk=0.7; pm=0.05

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
294	9.651	1111000001	1.713

Wartość funkcji dostosowania nie jest zła, ale widać jej duże zmiany w kolejnych populacjach (wpływ dużego prawdopodobieństwa mutacji).

We wszystkich przykładach widać, że algorytm działa poprawnie - populacja staje się coraz bardziej „idealna”, a znajdowane chromosomy mają fenotypy zbliżone do wartości 1.7 (która daje maksymalną wartość funkcji dostosowania), dlatego przy odpowiednio dobranych parametrach sterujących programem można osiągnąć satysfakcjonujące wyniki.

STRATEGIA ELITERNA

Strategia elitarna zakłada, że w procesie tworzenia nowej populacji kopiowany jest „najlepszy” chromosom. Nie podlega on jednak krzyżowaniu i mutacji, dzięki czemu jest on „chroniony”.

W przeciwieństwie do algorytmu klasycznego, gdzie najlepszy osobnik podlega krzyżowaniu i mutacji, może on z „najlepszego” stać się „gorszym”, „najgorszym” a nawet i wypaść z populacji, strategia elitarna zapewnia uzyskanie optymalnych rezultatów w kolejnych pokoleniach.

W naszym projekcie strategię elitarną zastosowaliśmy w następujący sposób :

Przed funkcją KRZYZOWANIE() uruchamiana jest funkcja NR_MAX_CHROM(), która znajduje chromosom o największej wartości funkcji dostosowania w populacji (właściwie to znajduje jego numer). Przed NR_MAX_CHROM() trzeba jeszcze wywołać OBLICZ_DOSTOSOWANIE().

Ten najlepszy chromosom jest zapamiętywany przez wywołanie funkcji PAMIETAJ_NAJ_CHROM(). Potem następuje krzyżowanie i mutacje. Następnie ten najlepszy chromosom jest przez funkcję WPISZ_NAJ_CHROM() wpisywany z powrotem do populacji, na miejsce zerowe.

W programie wybór strategii dokonuje się przez ustawienie zmiennej „elitarna” na początku kodu „elitarna=true;” dzięki czemu zostanie uruchomiona strategia elitarna.

Pojawia się tu pewien problem: a co będzie, gdy w tym miejscu jest chromosom lepszy od tego chronionego? Niestety ale zostanie on zniszczony, a na jego miejsce wpisany ten chroniony. Oczywiście byłoby najlepiej, gdyby ten chroniony chromosom wpisywać na miejsce najgorszego chromosomu, ale byłaby to dodatkowa komplikacja algorytmu.

Przejdźmy zatem do analizy algorytmu z zastosowaniem strategii elitarnej :

lp=50, N=10, pula=30, pk=0.7, pm=0.00

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
44	9.998	0100100001	1.772

Zaraz po uruchomieniu programu algorytm bardzo szybko (jeszcze przed piętnastym pokoleniem) odnalazł dobry chromosom. Z każdym kolejnym pokoleniem populacja staje się coraz bardziej optymalna, a pod koniec jest wręcz „idealna”, co zresztą widać na powyższym wykresie.

Teraz sprawdźmy jak będzie się zachowywał algorytm przy zmianie prawdopodobieństwa krzyżowania oraz mutacji :

lp=50, N=10, pula=30, pk=0.5, pm=0.01

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
48	9.998	0100100001	1.772

Po zmianie krzyżowania i wprowadzeniu niewielkiej mutacji wykres jest bardziej postrzępiony, wolniej osiąga wartość maksymalną (dopiero w 48 pokoleniu, a poprzednio w ok. 25), ale porównując z metodą ruletki, wydaje się, że mutacja i krzyżowanie nie powodują tu wyraźnych spadków „jakości” populacji w kolejnych pokoleniach.

lp=50, N=10, pula=30, pk=0.35, pm=0.01

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
31	9.998	0100100001	1.772

Kolejny raz strategia elitarna sprawdza się bardzo dobrze - wykres szybko osiągając dobre wartości funkcji dostosowania. W kolejnych pokoleniach występuje niewielkie oddziaływanie mutacji i krzyżowania np. między 15-20 pokoleniem oraz 33-50, ale zasadniczo nie wpływa na zmianę krzywej.

Spróbujemy teraz zmienić mutację i zaobserwować zmiany w projekcie :

lp=50, N=10, pula=30; pk=0.7; pm=0.1

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
43	9.749	1111111110	1.667

Algorytm nie zwrócił maksimum wartości funkcji dostosowania (które oczywiście chcemy osiągnąć), jak to miało miejsce na poprzednich wykresach, ale dobrze radzi sobie ze zmianami w mutacji na poziomie 0.1.

lp=50, N=10, pula=30; pk=0.7; pm=0.3

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
14	9.58	1111000001	1.713

Sytuacja analogiczna jak z poprzednim przykładem, z tą różnicą że tym razem bardzo uwidoczniły się skutki zwiększonego prawdopodobieństwa mutacji dla 0.3, przez co występują spore spadki wartości funkcji dostosowania w różnych pokoleniach na wykresie.

lp=50, N=10, pula=30; pk=0.7; pm=0.5

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
20	9.358	0100100001	1.722

Po zwiększeniu mutacji do 0.5 można odnieść wrażenie, że jeszcze bardziej pogorszyła się wartość funkcji dostosowania dla najlepszego chromosomu. Biorąc pod uwagę losowość zmian mutacji i spore wahania wykresu to dla wskazanej ilości pokoleń nie jesteśmy w stanie do końca ocenić jak dobry byłby algorytm dla innego zestawu danych. Dlatego też prześledzimy działanie algorytmu dla większej ilości pokoleń.

lp=300, N=10, pula=30; pk=0.7; pm=0.05

Wartość maksymalna :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
132	9.993	0100100001	1.722

Po zwiększeniu liczby pokoleń do 300 algorytm zachowuje się bardzo dobrze, wykres wartości funkcji dostosowania od liczby pokoleń nie jest zbytnio poszarpany, w przeciwieństwie do selekcji metodą ruletki.

Co prawda mutacja uwidacznia się wraz ze wzrostem ilości pokoleń i powoduje pewne spadki, ale jest to zjawisko naturalne i w dłuższej perspektywie czasowej można zaryzykować stwierdzenie,

że mutacja w tym wypadku nie jest parametrem strategicznym dla działania algorytmu.

PORÓWNANIE OBYDWU SELEKCJI

Na koniec przyjrzymy się jeszcze wykresom porównującym obydwie strategie :

metoda koła ruletki - kolor czerwony ; strategia elitarna - kolor purpurowy

lp=50, N=10, pula=30, pk=0.7, pm=0.00

Wartość maksymalna dla metody koła ruletki :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
44	9.510	0011111110	1.659

Wartość maksymalna dla strategii elitarnej :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
44	9.961	1111000001	1.713

lp=50, N=10, pula=30, pk=0.7, pm=0.05

Wartość maksymalna dla metody koła ruletki :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
33	9.265	1011111110	1.661

Wartość maksymalna dla strategii elitarnej :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
49	9.947	0100100001	1.722

lp=300, N=10, pula=30, pk=0.7, pm=0.1

Wartość maksymalna dla metody koła ruletki :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
236	9.579	1111000001	1.713

Wartość maksymalna dla strategii elitarnej :

nr. pokolenie	najw. wart. średniej wartości f-cji dostosow.	chromosom	fenotyp
185	9.955	0100100001	1.722

WNIOSKI KOŃCOWE

Postaramy się teraz wyciągnąć ogólne wnioski, dla obydwu metod selekcji sztucznej inteligencji, z naszego projektu.

Na podstawie załączonych wykresów, dochodzimy do wniosku, iż strategia elitarna zdecydowanie lepiej sprawdza się w eksperymencie niż metoda koła ruletki. Dzieje się tak, ponieważ koło ruletki dopuszcza w kolejnych pokoleniach nawet najsłabsze osobniki (choć w mniejszym stopniu), podczas gdy strategia elitarna stara się wyeliminować te najgorsze już w pierwszych pokoleniach.

Po zwiększeniu liczby pokoleń widzimy tendencję do „poprawy” działania koła ruletki, przy czym kluczowy jest dobór odpowiednich parametrów krzyżowania i mutacji, ponieważ przy błędnych parametrach algorytm działa niestabilnie.

Z kolei na działanie selekcji elitarnej wpływa mutacja a nie krzyżowanie. Przy dużych wartościach mutacji (także dla większej liczby pokoleń), obserwujemy „chaotyczne” zmiany na wykresie, ale algorytm o wiele lepiej sobie z nimi radzi niż ruletka (szczególnie na ostatnich wykresach porównujących obydwie metody selekcji).

Nie bez znaczenia ma także szybkość działania samego algorytmu, gdzie strategia elitarna w o wiele szybszym tempie (niż koło ruletki) osiąga oczekiwane maksimum.

---