Karol Bienkowski                                  Warszawa, dn. 19 czerwca 2000
-------------------------------------------------------------------------------
http://bienkowski.net




A l g o r y t m    e w o l u c y j n y   n a   k r a c i e   p r o c e s o w

PW Lab - zadanie 4
rok akademicki 1999/2000




1) Katalog zawiera pliki programu, ktory na kracie procesow realizuje prosty
algorytm ewolucyjny. Specyfikacje zadania stanowi opis z pliku zadanie4.txt.

2) Kompilacja: nalezy wydac polecenie
  make <fifo | msg | shm | shm1 | shm4 | shm16 | shm64 | shm128>,
parametr okresla jaka biblioteka komunikacyjna zostanie uzyta.
fifo - kolejki FIFO, msg - kolejki komunikatow (MSG), shmxxx - pamiec dzielona
o segmencie wielkosci xxx kilobajtow (domyslnie 16).
W wyniku kompilacji zostanie stworzonych 9 plikow wykonywalnych: start oraz
wezel-xx, gdzie xx okresla umiejscowienie wezla w kracie, przy przyjetych
oznaczeniach: p - prawo, g - gora, l - lewo, d - dol, ld - lewy dol, itp.
Tylko plik start sluzy do uruchamiania przez uzytkownika, pozostale sa
uruchamiany przez proces start.

3) Wywolanie: nalezy wydac polecenie
  start <wielkosc kraty> <wielkosc komunikatu> <ilosc powtorzen>,
wielkosc kraty powinna byc < 16 (fifo) lub < 9 (msg i shm).
Przy wiekszej program zapewne zostanie przerwany z powodu braku zasobow.
Zeby zobaczyc dzialanie ewolucji najlepiej uruchomic program na duzej
kracie (np. 8x8) a rozmiar genotypu powinien wynosic ok. 65 bajtow, zeby
miescil sie w jednym wierszu.
W czasie dzialania z ewolucja program wyswietla kolejne genotypy wraz z
policzona funkcja przystosowania (po kazdym pelnym przejsciu przez krate), 
gdy nie ma ewolucji to po zakonczeniu petli wyswietla obliczona wydajnosc.

4) Inne parametry programu:
a) w pliku ewolucja.h mozemy zdecydowac czy program ma realizowac algorytm
   ewolucyjny, czy tylko przesylac komunikaty (makro: EWOLUCJA); jezeli
   ewolucja bedzie symulowana to mozna podac zadanie jakie bedzie rozwiazywala
   (ZADANIE: liczba jedynek lub 3-CNF-SAT), okreslic sposob wyboru genotypu
   (SPOSOB_LOS: 0 = wersja ze specyfikacji - malo wydajna) oraz okreslic
   prawdopodobienstwo mutacji.
b) w pliku lacza_tymczasowe.h mozemy zdecydowac czy program ma miec stale lacza
   (duzo szybsze) czy tworzyc lacza na czas jednej transmisji
   (makro: LACZA_TYMCZASOWE)
   
5) Szczegoly dotyczace sposobu dzialania programu sa zawarte w poczatkowych
   komentarzach w plikach zrodlowych (zwlaszcza naglowkowych)
   
6) Krotki opis plikow:

Makefile           - kompiluje jedna wersje programu w biezacym katalogu
Readme             - to ten
err.c              - obsluga bledow, na koncu podnosci sygnal SIGINT
err.h              - standardowy
ewolucja.c         - implementacje funkcji niezbednych do ewolucji
ewolucja.h         - deklaracje jw.
kom_fifo.c         - implementacja biblioteki komunikacyjnej przy pomocy
                     kolejek FIFO
kom_msg.c          - jw. przy pomocy kolejek komunikatow (MSG)
kom_shm.c          - jw. przy pomocy pamieci dzielonej (SHM), takze funkcje
                     do obslugi semaforow
komunikacja.h      - deklaracje funkcji, ktorych implementacja sa trzy pliki
                     powyzej, biblioteka komunikacyjna
lacza_tymczasowe.h - makra do lacz tymczasowych
semun.h            - standardowa struktura
start.c            - lewy-gorny wezel, ktory tworzy i usuwa cala krate oraz
                     mierzy czas
sygnaly.c          - biblioteka ulatwiajaca obsluge sygnalow
sygnaly.h          - deklaracje jw.
wezel.c            - plik zrodlowy sluzacy do utworzenia 8 roznych plikow
                     wykonywalnych dla roznych rodzajow wezlow

7) Odstepstwa od specyfikacji:
- w przypadku ewolucji program przerywa sie po obliczeniu maksimum funkcji
  przystosowania (ma maksimum),
- sposob losowania genotypu jest inny (mozna zrobic zeby byl taki jak w 
  specyfikacji zmieniajac definicje makra SPOSOB_LOS).