Rysunek 1. Interfejs programu
Wrocław 18.06.2006
Jarosław Barcewicz [127486]
Łukasz Raciborski [128247]
Przedmiotem projektu było stworzenie programu, który ma za zadanie wyznaczenie przybliżonego wzoru funkcji, przechodzącej przez punkty podane przez użytkownika. Przybliżonego, czyli takiego, który byłby suboptymalnym wynikiem działania algorytmów genetycznych i ewolucyjnych zawartych w powyższym programie.
2. Opis projektu
Program, który został stworzony na potrzeby projektu, posiada wiele funkcji opisanych poniżej, które w przejrzysty dla użytkownika sposób, pozwalają mu się zapoznać z metodami ewolucyjnymi i w ciekawy sposób zaprezentować działanie programu. W projekcie wykorzystano metody genetyczne i ewolucyjne, program podczas działania po pewnej ilości iteracji, znajduje rozwiązanie problemu. Oczywistym jest, że rozwiązanie rzadko jest optymalne, co jest spowodowane metodą użytą w projekcie.
Na Rysunku 1. pokazano interfejs użytkownika. Głównym elementem interfejsu, jak i wizualizacji działania programu jest pole płaszczyzny, na której wizualizowany jest wykres funkcji o najlepszej wartości funkcji celu, jak i punkty, postawione przez użytkownika, i linie je łączące.
Aby program był w pełni konfigurowalny i efektywny, przed uruchomieniem należy ustawić parametry programu. W większości parametry te odpowiadają za sposób działania algorytmów genetycznych, ale są też elementy odpowiadające za prędkość i wizualizację działania programu.
Program został napisany oraz skompilowany w środowisku Borland C++ Builder 6.0.
W celu uruchomienia programu należy podać jakieś punkty klikając na wykresie, bądź wstawiając odpowiednie koordynaty i naciskając przycisk „dodaj punkt do wykresu”. Następnie należy wygenerować populację („generuj nową populację”) i po ustawieniu pozostałych parametrów, których opis znajduje się poniżej nacisnąć przycisk „start”.
Rysunek
1. Interfejs programu
Parametry
Liczebność populacji: parametr odpowiedzialny za ilość osobników biorących udział w symulacji. Minimalna wartość tego parametru wynosi 10. Parametr ten należy ustawić wg własnego uznania, lecz podczas przeprowadzonych symulacji zauważyliśmy, że dobrym ustawieniem są wartości od 100 do 300.
Maksymalna długość chromosomu. Parametr odpowiedzialny za ilość składowych chromosomu całkowitego. Każda z takich składowych zawiera w sobie wzór funkcji, który podczas parsowania jest sumowany z pozostałymi tworząc pełny opis chromosomu osobnika. Początkowo wartość tego parametru wynosi 6, jest to zalecane ustawienie, lecz, aby przyspieszyć działanie programu, warto go zmniejszyć. Dobrymi ustawieniem jest wartość 3 do 5.
% krzyżuj 1 z 4 najlepszych. Parametr odpowiedzialny za procentowe prawdopodobieństwo skrzyżowania dowolnego osobnika populacji z jednym z czterech pierwszych (i tym samym najlepszych) osobników. Duża wartość tego parametru zwiększa dążenie populacji do optimum lokalnego, mała, zwiększa obszar poszukiwań na płaszczyźnie rozwiązań poza dotychczas znalezionym suboptimum. Domyślnym ustawieniem jest 10%, dobrymi rozwiązaniami są wartości od 10 do 20. Pozwalają one na zawężenie poszukiwań w okolicy rozwiązań lokalnych, ale dają również możliwość „wyskoczenia” z lokalnego optimum.
% współczynnik krzyżowania. Parametr odpowiadający za procentowe prawdopodobieństwo skrzyżowania się osobnika z innym. Jeśli takie prawdopodobieństwo zajdzie, to odpowiednio do ustawionego parametru procentowego krzyżowania się z jednym z czterech najlepszych, jest wybierana opcja właśnie takiej czynności albo wyboru (przypadkowego) osobnika z populacji. Domyślnym ustawieniem jest 20%. Dobrymi wartościami są wartości dość wysokie mieszczące się w przedziale od 40 do 80 procent. Pozwalają one na tworzenie zróżnicowanych osobników i tym samym dają możliwość programowi na poszukiwania odleglejszych i często lepszych rozwiązań problemu.
% mutacji. Parametr odpowiadający za procentowe prawdopodobieństwo zmutowania chromosomu osobnika. Domyślną wartością jest 5%. Podczas eksperymentów zauważyliśmy, że dobrymi nastawami są także większe wartości (szczególnie jeśli populacja jest niewielka). Pozwala to generować osobniki o nowych i niewystępujących dotychczas właściwościach. Przykładowymi tego typu wartościami, są np. 30 lub 40 procent.
Włącz mutację całkowitą. Gdy ta opcja jest zaznaczona, istnieje 50% prawdopodobieństwo, że mutacja obejmie cały chromosom i jakiś jego element zostanie zastąpiony przypadkowo wygenerowanym wzorem funkcji. Dzięki temu do populacji zostanie wprowadzony nowy niezależny od reszty osobników element. Podczas symulacji uznaliśmy, że zaznaczenie tej opcji zwiększa prawdopodobieństwo „wyskoczenia” z optimum lokalnego, jednakże wadą jest to, że może przedłużyć czas znalezienia lepszego suboptimum w pobliżu już znalezionego.
Chaotyczna wymiana chromosomów. Opcja pozwala na wybór rodzaju krzyżowania elementów składowych kodu genetycznego osobnika. Jeśli jest zaznaczona zakładamy, że osobniki składają sie z „n” elementów, które nie mogą się krzyżować z innymi, będącymi na różnych od ich pozycji chromosomami pozostałych osobników. Czyli jeśli dana składowa chromosomu znajduje się na 2 miejscu w kodzie, nie może skrzyżować się z elementem chromosomu na pozycji innej niż 2. Zaznaczenie tej opcji, zmniejsza różnorodność osobników wynikowych po krzyżowaniu, jednakże jej zaletą po zaznaczeniu jest poszukiwanie optimum lokalnego w otoczeniu znalezionego dotychczas najlepszego rozwiązania. Zalecane jest, aby opcja była zaznaczona, jednakże warto jest eksperymentować, można ją (jak i inne parametry) zmieniać w trakcie działania programu.
Wykorzystane metody ewolucyjne i genetyczne.
Głównym założeniem projektu było wykorzystanie metod ewolucyjnych i genetycznych, takich jak krzyżowanie, mutacja i ukierunkowany dobór osobników przy pomocy funkcji celu. Funkcja celu jest jednym z najważniejszych kryteriów poprawnego działania programu. W naszym projekcie jej obliczenie jest dość proste, wyliczana jest odległość między wartością składowej Y punktu, a wartością funkcji w punkcie badanym. Wartości te są sumowane i powstaje wartość oceny, czyli wartość funkcji celu. Im ta wartość jest odleglejsza od 0, tym funkcja jest potencjalnie gorsza. Wyniki wraz z osobnikami są sortowane od najlepszych.
Cztery najlepsze osobniki są krzyżowane z przypadkowymi czterema osobnikami populacji (także ze sobą), a wynikowe jednostki są nakładane na cztery najgorsze osobniki populacji. Dodatkowo dwa najlepsze są obowiązkowo mutowane i kopiowane za osobniki 5 i 6 od końca. Stąd minimalna populacja musi wynosić 10 jednostek.
Mutacje (jak zostało wcześniej wspomniane) mogą być całościowe, w skali chromosomu, lub tylko zmieniać elementy równania znajdujące się w chromosomie. Równania generowane są z nastepujących funkcji:
funkcje trygonometryczne: sin, cos;
funkcja logarytm naturalny: ln;
operatory: *, /, +, -, ^ (gdzie „^” - potęgowanie);
liczby: 0 do 20;
zmienna: X.
Krzyżowanie polega na wymianie składowych chromosomów osobników w sposób częściowo ukierunkowany. Dwa osobniki najlepsze, zawsze pozostają niezmienione.
3.Przykładowe symulacje
Poniżej znajdują się wyniki przykładowych symulacji. Pierwszym elementem rysunku jest wykres funkcji i punkty zaznaczone przez użytkownika. Poniżej znajduje się wzór najlepszej z ocenianych funkcji i po jej prawej stronie wartość oceny przez funkcje celu. Dla pierwszego przykładu (Rysunek 2) pokazane jest także okno 10 najlepszych osobników.
Najlepsza funkcja: 11*cos(X)+6/X+cos(X)+15+X
Wartość funkcji celu: 46
Rysunek
2. Wynik przykładowej symulacji po 620 iteracjach.
Rysunek
3. Wynik przykładowej symulacji po 785 iteracjach.
Najlepsza funkcja: 20^ln(sin(X-X^3))+(16)+ln(cos(ln(X)))
Wartość funkcji celu: 76
Rysunek
4. Wynik przykładowej symulacji po 198 iteracjach.
Najlepsza funkcja: 33^sin(X)+34/X+ln(71)+ln(X)
Wartość funkcji celu: 28
Rysunek
5. Wynik przykładowej symulacji po 1740 iteracjach.
Najlepsza funkcja: X*(sin(X))+(cos(ln(X)))*ln(cos(X))+4^2+sin(cos((X)))+(X)-X/X
Wartość funkcji celu: 11
Rysunek
6. Wynik przykładowej symulacji po 5351 iteracjach.
Najlepsza funkcja: 8*ln(X)+X^sin(X/(X/ln(X)))+8*ln(X)+9-X+ln(ln((X)))
Wartość funkcji celu: 27
Rysunek
7. Wynik przykładowej symulacji po 548 iteracjach.
Najlepsza funkcja: ln((cos(X^3)))+ln((cos(X^3)))+ln(((X^5)))+(cos(X))+46-(32/X)
Wartość funkcji celu: 3
4. Wnioski
Jak widać z rysunków 2, 3, 4, 5 program jest daleki od znalezienia dokładnego przybliżenia wzoru funkcji przechodzącej przez wszystkie punkty podane przez użytkownika. Na rysunkach 6 i 7 widać że program poradził sobie dość dobrze (szczególnie w przypadku rys. 7.), co spowodowane jest po części faktem, że funkcje brane pod uwagę w przypadkach z rysunków 6, 7, jak widać, miały całkiem inny charakter. W powyższych sesjach, użyto parametrów podanych w ich opisie, jako dobre lub dające duże prawdopodobieństwo „wyskoczenia” z obszaru lokalnego optimum. Dobór metod ewolucyjnych i genetycznych był intuicyjny, gdyż brak jest materiałów opisujących właśnie ten konkretny problem, który staraliśmy się rozwiązać. Warto zauważyć, że funkcja oceny powinna obejmować jak najwięcej kryteriów, takich jak ilość harmonicznych funkcji pomiędzy kolejnymi punktami użytkownika, a także oceniać szybkość wzrostu odległości funkcji od współrzędnych funkcji osobników. Możliwości jest wiele, uważamy, że problem jest skomplikowany, lecz zarazem ciekawy, a jego rozwiązanie byłoby bardzo użyteczne, choćby do opisu sygnałów pobranych z natury (sygnały dźwiękowe, histogramy obrazów, kompresja obrazów) wzorami funkcji. Istnieją metody wielomianowe, są one jednak bardzo skomplikowane i dają duże przeregulowania. Nasze wynikowe funkcje ocenione przez program jako dobre (z małą wartością funkcji celu) przebiegają w pobliżu punktów i tym samym nie generowałyby większych błędów, np. przy odwróceniu operacji, czyli wygenerowaniu z nich punktów i zastosowaniu ich do jakichś badań/czynności.
5. Bibliografia
Książki:
Zbigniew Michalewicz, Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT Wydawnictwo Naukowo – Techniczne, Warszawa 2003.
Danuta Rutkowska, Maciej Piliński, Leszek Rutkowski, Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa 1999.
Leszek Rutkowski, Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, Warszawa 2005.
Internet:
http://knf.p.lodz.pl/~student/ - strona autora parsera wykorzystanego w tym projekcie