Blog Archives

Function optimization with Genetic Algorithm by using GPdotNET

Content

1. Introduction
2. Analytic function optimization module in GPdotNET
3. Examples of function optimizations
4. C# Implementation behind GPdotNET Optimization module

Introduction

GPdotNET is artificial intelligence tool for applying Genetic Programming and Genetic Algorithm in modeling and optimization of various engineering problems. It is .NET (Mono) application written in C# programming language which can run on both Windows and Linux based OS, or any OS which can run Mono framework. On the other hand GPdotNET is very easy to use. Even if you have no deep knowledge of GP and GA, you can apply those methods in finding solution. The project can be used in modeling any kind of engineering process, which can be described with discrete data. It is also be used in education during teaching students about evolutionary methods, mainly GP and GA. GPdotNET is open source project hosted at http://gpdotnet.codeplex.com

With releasing of GPdotNET v2 it is also possible to find optimum for any analytic function regardless of independent variables. For example you can find optimum value for an analytically defined function with 2, 5, 10 or 100 independent variables. By using classic methods, function optimization of 3 or more independent variables is very difficult and sometimes impossible. It is also very hard to find optimum value for functions which are relatively complex regardless of number of independent variables.
Because GPdotNET is based on Genetic Algorithm we can find approximated optimum value of any function regardless of the limitation of number of independent variables, or complex definition. This blog post is going to give you a detailed and full description how to use GPdotNET to optimize function. Blog post will also cover C# implementation behind optimization proce by showing representation of Chromosome with real number, as well as Fitness calculation which is based on Genetic Programming tree expression. In this blog post it will also be presented several real world problem of optimization which will be solved with GPdotNET.

Analitic Function Optimization Module in GPdotNET

When GPdotNET is opened you can choose several predefined and calucalted models from various domain problems, as weel as creating New model among other options. By choosing New model new dialog box appears like picture below.

By choosing Optimization of Analytic Function (see pic above) and pressing OK button, GPdotNET prepares model for optimization and opens 3 tab pages:

Analytic function,
Settings and
Optimize Model.

Analytic function

By using “Analytic function” tab you can define expression of a function. More information about how to define mathematics expression of analytic function can be found on this blog post.

By using “Analytic definition tool” at the bottom of the page, it is possible to define analytic expression. Expression tree builder generates function in Genetic Programming Expression tree, because GPdotNET fully implements both methods. Sharing features of Genetic programming in Optimization based Genetic Algorithm is unique and it is implement only in GPdotNET.

When the process of defining function is finished, press Finish button in order to proceed with further actions. Finish button action apply all changes with Optimization Model Tab. So if you have made some changed in function definition, by pressing Finish button changes will be send to optimization tab.
Defining expression of function is relatively simple, but it is still not natural way for defining function, and will be changed in the future. For example on picture 2, you can see Expression tree which represent:

$f(x,y)=y sin{4x}+1.1 x sin{2y}$ .

Setting GA parameters

The second step in optimization is setting Genetic Algorithm parameter which will be used in optimization process. Open the Setting tab and set the main GA parameters, see pic. 3.

To successfully applied GA in the Optimization, it is necessary to define:

population size,
probabilities of genetic operators and
selection methods.

These parameters are general for all GA and GP models. More information about parameters you can find at http://bhrnjica.net/gpdotnet.

Optimize model (running optimization)

When GA parameters are defined, we can start with optimization by selecting Optimization model tab. Before run, we have to define constrains for each independent variables. This is only limitation we have to define i order to start optimization. The picture below shows how to define constrains in 3 steps:

select row by left mouse click,
enter min and max value in text boxes
Press update button.

Perform these 3 actions for each independent variable defined in the function.

When the process of defining constrains is finished, it is time to run the calculation by pressing Optimize button, from the main toolbar(green button). During optimization process GPdotNET is presenting nice animation of fitness values, as well as showing current best optimal value. The picture above shows the result of optimization process with GPdotNET. It can be seen that the optimal value for this sample is $f_{opt}(9.96)=-100.22$ .

Examples of function optimization

