Zadanie 4. Algorytm ewolucyjny
------------------------------
Termin odbioru: 20 czerwca (sroda) godz. 15-ta.
Zadanie polega na zaprogramowaniu opisanego dalej algorytmu oraz
na porownaniu, przy jego uzyciu, wydajnosci okreslonych mechanizmow
komunikacji miedzyprocesowej. W ramach zadania, zbior procesow realizowac
bedzie prosty algorytm ewolucyjny, zatem ponizej przedstawiamy krotki wstep
teoretyczny.
Szersze wyjasnienia dostepne sa w literaturze, takze polskojezycznej.
-----
Wstep
-----
Osobnik: byt reprezentowany przez tzw. genotyp - u nas bedzie to napis zlozony
ze znakow '0' oraz '1'.
Populacja: zbior osobnikow.
Funkcja przystosowania: funkcja zwracajaca dla danego osobnika (genotypu)
wartosc reprezentujaca jego przydatnosc w rozwiazaniu konkretnego
problemu (inaczej mozna o niej myslec jako o jakosci osobnika lub
pewnego rodzaju odleglosci od rozwiazania). Np. gdy chcemy znalezc
maksimum pewnej funkcji, wartosc przystosowania osobnika moze byc
po prostu wartoscia badnej funkcji dla argumentu, ktorego reprezentacja
binarna jest genotypem osobnika (tu osobnik bedzie uznany za lepiej
przystosowany, gdy odpowiadajaca mu wartosc funkcji przystosowania
jest wieksza).
Algorytm ewolucyjny: (u nas) skonczony zbior operacji selekcji oraz mutacji,
kolejnych krokach dostarczajacy najczesciej osobniki coraz lepiej
przystosowane (czyli coraz blizsze rozwiazaniu zadania).
Selekcja: wybor z grupy osobnikow (populacji) nowej grupy osobnikow,
zgodny z ich wartosciami przystosowania (lepiej przystosowani
maja wieksza szanse trafic do nowej populacji i moga miec liczniejsze
potomstwo). W naszej wersji, na podstawie jednego lub dwoch osobnikow
tworzony bedzie jeden lub dwa osobniki.
Mutacja: losowa modyfikacja genotypu osobnika majaca na celu wprowadzenie
zmiennosci w populacji. Mutacja poprawia jakosc populacji jako calosci
tylko w polaczeniu z selekcja.
-------
Zadanie
-------
Prosty algorytm ewolucyjny realizowac bedziemy na kwardatowej kracie (NxN)
procesow nazywanych czasami wezlami.
(W opisie odwolujemy sie do wyobrazni przestrzennej, choc procesy w systemie
operacyjnym pozbawione sa tego typu polozenia.)
Schemat kraty:
+---+ +---+ +---+
+-->|1,1|->|1,2|-> ... ->|1,N|
| +---+ +---+ +---+
| | | |
| v v v
| +---+ +---+ +---+
| |2,1|->|2,2|-> ... ->|2,N|
| +---+ +---+ +---+
| | | |
| v v v
| ... ... ...
| | | |
| v v v
| +---+ +---+ +---+
| |N,1|->|N,2|-> ... ->|N,N|
| +---+ +---+ +---+
| |
+--------------------------+
Zadanie polega na:
- stworzeniu trzech bibliotek mechanizmow jednokierunkowej komunikacji
opartych o:
* kolejki fifo
* kolejki komunikatow
* pamiec dzielona
- stworzeniu kraty procesow, komunikujacych sie ze soba przy uzyciu
jednej ze stworzonych bibliotek (wybor biblioteki w czasie kompilacji)
Procesy maja byc polaczone tak, ze kazdy wezel (z ograniczeniami dla skrajnych)
ma miec polaczenia w pionie i poziomie (przeplyw komunikatow w prawo i w dol).
Cala krate procesow tworzy proces znajdujacy sie w lewym gornym rogu kraty
(proces glowny). Dostaje on jako parametr wywolania dlugosc boku kraty
(NxN procesow, N >= 2), rozmiar genotypu (liczba znakow w komunikacie) oraz
liczba pelnych przejsc populacji genotypow przez krate.
Wezel (z wyjatkiem lewego gornego) odbiera komunikaty (genotypy
osobnikow oraz byc moze inne typy komunikatow) od swojego sasiada z gory oraz
lewej (o ile nie jest skrajny) i po przetworzeniu przekazuje je do
sasiadow z prawej i dolu (o ile takich posiada). Jak widac wystarczaja
lacza jednokierunkowe.
Wezel z lewej u gory generuje jednorazowo pojedynczy losowy genotyp i
przekazuje go do przetworzenia kracie.
Wezel z prawej u dolu otrzymuje po przetworzeniu przez krate pojedynczy
genotyp wynikowy. Przekazuje go z powrotem do procesu z lewej u gory poprzez
dodatkowe polaczenie (mechanizm tego polaczenia mozna wybrac dowolnie).
Proces z lewego gornego rogu, otrzymawszy go, decyduje czy nalezy przepuscic
go ponownie przez krate (liczba okrazen to parametr) czy zakonczyc dzialanie.
- wymysleniu przykladowej funkcji przystosowania (okresla ona jakie zadnie
algorytm realizuje)
Prosty przyklad: liczba znakow '1' w genotypie - bedziemy maksymalizowac
te liczbe.
Zapisaniu tej funkcji:
int wartosc (char * genotyp), gdzie genotyp to ciag znakow '0' i '1'
(a nie bitow zapisanych w bajtach)
- napisaniu algorytmu genetycznego, ktory dziala na utworzonej kracie.
Przy dozwolonym zalozeniu dodatnich wartosci funkcji przystosowania,
algorytm w wezle wyglada nastepujaco (z wyjatkiem lewego gornego
oraz prawego dolnego):
1) jezeli mamy zarowno sasadia lewego jak i gornego
- odbieramy od nich genotypy A oraz B
- wybieramy genotyp C (o ile mamy sasiada z dolu)
/ A z prawdopodobienstwem rownym:
| wartosc(A)/(wartosc(A)+wartosc(B))
C = |
| B z prawdopodobienstwem rownym:
\ wartosc(B)/(wartosc(A)+wartosc(B))
- tak samo wybieramy genotyp D o ile mamy sasiada z prawej
- mutujemy genotypy (zamieniamy poszczegolne znaki '0' na '1',
'1' na '0' genotypu (geny), kazdy z okreslonym prawdopodobienstwem
odpowiednio w genotypach C i D - o ile sa potrzebne)
- przekazujemy C sasiadowi z dolu (o ile istnieje)
- przekazujemy D sasiadowi z prawej (o ile istnieje)
2) jezeli brakuje nam sasiada gornego lub lewego (niezaleznie od posiadania
prawego czy dolnego)
- odbieramy genotyp od tego z wymienionych sasiadow, ktorego mamy
(lewy lub gorny)
- mutujemy go niezaleznie dla sasiadow z dolu i/lub prawej
otrzymujac C i D (odpowiednio o ile mamy takiego sasiada)
- przekazujemy C i D do dolu i prawej (w zaleznosci od istnienia
odpowiednich sasiadow)
Wezel lewy gorny:
- inicjuje tworzenie kraty procesow. Nalezy zachowac synchronizacje tzn.
proces ten ma sie dowiedziec o utworzeniu calej kraty
(tj. procesow i lacz).
Informacje ta jest mu potrzebna - musi wiedziec kiedy rozpoczac
przetwarzanie tak aby pomiar czasu nie byl zaklocany tworzeniem
lacz.
- generuje losowy genotyp i zmutowawszy go niezaleznie dla dolnego i
prawego sasiada przekazuje go im
- oczekuje na wynik od prawego dolnego wezla (poprzez wspomniane wczesniej
dodatkowe polaczenie)
- okrazenie powtarza okreslona parametrem wywolania liczbe razy
- proces ten mozna wykorzystac do pomiarow czasu
- zamyka krate procesow (inicjuje proces zamykania np. informujac
o tym swoich sasiadow, oni swoich itd.) Oczywiscie nalezy zadbac
o usuniecie wszystkich zaalokowanych zasobow (fifo, ipc)
Przy usuwaniu rowniez wymagamy synchronizacji - tzn. proces glowny
ma sie dowiedziec o zakonczeniu pracy pozostalych procesow
i zwolnieniu zasobow - dopiero wtedy konczy prace.
Wezel prawy dolny:
- otrzymuje od sasiadow genotypy A i B i wybiera C
/ A z prawdopodobienstwem rownym:
| wartosc(A)/(wartosc(A)+wartosc(B))
C = |
| B z prawdopodobienstwem rownym:
\ wartosc(B)/(wartosc(A)+wartosc(B))
- wynik ten przesyla przez polaczenie do lewego gornego
procesu.
W celu synchronizacji tworzenia i usuwania kraty mozna wprowadzic
dodatkowe typy komunikatow.
UWAGA:
Jesli jakosc pomiarow moze byc zagrozona udzialem generatora liczb losowych
i obliczaniem wartosci funkcji przystosowania, dozwolone jest wylaczenie
0obu mechanizmow na czas zbierania wynikow.
---------------
Nalezy rowniez:
---------------
- zaprojektowac zestaw testow (rozne rozmiary kraty, wielkosci komunikatow,
dolaczone biblioteki komunikacyjne) badajacych wydajnosc roznych
mechanizmow komunikacji
- przeprowadzic zaprojektowane testy i zebrac ich wyniki
- opracowac raport zawierajacy prezentacje wynikow i wnioski z przeprowadzonych
eksperymentow
Do oceny nalezy przedstawiac wylacznie rozwiazania zlozone ze wszystkich
wymienionych elementow (dzialajacy kod, wyniki testow, analiza).
Powodzenia!
--------------------------------------------------------------
Maciek Grzonkowski (Maciej.Grzonkowski@students.mimuw.edu.pl),
Marta Karbowa (Marta.Karbowa@students.mimuw.edu.pl),
Adam Wasylewski (Adam.Wasylewski@students.mimuw.edu.pl)
--------------------------------------------------------------