Implementácia genetických algoritmov

Obsah práce

1.	Teória genetických algoritmov
2.	Implementácia genetických algoritmov
3.	Testovacia úloha pre genetický algoritmus

Celý program je napísaný v objektovo orientovanom programovacom jazyku c++. Hlavnými celkami, ktoré bolo nutné vyriešiť boli naprogramovanie parsera matematických výrazov a samotného genetického algoritmu, ktorý využíva v ohodnocujúcej funkcii práve tento parser. Program je vyhotovený aj s grafickým užívateľským prostredím GUI, pričom bola snaha aby jeho používanie bolo čo najviac používateľsky prijateľné. Je v ňom zakomponovaných viacero doplnkových funkcii, s pomocou ktorých má užívateľ viacero možností práce s genetickým algoritmom respektíve zadanými dátami a podobne. Patrí sem napríklad možnosť ručného nastavenia niektorých vlastností genetického algoritmu, zadanie intervalu, na ktorom budú zadané dáta aproximované, zobrazenie krivky priebehu genetického algoritmu a podobne.

Parser matematických výrazov

Jednou z najhlavnejších častí programu je, ako bolo už spomenuté, parser matematických výrazov. Keďže z globálneho hľadiska je úlohou programu zo vstupu, ktorým je užívateľom zadaná aproximačná funkcia a namerané dáta pomocou genetického algoritmu nájsť hodnoty konštánt vyskytujúcich sa v zadanej funkcii, je zrejmé že parser matematických výrazov je v tomto programe nevyhnutný. Je to z toho dôvodu, lebo zadaná aproximačná funkcia je načítaná ako reťazec textu a na to aby bol program schopný pracovať s touto funkciou je potrebné ju naparsovať. Tento parser teda slúži na prevedenie zadanej funkcie do takého tvaru, aby bolo možné ju jednoducho vyhodnotiť a následne slúži ako súčasť ohodnocujúcej funkcie genetického algoritmu na výpočet ohodnotenia jednotlivých jedincov v populácii a taktiež ešte pri vykresľovaní dát do grafu. Parser je založený na algoritme shunting-yard a umožňuje tak previesť zadaný matematický výraz na obrátený poľský zápis (postfix), pričom tento postfix prevádza do tvaru so špecifickou štruktúrou. V tomto prípade je postfix uložený v jednorozmernom poli, ktoré je súčasťou zásobníku typu LIFO, pričom položky v tomto poli sú reprezentované ako dátový typ TToken, čo je vlastne trieda špeciálne vytvorená pre tento parser. Štruktúra triedy TToken je nasledovná.

 class TToken{
    public:
	  int type;
	  double (*operFunc)(double,double);  
          double (*func)(double);
	  double operand;
	  TToken();
	  TToken(int, double (*)(double,double), double (*)(double), double);
};

Premenná type určuje o aký typ tokenu sa jedná. Môže to byť buď funkcia, operátor, operand, premenná x alebo konštanta chromozómu. Parser je naprogramovaný tak, že premennej type priraďuje hodnotu z vymenovaného typu, ktorý vyzerá nasledovne.

enum {EMPTY = 0, IS_FNC, IS_OPERATOR, IS_OPERAND, IS_VARX, IS_CHCONST};

