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í