Zadanie 4. Algorytm ewolucyjny
------------------------------

Termin odbioru: 20 czerwca (wtorek) 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
obu 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)
--------------------------------------------------------------