Analyzátor nameraných dát z meracích prístrojov v priemysle

	Trenčianska Univerzita Alexandra Dubčeka v Trenčíne Fakulta Mechatroniky
	Analyzátor nameraných dát z meracích prístrojov v priemysle zadanie práce Ročníková práca

Autor:	Bc. Pavel Hromada
Pedagogický vedúci:	Ing. Michal Štepanovský, PhD
Študijný odbor:	Mechatronika
Akademický rok	2009/2010

Obsah práce

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

Abstrakt Práca sa zaoberá genetickým algoritmom, opisuje princíp tohto algoritmu, jeho jednotlivé prvky a na ilustratívnych príkladoch ukazuje funkčnosť tohto algoritmu. Úlohou tohto projektu bolo vytvoriť program v ľubovoľnom programovacom jazyku, ktorý nájde aproximujúcu funkciu k nameraným dátam. Tento program pritom využíva genetický algoritmus, presnejšie genetický algoritmus s reálne kódovanými chromozómami.

Abstract This thesis deals with Genetic Algorithm, it describes the principle and individual parts of this algorithm and by using simple examples shows functionality of this algorithm. The task of this project was to develop a program in any programming language, which finds the approximating function to the measured data. This programm is also using the Genetic Algorithm, concretely Real Coded Genetic Algorithm.

Úvod

V súčasnej dobe patria najrôznejšie heuristické metódy založené na darwinowskom princípe evolúcie medzi veľmi populárne a často používané optimalizačné techniky. Každoročne sú organizované desiatky odborných konferencii zaoberajúcich sa problematikou evolučných algoritmov a ich aplikáciou, vychádzajú stovky publikácii a niektorý autori dokonca už začínajú varovať pred prílišnou popularizáciou evolučných techník, ktoré síce na jednej strane priťahujú nových užívateľov, ale na druhej strane nutne vedú k nerealistickým očakávaniam. Pri porovnaní genetického algoritmu s tradičnými optimalizačnými metódami je možné ľahko nájsť niekoľko výrazných odlišností, ktoré významným spôsobom prispievajú k univerzálnosti a robustnosti genetického algoritmu. Prvým zrejmým rozdielom je využitie celej populácie riešení z prehľadávaného priestoru namiesto jediného počiatočného riešenia, ako je to u väčšiny klasických algoritmov. Táto skutočnosť podstatne ovplyvňuje celkovú robustnosť algoritmu a súčasne priamo navádza na paralelizáciu vlastného výpočtu. Genetický algoritmus je slepý algoritmus, pretože okrem ohodnotenia jedincov v populácii nevyužíva žiadnu apriórnu informáciu či vlastnosť, ktorá sa viaže ku konkrétnemu problému alebo prehľadávanému priestoru. To ho na jednej strane robí veľmi všeobecným a univerzálnym, na druhej strane je zrejmé, že práve toto ignorovanie špecifických vlastností konkrétneho problému bude znamenať, že algoritmus bude len ťažko schopný konkurovať špeciálnym algoritmom, ktoré boli navrhnuté priamo pre daný problém.[3] Evolučným algoritmom, konkrétne genetickým algoritmom sa zaoberá aj tento ročníkový projekt. Výsledkom tohto projektu by mal byť počítačový program, ktorý aplikovaním genetického algoritmu nájde vhodnú aproximujúcu funkciu k vopred daným nameraným dátam. Nutné je podotknúť, že túto aproximujúcu funkciu zadá užívateľ programu ako vstup pre algoritmus. Úlohou genetického algoritmu v tomto programe potom teda bude nájsť konštanty vyskytujúce sa v zadanej funkcii tak, aby táto funkcia čo najlepšie aproximovala namerané dáta.

Teória genetických algoritmov

História

Problematika genetických algoritmov respektíve genetické algoritmy ako také sa ešte aj v súčasnosti považujú za mladú disciplínu, ktorá je stále predmetom skúmania a štúdia mnohých profesorov. Sú súčasťou evolučných výpočtov, ktoré patria do prudko sa rozvíjajúcej oblasti umelej inteligencie. Myšlienka evolučných výpočtov bola prvý raz zavedená v roku 1970 v práci I. Rechenberga s názvom Evolučné stratégie (originál Evolutionsstrategie). Táto myšlienka evolučných výpočtov bola ďalej rozvíjaná inými výskumníkmi. Zrod genetických algoritmov sa pripisuje Johnovi Hollandovi, ktorý v roku 1975 vydal knihu Prispôsobovanie sa v prírodných a umelých systémoch (originál Adaption in Natural and Artifiacial Systems). V roku 1992 použil John Koza genetický algoritmus pri vývoji ďalšej oblasti informatiky nazvanej genetické programovanie.

Biologické pozadie genetických algoritmov

Všetky živé organizmy v prírode sa skladajú z buniek. Sú to základné stavebné častice, ktoré sú v jednotlivých organizmoch zložené vždy z rovnakej série chromozómov, pričom sú to určité reťazce DNA a slúžia ako model pre celý organizmus. Ďalej ešte každý chromozóm pozostáva z génov, ktoré predstavujú bloky DNA. Každý gén v sebe nesie určitú informáciu, nazývanú alela. V zásade je možné povedať, že v sebe kóduje konkrétnu črtu. V živých organizmoch touto črtou môže byť napríklad farba očí. Každý gén má v chromozóme svoju vlastnú pozíciu. Táto pozícia sa niekedy označuje ako geometrické miesto génu. Pri ďalšom popise živých organizmov sa stretneme aj s pojmom genóm a genotyp. Genóm je kompletný súbor genetického materiálu (všetky chromozómy) a genotyp predstavuje genetickú informáciu určitej populácie jedincov. [1] V nasledujúcich kapitolách uvidíme, že podobnosť genetických algoritmov s vývojom v živej prírode je veľmi podobný.

Pri vývoji genetických algoritmov sa vychádzalo s Darwinovej teórie evolúcie, ktorá sa zakladá na téze prirodzeného výberu, podľa ktorej prežívajú len najlepšie prispôsobený jedinci populácie. Reprodukciou dvoch silných jedincov dostávame potomkov, ktorý s vysokou pravdepodobnosťou budú dobre prispôsobený k úspešnému prežitiu. Pri podrobnej analýze (hlavne matematickej) sa ukazuje, že samotné pôsobenie reprodukcie nie je dostatočne efektívne na vznik dobre prispôsobených jedincov s novými vlastnosťami, ktoré významne uľahčujú prežitie. Do evolúcie živej hmoty je nutné zapojiť aj tzv. mutácie. Tieto náhodným spôsobom ovplyvňujú (kladne alebo záporne) genetický materiál populácie jedincov. Biologická evolúcia je progresívna zmena obsahu genetickej informácie populácie v priebehu mnohých generácii. V genetických algoritmoch hrá kľúčovú úlohu sila genotypu. V biológii je sila definovaná ako relatívna schopnosť prežitia a reprodukcie genotypu v danom prostredí. Podobe sa chápe aj v umelom živote, je to kladné číslo priradené genetickej informácii reprezentujúcej organizmus (obvykle vyjadrenej pomocou bitového reťazca), ktoré reprezentuje jeho relatívnu úspešnosť plniť si v danom prostredí svoje úlohy (napr. zber potravy) a vstupovať do reprodukcie, t.j. tvoriť nové organizmy.

