Model NK - NK model
The Model NK je matematický model popsal jeho primární vynálezce Stuart Kauffman jako „ladně robustní“ fitness krajina. „Nastavitelná robustnost“ vystihuje intuici, že celkovou velikost krajiny i počet jejích místních „kopců a údolí“ lze upravit změnami jejích dvou parametrů, a , s být délkou řetězce evoluce a stanovení úrovně členitosti krajiny.
Model NK našel uplatnění v nejrůznějších oborech, včetně teoretického studia evoluční biologie, imunologie, optimalizace, technologický vývoj, a složité systémy. Model byl rovněž přijat v roce 2006 organizační teorie, kde se používá k popisu způsobu činidlo může prohledávat krajinu manipulací s různými jejími charakteristikami. Například agent může být organizace, představují kopce a údolí zisk (nebo jejich změny) a pohyb v krajině vyžaduje organizační rozhodnutí (jako je přidání produktových řad nebo změna organizační struktury), která mají tendenci vzájemně interagovat a ovlivňovat zisk komplexním způsobem.[1]
Časná verze modelu, která považovala pouze za nejhladší () a nejodolnější () krajiny, byl představen v Kauffman a Levin (1987).[2] Model, jak je v současné době znám, se poprvé objevil v Kauffmanovi a Weinbergerovi (1989).[3]
Jedním z důvodů, proč model přilákal širokou pozornost optimalizace je, že se jedná o obzvláště jednoduchou instanci tzv NP-úplný problém[4] což znamená, že je těžké najít globální optima. Nedávno se ukázalo, že je také model NK pro K> 1 PLS - kompletní[5] což znamená, že obecně je obtížné najít ani místní fitness optima. To má důsledky pro studium otevřená evoluce.
Matematické detaily
Model NK definuje a kombinační fázový prostor, skládající se z každého řetězce (vybraného z dané abecedy) délky . Pro každý řetězec v tomto vyhledávacím prostoru a skalární hodnota (nazývaná zdatnost ) je definováno. Pokud vzdálenost metrický je definován mezi řetězci, výsledná struktura je a krajina.
Hodnoty zdatnosti jsou definovány podle konkrétní inkarnace modelu, ale klíčovým rysem modelu NK je, že zdatnost daného řetězce je součet příspěvků od každého místa v řetězci:
a příspěvek každého lokusu obecně závisí na jeho stavu a stavu další loci ,:
kde je index ten soused lokusu .
Proto funkce fitness je mapování mezi řetězci délky K. + 1 a skaláry, které Weinbergerova pozdější práce nazývá „příspěvky na fitness“. Takové příspěvky na zdatnost se často vybírají náhodně z nějakého specifikovaného rozdělení pravděpodobnosti.
V roce 1991 zveřejnil Weinberger podrobnou analýzu[6] případu, ve kterém a příspěvky na fitness jsou vybrány náhodně. Ukázalo se, že jeho analytický odhad počtu místních optim byl chybný[Citace je zapotřebí ]. Numerické experimenty obsažené ve Weinbergerově analýze však podporují jeho analytický výsledek, že očekávaná vhodnost řetězce je obvykle distribuována s průměrem přibližně
a rozptyl přibližně
.
Příklad
Pro zjednodušení budeme pracovat binární struny. Zvažte model NK s N = 5, K. = 1. Zde je kondice řetězce dána součtem jednotlivých příspěvků na fitness z každého z 5 lokusů. Každý příspěvek na fitness závisí na hodnotě místního místa a na jednom dalším. Použijeme konvenci , takže každý lokus je ovlivněn sousedem a pro cyklickost. Zvolíme-li například funkci fitness F(0, 0) = 0; F(0, 1) = 1; F(1, 0) = 2; F(1, 1) = 0, hodnoty fitness dvou ukázkových řetězců jsou:
Laditelná topologie
Hodnota K. řídí stupeň epistáza v modelu NK, nebo kolik dalších lokusů ovlivňuje fitness příspěvek daného lokusu. S K. = 0, zdatnost daného řetězce je jednoduchý součet jednotlivých příspěvků lokusů: pro netriviální funkce zdatnosti globální optimum je přítomný a snadno lokalizovatelný (genom všech 0s, pokud F(0) > F(1) nebo všechny 1 s, pokud F(1) > F(0)). Pro nenulovou hodnotu K., fitness řetězce je součet fitness podřetězců, které mohou interagovat s zmařit systému (ve výše uvedeném příkladu zvažte, jak dosáhnout optimální kondice). Vzrůstající K. tak zvyšuje odolnost fitness krajiny.
Variace s neutrálními mezerami
Holý model NK nepodporuje fenomén neutrální prostor - tj. sady genomů spojených jednotlivými mutacemi, které mají stejnou fitness hodnotu. Byly navrženy dvě úpravy biologicky důležitá struktura. The Model NKP zavádí parametr : podíl z příspěvky na fitness jsou nastaveny na nulu, takže příspěvky několika genetických motivů jsou zdegenerovány[Citace je zapotřebí ]. The Model NKQ zavádí parametr a vynucuje diskretizaci ohledně možných hodnot příspěvků na fitness, aby každý příspěvek měl jednu z možné hodnoty, což opět zavádí degeneraci do příspěvků z některých genetických motivů[Citace je zapotřebí ]. Holý model NK odpovídá a případy podle těchto parametrizací.
Aplikace
Model NK našel uplatnění v mnoha oblastech, včetně studia rotující brýle, epistáza a pleiotropie v evoluční biologie, a kombinatorická optimalizace.
Reference
- ^ Levinthal, D. A. (1997). "Adaptace na drsné krajiny". Věda o řízení. 43 (7): 934–950. doi:10,1287 / měsíc 43,7,934.
- ^ Kauffman, S .; Levin, S. (1987). „Směrem k obecné teorii adaptivních procházek po drsné krajině“. Journal of Theoretical Biology. 128 (1): 11–45. doi:10.1016 / s0022-5193 (87) 80029-2. PMID 3431131.
- ^ Kauffman, S .; Weinberger, E. (1989). „NK model drsných fitness krajin a jeho aplikace na zrání imunitní odpovědi“. Journal of Theoretical Biology. 141 (2): 211–245. doi:10.1016 / s0022-5193 (89) 80019-0. PMID 2632988.
- ^ Weinberger, E. (1996), „NP-úplnost modelu Kauffman N-k, Tuneably Rugged Fitness Landscape“, Santa Fe Institute Working Paper, 96-02-003.
- ^ Kaznatcheev, Artem (2019). „Výpočetní složitost jako nejvyšší omezení vývoje“. Genetika. 212 (1): 245–265. doi:10.1534 / genetika.119.302000. PMC 6499524. PMID 30833289.
- ^ Weinberger, Edward (15. listopadu 1991). „Místní vlastnosti Kauffmanova modelu N-k: laditelně členitá energetická krajina“. Fyzický přehled A. 10. 44 (10): 6399–6413. Bibcode:1991PhRvA..44,6399W. doi:10,1103 / physreva.44,6399. PMID 9905770.