In this topic we are going to calculate optimal value for some functions by using GPdotNET. Zo be prove that the optimal value is correct or very close to correct value we will use Wolfram Alpha or other method.

Function: x sin(4x)+1.1 x sin(2y)

GP Expression tree looks like the following picture (left size):

Optimal value is found (right above picture) for 0.054 min, at 363 generation of total of 500 generation. Optimal value is f(8.66,9.03)=-18.59.

Here is Wolfram Alpha calculation of the same function. http://www.wolframalpha.com/input/?i=min+x*sin%284*x%29%2B+1.1+*y*+sin%282+*y%29%2C+0%3Cx%3C10%2C0%3Cy%3C10

Function: (x^2+x)cos(x), -10≤x≤10

GP expression tree looks like the following picture (left size):

Optimal value is found for 0.125 min, at 10 generation of total of 500 generation. Optimal value is F(9.62)=-100.22.

Here is Wolfram Alpha calculation of the same function. http://www.wolframalpha.com/input/?i=minimum+%28x%5E2%2Bx%29*cos%28x%29+over+%5B-10%2C10%5D

Easom’s function fEaso(x1,x2)=-cos(x1)•cos(x2)•exp(-((x1-pi)^2+(x2-pi)^2)), -100<=x(i)<=100, i=1:2.

GP expression tree looks like the following picture (left size):

Optimal value is found for 0.061 min, at 477 generation of total of 500 generation. Optimal value is F(9.62)=-1, for x=y=3.14.

Function can be seen at this MatLab link.

C# Implementation behind GPdotNET Optimization module

GPdotNET Optimization module is just a part which is incorporated in to GPdotNET Engine. Specific implementation for this module is Chromosome implementation, as well as Fitness function. Chromosome implementation is based on floating point value instead of classic binary representation. Such a Chromosome contains array of floating point values and each element array represent function independent variable. If the function contains two independent variables (x,y) chromosome implementation will contains array with two floating points. Constrains of chromosome values represent constrains we defined during settings of the optimization process. The following source code listing shows implementation of GANumChrosomome class in GPdotNET:

public class GANumChromosome: IChromosome
 {
 private double[] val = null;
 private float fitness = float.MinValue;
 //... rest of implementation
}

When the chromosome is generated array elements get values randomly generated between min and max value defined by function definition. Here is a source code of Generate method.

///
/// Generate values for each represented variable
///
public void Generate(int param = 0)
{
	if(val==null)
		val = new double[functionSet.GetNumVariables()];
	else if (val.Length != functionSet.GetNumVariables())
		val = new double[functionSet.GetNumVariables()];

	for (int i = 0; i < functionSet.GetNumVariables(); i++)
		val[i] = Globals.radn.NextDouble(functionSet.GetTerminalMinValue(i), functionSet.GetTerminalMaxValue(i));

}

Mutation is accomplish when randomly chosen array element randomly change itc value. Here is a listing:

///
///  Select array element randomly and randomly change itc value
///
public void Mutate()
{
	//randomly select array element
	int crossoverPoint = Globals.radn.Next(functionSet.GetNumVariables());
	//randomly generate value for the selected element
	val[crossoverPoint] = Globals.radn.NextDouble(functionSet.GetTerminalMinValue(crossoverPoint), functionSet.GetTerminalMaxValue(crossoverPoint));
}

Crossover is little bit complicated. It is implemented based on Book Practical Genetic Algoritms see pages 56,57,48,59. Here is an implementation:

///
/// Generate number between 0-1.
/// For each element array of two chromosomes exchange value based on random number.
///
///
public void Crossover(IChromosome ch2)
{
	GANumChromosome p = (GANumChromosome)ch2;
	int crossoverPoint = Globals.radn.Next(functionSet.GetNumVariables());
	double beta;
	for (int i = crossoverPoint; i < functionSet.GetNumVariables(); i++)
	{
		beta = Globals.radn.NextDouble();
		val[i] = val[i] - beta * (val[i] - p.val[i]);
		p.val[i] = p.val[i] + beta * (val[i] - p.val[i]);
	}
}

