10. Parametrizace výpočetních metod v chemii. Lokální vs. globální optimalizační metody. Příklad: Parametrizace potenciálové funkce Obecný zápis: f:Rn-> R Konkrétně: Ukážeme si? jak modelovat tuto veličinu Energie ohýbám vazebných úhlů s um a p ř e s v š e c hny vazebné úhly Energie deformace torzních úhlů - suma pře s všechny toizníúhly Vazebné interakce Energie van der Energie elektrostatických Waalsových interakcí interakcí - suma pře s vš e chny - suma pře s vš e chny dvojice atomu dvojice atomu Nevazebné interakce Příklad: Parametrizace potenciálové funkce - energie pnutí vazeb Pro reálnou chemickou vazbu je závislost potenciální energie (EB) této vazby na délce (1) dané vazby popsána křivkou: oj c LU Abychom mohli z 1 vypočítat EB, musíme najít rovnici EB = f(l), která by odpovídala výše uvedené křivce. Příklad: Parametrizace potenciálové funkce - energie pnutí vazeb Vhodnou funkcí je např. Morseův potenciál: EBM =De.(l-eaa-l°)f De disociační energie vazby a konstanta, příslušející vazbě mezi atomy určitých typů 1 délka vazby 10 délka ideální vazby První pokus o modelování závislosti EB = f(l). Přesné, ale nepohodlné. Každý typ vazby totiž vyžaduje 3 parametry (konstanty): De, a a 10. Tyto parametry musíme vypočítat na základě experimentálních dat. Příklad: Parametrizace potenciálové funkce - energie pnutí vazeb Proto se pro modelování pnutí vazeb využívá často harmonický potenciál: EBH = ^(i-i0ý kB konstanta, příslušející vazbě mezi atomy určitých typů Vztah pro výpočet EBH byl odvozen z Hookova zákona. Tento model závislosti EB = f(l) se využívá v silových polích AMBER, CHARMMaTRIPOS. Harmonický potenciál je méně přesným modelem než Morseův potenciál. Při výpočtu nás však většinou zajímají hodnoty EB pro 1 blízké l0av této oblasti odpovídá harmonický potenciál reálnému velmi dobře Příklad: Parametrizace potenciálové funkce - energie pnutí vazeb Daší možné funkce: Kubický potenciál: */=-f (/-/0)2(l-2(/-/0)) Využívá se v silovém poli MM2. Kvadratický potenciál: EBQ = (/ - kf [l - 2,55. (Z-/0) + ^ (2,55. (Z - Z0)): Využívá se v silovém poli MM3. Příklad: Parametrizace potenciálové funkce Podobně jako energii pnutí vazeb modelujeme i další členy potenciálové funkce. Např. Potenciálová funkce pro AMBER 4.1 vypadá takto: energie pnutí vazeb energie deformace vazebných úhlů energie rotace vazeb (torze) ^totaJ =(Žbonds Kr(r - reg)^^Eailgies Ke(9 - 8eg) vdW energie elektrostatická energie Příklad: Parametrizace potenciálové funkce - parametry silového pole Každému atomovému typu přísluší následující parametry: • Charakteristiky atomu*: vdW poloměr, náboj atomu, relativní hmotnost atomu, vaznost a geometrie vazeb. • Ideální parametry pro interakce atomu*: Délky vazeb, vazebné úhly a torzní úhly. • Konstrainty: Silové konstanty, určující, jak moc je odchylka od ideálních parametrů nevýhodná. *Je míněn libovolný atom, náležející k danému atomovému typu. Příklad: Parametrizace potenciálové funkce - ideální parametry interakcí Vazby a úhly: • délky vazeb, velikosti vazebných úhlů - z RTG krystalografie • silové konstanty - z empirických dat (vibrační frekvence) Torze: přizpůsobení torzní potenciálové funkce tak, aby co nejpřesněji reprodukovala experimentální (nebo ab initio kvantově mechanické) energetické bariéry Globální optimalizace Zatím jsme se zabývali jen lokálními optimalizačními metodami. Nyní se zaměříme na globální optimalizace Typy optimalizací Globální optimalizace: • Hledání nejhlubšího minima v daném intervalu Hledání globálního - obecně Obecné metody: • Systematické prohledávání • Náhodnostní metoda Heuristické metody • Simulované žíhání • Genetické algoritmy • Difuzní metody Systematické prohledávání Anglicky označováno grid search. Princip: Rozdelí vícerozměrný prostor, nad kterým je funkce definována na části pomocí vícerozměrné mřížky. Vypočítá pro každou část funkční hodnoty. Projde všechny funkční hodnoty a nalezne nejmenší z nich. V některých implementacích této metody analogickým způsobem prohledá okolí minima, nalezeného v předchozím kroku atd. Systematické prohledávání II Zhodnocení: Výhody: Nalezne všechna minima. Nevýhody: Složitost je vysoká - odpovídá součinu Pi.P2.....Pn> kde V{ je počet dílů mřížky pro i-tou proměnnou a N je rozměrů prostoru, nad kterým je studovaná funkce definována. Náhodnostní metoda Princip: V rámci každého kroku výpočtu je vypočítáno mnoho hodnot studované funkce pro náhodně vybrané hodnoty proměnných (tyto hodnoty jsou ovšem náhodně vybrány z určitého regionu). Poté je nalezena nejmenší hodnota funkce a ta se stane středem nového regionu (který má menší rozměry než původní region). Zhodnocení: Použitelné, ale pouze při dostatečně velkém počtu vypočítaných funkčnch hodnot v každém kroku. Nevýhodou je velká složitost metody. Simulované žíhání - obecně Počátkem 80. let dostali Kirkpatrick, Gelatt, Vecchi a Černý nápad, že problém hledání globálního minima funkce může být realizovatelný podobným způsobem jako žíhání tuhého tělesa a nazvali ho metodou simulovaného žíhání. Simulované žíhání - fyzikální interpretace Energie je funkcí uspořádání atomů zkoumaného tělesa v prostoru. Před každou iterací simulace se hodnota energie tělesa nachází v lokálním minimu. Simulované žíhání - fyzikální interpretace II V průběhu simulace zahřejeme těleso na vysokou teplotu. Tím se jeho atomům v rámci každé iterace umožní překonat energetickou bariéru a dostat se z výchozího lokálního minima do dalšího lokálního (případně i globálního) minima. Během simulace se energie lokálních minim snižuje. E Simulované žíhání - fyzikální interpretace III minimum x Simulované žíhání - fyzikální interpretace IV V průběhu simulace je také postupně snižována teplota, což má za následek, že se polohy atomů fixují. Takže při konečné teplotě žíhání (podstatně nižší než byla počáteční) j sou atomy tělesa rozmístěny tak, aby jejich energie byla globálním energetickým minimem. Simulované žíhání - matematická interpretace Uvažujme hypotetický systém popsaný n-rozměrným stavem x = (xpx2 ,...,xj, kde xt patří do nejakého intervalu. Stavy tohoto systému j sou ohodnoceny funkcí/, která přiřadí každému hodnotu y=fW- Simulované žíhání - matematická interpretace II Naší úlohou je najít takový stav xmin, ve kterém nabývá funkce/globálního minima. Nechť x je přípustný stav systému, ten přejde do nového stavu x Formálně zapsáno x '=Opert(x), kde Opert je "operátor" poruchy - perturbace. Simulované žíhání - matematická interpretace III Otázka, zda bude nový stav akceptován do dalšího procesu, se řeší pomocí tzv. Metropolisova kritéria, které určuje pravděpodobnost nahrazení starého stavu novým. Celý tento vztah lze zapsat: P (x -> x) = 1 pro f(xO < f(x) |f(x')-f(x)| P (x -> x') = e Ť pro f (x') > f(x) kde T je parametr, interpretovaný jako teplota. Simulované žíhání - matematická interpretace IV V případě, že nový stav x' má menší nebo stejnou funkční hodnotu jako původní stav x, provedeme záměnu stavu x stavem xV opačném případě je nový stav x' akceptován s pravděpodobností: 0 < P (x -> x) < 1 Simulované žíhání - matematická interpretace V Nechť R je náhodné číslo z intervalu (0,1). Potom je nový stav akceptován, pokud pro R platí: R < P (x -> x) Jinak se proces opakuje s původním stavem x. Simulované žíhání - matematická interpretace VI Závislost pravděpodobnosti přijmutí nového stavu na teplotě T: P(x->x') křivka pravděpodobnosti Simulované žíhání - matematická interpretace VII Hodnota parametru T podstatně ovlivňuje hodnotu pravděpodobnosti. Pro velké hodnoty T je tato pravděpodobnost blízká jedné (tj. přijmou se téměř všechny nové stavy), ale blíží-li se T k nule, potom pravděpodobnost přijmutí je velmi nízká, téměř nulová. Simulované žíhání - matematická interpretace VIII Při vhodném nastavení počáteční "teploty" Tmax (větší hodnota) metoda simulovaného žíhání prohledává nejprve prostor řešení silně stochasticky a přijímá i stavy s horším ohodnocením než má současné řešení. Tato vlastnost simulovaného žíhání je velmi důležitým rysem, protože poskytuje možnost snadno se dostat z lokálního extrému a prohledat i j iné oblasti v prostoru řešení. Simulované žíhání - matematická interpretace IX Možnost realizovat energeticky nevýhodné přechody se pak postupně snižuje úměrně se zmenšováním hodnoty T. Pro malé T připustí Metropolisovo kritérium akceptování už jen lepšího řešení než je současné. Simulované žíhání - příklad aplikace Úkol: Je dána molekula, urči konformace této molekuly, které jsou v definovaném chemickém prostředí nej stabilnější. Konformace = uspořádání atomů v prostoru. Strukturní vzorec: Konformace: H H H H H H \ C / H H Židličková r~wA v /■ v r v • 11 • vi r Zkrizena zídlickova H H H H Vaničková Poloviční židličková Simulované žíhání - příklad aplikace II Popíšeme vztah mezi souřadnicemi a E t: Epoi = 2* * sN^/ s\e\ Energie pnuti vazeb - suma pře s všechny vazby Energie ohýbáni vazebných úhlu suma přes všechny vazebné úhly Energie deformace torzních úhlu - suma přes všechny toizní úhly Vazebné interakce + Energie van der Waalsových interakcí - suma přes všechny dvojice atomů Energie elektrostatických interakcí - suma přes všechny dvojice atomů Nevazebné interakce Simulované žíhání - příklad aplikace III Grafem potenciálové funkce Potenciálová funkce: Simulované žíhání - příklad aplikace IV Hledáme globální minimum hyperplochy. Simulujeme konformační chování molekuly v chemickém prostředí pomocí tzv. molekulové dynamiky: Každý atom molekuly se pohybuje jistou rychlostí. Z poloh a rychlostí atomů a sil působících v rámci systému v čase t určíme polohy atomů v čase t +dt (a samozřejmě i rychlosti atomů a síly a tomto čase). Simulované žíhání - příklad aplikace V V rámci této simulace využíváme pro překonání vysokých energetických bariér simulované žíhání. Díky simulovanému žíhání dodáme molekule tepelnou energii, díky které může molekula překonat danou energetickou bariéru. Simulované žíhání - příklad aplikace VI Příklad snímků molekulové dynamiky - dekamer alaninu 1. snímek: 15. snímek: 30. snímek: Ság* 45. snímek: 60. snímek: ^1 ^';J't -vs Genetické algoritmy - obecně Jsou založeny na Darwinově evoluční teorii: a) Populace jsou variabilní, proměnlivost je náhodná vzhledem k prostředí a je dědičná. b) Populace mají neomezenou kapacitu růstu, ale potravní a prostorové zdroje jsou omezené => mezi jedinci musí existovat „boj o přežití". c) Potomky plodí hlavně nejlépe vybavení jedinci, a tím přenášejí své genetické vlastnosti ve zvýšené míře do dalších generací => zastoupení genetických vlastností vhodných pro dané prostředí se tak stále zvyšuje. d) Díky tomuto přirozenému výběru se druhy přizpůsobují (adaptují) prostředí. Genetické algoritmy - obecně II Genetické algoritmy se snaží využít modelů evolučních procesů, aby tak nalezly řešení náročných a rozsáhlých úloh. Veškeré takové modely mají několik společných rysů: 1) pracují zároveň s celou skupinou možných řešení zadaného problému 2) řešení postupně vylepšují zařazováním nových řešení, získaných kombinací těch původních 3) kombinace řešení jsou následovány náhodnými změnami (mutacemi) a vyřazováním nevýhodných řešení Genetické algoritmy - obecně III Kvalita jedince neboli jeho schopnost přežít bývá také někdy označována síla genů případně v angličtině fitness. V genetice je fitness funkcí struktury genů studovaného organismu. Při aplikaci evolučních modelů pro hledání globálního minima funkce f: Rn -> R, platí: matematika genetika x bod v Rn geny studovaného jedince f(x) funkční hodnota fitness jedince s geny x funkce f v bodě x Genetické algoritmy - příklad Graf závislosti fitness jedinců na složení jejich genotypu (A). V tomto jednoduchém případě se jedná o organismus s dvoj genovým chromozómem, přičemž jeho složky jsou reálná čísla. Konturový graf (B) odpovídá povrchu fitness, oblak bodů znázorňuje populaci jedinců. Genetické algoritmy - obecně IV Základní myšlenkou genetických algoritmů je snaha napodobit evoluci živočišného druhu a takto vzniklý algoritmus použít při řešení úloh, které se vyskytuj í ve složitém, případně i měnícím se prostředí, kde programátor není schopen dopředu nadefinovat všechny vzniklé případy a správné reakce na ně. Genetické algoritmy - obecně V V přírodě a tedy i v genetických algoritmech platí, že kvalitnější jedinci se častěji rozmnožují a také déle přežívají, proto zanechávají více potomků, kteří nesou dál část jejich genetické informace. Přesto je tento výběr ovlivněn náhodou, neboť se i kvalitní řešení vybírají k dalšímu přežití úměrně své kvalitě, ale náhodně. V informatice pro tento tzv. kvazináhodný výběr podle kvality používáme zařízení nazývané ruleta. Genetické algoritmy - obecně VI Situaci, kdy se většina jedinců natolik zkříží, že by další křížení produkovalo stejné jedince, a tudíž nemělo smysl, brání mutace. Mutace také nabízejí možnost adaptovat populaci na měnící se prostředí, ale musí se provádět jen u malého procenta populace, protože často už dobré řešení spíše pokazí. Genetické algoritmy - implementace Z populace se kvazináhodně vyberou dva chromozomy, které si křížením vymění část řetězců. Výsledné chromozomy se pak ještě podrobí mutaci, která překlopí náhodně zvolený bit. Tato dvojice se vrací do populace, kde vytěsní dvojici kvazináhodně vybraných chromozomů s malou silou. kvaziriáhodný výběr "ruletou populace chromozomů kvaziriáhodný výběr vyřazovaných chromozomů "inverzní ruletou" krizeni mutace Genetické algoritmy - implementace II Chromozom je nejčastěji implentován lineární posloupností symbolů, např. bitovým řetězcem. Každý chromozom je ohodnocen funkcí, která mu přiřadí tzv. sílu, vyjádřenou kladným reálným číslem. Čím má chromozom větší sílu, tím je kvalitnější. Genetické algoritmy - implementace III Příklad implementace genetického algoritmu: t:=0; P0 := náhodně vygenerovaná populace chromozomů; ohodnoť každý chromozom z populace P silou; whilet velká změna hodnoty • Přičtením náhodného malého čísla blízkého nule k původní hodnotě Genetické algoritmy - genetické programování Na přelomu 80. a 90.let americký informatik John Koza ze Stanfordské univerzity navrhl originální modifikaci genetického algoritmu, kterou nazval genetické programování. Při tomto přistupuje původní reprezentace chromozomů znakovými řetězci nahrazena složitějšími funkcemi. V nejjednodušší verzi genetického programování se funkce rovnají výrazům obsahujícím proměnné, konstanty, základní aritmetické operace a elementární funkce. Genetické algoritmy - využití Velké uplatnění nacházejí genetické algoritmy při vytváření rozvrhů práce pro stroje v továrnách, v teorii her, v managementu, pro řešení optimalizačních problémů multimodálních funkcí, při řízení robotů, v rozpoznávacích systémech a v úlohách umělého života. Genetické algoritmy překvapivě dobře fungují při řešení problémů, kde téměř všechny ostatní algoritmy selhávají, např. pro NP-úplné problémy, tj. kde výpočetní čas je exponenciálně nebo faktoriálně závislý na počtu proměnných. Nemá však smysl je používat u relativně jednoduchých optimalizovaných funkcí nebo u funkcí, pro které existují specializované algoritmy. Difúzni metody Minimalizovaná funkce je postupně měněna tak, že ubývají lokální minima, až zaniknou všechna s výjimkou globálního. Jsou prováděny například změny: - příspěvky ve směru kolmém k hyperploše => pro minima vzrůstá energie a pro maxima a sedlové body energie klesá