Osnove rada

3.1. Jedinka

Jedinka u računalu može biti predstavljena na više načine : kao niz bitova (eoBit) , niz cijelih brojeva (eoInt) ili niz realnih brojeva (eoReal).
EO framework pruža podršku za sve tri vrste jedinki .
Prilikom definiranja jedinke potrebno je definirati i tip podatka koji predstavlja njezinu dobrotu.

primjeri:

eoBit< double > jedinka ;   // definiramo jedinku koja se sastoji od niza bitova i ima vrijednost dobrote tipa double

eoInt< int > jedinka;    // jedinka tipa int i dobrote tipa int

eoReal< double > jedinka;   // jedinka tipa real (float) i dobrote double

Zbog jednostavnosti programiranja biti će uputno definirati novi tip podatka npr.

typedef eoBit< double > tip_jedinke;

Važno je za napomenut da su sve tri klase naslijedile svojstva iz klase vector iz standardne biblioteke predložaka .

eoBit , eoInt , eoReal

3.2. Populacija

Da bi se objedinile jedinke u populaciju definira se populacija :

eoPop< tip_jedinke > ime_populacije;

Ovo je zapravo klasa koja će u vektoru čuvati sve jedinke, no uz to sadrži veliki broj metoda koje mogu dati korisne informacije o populaciji (npr. i-ta najbolja jedinka).

Primjeri nekoliko operacija nad populacijom :

ime_populacije.push_back(jedinka); // dodajemo jedinku u populaciju

ime_populacije.sort( ); // sortiramo populaciju

cout<<ime_populacije; // ispišemo cijelu populaciju

eoPop

3.3. Funkcija dobrote

Tijekom traženja rješenja potrebno je odrediti koliko je dobro već postojeće rješenje (jedinka). Računanje dobrote ovisi o problemu koji se rješava. Najčešće je to neka kraća funkcija koja kao parametar ima jedinku , a vraća dobrotu te jedinke ( napomena: vraća onaj tip podatka koji je definiran kao dobrota u deklaraciji jedinke).

npr. funkcija bi mogla izgledati ovako

double dobrota( const jedinka & x) {
. . .

// ovdje je nešto radimo

. . .
return varijabla;
}

Kako EO framework ne radi direktno s funkcijama nego s funkcijskim objektima funkciju dobrote mora se pretvoriti (ubaciti) u funkcijski objekt koji će se kasnije koristiti

eoEvalFuncPtr< tip_jedinke > ime_funkcijskog_objekta ( pokazivač_na_funkciju);

eoEvalFuncPtr

3.4. Generiranje random populacije

Da bi se generirala početna populacija potrebno je stvoriti jedinke. Kod populacije se zahtijeva određena slučajna razdioba. Za to framework nudi random number generator ( rng ) objekt koji je već ugrađen u framework . Tako ako se želi napuniti neku jedinku tipa eoBit s 1 i 0 gdje je vjerojatnost pojave 1 ili 0 50% koristit će se rng.flip( ) metodu pa bi sljedeći programski odsječak napravio upravo željeno :

eoBit< double > jedinka ; // definiramo dobrotu kao double tip , iako ju ovdje nećemo koristiti

rng.reseed( time (NULL) ) // definiramo seed za generator , koristeći time( ) funkciju dobivamo da prilikom svakog pokretanja dobijemo // durgačji niz brojeva

for (int i=0; i<VELICINA_JEDINKE; i++) {

jedinka.push_back( rng.flip ( ) ) // napuni jedinku s 1 i 0

}

Deklaracije nekih razdiobi brojeva :

flip

bool eoRng::flip ( double vjerojatnost=0.5 )

Ovdje vjerojatnost predstavlja vjerojatnost pojavljivanja 1 i ako se ne navede pretpostavljena je 0.5.

uniform

double eoRng::uniform (double m = 1.0)

