Pojam “Genetsko programiranje” za čitaoce koji nisu upućeni u ovu temu pomisliće da se radi o nekakvom genetskom inžinjeringu, kloniranju i svim onim temama koji su vezani za genetiku. Međutim, nije tako. Genetsko programiranje je prvenstveno inženjerska metoda koja rješava određene probleme iz domena statistike, modeliranja inženjerskih problema, i šire. Metoda se široko koristi od komponovanja muzike do izračunavanja određenih kalkulacija u istraživanju svemira. Moje prvo upoznavanje sa Evolucijskim algortmima bilo je prošle godine na predavanju u sklopu postdiplomskom studijia na Tehničkom fakultetu u Bihaću. Iskreno na početku sam bio zbunjen, a malo kasnije definitivno odlučio primjenjivati tamo gdje god je to efikasno i provodljivo.

Naime o čemu se radi…

Sredinom 60-tih godina profesor Holland je prvi razvio metodu rješavanja problema optimizacije genetskim algoritmom. Njegov student Goldber razvio je i usavršio metodu za rješavanje kompleksnih problema optimizacije. 1989 godine Goldber objavljuje knjigu koja se poslije javlja kao inspiracija i startna tačka skoro svih metoda razvijenih na bazi evolucijskog programiranja.

Kroz primjer pokušat ćemo da objasnimo osnove Genetskog algoritma kao preteče genetskog programiranja. Na primjer, posmatrajmo funkciju y=f(x). Kad postavimo problem određivanja optimuma ove funkcije, prvo što nam na um pada je da izračunamo derivaciju funkcije, te izjednačimo je s nulom i riješimo matematičku jednačinu. Međutim, šta ako funkcija nije derivabilna, odnosno neprekidna u nekom intervalu (što je čest slučaj realnih procesa), šta ako ona ima više od 3 nezavisno promjenjive. U tom slučaju koristićemo iterativne metode postepenog približavanja datom cilju (jer su jednostavnije i lakše primjenjive pomoću računara). Međutim, za više nezavisnih varijabli (10, 20 pa čak i 100) ovaj problem postaje vrlo složen. Ista je situacija ako je funkcija vrlo kompleksna matematička jednačina. Čak idemo do toga da je funkcija y=f(x), skup diskretnih brojeva, odnosno skup eksperimentalnih podataka. U tom slučaju prstupi ćemo korištenjem regresijske analize i Gausove metode izračunavanja najmanjih kvadrata, prevođenjem eksperimentalnih rezultata u polinomni oblik, te opet tražiti derivaciju polinoma u odredjenom intervalu itd …

Svi navedeni problemi (kod rješavanja optimizacije) upravo su prednosti Genetskog algoritma. Sumiranjem iznesenog možemo navesti prednosti korištenja Genetskog algoritma (GA) i to:

1. Optimizacija kako kontinualnih tako disketnih varijabli
2. Neprekidnost funkcije (derivabilnost) nije potreban uslov
3. Simultano traženje rješenja iz širokog skupa mogućih rješenja, inteligentno približavanje tačnom riješenju
4. Uspješno se primjenjuje kod velikog broja nezavisno promjenjihvih varijabli
5. Nema tendenciju padanja u lokalne optimume (veliki problem klasičnih metoda)
6. Uspješno se primjenjuje nad generiranih podacima – eksperimentalnim ili analitičkih funkcija

A sad malo teorije….

GA počinje definisanjem strukture hromosoma. Ako hromosom ima N_var (N_var dimenzionalni optimizacijski problem ) određen sa p₁,p₂,p₃,…,p_n, tad se hromosom može odrediti kao vektor od N_var koordinata:

hromosom=[ p₁,p₂,p₃,…,p_n],
gdje je p₁,p₂, …p_n, binarni, cijeli ili realni brojevi koji reprezentiraju (predstavljaju) hromosom.

Npr. ako rješavamo optimizacvijski problem sa dvije nazavisne varijable tada je:
vrijednost=f(hromosom)=f(x,y)

