Genetické algoritmy. Informační a komunikační technologie ve zdravotnictví

Genetické algoritmy Informační a komunikační technologie ve zdravotnictví

Přehled přednášky          

Úvod Historie Základní pojmy Principy genetických algoritmů Možnosti použití Související metody AI Příklad – problém obchodního cestujícího Příklad – umělý život Dotazy Zdroje

Úvod  

Aplikace Darwinovy evoluční teorie na informatiku Hlavní myšlenka  vyhovující

organismus lze získat přirozenou selekcí, křížením a mutacemi

Přírodní motivace  



Metafora Darwinovy evoluční teorie o vývoji druhu Pravděpodobnostní metody přiblížení technického základu k ideálu podle přírodních genetických a vývojových principů Nejčastěji používané ze skupiny evolučních optimalizačních algoritmů jsou Genetické algoritmy

Historie   

1960 - I. Rechenberg "Evolution strategies„ 1975 - John Holland "Adaption in Natural and Artificial Systems„ 1992 John Koza - „Genetic programming"

Vlastnosti GA     

Robustnost Efektivní způsob vyhledávání mnohonásobným opakování jednoduchých operací Paralelní prohledávání celého prostoru ve více směrech současně Schopnost vyváznout z lokálního extrému GA hledá celou skupinu přípustných řešení výběr nejlepšího

Základní pojmy 

Jedinec 



Genom 



řetězec nukleotidů kódující jednu vlastnost

Genotyp x fenotyp 



genetický materiál určitého druhu

Gen 



nositel genetické informace

genetická informace o řešení vs. Konkrétní hodnoty parametrů řešení

Chromozom 

řetězec genů

Reprezentace chromozomu 

Volba závisí na charakteru problému  Binárně  Permutace

přirozených čísel  Sekvence hodnot  Stromová struktura

Binární reprezetace chromozomu



Chromozom je reprezentován řadou 1 a 0 Velké množství možností s malým počtem genů Jednoduchá realizace



Příklad použití – problém plného batohu

 

1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 0 1 0 1 0

Reprezetace permutací čísel



Každý gen reprezentuje pořadí v sekvenci Ideální pro úlohy řešící řazení



Příklad – problém obchodního cestujícího



1 4 2 7 9 3 5 8 6 7 4 1 8 2 5 3 6 9

Posloupnost hodnot   

Gen reprezentuje nějakou složitější hodnotu Přirozená reprezentace mnoha problémů Pro křížení jsou nutné speciální operátory 1.54

2.95

4.92

1.32

4.07

A A B A F E D E A C E B C G G (back)

(left)

(left)

(forward)

Stromová struktura  

Chromozom je stromová struktura obsahující ve svých uzlech a větvích nějaké objekty Příklady použití: +

list

0

3

list

1

2

Genetické programování

a

* 3

x

Regresní analýza

Algoritmus - schéma

Algoritmus   

Vytvoř první populaci jedinců Ohodnoť jedince v populaci Vytvoř novou populaci  Vyber

rodiče některou metodou selekce  Vytvoř nové jedince křížením a mutací  Ohodnoť nové jedince  Přidej potomky do populace  

Nahraď starou populaci novou Opakuj dokud nejsou splněny podmínky zadání

Inicializace počáteční populace 

Náhodná inicializace Náhodný výběr zvoleného počtu chromozomů (náhodný generátor 0 a 1 s p-stí 0,5)  Žádná apriorní znalost o podobě hledaného řešení  Spoléhá pouze na šťastné navzorkování celého prohledávaného prostoru omezeným počtem příkladů 



Informovaná inicializace Využívá apriorní znalost  Může vést jednak k nalezení lepších řešení  Může zkrátit celkový výpočet  Může způsobit nevratné nasměrování GA k suboptimálnímu řešení 

Inicializace počáteční populace 

Předzpracování jedinců pro počáteční populaci

Algoritmus   

Vytvoř první populaci jedinců Ohodnoť jedince v populaci Vytvoř novou populaci  Vyber