Biologická evolúcia obsahuje dve základné zložky:

• Prirodzený výber (Darwin) – organizmy s väčšou silou produkujú viac potomkov, ktorí sa dožijú dospelosti a ďalej sa reprodukujú, ako organizmy s malou silou.

• Genetický drift – náhodné udalosti (napr. mutácia alebo náhodná smrť organizmu s veľkou silou prv ako stihol vyprodukovať potomkov) môžu podstatne ovplyvniť evolučné procesy v malých populáciách. [2]

Genetický algoritmus

Ako som už spomenul, genetický algoritmus je založený na myšlienke Darwinovského princípu evolúcie. Hľadanie optimálneho riešenia (respektíve dostatočne vyhovujúceho) prebieha formou súťaže v rámci populácie postupne sa vyvíjajúcich riešení. K tomu, aby bolo možné posúdiť, ktorí členovia populácie majú väčšiu šancu podieľať sa na ďalšom vývoji hľadaného riešenia, musí byť táto schopnosť jedincov kvantifikovaná. V tejto súvislosti sa hovorí o ohodnocovaní, miere kvality, vhodnosti, sile, respektíve reprodukčnej schopnosti jedinca (často sa používa anglický výraz fitness). Jedinci s lepším ohodnotením (vyššou hodnotou fitness) majú prirodzene väčšiu šancu prežiť dlhšie a podieľať sa na vytváraní nasledujúcej generácie. Použitím rozmanitých techník kríženia, mutácie a reprodukcie potom vznikne nová generácia jedincov, v ktorej sú vlastnosti týchto jedincov čiastočne zdedené po rodičoch a čiastočne ovplyvnené náhodnými mutáciami v procese reprodukcie. Ak sa opakuje tento evolučný cyklus niekoľkokrát, obvykle po desiatkach až stovkách opakovaní vznikne populácia s jedincami, ktorí majú vysoké ohodnotenie a môžu predstavovať dostatočné (možno aj optimálne) riešenie daného problému. Pretože tento evolučný proces v sebe zahrňuje značný diel náhodnosti, je zrejmé, že každý beh daného algoritmu sa bude obvíjať odlišným spôsobom. [3]

Tento princíp by sa tiež dal popísať aj trochu inými slovami a o niečo konkrétnejšie. Genetický algoritmus je v podstate postupná tvorba generácii rôznych riešení daného problému. Pri riešení sa uchováva tzv. populácia, ktorej každý jedinec predstavuje jedno riešenie daného problému (konkrétny chromozóm). Tak ako populácia prebieha evolúciou, riešenia sa zlepšujú. Tradične býva riešenie reprezentované binárnymi číslami, reťazcom núl a jednotiek, ale využívajú sa aj iné typy reprezentácie. Typicky je na začiatku procesu genetického algoritmu populácia zložená z náhodných členov. V prechode do novej generácie je každý jedinec ohodnotený fitness funkciou, čo vlastne vyjadruje kvalitu riešenia reprezentovanú týmto jedincom. A následne sú podľa tejto kvality stochasticky vyberané jedince, ktoré sú modifikované (krížením a mutáciou), čím vznikne nová populácia. Tento postup sa opakuje iteratívne, čím sa kvalita populácie postupne vylepšuje. Algoritmus sa obvykle zastaví pri dosiahnutí dostačujúcej kvality riešenia, prípadne po dosiahnutí maximálneho počtu iterácii. [4]

Princíp tohto algoritmu by sa teda dal zapísať nasledovnými krokmi:

1. [inicializácia] Nastav počítadlo na N = 0 a vytvor nultú populáciu jedincov P(N)
2. Spočítaj silu (fitness) jedincov z populácie P(N)
3. [začiatok cyklu] Selekciou respektíve určitou výberovou metódou vyber z populácie niekoľko zdatných jedincov
4. Z týchto jedincov pomocou genetických operátorov vytvor nové, čím vznikne nová generácia
   • Reprodukcia
   • Kríženie
   • Mutácia
5. Spočítaj silu jedincov v novovytvorenej populácii
6. [koniec cyklu] Ak nie je splnená ukončovacia podmienka choď na bod 3
7. [koniec algoritmu] Najzdatnejší jedinec je riešením

Následne je už jednoduché vytvoriť všeobecný pseudo kód genetického algoritmu, ktorý môže vyzerať nasledovne:

N = 0;                      // vynulovanie pocitadla
pociatocna_populacia( P );  // inicializacia pociatocnej populacie
ohodnot( P );               // ohodnotenie jedincov v pociatocnej populacii
while (ukoncovacia_podmienka)
{
    N = N + 1;                      // inkrementuj pocitadlo o 1
    while(Q < P){                   // kým nie je Q rovnako velke ako P
      (x1,x2) = select_from(P);     // vyber 2 zdatne chromozomy x1,x2   P
      (x1‘,x2‘) = crossover( x1, x2 );       // krizenie chromozomov
      (x1‘,x2‘) = mutate( x1‘, x2‘ );          // mutacia chromozomov
      Q = Q  (x1‘,x2‘); //pridanie novych chromozomov do docasnej populacie   
    }
    P = Q;              // nahradenie starej generacie novou	     
    ohodnot( P );       // ohodnotenie jedincov v novej populacii
}

Vonkajší while cyklus sa bude opakovať tak dlho, až kým nebude splnená ukončovacia podmienka. Touto podmienkou pritom môže byť dosiahnutie maximálneho počtu iterácii teda maximálneho počtu vytvorených populácii alebo priblíženiu sa k požadovanej hodnote, ktorú dosahujú chromozómy svojou hodnotou fitness. Vnútorný cyklus while slúži na vytvorenie novej populácie. Opakuje sa dovtedy, kým veľkosť novovytvorenej dočasnej populácie Q a predošlej populácie P nie je rovnaká. V tele tohto cyklu sa vykonávajú operácie genetického algoritmu teda výber zdatných chromozómov, kríženie a mutácia. Následne po týchto operáciách sa novovytvorené chromozómy pridajú do dočasnej populácie Q. Keď tento vnútorný cyklus skončí, pôvodná populácia P bude nahradená novou Q a následne sa ohodnotia jej chromozómy.

Obr. 1.1: Vývojový diagram genetického algoritmu

Ilustratívny príklad princípu genetického algoritmu

V tejto kapitole rozoberiem princíp genetického algoritmu, pričom nebudem rozoberať konkrétny prípad z praxe, ale v niekoľkých krokoch ilustratívne ukážem ako v genetickom algoritme pôsobia genetické operátory, selekcia a ako sa zmení ohodnotenie jednotlivých chromozómov populácie po jednej iterácii takéhoto algoritmu. Pre jednoduchšie pochopenie bude zvolené binárne kódovanie chromozómov.