Varijable u GA odnosno hromosome prikazujemo binarno (binarnim brojevima), cijelim ili realnim brojevima. Zavisno od prirode procesa kojeg optimiziramo, primjenjuje se i adekvatan tip hromosoma.

Selekcija je proces kojim se osigurava prenošenje boljeg genetskog materijala iz generacije u generaciju. Postupci selekcije međusobno se razlikuju po načinu odabira hromosoma koji će se prenijeti u sljedeću generaciju.
Prema načinu prenošenja genetskog materijala selekcije se dijele na (slika 3.3):

• Generacijske selekcije -proces odabire najbolje jedinke i od njih kreira novu generaciju.
• Eliminacijske selekcije – proces selekcije eliminira najgore jedinke iz te generacije.

Ukrštanje je proces u kojem se od dva roditelja, parenjem njihovih gena, dobiju jedan ili dva hromosoma koji predstavljaju njihovo potomstvo. Ukrštanje u GA pomoću računara uveliko zavisi od tipa hromosoma. Kada je hromosom prikazan u obliku vektora bitova (binarni hromosom) postoji nekoliko načina ukrštanja.

Ukrštanje binarnog hromosoma dijelimo na:

1. Ukrštanje s jednom tačkom prekida
2. Ukrštanje s dvije tačke prekida
3. Jednoliko ukrštanje – provodimo kao logičke operacije nad bitovima, AND, OR, XOR itd. Npr. Ako su roditelji A i B, tada je POTOMAK= A + XOR(A * B).

Ukrštanje hromosoma s jednom tačkom prekida

Mutacija kao i sama pojava u prirodi dovodi do toka da se u hromosomu ili jedinci unosi potpuno novi genetski materijal. Ona uglavnom potpomže da se izbjegne “padanje” u lokalni optimum funkcije cilja. Primjenom mutacija postiže se raznolikost genetskog materijala i omogućava pretraživanje novih – potencijalno najboljih rješenja.

Mutacija hromosoma predstavljeni binarnim brojevima

Kad svi geni u jednom hromosomu postanu jednaki, vrijednost hromosoma se ne može promijeniti putem ukrštanja, nego mutacijom, gdje se postiže da upravo takvi dijelovi u hromosomu budu promjeni.

Parametri GA odredjuju način evolucije hromosoma u populaciji te njihovim podešavanjem možemo znatno smanjiti vrijeme izvodjenja algoritma, agresivnost s kojom će algoritam konvergirati u optimum.

Parametri GA:

1. veličina populacije M,
2. broj iteracija I
3. vjerojatnost mutacije v_m
4. vjerojatnost ukrštanja v_u
5. metoda selekcije

Ovisno o tipu hromosoma, vrsti selekcije mogu se pojaviti i neki parametri svojstveni npr. binarnom hromosomu kao što je dužina hromosoma, selekcijski pritisak kod turnirske selekcije, itd.

Vjerojatnost mutacije je jedan od najvažnijih parametara optimizacijskog GA, i direktno uslovljava izbjegavanje padanja u lokalni optimum funkcije cilja.

Pored vjerojatnosti mutacije veličina populacije (M) je parametar koji direktno utiče na kvalitet dobijenih rješenja. Medjutim to je i parametar koji naviše utiče na brzinu kompjuterske obrade GA. Ovaj parametar je u direktnoj vezi sa brojem iteracija. Što je veličina populacije manja potrebno je smanjiti i broj iteracija, i obrnuto.

Broj iteracija takodjer utiče na vrijeme obrade algoritmai na kvalitetu dobijenih rješenja. Što je veći broj iteracija to su i rješenja kvalitetnija. Obzirom da je cilj da se za što kraće vrijeme dobiju što kvalitetniji rezultati, cilj svakog istraživanja pomoću GA je da se minimalnim brojem iteracija i veličine populacije dobiju zadovoljavajuća riješenja.

Pokušaja da se parametri GA povežu i formira njihova medjuzavisnost uvijek je rezultirala neuspjehom, te se došlo do činjenice da rješenje jednog problema nema uticaja za rješavanje nekog drugog primjenom istih parametara.