rodiče některou metodou selekce  Vytvoř nové jedince křížením a mutací  Ohodnoť nové jedince  Přidej potomky do populace  

Nahraď starou populaci novou Opakuj dokud nejsou splněny podmínky zadání

Fitness funkce   

Určuje úspěšnost jedince Na výsledku závisí jakou měrou se jedinec projeví v následující generaci Příklad: hledání největší Euklidovské vzdálenosti vzdálenosti a,b – rozsah hodnot 0-31, binární kódování fitness: f(a,b)=a 2 +b2

Algoritmus   

Vytvoř první populaci jedinců Ohodnoť jedince v populaci Vytvoř novou populaci  Vyber

rodiče některou metodou selekce  Vytvoř nové jedince křížením a mutací  Ohodnoť nové jedince  Přidej potomky do populace  

Nahraď starou populaci novou Opakuj dokud nejsou splněny podmínky zadání

Selekce a metody selekce 

Uplatnění Darwinovy teorie – „Nejlepší přežijí a stvoří potomky“



Ruletové kolo Rank Selection Turnaj

 

Ruletové kolo 

Pravděpodobnost výběru jedince x 0

- fitness funkcef pro i-tého jedince jedinců - fitness funkce pro i-tého jedince  f ( x) - suma fitness funkcífivšech i

xk

pi 

f i  x0



f ( x)

xk

Algoritmus: Spočti celkovou sumu všech fitness funkcí = S Generuj náhodné číslo z intervalu < 0, S > = r Procházej populaci a sčítej fitness fci. Když r < aktuální součet zastav a vrať daný chromozóm

Pořadová selekce (rank selection) 

Obdoba ruletového kola – nepracujeme s hodnotami fitness funkcí ale s pořadovým číslem jedince: N

je počet jedinců v populaci,  funkce rank(i) vrací pořadí i-tého jedince v populaci  shift udává hodnotu f' nejhoršího jedince v populaci   

Nejhoršímu jedinci přiřadíme 1, dalšímu 2, atd. Pro problémy, kde je velký rozdíl hodnot fitness funkcí Pomalejší konvergence

Turnaj   

Náhodně vybraní jedinci z populace podstupují „souboj o přežití“ Vybrán je jedinec s lepším ohodnocením Výhody - jednoduchá implementace, zajišťuje rozmanitost i selekční tlak

Algoritmus   

Vytvoř první populaci jedinců Ohodnoť jedince v populaci Vytvoř novou populaci  Vyber

rodiče některou metodou selekce  Vytvoř nové jedince křížením a mutací  Ohodnoť nové jedince  Přidej potomky do populace  

Nahraď starou populaci novou Opakuj dokud nejsou splněny podmínky zadání

Křížení  

Metoda, jejímž použitím získáme nové jedince, kteří nebyli součástí předchozí populace Dle typu úlohy existuje několik typů operátorů křížení  Crossover  Edge

recombination crossover  A mnoho dalších …

1 1 0 0 1 1 0

1 0 0 1 1 0 1

1 1 0 1 1 0 1

1 0 0 0 1 1 0

Způsoby křížení 

Jednobodové 11101001000 00001010101



11101010101 00001001000

00111110000 maska

11001011000 00101000101

Dvoubodové 11101001000 00001010101



11111000000 maska

Rovnoměrné (uniform) 11101001000 00001010101

10011010011 maska

10001000100 01101011001

Mutace   

Náhodná změna vybraných genů jedince Rozšiřuje prohledávaný prostor o řešení, které nelze dosáhnou křížením Zabraňuje uváznutí v lokální maximu / minimu 1 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1

Nahrazovací strategie 



Určuje jak velká část populace (a kteří jedinci konkrétně) bude nahrazena v jednom generačním kroku Generační strategie  Stará

populace je kompletně nahrazena novou populací



Steady-state  Pouze

část populace je nahrazena, ostatní jedinci zůstávání

Elitářství   