Uniformna razdioba ( vjerojatnost pojavljivanja bilo kojeg broja je ista ) koja vraća brojeve iz intervala [0,m>. Ako ne definiramo m pretpostavlja se m = 1.0.

Postoje još neke razdiobe koje nisu ovdje navedene , ali ih se može pronaći na donjem linku .

No to nije jedini način generiranje random populacije. Framework podržava objekte koji mogu stvoriti čitavu populaciju.

Programski odsječak koji će generirati jednu random populaciju :

typedef eoReal < double > jedinka; //definiramo tip podataka

//...

rng.reseed(time(NULL));

eoEvalFuncPtr< jedinka > eval( funkcija_dobrote );

eoUniformGenerator< double > generator(-10.0,10.0); //definiramo generator koji će generirati uniformno brojeve između -10 i 10

eoInitFixedLength< jedinka > random (5, generator); // određujemo veličinu jedinki u našem slučaju 5

eoPop< jedinka > pop(10,random); // stvaramo populaciju veličine 10

apply < jedinka >(eval,pop); // računamo dobrote pojedinih jedinki

eoRng , eoRndGenerator , eoNegExpGenerator , eoNormalGenerator , eoUniformGenerator

3.5. Unarni operatori (mutacija)

Jednostavna mutacija
Parametar koji određuje tu mutaciju je vjerojatnost promjene određenog bita (možda bi bolje bilo rečeno da se mijenja svaki x-ti bit ) .

Definiranje jednostavne mutacije nad bitovima :

eoBitMutation< tip_jedinke > mutacija( vjerojatnost ) // definiramo mutaciju s parametrom vjerojatnost

konstruktor klase

template < class Chrom >
eoBitMutation < Chrom >::eoBitMutation(const double & _rate=0.01, bool _normalize = false )

Kao što je vidljivo u konstruktoru je moguće definirati:
_rate - vjerojatnost promjene bita (0.01 default) npr. 0.01 znači da se će se promijeniti svaki 100-ti
_normalize - true ili false - ako je true tada će _rate biti promijenjen u -rate/jedinka.size() inače ostaje _rate

Također je definiran operator () pa je moguće obaviti mutaciju nad jednom jedinkom

typedef eoBit< double > jedinka ; // definiramo tip podatka jedinka

//.....

jedinka v; // definiramo novu jedinku v

//.....

eoBitMutation< jedinka > mutacija(0.1) // definiramo mutaciju

mutacija(v); // primjenimo mutaciju vraća vrijednost true ako se je nešto promijenilo inače false

Uniformna mutacija
Uniformna mutacija radi mutaciju nad jedinkom u granicama [jedinka(i) - epsilon, jedinka(i) + epsilon]

konstruktor

template < class EOT >
eoUniformMutation< EOT >::eoUniformMutation(const double &_epsilon, const double &_p_change=1.0)

_epsilon - zadane granice
_p_change - vjerojatnost promjene (default =1.0)

Normalna mutacija

konstruktor

template < class EOT >
eoNormalMutation< EOT >::eoNormalMutation(const double &_sigma, const double &_p_change=1.0)

_sigma - zadane granice za uniformnu mutaciju
_p_change - vjerojatnost promjene (default =1.0)

eoBitMutation , eoUniformMutation , eoNormalMutation

3.6. Binarni operatori (križanje)

Jednostavno križanje jednog bita

eo1PtBitXover< tip_jedinke > krizanje;

Križanje N bitova
Omogućuje da se dvije jedinke križaju na dva ili više mjesta

eoNPtsBitXover< tip_jedinke > krizanje(4); // definiramo križanje koje će križati dvije jedinke na 4 mjesta

Uniformno križanje

eoUBitXover< tip_jedinke > krizanje

Segmentno križanje

eoSegmentCrossover< tip_jedinke > krizanje;

Konstruktor

template < class EOT >
eoSegmentCrossover < EOT >::eoSegmentCrossOver (const double & _aplha =0.0)

-alpha - granice križanja

eoNPtsBitXover , eoUBitXover , eoSegmentCrossover

3.7. Selekcija

Jednostavna selekcija ( roulette wheel )

eoProportionalSelect< tip_jedinke > selekcija;

Turinirska selekcija
Definira se turnirska selekcija gdje je velicina veličina turnirske selekcije.

eoDetTournamentSelect< tip_jedinke > selekcija(velicina);

Napomena : velicina >= 2

Stohastička binarna turnirska selekcija

eoStochTournamentSelect< tip_jedinke > selekcija(postotak) // postotak=[0.5,1]

Napomena : 0.5<= postotak <= 1

Random selekcija

eoRandomSelect < tip_jedinke > selekcija;

Jasno je da je ovo najlošija selekcija koja selektira random jedinke .

eoProportionalSelect , eoDetTournamentSelect , eoStochTournamentSelect , eoRandomSelect

3.8. Trajanje evolucije

Da bi se definiralo koliko dugo će se izvršavati evolucijske operacije može se definirati maksimalan broj generacija prije završetka algoritma

eoGenContinue < tip_jedinke > trajanje ( MAX_BROJ_GENERACIJA)

eoGenContinue

3.9. Genetski algoritmi

SGA (Simple Genetic Algoritm)

Jednostavni genetski algoritam predložen od Hollanda :

eoSGA< tip_jedinke > algoritam (selekcija, krizanje, CROSS_RATE, mutacija, MUT_RATE, ime_funkcijskog_objekta,trajanje) ;

algoritam (populacija); // izvršavanje algoritma nad populacijom

eoSGA

3.10. Programski primjer

Početni primjer koji demonstrira do sada objašnjeni dio : link

EO radno okruženje

3. EO radno okruženje