Vytvorenie počiatočnej populácie:

V tomto prípade bude teda počiatočnú populáciu tvoriť množina náhodne vygenerovaných binárnych reťazcov danej dĺžky. Predpokladajme, že náhodne vygenerovaná populácia sa skladá zo štyroch jedincov, pričom každý z nich je reprezentovaný chromozómom dĺžky 8 nasledovne:

Tab. 1.1: Ukážka náhodne vygenerovanej populácie

Jedinec č.	Chromozóm
1	(1,0,1,0,1,1,0,0)
2	(0,1,1,1,1,0,1,1)
3	(0,0,0,1,0,0,0,1)
4	(1,1,0,0,1,1,0,0)

Ohodnotenie jedincov:

Je zrejmé, že ohodnocujúca funkcia je vždy zviazaná s konkrétnym problémom, pretože cieľom je nájsť takého jedinca respektíve jedincov, ktoré majú z hľadiska príslušného problému čo možno najvhodnejšie vlastnosti. V tomto ilustratívnom príklade bude ohodnocujúca funkcia predstavovať súčet všetkých jednotkových bitov v chromozóme. Priemerné ohodnotenie populácie bude mať hodnotu 4.

Tab. 1.2: Ukážka ohodnotenia jedincov populácie

Jedinec č.	Chromozóm	Ohodnotenie (fi)	% z celku	Kumulovane
1	(1,0,1,0,1,1,0,0)	4	25,0 %	0,250
2	(0,1,1,1,1,0,1,1)	6	37,5 %	0,250
1	(0,0,0,1,0,0,0,1)	2	12,5 %	0,750
4	(1,1,0,0,1,1,0,0)	4	25,0 %	1,000

Výber dvojíc určených k reprodukcii:

Nasledujúci výber jedincov určených k reprodukcii by mal byť imitáciou prirodzeného výberu, ako to popisuje Darwin vo svojej teórii o pôvode druhov. To znamená, že zdatnejší jedinci majú väčšiu šancu prežiť a majú tiež väčšiu pravdepodobnosť byť vybrané na reprodukciu. Selekčné mechanizmy (postupy výberu jedincov) sú popísané v kapitole 1.3.4. V tomto príklade boli k reprodukcii vybrané jedince číslo 2, 3 a 4. Vidno, že najlepšie ohodnotený jedinec bol vybraný dva krát (číslo 2).

Tab. 1.3: Ukážka dvojíc vybraných pre účely reprodukcie

	Jedinec č.	Chromozóm
1.pár	2	(0,1,1,1,1,0,1,1)
	4	(1,1,0,0,1,1,0,0)
2.pár	3	(0,0,0,1,0,0,0,1)
	2	(0,1,1,1,1,0,1,1)

Kríženie:

Princípov kríženia existuje v genetických algoritmoch niekoľko. Podrobnejšie sú rozobrané v kapitole 1.3.5.1. Pre účely tohto príkladu postačí zrejme najjednoduchší druh kríženia a to jednobodové kríženie. Zvolíme teda náhodne jeden gén v chromozóme a od tohto génu vymeníme ostatné časti chromozómu medzi obidvomi rodičmi. Tak vzniknú dvaja nový jedinci, z ktorých každý má časť genetickej výbavy po prvom a časť po druhom z rodičov. V tomto príklade bol vybraný druhý gén ako bod kríženia pre prvý rodičovský pár a štvrtý gén pre druhý pár. Výsledok je potom nasledovný:

Tab. 1.4: Ukážka kríženia rodičovských chromozómov

	Chromozóm		Nový chromozóm
1.pár	(0,1, | 1,1,1,0,1,1)	->	(0,1, | 0,0,1,1,0,0)
	(1,1, | 0,0,1,1,0,0)	->	(1,1, | 1,1,1,0,1,1)
2.pár	(0,0,0,1, | 0,0,0,1)	->	(0,0,0,1, | 1,0,1,1)
	(0,1,1,1, | 1,0,1,1)	->	(0,1,1,1, | 0,0,0,1)

Mutácia:

Mutácia väčšinou veľmi jednoduchým spôsobom a s relatívne malou pravdepodobnosťou mení náhodne hodnotu jednotlivých génov. V prípade binárneho kódovania to znamená zmeniť hodnotu génu z nuly na jednotku respektíve naopak. V tomto príklade môže populácia po mutácii vyzerať nasledovne:

Tab. 1.5: Ukážka mutácie chromozómov vzniknutých krížením

header 1		header 3
(0,1,0,0,1,1,0,0)	->	(0,1,0,1,1,1,0,0)
(1,1,1,1,1,0,1,1)	->	(1,1,1,1,1,0,1,1)
(0,0,0,1, 1,0,1,1)	->	(0,0,0,1, 1,0,1,1)
(0,1,1,1, 0,0,0,1)	->	(0,1,1,1, 0,0,0,0)

Vytvorenie novej populácie:

Ďalším krokom je vytvorenie novej populácie z pôvodnej populácie a množiny potomkov. Ak použijeme najjednoduchšiu tzv. generačnú stratégiu vytvárania novej populácie, ktorá je založená na predpoklade vymretia pôvodnej populácie, stará populácia P(0) stratí už akýkoľvek význam a bude z ďalšieho uvažovania vylúčená (úplne vymrie). Práve vytvorené potomstvo pôvodnej populácie sa stáva novou populáciou P(1), ktorá má v tomto príklade nasledujúcu podobu:

Tab. 1.6: Ukážka zmeny kvality (ohodnotenia) novej populácie

Jedinec č.	Chromozóm	Ohodnotenie
5	(0,1,0,1,1,1,0,0)	4
6	(1,1,1,1,1,0,1,1)	7
7	(0,0,0,1, 1,0,1,1)	4
8	(0,1,1,1, 0,0,0,0)	3

Tým bol dokončený prechod od jednej populácie k druhej a celý cyklus sa bude opakovať tak dlho, pokým nebude splnená ukončovacia podmienka. V novovytvorenej populácii možno vidieť, že ohodnotenie jednotlivých jedincov sa zlepšilo a vzrástlo tiež priemerné ohodnotenie populácie na hodnotu 4,5. [3]

Kódovanie chromozómov

Keď začínate riešiť určitý problém s genetickými algoritmami je potrebné správne sa rozhodnúť aký spôsob kódovania zvolíte. V dobe vzniku genetických algoritmov bolo ako spôsob kódovania teda reprezentácie jednotlivých génov v chromozóme určené binárne kódovanie. Chromozóm bol tvorený reťazcom núl a jednotiek. Takéto kódovanie je ešte aj v súčasnosti najpoužívanejším typom a dôvod prečo je to tak spočíva v tom, že mnohí programátori, ktorí používajú genetické algoritmy, vychádzajú z prác, ktoré vznikli na počiatkoch genetických algoritmov, v ktorých bolo používané práve toto kódovanie. Až postupom času boli vymyslené ďalšie spôsoby kódovania, pomocou ktorých je možné reprezentovať hodnoty génov v chromozómoch. Patria sem kódovanie reálnymi hodnotami, permutačné kódovanie a kódovanie pomocou stromov, pričom stromová reprezentácia chromozómu sa používa v oblasti genetického programovania, ktorú popísal J.R. Koza vo svojej práci.

