Genetika u programiranju

Računari Fon-Nojmanovog tipa (oni koji se danas najčešće koriste) po svojoj suštini su sekvencijalne mašine. Programi se izvršavaju korak po korak sve dok ne naiđu na instrukciju skoka, posle čega program nastavlja sa svojim radom sa neke druge lokacije. Zahvaljujući dobrim operativnim sistemima moguće je izvršavati više programa istovremeno, ali se u većini slučajeva to svodi na prekidanje jednog programa da bi drugi radio i obrnuto. Ovi prekidi su za čoveka veoma kratki te mi takvo sekvencijalno izvršavanje više različitih programa vidimo kao paralelno izvršavanje programa, iako ono to nije. Pravi paralelizam softvera dobija se tek uz odgovarajući hardver, to su danas višeprocesorski sistemi, klaster računari, vektorski procesori kao i procesori sa HT (Hyper Threading) tehnologijom.

Uvođenjem paralelizma dobija se mnogo, međutim, većina algoritama razvijana do sada je sekvencijalne prirode (kao i računari za koje su pisani). Veoma je teško već postojeće, tako napisane programe, naterati da se izvršavaju simultano na više procesorskih jedinica, te se jedini dobitak postiže u pokretanju više instanci jednog programa koje bi rešavale različite probleme. To međutim, nije način da se izvuče maksimum iz računara. Jedini pravi način je prilagođavanje algoritama paralelnom sistemu. Neke algoritme je nemoguće paralelizovati jer je njihov dalji rad baziran na prethodno dobijenim rezultatima (npr razvijanje rekurentnih formula), dok su neki algoritmi prosto stvoreni za pralelno izvršavanje.

Nije mi namera da u ovom tekstu pišem o evolutivnom napredku programiranja, niti o paralelnim računarima, već o jednom heurističkom metodu izračunavanja (tačnije metodu optimizacije) koji se prirodno i lako može paralelizovati i na taj način dati mnogo bolje rezultate.

Samo na prvi pogled čini se da bilogija i računarstvo nemaju zajedničkih tačaka. U osnovi funkcionisanje živog organizma se u mnogim stvarima poklapa sa funkcionisanjem računara. Samim tim u računarstvu je iskorišćen jedan od interesantnijih prirodnih fenomena za rešavanje problema optimizacije. Evolutivni proces u prirodi iskorišćen je za konstrukciju tzv Genetskih algoritama (GA). GA predstavlja usmereno slučajno pretraživanje prostora rešenja u potrazi za globalnim optimumom. Osnovni delovi ovog algoritma su prepisani iz prirodne evolucije, a to su: ukrštanje, selekcija i mutacija. Kombinacijom prva dva operatora i sporadičnim ubacivanjem trećeg prave se generacije i na taj način se populacija održava u životu pri čemu ona biva sve kvalitetnija i bliža rešenju.

U prethodnoj rečenici pomenuo sam neke termine teorije evolucije, u GA oni se nazivaju genetskim operatorima. Kao i u prirodi najvažniji su ukrštanje i selekcija. Osnovna razlika između prirodne evolucije i GA je u cilju. Cilj evolutivne promene neke populacije u prirodi je njeno prilagođavanje na spoljašnje uslove radi preživljavanja, dok je u GA cilj proizvesti savršenu jedinku (rešenje problema) ili pronaći dovoljno dobro rešenje (ukoliko pravo rešenje ne postoji). Jedinka u GA predstavlja model potencijalnog rešenja. Da bi selekcija bila moguća, potrebno je na dobar način definisati normu - funkciju cilja (eng: fitness function). Najčešće se za normu bira upravo ona funkcija čije se rešenje traži. Jedan od najčešćih primera demonstracije ove tehnike je pronalaženje globalnog ekstremuma neke funkcije na zadatom domenu. U tom slučaju ta funkcija predstavlja funkciju cilja, a jedinka predstavlja tačku u kojoj se računa funkcija. Primena norme na jedinku za rezultat daje brojčanu vrednost koja se dalje može porediti sa normama drugih jedinki čime se definiše uređenje tih jedinki a samim tim i mogućnost selekcije.

Najzgodniji način prikazivanja jedinki je njihovo prevođenje u binarni oblik, za koji je naravno, potrebno da bude prilagođen problemu. Binarni prikaz nekog podatka je naročito dobar kada se radi o ukrštanju i mutaciji. Ukrštanje se kao operator može definisati na razne načine, jedan od najjednostavnijih načina ukrštanja je slučajan izbor tačke ukrštanja i jednostavna zamena "genetskog" materijala dvema jedinkama desno od te tačke ukrštanja. Jedinke se, naravno mogu ukrštati i po nekim drugim binarnim šablonima. Mutacija čija se učestalost meri u promilima se izvodi na taj način što se vrednost nekog bita jednostavno negira.