Obzirom da se GA izvodi pomoću računara moguće je da se parametri GA dinamički mjenjaju u toku izvodjenja algoritma, tako da se npr. poslije 500 iteracija mijenjaju parametri GA, ako algoritam nije u tom razmaku ponudio bolje rješenje.

GENETSKO PROGRAMIRANJE

Ideja genetskog programiranja (GP) došla je kao generalizacija GA. Obzirom da u GA vršimo manipulaciju sa hromosomima koji predstavljaju binarne prirodne ili realne brojeve, moguće je formirati hromosome koji predstavljaju kompjuterske programe nad kojim bi vršili operacije ukrštanja i mutacije i tako dolazili do kompjuterskog programa koji bi rješavao odredjeni problem. Ovu metodu prezentirao je John Koza 1990 godine. Slično kao kod GA u GP razvijena je metoda reprezentacije hromosoma.

U GP hromosomi u populaciji su u obliku hiearhijske strukture sastavljani od primitivnih funkcija i terminala za pojedina problemska područja.

Skup primitivnih funkcija od kojih su hromosomu sastavljani čine aritmetičke operacije, matematičke funkcije, bulove logičke operatore i posebne funkcije specifične za pojedine probleme.

Skup terminala koji takodjer čine strukturu hromosoma obično su sastavljani od ulaznih parametara procesa i različitih numeričkih konstanti.

Kompozicija primitivnih funkcija i terminala kao ideja pronadjena je u programskom jeziku LISP, gdje se takve kompozicije nazivaju simbolički izrazi ili S-izrazi. Simbolički izrazi predstavljaju se kao binarno uređeno drvo, gdje je korijen i ostali unutrašnji čvorovi binarnog drveta označeni sa funkcijama, dočim su vanjski čvorovi označeni terminalima. Tako definisan algoritam pretražuje rješenje problema u prostoru svih mogućih kompozicija funkcija, koje se rekurzivo generišu od dostupnih primitivnih funkcija, i terminala.

U GP populacija sastavljenja od hromosoma se razmnožava po Darwinovom principu opstanka i reprodukcija najprilagođenijih; preko genetskog reproduciranja (ukrštanja) operacija prilagodjenih parenju kompjuterskih programa.

GP kao i GA počinje inicijalizacijom početne populacije slučajno odabranim kompjuterskim programima sastavljanim od funkcija i terminala. Svaki kompjuterski program (hromosom) u populaciji evaluira se u smislu kako dobro riješava problem. Analogno GA ovo mjerenje zovemo mjerenje funkcije cilja hromosoma.

Hromosome u GP predstavljamo u obliku binarnog drveta. Korijen i unutrašnji čvorovi sastavljeni su od funkcija dok su vanjski čvorovi sastavljeni od terminala.

Pretpostavimo kompjuterski program (hromosom): (+,(*,a,b),(ln,c)) , njegova reprezentacija predstavljena je na sljedećeoj slici.

Reprezentacija hromosoma u GP (a*b+ln(c))

Program uzima 3 terminala a,b,c i 3 algebarske funkcije sabiranja, množenja, i prirodnog logaritma. Kompjuterski program u prirodnom obliku možemo prikazati kao: a*b+ln(c), gdje su a,b,c ulazni prarametri problema ili slučajno generirane konstante.

U GP kompjuterski programi ukrštaju se shodno Darwinovom principu reprodukcije i opstanka najprilagodjenijih jedinki. Slučajnim odabirom dva kompjuterska programa (hromosoma) iz populacije ukrštamo i na način de se slučajno odabere tačka ukrštanja te se genetski materija razmijeni izmedju roditelja stvarajući na taj način potomke.

Donja slika predstavlja ukrštanje dva kompjuterska programa.

Ukštanje u GP

Slučajno izabrane tačke ukrštanja u oba kompjuterska programa označavaju koje čvorove programi će razmijeniti i tako generirati svoje potomke.

