Evolučný algoritmus

Zadanie

Vytvorte systém na získanie funkcie, ktorá bude čo najvernejšie aproximovať určenú sadu bodov, zadaných ako dvojice (x,f(x)). Systém bude využívať evolučný algoritmus na hľadanie vhodnej funkcie. K systému vypracujte dokumentáciu.

Základná sada génov

Označenie Význam génu Ďalšie vlastnosti, podmienky
G1 +1  
G2 -3  
G3 *2  
G4 /3  
G5 +X  
G6 -X  
G7 *X  
G8 /X Menej častý výskyt
G9 *( Nemal by sa vyskytovať tesne pred ani po G10
G10 /( Nemal by sa vyskytovať tesne pred ani po G9
G11 ) Mal by sa vyskytovať až po G9 alebo G10

Sadu uvedených génov je možné rozšíriť o ďalšie matematické operácie (odmocnina, logaritmus, goniometrické funkcie a i.), prípadne ich kombinácie (polynóm, všeobecný výraz). Je vhodné pridať génom aj ďalšie vlastnosti. Je však možné využiť aj iný spôsob tvorby génov, ako tento preddefinovaný.

Typická vlastnosť génov je, že ich význam je závislý aj od pozície v reťazci, aj od iných, zvyčajne predchádzajúcich génov. Tak napríklad prvý gén môže určovať základný typ funkcie – či je konštantná, lineárna, inverzná, logaritmická, exponenciálna, sinusoidná, polynomická atď. Zároveň bude určovať počet prislúchajúcich génov – konštantnej funkcii stačí jeden, lineárna už potrebuje dva, polynóm podľa svojho stupňa. Druhý gén v poradí (alebo druhý a tretí alebo druhý a …) teda zvyčajne určuje konštantu (posun hodnôt v smere osi Y). Ak je nasledujúcich génov menej, použije sa pre príslušný parameter štandardná (default) hodnota. Ak je génov viac, než vyžaduje základný typ funkcie, zvyšné gény určujú ďalšiu funkciu. Prvý gén určuje, či sa budú funkcie sčitovať, násobiť alebo skladať a akú váhu pri tom bude mať druhá funkcia. Nasledujúci gén už znovu určuje typ funkcie a ostatné sa použijú rovnako ako u predchádzajúcej funkcie.

Príklad viacvýznamových génov:
Označenie Význam 1 Argumenty Význam 2 Význam 3
G1 Konštanta 1 +1 Pripočítaj funkciu
G2 Lineárna 2 +2 Pripočítaj funkciu s polovičnou váhou
G3 Kvadratická 3 +3 Pripočítaj funkciu s tretinovou váhou
G4 Kubická 4 +5 Pripočítaj funkciu s štvrtinovou váhou
G5 Piateho rádu 5 -1 Odpočítaj funkciu
G6 Odmocnina 1 – 3 -2 Odpočítaj funkciu s polovičnou váhou
G7 Tretia odmocnina 1 – 3 -3 Odpočítaj funkciu s tretinovou váhou
G8 Sínusoida 1 – 4 -5 Vynásob funkcie
G9 Tangenta 1 – 4 0,1 * nasledujúci gén Vydeľ funkcie
G10 Logaritmická 1 – 4 10 * nasledujúci gén Zlož funkcie f(g)
G11 Exponenciálna 1 – 4 0 Zlož funkcie g(f)

Náčrt algoritmu

Algoritmus je celkom jednoduchý a pozostáva z troch základných krokov:
  1. Inicializácia hodnôt a vytvorenie prvej generácie jedincov.
    Určia sa hodnoty (xi,f(xi)), množstvo jedincov v generácii, počiatočný počet génov jedincov, výkonnostná funkcia, ohraničenia na počet generácií. Po nastavení všetkých hodnôt sa vygeneruje prvá generácia jedincov a prejde sa na krok dva.
  2. Ohodnotenie jedincov a test na ukončenie činnosti.
    Všetci (noví) jedinci sa ohodnotia podľa výkonnostnej funkcie. Ak dosiahol najlepší jedinec dostatočný výkon (priblížil sa k hodnotám (xi,f(xi))), prípadne ak nastalo iné kritérium, napr. maximálny počet generácie, riešenie sa ukončí a najlepší jedinec je stanovený ako výsledné riešenie. Ak sa nesplnila žiadna ukončovacia podmienka, pokračuje sa krokom tri.
  3. Výber jedincov na prežitie a vytvorenie novej generácie.
    Vyberú sa jedinci na prežitie a vytvorenie novej generácie. Vyberá sa zopár najlepších jedincov, aby sme nestratili doteraz najlepšie riešenie, a aj niekoľko slabších jedincov pre „novú krv“. Noví jedinci vznikajú z vybraných jedincov vzájomným krížením skupín génov, mutáciou jedného génu, pridaním alebo ubratím jedného génu a prípadne aj kombináciou uvedených postupov. Noví jedinci sa pridajú k prežívajúcim a vytvoria novú generáciu. Pokračuje sa krokom dva.
Tu je ukážka, ako sa mení pravdepodobnosť výberu zvoleného jedinca od počtu jedincov v turnaji. Pri dvoch jedincoch je závislosť lineárna (tak ako pri selekcii ohodnotením). Viac ako štyroch jedincov v turnaji zvyčajne nepoužívame, lebo je príliš malá šanca, že sa vyberie nejaký jedinec zo slabšej polovice generácie.

Ohodnotenie každého jedinca sa robí v troch fázach. Najprv sa z postupnosti génov vytvorí matematický výraz, potom sa za každý výskyt X dosadzuje príslušná vstupná hodnota a počítajú sa zodpovedajúce výstupné hodnoty a na záver sa spočíta výkonnostná funkcia. Ako výkonnostná funkcia je štandardne určená stredná kvadratická chyba, ale je možné ju rozšíriť aj o iné vzdialenostné metódy. Je jasné, že čím je menšia vzdialenosť, tým je jedinec výkonnejší. Systém musí vhodne zareagovať, ak by malo nastať delenie nulou, prípadne iná nepovolená matematická operácia. Vhodne zareagovať znamená, okrem iného, neprerušiť výpočtový cyklus.

Pre kríženie, mutáciu, odoberanie, pridávanie génov je možné pridať ďalšie podmienky. Zvlášť u viacvýznamových génov je vhodné zašpecifikovať tzv. „ľahkú mutáciu“, kde mením len parametre funkcií a „ťažkú mutáciu“, kde mením (uberám, pridávam) celú funkciu.

Dokumentácia

Dokumentácia musí obsahovať konkrétne použitý algoritmus (nie len náčrt algoritmu, ako v zadaní), podrobný opis všetkých použitých génov, podmienok ich umiestňovania, spôsob generovania matematického výrazu a presný spôsob tvorby novej generácie. Dôležitou časťou dokumentácie je zhodnotenie vlastností vytvoreného systému a porovnanie dosahovaných výsledkov aspoň pre dva rôzne spôsoby tvorby novej generácie alebo rôzne výkonnostné funkcie. Dosiahnuté výsledky je vhodné zobraziť grafom. Dokumentácia by mala tiež obsahovať opis vylepšovania, dolaďovania riešenia.

Príklady funkčných hodnôt

Funkčný predpis Konkrétne vstupné hodnoty pre program
3*cosX-2*sinX+4 (1;3,94) (2;0,93) (3;0,74) (4;3,55) (5;6,77) (6;7,44) (7;4,95) (8;1,58) (9;0,44) (10;2,57) (11;6,01) (12;7,6) (13;5,88) (14;2,43) (15;0,42) (16;1,7)
4*sin2X+5 (1;8,64) (2;1,97) (3;3,88) (4;8,96) (5;2,82) (6;2,85) (7;8,96) (8;3,84) (9;2) (10;8,65) (11;4,96) (12;1,38) (13;8,05) (14;6,08) (15;1,05) (16;7,2)
X+2/X (1;3) (2;3) (3;3,67) (4;4,5) (5;5,4) (6;6,33) (7;7,29) (8;8,25) (9;9,22) (10;10,2) (11;11,18) (12;12,16) (13;13,15) (14;14,14) (15;15,13) (16;16,12)
3-X/10 (1;2,9) (2;2,8) (3;2,7) (4;2,6) (5;2,5) (6;2,4) (7;2,3) (8;2,2) (9;2,1) (10;2) (11;1,9) (12;1,8) (13;1,7) (14;1,6) (15;1,5) (16;1,4)
X je v radiánoch.

Jednoduchý príklad, pracujúci približne podľa prvej sady génov.