Ukoliko imamo dve jedinke sa solidno dobrom normom, pokazuje se da se u velikoj verovatnoći njihovim ukrštanjem dobijaju jedinke sa bar toliko dobrom normom kao i kod roditelja, a često je ta norma i veća. Mutacijom se u principu kvari genetski materijal neke jedinke, ali ukoliko ukinemo mutaciju ukrštanje i selekcija zbog nedostatka genetskog materijala mogu odvesti proces u ćorsokak. Drugi način osvežavanja genetskog materijala u nekoj populaciji je sporadično dodavanje određenog procenta novih jedinki pre ukrštanja, bez obzira da li dobro zadovoljavaju normu ili ne. Konkretno, koristio sam GA za pokazivanje zadovoljivosti formula u iskaznoj logici. Ovaj problem nije rešiv u polinomijalnom vremenu i dokazano je da on spada u NPkompletne (teške probleme). Odgovor da li je neka formula zadovoljiva ili ne je diskretan (DA/NE) što otežava definisanje norme (funkcije cilja). Na sreću postoji više različitih formi u kojima ista formula može da se zapiše zadržavajući logičku ekvivalentnost sa polaznom formulom. Jedan od tih oblika je KNF (Konjuktivna Normalna Forma). KNF predstavlja konjunkciju klauza, dok je svaka klauza disjunkcija literala. Za GA zgodno je da te klauze budu što ravnopravnije, zbog toga sam koristio 3-KNF (formu kod koje su sve klauze dužine 3) za koju takođe postoji algoritam prevođenja polinomijalne kompleksnosti. Formula je zadovoljiva ukoliko je svaka klauza pojedinačno tačna, a norma se definiše brojem tačnih klauza. Svaka od klauza sadrži po 3 literala (iskazna slova koja eventualno mogu biti negirana). Svako od slova predstavljeno kao uključen ili isključen bit u binarno zapisanom podatku. Takav podatak naziva se jedinka, ona jedinka za koju su sve klauze zadovoljive naziva se model te formule. Ukoliko se pokaže postojanje tog modela formula je zadovoljiva – u semantičkom smislu (odnosno formula je teorema – u sintaksno deduktivnom smislu).

Eksperimenti su pokazali da se za rešavanje teških 3-SAT problema mogu koristiti genetički algoritmi. Mana ovog metoda je generalna mana svih heurističnih metoda a to je poluodlučivost, tj metod sa velikom verovatnoćom može brzo pronaći rešenje ukoliko ono pstoji, dok ukoliko rešenje ne postoji metod to ne može utvrditi sa sigurnošću. Međutim velika prednost ovog metoda je prilagođenost paralelnom izvršavanju, upravo onoj temi sa kojom sam i započeo priču. Paralelizacija se može naprviti pokretanjem programa na više različitih procesorskih jedinica, kod kojih će svaka razvijati sopstvene populacije i usavršavati ih u potrazi za ciljom sa eventualnom mogućnošću prebacivanja nekih jedinki sa jedne procesorske jedinice na drugu (radi osvežavanja genetičkog materijala u populaciji). Ovakva igra u potrazi za rešenjem nudi velike mogućnosti eksperimentisanja sa parametrima GA (veličina populacije, procenat ukrštanja, procenat mutacije, procenat dodavanja novih jedinki...) u potrazi za dobrim GA koji bi rešavao određenu klasu problema. Jedan interesantan koncept određivanja ovih parametara je upravo GA, što znači postaviti GA koji bi menjanjem parametara algoritmu koji rešava problem, rešavao taj problem više puta u potrazi za vremenski najbržim rešavanjem. Rešavanje 3-SAT problema je veoma interesantno jer je 3-SAT problem predstavnik NPkompletnih problema (NP – nedeterministički polinomijalno rešivi problemi).

Kompletnost klase NP-kompletnih problema omogućava da se rešavanjem jednog problema iz te klase reši svaki problem iz te klase, jer se algoritmom polinomijalne kompeksnosti jedni problemi iz ove klase mogu svesti na druge). I na kraju vredi napomenuti da je problem "P=NP?" jedan od milenijumskih problema, vredan milion dolara i koga interesuje dobra zarada može da pokuša da razreši ovaj problem, više o tome na: http://www.claymath.org/millennium/

Ukoliko nekog interesuje nešto više o GA i samom problemu koji sam rešavao to može pročitati na http://www.jwork.net/GA3SAT