Kao i kod GA mutacija predstavlja unošenje novog genetskog materijala u kompjuterski program. Mutacija se ivodi tako što se slučajno izabere čvor koji će mutirati te se slučajno generira simbol koji predstavlja uniju skupa funkcija i terminala. Donja slika predstavlja primjer mutacije kompjuterskog programa, gdje je čvor sa oznakom funkcije ln mutirao u funkciju /. Obzirom da funkcija / zahtjeva dva argumenta slučajno se generira drugi argument iz skupa terminala ili funkcija. Obzirom da kod mutiranja ovakav proces može se neprekidno generirati, organičenja u pogledu dubine mutiranja čini sastavni dio parametara GP.

Mutacija u GP

Početna struktura u GP sadrži jedinke u početnoj populaciji sastavljene od slučajno generiranih S -izraza. Početak generiranja počinje slučajnim odabirom jedne od funkcija i skupa F. Ovo ograničenje korijenskog čvora samo na skup funkcija je iz razloga da se strukture ne degeneriraju u samo jedan čvor.

Nakon generiranja koriejnskog čvora postoji nekoliko metoda generiranja strukture.

Puna (Full) metoda generiranja

Kod pune metode generiranja struktura drveta je odredjena konstantnom veličinom dubine strukture. Punom metodom generiramo binarno drvo iz skup funkcija sve dok se ne dostigne maximalna novo (dubina) strukture. Kada se to desi generiraju se simboli iz skupa terminala T.

Rastuća (GROW) metoda generiranja

Rastuća metoda sastoji se u slučajnom generiranju strukture. Ovakvo generiranje proizvodi oblike strukture različitim. Metoda kreće sa slučajnim generiranju čvora koji popima vrijednosti iz skupa C=F U T, odnosno skupa funkcija i terminala. Ovakva metoda ograničena je uslovom da dubina ovako generirane strukture može biti u intervalu 0 do maksimalne dubine drveta. Ako struktura dostigne maksimalnu dubinu drveta u tom nivou se prisiljava algoritam da poprimi vrijednost terminala, a samim tim i završava generiranje.

Miješana (“ramped half-and-half“) metoda generiranje

Ovu metodu autor GP preporuča za mnoge problema koji se rješavaju sa GP. Suština ove metode je da se iskoriste prednosti obe pomenute metode. Iz tog razloga ova metoda se zove još i mješana metoda generiranja. Metoda se jednostavno pojašnjava na primjeru: Npr. ako je

6 maksimalna dubina drveta, tada 20% početne populacije će sadržavati binarne strukture od 2 nivoa dubine, 20% 3 nivoa, 20% 4 nivoa, itd sve do 6 nivoa (1). Tada populacija u ovom stanju sadrži 50% binarnih struktura koje su generirane rastućom metodom, a 50 % punom metodom.

Evaluacija funkcije cilja u GA i GP

Svaki genetski algoritam zahtjeva implementaciju ocjene jedinke. Podobnost neke jedinke – hromosoma ili (S- izraza u GP) mjera je kvalitete toga riješenja u zadanom prostoru rješenja. Kod problema rješavanja optimizacije u GA podobnost hromosoma predstavlja optimalnu vrijednost funkcije cilja. Kod simboličke regresije u GP podobnost jedinke mjeri se odstupanjem kompjuterskog programa od stvarnog rješenja. Zavisno od problema kojeg rješavamo genetskim algoritmima zavisi će i evaluacija hromosoma u populaciji.

PS

Ovo je dio teksta prezentiranog u naučnom radu kojeg sam zajedno sa prof. dr. M. Jurkovićem objavio pod naslovom: MODELLING AND OPTIMIZATION OF THE TOOL STRESS IN DRILLING PROCESS BY EVOLUTION ALGORITHMS by Milan Jurković, Bahrudin Hrnjica, INTERNATIONAL CONFERENCE ON MANUFACTURING SCIENCE AND EDUCATION- MSE 2007- SIBIU-ROMANIA