Binárne kódovanie:

Ako som už spomenul, binárne kódovanie je najrozšírenejším typom reprezentácie chromozómov, kde daný chromozóm pozostáva z reťazca núl a jednotiek. V nasledujúcom texte rozoberiem konkrétny prípad kódovania reálnych hodnôt do binárnych chromozómov. Predpokladajme, že chceme použiť genetický algoritmus na nájdenie maxima funkcie dvoch premenných f(x,y) na množine D={(x,y) | x,y [math]\in \lt -100,100\gt [/math].K reprezentácii hodnôt premenných x a y bude použitý binárny vektor, ktorého dĺžka bude závislá od požadovanej presnosti. Predpokladajme, že požadovaná presnosť budú štyri miesta za desatinnou čiarkou. Tým pádom je potrebné rozdeliť interval aspoň na

[math]\left( 100-\left( -100 \right) \right).10 000=2 000 000[/math]

(1)

rovnakých dielov. To znamená použiť binárny vektor dĺžky 42 bitov (21 bitov pre premennú x a 21 bitov pre y), pretože platí

[math]1 048 576=2^{20}\lt 2 000 000\lt 2^{21}=2 097 152[/math]

(2)

Vzdialenosť dvoch susediacich bodov v takto zvolenej reprezentácii bude 0,0000954, čo je postačujúci kompromis medzi požadovanou presnosťou a dobou výpočtu, ktorá logicky s predlžujúcou sa dĺžkou vektoru narastá. Chromozóm bude teda mať dĺžku 42 bitov, pričom prvých 21 bitov reprezentuje reálnu hodnotu premennej x z intervalu [math]\in \lt -100,100\gt [/math].Prevod medzi binárnym vektorom [math]v=(v_{1},v_{2},...,v_{21},v_{22},...,v_{41},v_{42})[/math] a príslušnými hodnotami premenných x a y je veľmi jednoduchý a tento prevod je možné vykonať v nasledujúcich dvoch krokoch:

1. Binárny vektor sa rozdelí na dve polovice a obidve sa prevedú do desiatkovej sústavy.

[math]x'=\sum\limits_{i=1}^{21}{v_{i}.2^{21-i} }a y'=\sum\limits_{i=22}^{42}{v_{i}.2^{42-i} }[/math]

(3)

1. Príslušné reálne čísla x a y potom budú získané aplikáciou lineárnej transformácie nasledovne:

[math]\begin{align} & x=-100+\frac{(100-(-100))}{2^{21}-1}.x' \\ & \\ & y=-100+\frac{(100-(-100))}{2^{21}-1}.y' \\ \end{align}[/math]

(4 5)

Napríklad chromozóm :

[math]v=(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)[/math]

obsahujúci okrem prvej a poslednej pozície samé nuly, odpovedá bodu so súradnicami:

[math][x,y]=[0,0000;-99,9999][/math]

Samozrejme, že chromozómy, ktoré obsahujú samé nuly respektíve samé jednotky, odpovedajú krajným bodom prehľadávaného priestoru. [3] V súvislosti s binárnym kódovaním sa objavuje jedna veľmi závažná skutočnosť, ktorá môže významným spôsobom ovplyvniť chovanie genetického algoritmu. Často sa totiž predpokladá, že nepatrná zmena vlastností indivídua sa prejavia len nepatrnou zmenou v jeho chromozóme a naopak, že nepatrná zmena v chromozóme, spôsobená napríklad mutáciou sa prejaví len malou zmenou fenotypu. V prípade binárneho kódovania je ale tento predpoklad veľmi silno narušený, čo sa dá demonštrovať na niekoľkých indivíduách z predchádzajúceho príkladu (pre jednoduchosť budeme uvažovať iba s prvou polovicou originálnych chromozómov, ktorá reprezentuje 21 bitov súradnice x). Celkom zreteľne sú napríklad reprezentované dva susediace body a binárnymi reťazcami

[math]v_{1}=( 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 )[/math]

[math]v_{2}=(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)[/math]

, ktoré sa líšia dokonca vo všetkých 21 bitoch. Veľmi podobné chromozómy

[math]v_{3}=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)[/math]

[math]v_{4}=( 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)[/math]

potom naopak reprezentujú veľmi vzdialené body [math]x_{3}=-100[/math] a [math]x_{4}=0,000048[/math].Odtiaľto je na prosto zrejmé, že aj malá zmena chromozómu môže mať veľmi výrazný vplyv na vlastnosti jedinca, zatiaľ čo zdanlivo malý krôčik medzi susediacimi bodmi prehľadávaného priestoru nie je uskutočniteľný bez vcelku zásadnej zmeny celého chromozómu. Táto nevýhoda štandardného binárneho kódovania je ľahko riešiteľná použitím Grayovho kódu, ktorého základnou vlastnosťou je, že dve susedné hodnoty sú zakódované binárnymi reťazcami príslušnej dĺžky tak, že sa tieto reťazce líšia práve v jednom bite. [3]

Tab. 1.7: Rozdiely binárneho a Grayovho kódovania

Číslo	Binárny kód	Grayov kód
0	000	000
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

Kódovanie reálnymi číslami:

Reprezentácia používajúca reálne čísla sa javí ako veľmi výhodná hlavne pri riešení úloh, kde je vyžadovaná veľká presnosť a binárna reprezentácia by znamenala použiť príliš dlhé reťazce, čo so sebou prináša nielen vyššie nároky z hľadiska pamäti, ale aj času spracovávania. V ilustratívnom príklade (vyššie v problematike binárneho kódovania) by tak bolo namiesto 42 bitového reťazca možné použiť chromozóm [math]u=(x,y)[/math] dĺžky 2, kde [math]x,y\in \lt -100,100\gt [/math].Pretože je v týchto prípadoch použitie reálnych čísel prirodzenejšie, je pre užívateľa jednoduchšie navrhnúť aj špeciálne genetické operátory, ktoré využívajú napríklad jednoduché aritmetické operácie. [3]

Permutačné kódovanie:

Veľmi často sa pri riešení rôznych kombinatorických a plánovacích úloh používa takzvané permutačné kódovanie, kedy je jedinec reprezentovaný permutáciou niekoľkých čísiel. Touto permutáciou je určené poradie jednotlivých objektov v riešení konkrétneho problému a našim cieľom je nájsť permutáciu reprezentujúcu optimálne riešenie. Asi najznámejšia úloha tohto druhu je takzvaný problém obchodného cestujúceho, ktorý ma za úlohu navštíviť n zadaných miest a prejsť pritom čo najmenšiu vzdialenosť. Pretože smie každé mesto navštíviť práve jeden krát, dá sa každé prípustné riešenie tohto problému reprezentovať ako permutáciu identifikátorov týchto miest, čím je určené poradie, v akom budú mestá navštívené. Ak uvažujeme napríklad päť miest, ktorým priradíme čísla 1 až 5, potom permutácia (2,3,1,5,4) reprezentuje poradie, kedy je nutné navštíviť najprv mesto číslo 2, odtiaľ pokračovať do mesta číslo 3, ďalej 1 atď. [3]