Význam jednotlivých identifikátorov v tomto vymenovanom type je zrejmý. Ďalšou premennou v triede TToken je (*operFunc)(double,double), čo je vlastne ukazovateľ na funkciu, ktorá má návratovú hodnotu typu double a tiež má dva parametre typu double. Do tohto ukazovateľa sa ukladá adresa funkcie, ktorá predstavuje funkciu operátora. Patria sem funkcie sčítavania, odčítavania, násobenia, delenia a umocňujúca funkcia. Tieto funkcie sú zadeklarované v pomocnom hlavičkovom súbore. Treťou premennou triedy TToken je (*func)(double, ktorá tiež predstavuje ukazovateľ na funkciu vracajúcu hodnotu typu double, ale má len jeden parameter typu double. Do tohto ukazovateľa sa ukladá adresa funkcie z knižnice math.h, ktorá obsahuje matematické funkcie sin, cos, tan a ďalšie. Poslednou premennou v triede TToken je operand a je typu double. Do tejto premennej sa ukladá hodnota operandu vyskytujúceho sa v zadanej aproximačnej funkcii. Je to teda hociktoré číslo vystupujúce v tejto funkcii. Trieda TToken ešte zahŕňa dva konštruktory, jeden bez parametrov a jeden s parametrami. Deštruktor v takto navrhnutej triede nie je potrebný.

Ako už bolo spomenuté, tento parser matematických výrazov ukladá prvky typu TToken do zásobníka, ktorý má dátové položky uložené v jednorozmernom poli. Zásobník v tomto konkrétnom prípade predstavuje taktiež triedu, ktorá na rozdiel od triedy TToken už obsahuje aj viacero metód. Patria sem metódy slúžiace pre prácu so zásobníkom, ktorými sú pop() slúžiaca na vyberanie prvkov, push() slúžiaca na vkladanie prvkov, empty(), ktorá len zisťuje či je zásobník prázdny. Ďalej trieda zásobníku zahŕňa metódy, ktoré sú už konkrétne navrhnuté pre prácu v hlavnom programe. Patria sem:

int numberOfGenes()

vráti počet génov (hľadaných konštánt) v chromozóme (jedincovi)

double evaluate(double**,const int&,const int&,const double*,const int &)

používa sa v ohodnocujúcej funkcii genetického algoritmu

double getY(const double, double *, const int)

používa sa na výpočet hodnôt určených na vykreslenie v grafe

TToken createToken(TOperator)

pomocná metóda, ktorá vytvorí z načítaného znaku respektíve znakov typ TToken, ktorý sa následne vloží do zásobníka

void toPostfix(AnsiString)

metóda, ktorá užívateľom zadanú aproximačnú funkciu prevedie na špecifický postfix

Riešenie genetického algoritmu

Pri riešení genetického algoritmu použitého v tomto programe bolo potrebné uvažovať s tým, že prakticky všetky jednotlivé časti respektíve operácie algoritmu budú musieť byť navrhnuté tak, aby dokázali efektívne pracovať s reálnymi číslami. Bolo potrebné navrhnúť genetický algoritmus typu RCGA (Real Coded Genetic Algorithm), teda s kódovaním v reálnych hodnotách. A keďže v drvivej väčšine použitých genetických algoritmov sa počíta s binárnou reprezentáciou hodnôt, bolo potrebné vytvoriť špecifické prvky tohto konkrétneho algoritmu. Jedná sa o vygenerovanie počiatočnej populácie, operátory kríženia a mutácie, takisto ohodnocujúcu funkciu, elitizmus a niektoré ďalšie. Na jednej strane použitie reálnych hodnôt dáva viacero možností ako pristúpiť návrhu týchto častí algoritmu, na strane druhej je potreba širšieho experimentovania, tak aby výsledný návrh bol čo najefektívnejší.

Inicializácia počiatočnej generácie

V tomto programe je dané, že populácia jedincov, teda pole možných riešení pozostáva zo 100 prvkov. Na začiatku vykonávania genetického algoritmu je teda potrebné vygenerovať pole pozostávajúce zo 100 riadkov a niekoľkých stĺpcov, pričom počet stĺpcov je daný počtom konštánt, ktoré má za úlohu algoritmus nájsť. Ako bolo spomenuté vyššie v časti 2.1 počet konštánt, ktoré hľadá algoritmus zistí metóda numberOfGenes(). Na inicializáciu počiatočnej generácie je použitá funkcia, ktorá má nasledujúcu podobu:

double **initialize_population(const int &ch_length)
{
  int i,j;

  double **p = new double*[100];     
  for(i=0; i<100; i++)
    p[i] = new double[ch_length + 1];   

  for(i=0;i<100;i++){
    p[i][ch_length] = 0.0;
    for(j=0;j<ch_length;j++)
      p[i][j] = randdouble(-10.0, 10.0);
  }

  return p;
}

Ako vidno, táto funkcia vracia ukazovateľ na dvojrozmerné pole, ktorého prvky sú typu double. V podstate všetko čo robí je to, že alokuje miesto pre pole o veľkosti 100 riadkov a ''ch_length+1'' stĺpcov, pričom ''ch_length'' predstavuje počet hľadaných konštánt a pripočítanie jednotky znamená, že sa vyhradí ešte jedno miesto, do ktorého sa bude ukladať hodnota ohodnotenia daného jedinca. V ďalšom cykle sa pole naplní náhodne generovanými hodnotami z intervalu <nowiki>< -10 ; 10 ></nowiki>. O náhodné generovanie hodnôt sa starajú nasledujúce funkcie, ktoré majú takýto tvar:

<source lang="c">
double randdouble()
{
  return rand()/(double(RAND_MAX)+1);
}
//-------------------------------------------------------------------------
double randdouble(double min, double max)
{
  return min>max?(randdouble()*(min-max)+max):(randdouble()*(max-min)+min);
}

Funkcia randdouble() využíva na generovanie náhodných reálnych hodnôt štandardnú funkciu rand(), ktorá však generuje len celočíselné náhodné hodnoty a preto jej návratovú hodnotu musí upraviť. Výsledkom je, že randdouble() vráti reálne číslo typu double menšie ako 1. A následne funkcia randdouble(double, double) využitím predchádzajúcej funkcie vygeneruje reálne číslo z intervalu < min ; max >.

Ohodnotenie jedincov populácie

Na ohodnocovanie jednotlivých jedincov v populácii sa využíva ako bolo už vyššie naznačené metóda z triedy zásobníka postfixu evaluate, ktorá je volaná z funkcie fitness. Táto funkcia má nasledovný tvar:

void fitness(double **P, const int &ch_length, double **dat, const int &p_min, const int &p_max, StackPostfix *pFix, const int &len)
{
  int i;

  for(i=0; i<len; i++)
  {               
    P[i][ch_length] = pFix->evaluate(dat,p_min,p_max,P[i],ch_length);
  }
}

Telo funkcie fitness je pomerne jednoduché. V podstate cyklus for prechádza celú populáciu po riadkoch a v každej svojej iterácii zapíše na pozíciu P[i][ch_length] hodnotu ohodnotenia daného jedinca. Táto pozícia pritom predstavuje miesto alokované práve pre zapísanie tejto hodnoty, tak ako to bolo spomenuté v časti 2.2.1. Metóda evaluate pracuje na nasledujúcom princípe. Prechádza všetky zadané vstupné body a pre hodnotu x každého bodu vypočíta hodnotu y, pričom ako funkciu na výpočet hodnoty y použije užívateľom zadanú aproximačnú funkciu, do ktorej dosadí hodnoty konštánt konkrétneho jedinca aktuálnej populácie. Následne po vypočítaní hodnoty y vypočíta vzdialenosť medzi touto hodnotou a hodnotou y zo zadaných dát prislúchajúcou aktuálnej hodnote x. Pričom táto hodnota predstavuje kladnú vzdialenosť. Takto teda prejde cez všetky body, pričom jednotlivé vzdialenosti spočítava a na konci, po prejdení všetkých zadaných bodov funkcia vráti hodnotu posčítavaných vzdialeností, ktorá predstavuje ohodnotenie jedinca. Z toho vyplýva, že čím väčšia bude hodnota ohodnotenia daného jedinca, tým horší tento jedinec bude.

Výber jedincov

Slúži na určenie jedincov, ktorí budú slúžiť ako rodičovské chromozómy pri vytváraní novej populácie. V teórii genetických algoritmov v časti 1.3.4 je opísaných niekoľko prístupov, podľa ktorých je možné navrhnúť výber jedincov z populácie. V tomto prípade je použitý takzvaný turnajový výber, kedy sa z populácie náhodne vyberú dva jedince a stretnú sa v pomyselnom turnaji, v ktorom vyhrá ten s vyšším ohodnotením stane sa z neho rodičovský jedinec určený k reprodukcii. Presne takto je tento princíp spracovaný vo funkcii tournamentSelection. Prepis funkcie je nasledovný:

int tournamentSelection(double **P, const int &ch_length)
{
  int winner, first, second;
  first = rand()%100;
  second = rand()%100;
  winner = P[first][ch_length] < P[second][ch_length] ? first : second;   
  return winner;
}

Tým sa ale výber jedincov nekončí. Hlavnou funkciou určenou k výberu jedincov je funkcia selection. Jej prepis je nasledovný:

void selection(double **P,double **Q,const int &ch_length,const int &Q_size)
{
  int selected1, selected2;

  selected1 = tournamentSelection(P,ch_length);
  selected2 = tournamentSelection(P,ch_length);
  for(int i=0; i<ch_length; i++){
    Q[Q_size][i] = P[selected1][i];
    Q[Q_size + 1][i] = P[selected2][i];
  }
}

V tele tejto funkcie je dva krát zavolaná funkcia tournamentSelection, pomocou ktorej sú vyberané z populácie dva rodičovské jedince. Následne sa tieto prekopírujú do novovznikajúcej populácie Q, kde na ne budú aplikované operátory kríženia a mutácie.

Kríženie

Na operátor kríženia bol implementovaný princíp uniformného kríženia, ktorý je opísaný aj v časti 1.3.5.1. Keďže hodnoty konštánt, ktoré tvoria gény jedincov v populácii sú reprezentované reálnymi hodnotami, bolo viacero možností ako navrhnúť operáciu kríženia. V tomto programe je nasadený princíp rozširujúci, ktorý spočíva v tom, že rozdiel medzi hodnotami rodičov sa pripočíta k väčšiemu z nich a odpočíta od menšieho. Tak je to možné vidieť aj v prepise funkcie crossover slúžiacej práve na kríženie rodičovských jedincov:

void crossover(double **Q, const int &ch_length, const int &Q_size)
{
  double tmp;
  for(int i=0; i<ch_length; i++)       
    if(randdouble(0.0,1.0)<0.5)
    {
      tmp = fabs(Q[Q_size][i]-Q[Q_size + 1][i]);
	if(Q[Q_size][i]>Q[Q_size+1][i])
        {
	  Q[Q_size][i] -= tmp;
	  Q[Q_size + 1][i] += tmp;
	}
	else
         {
	  Q[Q_size][i] += tmp;
	  Q[Q_size + 1][i] -= tmp;
         }
    }
}

Mutácia

Pri navrhovaní a implementácii operátora mutácie taktiež vystupovalo viacero princípov, ktoré mohli byť zapracované do funkcie slúžiacej k mutácii rodičovských jedincov. V prípade tohto programu bol implementovaný princíp náhodnej výmeny konkrétneho génu čiže konštanty. Tak ako v inicializácii počiatočnej populácie, kedy sa hodnoty konštánt generovali z intervalu < -10 ; 10 >, tak aj pri náhodnej výmene konštanty z dôvodu mutácie sa táto hodnota generovala z intervalu < -10 ; 10 >. Vo funkcii mutácie vystupuje premenná mut_prb, ktorá určuje pravdepodobnosť mutácie. Táto premenná by tam ani nemusela byť, mohla by tam byť konkrétna hodnota, ale program umožňuje nastavenie niektorých vlastností genetického algoritmu užívateľom a preto je pravdepodobnosť mutácie riešená takýmto spôsobom. Prepis funkcie mutácie je nasledovný:

void mutation(double **Q, const int &ch_length, const int &Q_size, const double &mut_prb)
{
  int i;
  for(i=0; i<ch_length; i++)
    if(randdouble(0.0,1.0)<mut_prb)    
	Q[Q_size][i] = randdouble(-10.0, 10.0);

  for(i=0; i<ch_length; i++)
    if(randdouble(0.0,1.0)<mut_prb)
	Q[Q_size + 1][i] = randdouble(-10.0, 10.0);
}

Elitizmus

Použitie elitizmu v genetickom algoritme má veľmi veľké výhody. Spôsobuje to, že genetický algoritmus dokáže rýchlejšie skonvergovať populáciu a taktiež to, že hodnota najlepšieho jedinca nebude kolísať, ale sa veľmi rýchlo ustáli. V prípade tohto programu je štandardne dané, že genetický algoritmus bude zachovávať 10 jedincov v každej generácii. Je ale možné v nastaveniach tento počet zmeniť, pričom tento počet udáva premenná el_cnt. Taktiež je možné nastaviť či sa vlastne elitizmus bude alebo nebude používať pri hľadaní riešenia. V tomto prípade vyzerá prepis funkcie elitizmu nasledovne:

void elitism(double **P,double **Q, const int &ch_length, const int &el_cnt)
{
  int best = 0;

  for(int i=0; i<el_cnt; i++){
    best = findBest(P,ch_length,100);
 for(int j=0; j<ch_length+1; j++)
   Q[i][j] = P[best][j];
 P[best][ch_length] = 10000000.0;
  }
}