Fitness function for Optimization is straightforward, it evaluates each chromosome against tree expression. For minimum the better chromosome is lower value. For maximum better chromosome is the chromosome with higher fitness value. Here is a implementation of Optimizatio Fitness function:

///
/// Evaluates function agains terminals
///
///
///
///
public float Evaluate(IChromosome chromosome, IFunctionSet functionSet)
{
	GANumChromosome ch = chromosome as GANumChromosome;
	if (ch == null)
		return 0;
	else
	{
		//prepare terminals
		var term = Globals.gpterminals.SingleTrainingData;
		for (int i = 0; i < ch.val.Length; i++)
			term[i] = ch.val[i];

		var y = functionSet.Evaluate(_funToOptimize, -1);

		if (double.IsNaN(y) || double.IsInfinity(y))
			y = float.NaN;

		//Save output in to output variable
		term[term.Length - 1] = y;

		if (IsMinimize)
			y *= -1;

		return (float)y;
	}
}

Summary

We have seen that Function optimization module within GPdotNET is powerful optimization tool. It can find pretty close solution for very complex functions regardless of number of independent variables. Optimization module use Genetic Algorithm method with floating point value chromosome representation described in several books about GA. It is fast, simple and can be used in education as well as in solving real problems. More info about GPdotNET can be found at http://bhrnjica.net/gpdotnet.

Posted in .NET, C#, CodeProject, GPdotNET

GPdotNET on .NET 4.0 Client Profile

May 13

Posted by Bahrudin Hrnjica

Finlay, I found some time to convert GPdotNET on Visual Studio 2010 solution, and make beta release with .NET 4.0 Client Profile. The new version is the same as previous, and you no longer need ParallelFX CTP for running GPdotNET.

For running GPdotNETv0.9 you need to install only:

.NET 4.0 Client Profile, which you can download freely at Microsoft web site

Just go to http://gpdotnet.codeplex.com and download the new version.

P.S: The next version of GPdotNET is still in development processes so be patient.

Posted in .NET, GPdotNET

GEALIB – aplikacija za modeliranje i optimizaciju evolucijskim algoritmima

Jul 15

Posted by Bahrudin Hrnjica

Napomena: Juni 2010. Ovaj tekst predstavlja početak razvoja aplikacije koja je poslije prerasla u GPdotNET open source projekat.

Dio rada iz predanog u maju 2008 godine sa postdiplomskog studija, vezano za aplikaciju za modeliranje i optimizaciju evolucijskim algoritmima.

U pripremi Seminarskih radova na postdiplomskom studiju, za obradu eksperimentalnih podataka procesa bušenja kao i eksplozivne obrade, razvijana je .NET biblioteka napisana u programskom jeziku C# za primjenu evolucijskih algoritama u obradnim procesima.

Aplikacija podržava proizvoljan broj nezavisnih ulaznih varijabli X_i i jednu zavisno promjenjivu izlaznu varijablu Y.

clip_image002

Slika 14: Osnovni Izgled GEALIB aplikacije

Učitavanje eksperimentalnih podataka

Početak rada u aplikaciji počinje učitavanjem exsperimentalnih podataka iz datoteke. Aplikacija podržava CSV (Comma Separated Value) extenziju. Učitavanje podataka počinje klikom da dugme „Učitaj…“.

Nakon učitavanja podataka podaci se raspoređuju dijagramski te tabelarno kao na slici 13. U dijagramu su prikazan vrijednosti preko broja pokusa (x osa) i vrijednosti izlazne promjenjive (y- osa).

Podešavanje parametara genetskog programiranja

Nakon učitavanja eksperimentalnih podataka, počinje proces podešavanja GP parametara. Klikom da Tab „Podešavanje“, pojavljuje se dijaloški okvir za podašavanje osnovnih parametara GP.

clip_image004
Slika 15: Parametri GP

Osnovni parametri GP su:

1. Veličina populacije – broj hromosoma u populaciji

2. Maksimalna dubina drveta hromosoma pri inicijalizaciji, ukrštanju i mutaciji

3. Vjerojatnost operacija za ukršatanje, mutaciji i reprodukciju

4. Kriterij odabira – najvažniji parametar GP. Pored višestruke regresije GEALIB podržava i ostale kriterije.