Kódovanie pomocou stromov:

Je celkom odlišný a veľmi zaujímavý spôsob reprezentácie, ktorý sa používa pri genetickom programovaní. Chromozóm v tomto pojatí už nie je reťazcom o pevnej dĺžke nad zvolenou abecedou, ale vo vhodnom syntaktickom tvare reprezentuje určitý program zložený z danej množiny funkcii a terminálov (napr. postup výpočtu matematickej funkcie, popis chovania objektu v určitom prostredí, reakcia hráča na konkrétnu hernú situáciu atď.). Genetickým algoritmom, ktorý sa od vyššie prezentovanej verzie líši obvykle iba špeciálnymi operátormi kríženia a mutácie, sa dá z počiatočnej populácie náhodne vygenerovaných programov postupne vytvoriť program riešiaci zadaný problém. [3] Názorné zobrazenie, ako by mohol vyzerať konkrétny matematický výraz reprezentovaný pomocou stromu je zobrazený na obrázku 1.2.

Obr. 1.2: Ukážka stromu reprezentujúceho výraz sin(x).x+ln(y)/x

Ohodnocujúca funkcia - Fitness funkcia

Ohodnocujúca funkcia musí byť úzko zviazaná s konkrétnym problémom, ktorý sa pokúšame použitím genetického algoritmu riešiť. Často sa ako ohodnocujúca funkcia používa priamo účelová funkcia respektíve jej vhodná modifikácia tak, aby bolo možné bez veľkých problémov usporiadať všetky potenciálne riešenia z hľadiska ich vhodnosti. Takisto v tejto práci bude použitá priamo účelová funkcia na ohodnotenie jednotlivých jedincov. Znamená to teda, že aproximujúca funkcia, ktorú zadá na vstupe užívateľ aby aproximovala namerané dáta, bude použitá na výpočet ohodnotenia daných jedincov populácie. Na druhej strane je možné ľahko nájsť prípady, kedy takto jednoducho postupovať nejde a bude nutné pristúpiť k inému spôsobu ohodnotenia jedincov. Predpokladajme napríklad, že jedince v populácii reprezentujúce rôzne herné stratégie istej hry. Ak nastane situácia, že stratégia A je lepšia ako stratégia B (to znamená, že pri použití stratégie A vyhráme nad hráčom, ktorý postupuje podľa stratégie B), B je lepšie ako C a C je lepšie než A, dostaneme sa do problémov s ohodnotením príslušných jedincov. Pokiaľ budú všetky jedince ohodnotené rovnakou hodnotou (pretože každá stratégia poráža jednu z dvoch ostatných), strácame informáciu o tom, že pri vzájomnom posúdení ľubovoľnej dvojice stratégii môžeme určiť jasného víťaza príslušného duelu. Pokiaľ naopak zvolená funkcia určí pre tieto tri jedince vzájomne rozdielne ohodnotenie, nutne bude existovať dvojica stratégii, pre ktoré ich ohodnotenie bude v spore s výsledkom ich vzájomného stretnutia v hre. Dôsledkom toho by bol v oboch prípadoch evolučný algoritmus použitou funkciou klamaný. Takto popísaný problém je spôsobený skutočnosťou, že použitá miera vhodnosti neumožňuje určiť absolútne poradie všetkých jedincov, pretože ide o mieru relatívnu, spočívajúcu vo vzájomnom porovnaní alebo súťažení jedincov v danej populácii. Relatívne ohodnotenie jedinca môže byť vypočítané napríklad ako celkový počet víťazstiev pri porovnaní so všetkými ostatnými jedincami v populácii. Pretože tento spôsob vyžaduje prevedenie celkom

[math]\frac{N \cdot (N-1)}{2}[/math]

(6)

Porovnaní, kde N je veľkosť populácie, ide o časovo pomerne náročnú záležitosť a preto boli navrhnuté alternatívne metódy. Celú populáciu je možné napríklad rozdeliť do dvoch rovnako veľkých častí o veľkosti N/2 a potom jedinec pri svojom ohodnotení podstupuje porovnanie iba s jedincami z druhej polovice populácie. Toto riešenie je vo svojej podstate predstupňom koevolúcie, kedy sa paralelne vyvíjajú dve vzájomne súperiace alebo naopak kooperujúce populácie jedincov. Inou cestou je usporiadanie turnaja medzi jedincami, kedy lepší jedinec z každej náhodne vylosovanej dvojice postupuje do ďalšieho kola, kde sa stretne s iným náhodne vybraným víťazom predchádzajúceho kola. Na konci turnaja ostáva jediný víťaz a ostatným jedincom sa priradí hodnota zodpovedajúca ich pôsobeniu v turnaji. Táto metóda so sebou prináša riziko prílišného zjednodušenia, ktorým platíme za veľmi malý počet potrebných porovnaní (stačí vykonať len N-1 porovnaní). Veľmi úspešným je postup populárne nazývaný „sieň slávy“, kedy ohodnocovaný jedinec podstupuje porovnanie s najlepšími jedincami z predchádzajúcej populácie, ktoré postupne vstupujú do testovacej množiny (siene slávy) a celkom logicky predstavujú ťažkých a náročných konkurentov. [3]

Selekcia – výber chromozómov

Ako je už známe, v cykle genetického algoritmu nastáva operácia nazývaná selekcia alebo inak povedané výber rodičovských chromozómov, ktoré sa ďalej zúčastňujú procesu kríženia. Problémom teraz je, ako vybrať tie najvhodnejšie chromozómy z populácie. Vzhliadnuc k Darwinovej evolučnej teórii, podľa ktorého sa zúčastňujú reprodukcie najzdatnejšie jedince, by mal výber chromozómov v genetickom algoritme podliehať tiež týmto pravidlám. Je známych viacero metód, akými môžu byť chromozómy vybrané. Patria sem napríklad ruletové koleso (Roulette Wheel selection), výber podľa poradia (Rank selection), turnajový výber (Tournament selection), Boltzmanov výber alebo niektoré iné. [1]

Ruletové koleso – Roulette wheel

