Genetické algoritmy
Metodický koncept k efektivní podpoře klíčových odborných kompetencí s využitím cizího jazyka
ATCZ62 - CLIL jako výuková strategie na vysoké škole
C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Heuristický postup, patří mezi evoluční algoritmy
•Patří do umělé inteligence
•Aplikací znalostí z evoluční biologie hledá řešení složitých problémů, pro které neexistuje
exaktní algoritmus
•Napodobuje techniky evoluční biologie
•Dědičnost
•Mutace
•Přirozený výběr
•Křížení
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Princip:
1.Inicializace - Vytvoř nultou populaci (obvykle složenou z náhodně vygenerovaných jedinců)
2.Začátek cyklu – Vyber (zpravidla zčásti náhodné) z populace několik jedinců s vysokou zdatností
3.Z vybraných jedinců vygeneruj novou generaci použitím následujících metod (operátorů):
• křížení - „prohoď“ části několika jedinců mezi sebou
• mutace - náhodně změň část jedince
• reprodukce - kopíruj jedince beze změny
4.Vypočti zdatnost těchto nových jedinců
5.Konec cyklu - Pokud není splněna zastavovací podmínka, tak pokračuj od bodu 2
6.Konec algoritmu - Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje
nejlepší nalezené řešení.

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Pojmy:
•Fenotyp – označení jedince
•Genotyp, genom, chromozom – reprezentace fenotypu
•Chromozom – dělí se na jednotlivé lineárně uspořádané geny (i-tý gen chromozomů stejného typu
reprezentuje stejnou charakteristiku)
•Alely – různé hodnoty genu
•Fitness hodnota – z rozmezí 0-1, vyjadřuje kvalitu každého jedince
•Individua mohou být zakódována (geneticky popsána) různým způsobem
•Způsobem popsání, může být důležitý pro úspěch či neúspěch řešení konkrétní úlohy
•

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Příklad:
•Nultá generace (fitness hodnota = počet „1“):
1.0100011011 f=0,5
2.0101000100 f=0,3
3.1010110000 f=0,4
4.1110111000 f=0,6

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Křížení
•Rodiče si vymění část genetického kódu
•Nejjednodušší metoda – jednobodové křížení
•Náhodně vybere místo pro řez
•X: 010001|1011
•Y: 111011|1000
•P: 0100011000 f=0,3
•Q: 111011 1011 f=0,8
•Vícebodové křížení, možnost více než dvou rodičů

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Mutace
•Náhodná změna náhodného genu v jedinci
•Velmi malá pravděpodobnost
1.0100011011 ⇒ 0101011011
2.0101000100 ⇒  0101100100
3.1010110000 ⇒  1010110100
4.1110111000 ⇒ 1010111000
•Lze dosáhnout vlastností, které se v původní generaci nevyskytují

C:\Users\21536\AppData\Local\Temp\7zOCBEF4013\interreg_Rakousko_Ceska_Republika_RGB.jpg
https://www.email.cz/download/k/vPwBms0jPnQoTvgo0jFvvGwDhdh9Jlfl9rKdiuyzDRyHOOMId1HvJLvOPRBH2skc4uZ
VKBw/image001.png Fachhochschulen Oberösterreich
Genetický algoritmus
•Ukončení
•Dosažení maximálního počtu generací (časové omezení)
•Dosažení minimálního potřebného fitness skóre
•Alespoň jeden jedinec dosáhl dostatečně uspokojivého výsledku
•Dosažený přidělený rozpočet (počítačový čas/peníze)
•Po sobě jdoucí iterace nedosahují žádného zlepšení
•Ruční kontrola
•Kombinace výše uvedených kritérií