Metode selekcije mogu biti: Elite,Rank, Roulet

5. Metoda inicijalizacije hromosoma: Puna, Rastuća i Miješana.

Izbor Terimana i Funkcija u GP

Nakon definisanja osnovnih parametara GP, slijedi izbor terminala i funkcija u GP. Naredna slika pokazuje dostupne funkcije u GEALIB.

clip_image006
Slika 16: Definisanje Funkcija i Terminala u GEALIB

Pored skupa nezavisno promjenjivih X_i u Terminale spadaju i slučajno generirane konstante koje se u ovom fazi podašavanja GP definišu. Sa slike se može vidjeti da se konstante mogu generisati iz proizvoljnog intervala, kao broj konstanti koji se generiše.

Pokretanje GP

Pokretanje GP započinje definisanje broja evolucija, kroz koje će GP proći dok ne završi proces. Proces se može i prije završiti ako se dobije tačan model. Startanje GP implementirano je na način da se GP pokreće u pozadinskoj niti, dok glavna nit programa ostaje slobodna i korisnik može prelaziti iz tabulatora.

Dodatno je implementirana i opcija nasilnog zaustavljanja GP, koja poslije zaustavljanja izračunava najbolji horomosom koji je izračunat i prikazuje ga.

clip_image008
Slika 17: GEALIB u izračunavanju modela

Tokom izračunavanja modela, desni dijagram prikazuje simulaciju najboljih rješenja dobijenih tokom evolucije. U donjem dijelu je progres kontrola za prikaz statusa GP.

Kada aplikacija postigne tačan rezultat ili maksimalan broj iteracija (evolucija) zaustavlja se GP i prikazje se najbolje dobijeno rješenje.

U tabulatoru „Rezultati“ prikazano je najbolje rješenje kao i tabelarna komparacija eksperimentalnih rezultata i rezulatata dobijenog pomoću GP. U ovoj fazu GP završava svoj proce i počinje proces optimizacije dobijenog modela pomoću Genetskog Algoritma.

Dobijeni model prikazan je u notaciji koji je kompatibilan sa MS Excel, kao i MS Word, tako da se jednostavni kopiranje model može importovati u Excel za daljnju obradu i preračunavanje modela.

clip_image010
Slika 18: Prikaz modela i komaparacija rezulatata

Optimizacija GP modela pomoću GA

Nakon dobijanja GP modela nastupa faza optimizacije modela pomoću GA. Donja slika prikazuje interfejs za optimizaciju. Slično kao i kod GP prolazi se proce definisanja parametara GA i pokretanje GA.

clip_image012
Slika 19: Podešavanje parametrara GA za optimizaciju

Aplikacija je testirana na bezbroj primjera kako analitičkih funkcija tako i eksperimantalnih podataka. Sadrži sve opcije i parametre klasične metode genetskog programiranja i optimizacije genetskim algoritmom koji ima mogućnost reprezentacije pomoću binarnog, cjelobrojnog i realnog broja.

Aplikacija radi sa proizvoljnim brojem nezavisnih varijabli i samo jednom zavisno promjenjivom.

Posted in .NET, C#, Evolucijski Algoritmi

Genetic programming – Genetsko programiranje (GP)

Aug 16

Posted by Bahrudin Hrnjica

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:

Optimizacija kako kontinualnih tako disketnih varijabli
Neprekidnost funkcije (derivabilnost) nije potreban uslov
Simultano traženje rješenja iz širokog skupa mogućih rješenja, inteligentno približavanje tačnom riješenju
Uspješno se primjenjuje kod velikog broja nezavisno promjenjihvih varijabli
Nema tendenciju padanja u lokalne optimume (veliki problem klasičnih metoda)
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_varkoordinata:

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:

Ukrštanje s jednom tačkom prekida
Ukrštanje s dvije tačke prekida
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).

ukrstanjegena
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.

mutacijagena
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:

veličina populacije M,
broj iteracija I
vjerojatnost mutacije v_m
vjerojatnost ukrštanja v_u
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.

gphromosom
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.

ukrstanjegp

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.

mutacijagp

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