Základom pre princíp ruletového kolesa je ohodnotenie všetkých chromozómov v populácii. Následne sa každému chromozómu priradí taký veľký výsek kolesa, aká je veľkosť sily (fitness) daného chromozómu. Znamená to, že veľkosť výseku, ktorý sa priradí určitému chromozómu je priamo úmerný sile tohto chromozómu a tým pádom má tento chromozóm väčšiu šancu na výber. Slabšie chromozómy majú priradený menší výsek, čo ich síce dopredu nevylučuje, ale pravdepodobnosť, že sa pomyselná gulička rulety zastaví na im priradenom výseku a dôjde tak k vybraniu jedného z nich, je menšia. Existuje niekoľko bežne používaných spôsobov, ako ruletové koleso skonštruovať. Líšia sa hlavne v spôsobe určovania veľkosti výsekov pre jednotlivé chromozómy. Veľmi rozšírený je takzvaný roletový mechanizmus výberu s pravdepodobnosťou výberu chromozómu priamo úmernou jeho ohodnoteniu (tzv. fitness-proportionate selection), kde má každý chromozóm priradený výsek, ktorého plocha je priamo úmerná ohodnoteniu tohto chromozómu. K vytvoreniu takéhoto ruletového kolesa stačí spočítať ohodnotenia všetkých členov populácie a potom priradiť každému chromozómu proporcionálne odpovedajúci kruhový výsek. Nech má uvažovaná populácia veľkosť a , nech je ohodnotenie i-teho chromozómu (predpokladáme, že ohodnocujúca funkcia je vždy nezáporná), potom pravdepodobnosť, s akou bude i-ty chromozóm vybraný, je daná nasledujúcim vzťahom: [3]

[math]p_{i}=\frac{f_{i}}{\sum\limits_{j=1}^{N}{f_{j}}} ,i\in (1,.....,N)[/math]

(7)

Obr. 1.3: Ruletové koleso (silnejšie chromozómy majú väčšiu šancu výberu)

Výber podľa poradia – Rank selection

Predchádzajúca metóda ruletového kolesa môže mať v niektorých prípadoch aj svoje nevýhody. Nastáva to vtedy, ak sa sily jednotlivých chromozómov populácie od seba veľmi odlišujú. Napríklad, ak zaberá najsilnejší chromozóm okolo 90% výseku kolesa, potom budú mať ostatné chromozómy veľmi malú šancu zúčastniť sa kríženia. V prípade rank selection sa najprv chromozómom určí poradie podľa ich sily. Najslabší bude 1, druhý najslabší 2 a tak ďalej až najsilnejšiemu bude priradené poradie N. Pri takomto prístupe budú mať všetky chromozómy šancu byť vybrané na kríženie. Takáto metóda výberu môže viesť k pomalšej konvergencii algoritmu, pretože sa chromozómy príliš od seba neodlišujú. [1] Názornú ukážku možno vidieť na obrázku 1.4.

Obr. 1.4: Rank selection (vľavo je ukážka príliš silného chromozómu, vpravo rozdelenie kolesa podľa princípu rank selection)

Turnajový výber – Tournament selection

Princíp tohto výberu chromozómov je vskutku jednoduchý. Z danej populácie chromozómov určenej k výberu rodičovských chromozómov sa vždy náhodne vyberú dva jedince, ktoré sa proti sebe stretnú v pomyselnom turnaji. Silnejší z týchto dvoch chromozómov sa dostane do skupiny jedincov určených na kríženie teda reprodukciu. Pôvodné dva chromozómy, ktoré sa stretli v turnaji sa ale vrátia späť do pôvodnej populácie, a majú tak možnosť byť znovu vybrané do turnaja. Ak sa takýmto spôsobom vyberie potrebný počet chromozómov tak sa turnajový výber ukončí a nasleduje kríženie a mutácia.

Goldberg a Deb analyzovali tento spôsob výberu jedincov a navrhli vylepšenú verziu, ktorá priradením istej pravdepodobnosti dáva aj slabšiemu jedincovi určitú šancu poraziť silnejšieho súpera, vyhrať turnaj a zúčastniť sa reprodukčného procesu (napr. s pravdepodobnosťou p = 0,05 to jest v 95% prípadov vyhrá silnejší jedinec). Goldberg a Deb uskutočnili pomerne podrobné porovnanie vlastností selekčných mechanizmov s pravdepodobnosťou výberu úmernou ohodnoteniu jedinca, podľa poradia aj turnajovým výberom a dospeli k záveru, že vhodnou voľbou parametrov je možné docieliť vo všetkých prípadoch zrovnateľné výsledky a všeobecne teda nie je možné povedať, že by niektorá z týchto metód prekonávala ostatné metódy. [3]

Operátory genetických algoritmov

V predchádzajúcich kapitolách už boli spomenuté výrazy ako kríženie, mutácia alebo reprodukcia. Tieto výrazy sa nazývajú operátory genetických algoritmov. Takisto je už možné aj usúdiť na čo sú tieto operátory určené. Ich úlohou je vytvoriť novú generáciu (populáciu) chromozómov (jedincov), ktoré budú mať lepšie vlastnosti oproti predchádzajúcej generácii. Pričom chromozómy tejto novej generácie boli vytvorené z najzdatnejších chromozómov predchádzajúcej generácie. V niektorých literatúrach sa uvádzajú ako operátory genetických algoritmov len kríženie a mutácia. Z toho potom vyplýva, že do novovzniknutej generácie sa nedostane žiaden chromozóm z predchádzajúcej generácie. Môže to mať za následok to, že niektorý z najzdatnejších chromozómov nebude respektíve nebudú pseudonáhodnou selekciou vybraný k vytvoreniu novej generácie a jednoducho zaniknú. Niektorý autori však zaviedli do genetického algoritmu aj operátor reprodukcie (respektíve elitizmus). Ten má za úlohu vybrať z populácie jeden alebo niekoľko chromozómov s najvyššou hodnotou sily (fitness, zdatnosť), ktoré sa priamo dostanú do novej generácie jednoduchým prekopírovaním. Títo autori pritom vychádzali z poznatkov o živej prírode, v ktorej sa tiež najzdatnejší jedinci nezúčastňujú len jedného reprodukčného cyklu. V nasledujúcich dvoch kapitolách sú popísané dva hlavné operátory genetických algoritmov.

Kríženie

Podobne ako u ľudí, kedy má dieťa niektoré črty zdedené po otcovi a niektoré po matke, prebieha kríženie aj v genetických algoritmoch. Ide tu vlastne o náhodnú výmenu určitých rovnako veľkých častí rodičovských chromozómov medzi sebou. V rôznych literatúrach býva uvádzané, že kríženie chromozómov sa deje s pravdepodobnosťou medzi 0,75 až 0,95. Najjednoduchšou formou kríženia v genetickom algoritme je jednobodové kríženie. Jeho princíp je jasne pochopiteľný z nasledujúceho obrázku 1.5.

Obr. 1.5: Jednobodové kríženie

Pri tomto type kríženia sa náhodne určí bod kríženia a gény (respektíve alely), ktoré sa nachádzajú za týmto bodom sa vymenia medzi rodičovskými chromozómami. Podľa princípu jednobodového kríženia je jednoduché pochopiť ako bude vyzerať k-bodové kríženie. V tomto prípade sa náhodne určí viacero bodov kríženia a výmena génov prebehne spôsobom ako je to zobrazené na obrázku 1.6.