Do další generace je zachováno beze změny několik nejlepších jedinců Zajišťuje zachování dosud nejlepších jedinců Může znatelně urychlit řešení

Parametry genetických algoritmů 

Počet jedinců v generaci



Pravděpodobnost křížení



Pravděpodobnost mutace

Pravděpodobnost křížení a mutace:  

2 nejzákladnější parametry GA. Pravděpodobnost křížení:  Udává

četnost křížení  0%  nová populace je kopií původní.  100%  každý potomek je stvořen pomocí křížení 

Pravděpodobnost mutace:  Udává

četnost mutace nových potomků.  100%  Každý chromozóm je pozměněn  0 %  Ani jeden není pozměněn.

Předčasná konvergence

Stagnace

Škálování 

Škálování - úprava ohodnocení jedinců, aby bylo dosaženo požadovaného selekčního tlaku:

σ   

f m ax f avg

Lineární škálování: fi '  a  fi  b Parametry a, b jsou spočítány tak, aby platilo:  průměrná

hodnota fitness se nezmění (takže f'avg =

favg) a  maximální hodnota f'max bude nejvýše c ×f'avg.  c je parametrem metody (1,5 – 2,0)

Efekt lineárního škálování

Teorie schémat 

Teorie schémat  Založena

na protěžování dominantních vzorů, zastoupených v aktuální populaci  Propagovány s velkou frekvencí do dalších generací. Z těchto vzorů je poskládáno výsledné optimální řešení.  Nutný předpoklad: problém musí být dekomponovatelný na menší podproblémy

Teorie schémat 

Schéma  Řetězec

obsahující 0, 1, * (“cokoliv”)  Schéma zahrnuje právě 2r řetězců, kde r je počet * ve schématu   

Příklad schématu: 10**0* Jedinci odpovídající výše uvedenému schématu: 100000, 100001, 100100, 100101, 101000, 101001, 101100, 101101

Teorie schémat 

Řád schématu   



O(S) je počet specifikovaných pozic ve schématu S pro S = (0,1,*,*,0,1,*) » o(S) = 4 schéma řádu o(S) pokrývá 2L-o(S) řetězců

Definiční délka schématu (kompaktnost) d(S) je největší vzájemná vzdálenost dvou specifických symbolů  Schéma S = (0,1,*,*,0,1,*) má d(S) = 5 

 

Schémata řádu 0 a 1 mají definiční délku 0 Fitness schématu 



f(S) je průměrná fitness všech řetězců v populaci, pokrytých daným schématem

Četnost výskytu schématu v populaci v čase t: m(S,t)

Vlastnosti genetických algoritmů (+) Dají se použít pro řešení problémů jinak těžko řešitelných (například, když interakce mezi jednotlivými částmi jsou těžko popsatelné). (+) Většinou neuváznou v lokálním extrému. (+) Vždy poskytnou nějaké řešení. (+) Jsou snadno implementovatelné a paralerizovatelné . (−) Nemáme žádnou záruku, že nalezené řešení je optimální. (−) Někdy mohou být velmi pomalé (obzvlášt’ pokud nejsou dobře navrženy reprezentace jedinců a operátory křížení a mutace). (−) Vyžadují vhodné nastavení většího množství parametrů algoritmu (naprˇ. PC, PM, p).

Využití  

Optimalizační úlohy Úlohy, kde neznáme algoritmus řešení, nebo je tento algoritmus výpočetně příliš náročný  Rozvrhování  Automatické

navrhování elmech. systémů  Optimalizace rozmístění telekomunikačních zařízení  Učení neuronových sítí  Učení robotů  Zkoumání a vývoj léků

Příklady aplikací GA       

Optimalizace nákládání kontejnerů Učení chování robotů. Optimalizace infrastruktury pro mobilní komunikaci. Optimalizace struktury molekul. Návrh uspořádání výrobních hal. Různé plánovací problémy (např. když jednotlivé úlohy jsou navzájem závislé). Predikce akciových trhů