Obr. 1.6: k-bodové kríženie (konkrétne 2-bodové)

Ďalším rozšírením k-bodového kríženia sa dá postupne dôjsť až k takzvanému uniformnému kríženiu. Pri vzniku prvého z potomkov sa pre každý jednotlivý gén rozhodne s pravdepodobnosťou pu = 0,5, po ktorom z rodičov zdedí príslušnú alelu. Druhý potomok dostane potom jednotlivé alely vždy od opačného rodiča. Tento princíp je vidieť na obrázku 1.7. [3]

Obr. 1.7: Uniformné kríženie

Doteraz boli operácie kríženia prezentované na binárnych chromozómoch. Princípy týchto operátorov je ale možné použiť na chromozómy, ktorých gény sú zložené z hodnôt z oboru reálnych čísiel. Ukážka takéhoto k-bodového kríženia je zobrazená na obrázku 1.8. Zaujímavejšie však je to, že v nebinárnej reprezentácii chromozómov je relatívne jednoduché definovať zmysluplné a konkrétnemu problému odpovedajúce špeciálne genetické operátory kríženia. Môže sa napríklad jednať o tieto: [3]

• aritmetický– nová alela je určená aritmetickým priemerom rodičovských alel
• geometrický – nová alela je odmocninou súčinu rodičovských alel
• rozširujúci – rozdiel medzi hodnotami rodičov sa pripočíta k väčšiemu z nich a odpočíta od menšieho

Obr. 1.8: k-bodové kríženie chromozómov s kódovaní v reálnych číslach

Problém môže vzniknúť pri permutačnom kódovaní. Chromozóm pri tomto type kódovania predstavuje isté poradie objektov respektíve akcií, ktoré je nutné rešpektovať. Na obrázku 1.9 vidno, že pri použití štandardného operátoru kríženia sa môže stať, že po výmene príslušných častí chromozómu už výsledné chromozómy permutačné nebudú, pretože niektorý objekt v permutácii chýba, zatiaľ čo iný sa tam vyskytuje dvakrát. Pretože tomuto efektu nejde zabrániť, je potrebné následne po krížení vykonať opravnú procedúru, ktorá z výsledných chromozómov vyrobí opäť permutačné. [3]

Obr. 1.9: Chyba pri krížení permutačne kódovaných chromozómov

Mutácia

Mutácia je operátor, ktorý sa aplikuje na novovytvorený chromozóm, ktorý vznikol z rodičovských chromozómov aplikovaním operátora kríženia. Tento operátor má za úlohu vykonať náhodnú zmenu alely (hodnoty génu) náhodne vybraného génu z chromozómu. Podstatným faktom ale je ten, že táto operácia mutácie sa vykonáva len s veľmi malou pravdepodobnosťou. V literatúre býva uvádzaná pravdepodobnosť 0,001 až 0,05. Na obrázku 1.10 je ilustrovaná jednoduchá ukážka toho, ako by mohla vyzerať operácia mutácie na niekoľkých chromozómoch reprezentovaných binárne.

Obr. 1.10: Mutácia binárnych chromozómov

V prípade, ak sú chromozómy reprezentované reálnymi hodnotami génov, tak sa naskytá viacero možností mutácie. Medzi tieto patria:

• Náhodná výmena – nahradenie pôvodnej alely náhodne vygenerovanou hodnotou
• Aditívna zmena – pripočítanie náhodne vygenerovanej hodnoty k pôvodnej alele
• Multiplikatívna zmena – vynásobenie pôvodnej hodnoty náhodne generovaným číslom

V prípade permutačného kódovanie chromozómov musí podobne ako u kríženia permutačných chromozómov dávať pozor na jeden fakt. Je zrejmé, že náhodná zmena jedného čísla v reťazci by spôsobila značné problémy, pretože pôvodné číslo by z permutácie touto zmenou vypadlo a iné by sa v nej zrejme vyskytovalo dva krát. Riešenie tohto problému je však veľmi jednoduché a nie je potrebné ani navrhovať nejaký opravný mechanizmus, ktorý by mutáciou narušený reťazec opäť zmenil tak, aby výsledok bol znova permutáciou. Stačí, keď sa namiesto jednej pozície v chromozóme zvolia dve pozície a potom sa príslušné hodnoty vzájomne vymenia. Na obrázku 1.11 je naznačená operácia, kedy sú na mutáciu vybrané tretia a ôsma pozícia v chromozóme. [3]

Obr. 1.11: Mutácia permutačne kódovaných chromozómov

Vytvorenie novej populácie

Základný genetický algoritmus, ktorý bol prezentovaný v predchádzajúcich častiach tejto práce, využíval jednoduchý generačný princíp, kedy predošlá generácia úplne vymrie. Nová populácia sa potom automaticky skladá iba z jedincov, ktoré vznikli ako potomstvo predchádzajúcej populácie. Neexistuje tu teda žiadna možnosť pre jedince zo staršej populácie prežiť a ovplyvňovať evolučný proces po dlhšiu dobu než len jeden generačný cyklus. Táto metóda v sebe skrýva celkom evidentné nebezpečenstvo spočívajúce v tom, že sľubný jedinec či celá skupinka takýchto jedincov môže byť navždy stratená, pokiaľ sa im nepodarí prejsť procesom selekcie alebo pokiaľ ich genetická informácia bude zmenená použitím genetických operátorov. Samozrejme, že táto potenciálna slabosť môže byť ľahko prekonaná, pokiaľ istému počtu nádejných jedincov bude umožnené prežiť v nezmenenej podobe a automaticky dostanú miesto v nasledujúcej populácii. Z tohto hľadiska sú využívané v podstate dva rôzne prístupy líšiace sa hlavne v počte jedincov, ktorým je umožnené prežiť a podieľať sa na evolučnom procese po viac ako jednu generáciu. Prvý z nich, ktorý sa nazýva elitizmus, umožňuje genetickému algoritmu si ponechať vždy niekoľko najlepších jedincov z aktuálnej populácie. Táto „elita“ sa jednoducho a bez akejkoľvek zmeny prekopíruje do nasledujúcej populácie a tým nemôže dôjsť ku strate príslušnej genetickej informácie. Druhým prístupom je náhradová stratégia typu zotrvaný stav (steady-state reproduction), ktorá naopak uchováva väčšinu populácie v nezmenenom stave. Iba niekoľko málo najhoršie ohodnotených jedincov je v každej generácii nahradených novo vytvorenými potomkami, čím automaticky dochádza k uchovávaniu najlepšej časti doterajšej populácie a súčasne k pomalému postupnému vývoju populácie. Pre zachovanie čo najväčšieho množstva genetickej informácie z aktuálnej populácie je v niektorých prípadoch potrebné ešte viacej sprísniť podmienky pre možný vstup novovytvorených potomkov do vznikajúcej populácie. Ich pozícia tu nemusí byť automaticky garantovaná istým počtom miest, ako to bolo v doteraz uvažovaných prípadoch, ale môžu byť napríklad do úvahy vzaté iba také jedince, ktoré majú vyššie ohodnotenie ako dočasne najslabší jedinec v populácii. Ak je táto podmienka splnená, dočasne najslabší jedinec je z populácie vypustený a na jeho miesto sa dostane nový jedinec. V iných prípadoch môže byť naopak veľmi dôležité čo možno najväčšiu rozmanitosť v rámci populácie a z tohto dôvodu nie je žiaduce, aby sa v populácii vyskytovali dva alebo viac identických jedincov (s totožným chromozómom a teda aj s rovnakým ohodnotením). Ak sa teda medzi potomstvom objaví jedinec, ktorý je identický s niektorým doterajším členom populácie, bude vylúčený z ďalších úvah bez ohľadu na jeho ohodnotenie a v populácii sa zachová iba pôvodný jedinec. Niektorý autori išli v tomto smere ešte ďalej a okrem celkom totožných jedincov v populácii sa rôznymi spôsobmi pokúšali obmedzovať aj množstvo podobných jedincov. De Jong experimentoval s vytlačovacou stratégiou (crowding), kedy potomok novo zaradený do populácie zaujme miesto „vytlačí“ najpodobnejšieho jedinca v populácii. Zatiaľ čo originálna verzia vytláčania predpokladala, že potomok vytlačí jedného (podobnejšieho) z vlastných rodičov, novšie varianty využívajú skôr určitý spôsob turnaja medzi potomkom a rodičom, pričom potomok nahradí príslušného rodiča v populácii iba vtedy, ak je sám zdatnejší (má vyššie ohodnotenie). Iný prístup navrhli Goldberg a Richardson, ktorí dosiahli podobného efektu použitím ohodnocujúcej funkcie, do ktorej bola zahrnutá zložka penalizácie za eventuálnu prítomnosť podobných jedincov v populácii. Ohodnotenie každého jedinca je tu znižované jednak v závislosti na počte podobných jedincov, pretože každý jedinec je porovnávaný so všetkými ostatnými v populácii, ale tiež podľa mieri tejto podobnosti. Goldberg a Richardson pri použití tohto prístupu sledovali aj ďalší pozitívny efekt prejavujúci sa v problémoch, ktoré majú viac rôznych riešení. Nutnosť udržovať dostatočnú rozmanitosť v populácii totiž vedie vo výsledku k tomu, že populácia má tendenciu skôr než k jednému riešeniu konvergovať k niekoľkým rôznym riešeniam. Až do teraz boli všetky tu popísané spôsoby vytvárania novej populácie statické v tom zmysle, že množina potenciálnych rodičov bola v danej generácii nemenná. To znamená, že potomkovia súčasných rodičov musia najprv dospieť (to jest počkať do nasledujúcej generácie) a až potom sa v súťaži s ostatnými stretnúť o možnosť vytvoriť vlastných potomkov. Aj tu je ale možná alternatíva, ktorú predstavuje prístup umožňujúci práve vytvorenému potomkovi okamžite vstúpiť do rodičovskej populácie a zúčastniť sa bezodkladne výberu budúceho rodičovského páru, čím sa bohatá paleta možností spôsobu vzniku novej populácie ďalej rozširuje. [3]

Ukončovacie podmienky genetického algoritmu

Existuje viacero prístupov, ako je možné určiť či už genetický algoritmus vykonal úlohu, na ktorú bol navrhnutý a je vhodné ho ukončiť, teda ukončiť hľadanie konkrétneho riešenia. K tomu slúžia takzvané ukončovacie podmienky. Tieto podmienky sú vyhodnocované vždy potom, ako sa vytvorí nová generácia chromozómov pomocou operátorov kríženia a mutácie. Medzi najrozšírenejšie ukončovacie podmienky patria tieto:

Počet generácii

Táto podmienka je zo všetkých asi najjednoduchšia. Na začiatku sa určí koľko generácii sa má pomocou genetických operátorov vytvoriť a po dosiahnutí tohto počtu sa genetický algoritmus zastaví. Takúto podmienku je vhodné použiť v prípade, ak dopredu vieme, že správne riešenie sa pomocou tohto algoritmu nájde už po vytvorení niekoľkých generáciách. Na uvedenie príkladu uvediem nasledovné. Majme problém obchodného cestujúceho, kedy musí cestujúci navštíviť všetky mestá tak, aby prešiel čo najkratšiu vzdialenosť. Určime, že genetický algoritmus sa má ukončiť po 100 vytvorených generáciách. Po spustení algoritmu sa ale už po 30 generáciách nájde optimálne riešenie. Tým pádom bude výsledok nasledovných 70 generácii stagnovať a algoritmus bude pracovať ako keby zbytočne.

Čas evolúcie

Táto metóda ukončí vykonávanie algoritmu vtedy, keď čas po ktorý daný algoritmus pracuje prekročí užívateľom respektíve programátorom zvolený maximálny čas výpočtu. Štandardne je dané, že evolúcia nie je zastavená pokiaľ nie je vytvorená aktuálne spracovávaná generácia, ale takéto správanie je možné zmeniť tak, že genetický algoritmus sa zastaví aj bez toho, aby bola dokončené táto generácia.

Hraničná úroveň ohodnotenia generácie

Úlohou tejto metódy je ukončiť vykonávanie genetického algoritmu vtedy, ak ohodnotenie (fitness) najlepšieho jedinca v populácii bude menšie ako je užívateľom definovaná hranica ohodnotenia. A to v prípade ak je genetický algoritmus nastavený tak, aby sa číslo predstavujúce ohodnotenie daného jedinca zmenšovalo. Tiež je možné nastaviť túto podmienku opačne a to tak, že sa vykonávanie algoritmu zastaví v prípade ak ohodnotenie najlepšieho jedinca bude väčšie ako užívateľom definovaná hranica. To nastáva vtedy, ak je číslo predstavujúce ohodnotenie jedinca v populácii priamo úmerné sile tohto jedinca. Teda ak sa jedinec zlepšuje, číslo predstavujúce jeho ohodnotenie narastá.

Konvergencia populácie

Ukončenie genetického algoritmu pomocou tejto metódy nastáva v čase, kedy sa populácia stane konvergentnou. A to, kedy sa stane populácia konvergentnou je možné zistiť podľa toho, že rozdiel ohodnotenia predchádzajúcej a aktuálnej generácie je menší ako je užívateľom definovaná hodnota rozdielu respektíve rozdiel medzi ohodnoteniami predchádzajúcej a aktuálnej populácie je niekoľko generácii menší ako užívateľom definovaná hodnota rozdielu.

Konvergencia génov

Ukončovacia podmienka, ktorá zastaví vykonávanie genetického algoritmu vtedy, keď užívateľom definované percento génov, ktoré tvoria chromozóm budú považované za konvergentné (nemenia sa). Daný gén je považovaný za konvergentný vtedy, keď určité užívateľom definované percento (môže to byť 95%) populácie má takú istú hodnotu v tomto géne.