Evoluční modelování

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 30. září 2017; kontroly vyžadují 8 úprav .

Evoluční výpočet využívá rysy Darwinovy ​​teorie k  budování inteligentních systémů (metody skupinového účetnictví, genetické algoritmy ) . Je součástí širší oblasti umělé inteligence  - výpočetní inteligence .

Evoluční modelování je již poměrně zavedenou oblastí, ve které je možné rozlišit:

  1. modely vzniku molekulárně genetických informačních systémů;
  2. modelování obecných vzorců evoluce ( Evoluční algoritmy ). Jsou to systémy, které využívají pouze evolučních principů. Byly úspěšně použity pro úlohy typu funkční optimalizace a lze je snadno popsat matematickým jazykem. Patří mezi ně evoluční algoritmy, jako je evoluční programování , genetické algoritmy , evoluční strategie , genetické programování ;
  3. evoluční modely. Jedná se o systémy, které jsou biologicky realističtější než evoluční algoritmy, ale neukázaly se jako užitečné v aplikovaném smyslu. Jsou spíše biologické systémy a méně se zaměřují na řešení technických problémů. Mají složité a zajímavé chování a zřejmě brzy najdou praktické využití. Mezi tyto systémy patří tzv. umělý život .
  4. aplikované evoluční modelování.

Historie

Použití darwinovských principů pro automatizované řešení problémů začalo v 50. letech 20. století. Do roku 1960 se na třech různých místech rozvíjely tři různé interpretace této myšlenky. Evoluční programování zavedl Lawrence J. Vogel v USA, zatímco John Henry Holland nazval jeho metodu genetickým algoritmem . V Německu představili Ingo Rechenberg a Hans-Paul Schwefel evoluční strategický přístup . Tyto oblasti byly samostatně vyvíjeny asi 15 let. Od počátku 90. let byly sjednoceny jako „dialekty“ jediné technologie zvané evoluční výpočty. Počátkem devadesátých let se navíc objevil čtvrtý proud – genetické programování . Od 90. let 20. století se evoluční výpočetní technika do značné míry spojuje s myšlenkou swarm intelligence a přírodou inspirované algoritmy se stávají stále významnější součástí tohoto trendu.

Pojmy "evoluční programování", "evoluční strategie", "genetické algoritmy" a "genetické programování" jsou tedy považovány za zvláštní případy obecného pojmu "evoluční počítání" nebo "evoluční modelování".

Modelování evoluce pomocí myšlenek evolučních algoritmů a umělého života začalo prací Nielse Aalla Barricelliho v 60. letech 20. století a rozšířil jej Alex Fraser, který publikoval řadu prací o modelování umělého výběru . [1] Evoluční algoritmy se staly zavedenou optimalizační technikou jako výsledek práce Ingo Rechenberga v 60. a na počátku 70. let, který je používal k řešení složitých inženýrských problémů. [2] Genetické algoritmy se staly obzvláště populární díky práci Johna Hollanda . [3] Spolu s růstem akademického zájmu umožnil dramatický nárůst výkonu počítačů praktické aplikace, včetně automatické evoluce počítačových programů. [4] Evoluční algoritmy se v současnosti používají k řešení vícerozměrných problémů efektivněji než software vyvinutý člověkem. [5]

Obecná myšlenka

Obrázek ukazuje schéma fungování jedné z odrůd evolučních výpočtů - genetického algoritmu (GA), ale lze jej použít k pochopení obecné myšlenky přístupu.

Počáteční populace je chápána jako určitý počet získaných objektů, obvykle náhodně. V GA jsou takovými objekty vektory („genotypy“) genů, kde každý gen může být bit, číslo nebo nějaký jiný objekt. Evoluční strategie (ES) pracuje s vektory reálných čísel. V genetickém (GP) a evolučním (EP) programování hrají roli objektů programy, které stále lépe (podle určité fitness funkce) řeší zadaný výpočetní problém.

Mutace a křížení

Mutace je náhodná změna v „genotypu“. V GA a ES může být operátor mutace implementován jednoduchým přidáním normálně distribuované náhodné proměnné ke každé složce vektoru. V GP a EP tato operace silně závisí na způsobu kódování pěstovaných programů. Například u stromového kódování (viz obrázek) to lze provést náhodnou změnou informací v uzlu nebo přidáním či odstraněním uzlu nebo celého podstromu.

Operátor "crossover" vytváří rekombinaci kandidátských řešení, jejichž role je v podstatě podobná roli crossoveru. Reprodukce je v evolučních výpočtech obvykle pohlavní – k produkci potomků je zapotřebí několika rodičů, obvykle dvou. Reprodukce v různých algoritmech je definována odlišně – záleží samozřejmě na reprezentaci dat. Hlavním požadavkem pro reprodukci je, aby potomci nebo potomci měli možnost zdědit vlastnosti obou rodičů a nějakým způsobem je „namíchat“.

Výběr (výběr)

Ve fázi selekce je nutné vybrat určitý podíl z celé populace, která v této fázi evoluce zůstane „naživu“. Existují různé způsoby výběru. Pravděpodobnost přežití jedince h musí záviset na hodnotě tzv. fitness funkce Fitness(h). Tato funkce by měla být nastavena tak, aby její hodnota pro daný genotyp (genový vektor, výsledky pěstovaného programu) mohla být použita k posouzení míry úspěšnosti daného genotypu. Samotná míra přežití je obvykle parametrem genetického algoritmu a je jednoduše daná předem. V důsledku selekce musí z N jedinců populace H zůstat sN jedinců, kteří budou zahrnuti do konečné populace H'. Zbytek jedinců zemře.

Modely pro vznik molekulárně genetických informačních systémů

Na počátku 70. let 20. století se nositel Nobelovy ceny M. Eigen působivě pokusil vybudovat modely pro vznik systémů zpracování molekulárně genetické informace v rané biosféře Země [ 6] . Nejznámější z nich je model „quasispecies“, který popisuje jednoduchý vývoj polynukleotidových (informačních) sekvencí. V návaznosti na Eigen v roce 1980 novosibirští vědci V. Ratner a V. Shamin navrhli model „sizerů“ [7] .

Model kvazidruhů uvažuje postupný vývoj populace informačních sekvencí ( vektorů ), jejichž složky nabývají malého počtu diskrétních hodnot. Fitness "jednotlivců" v modelech je dán jako funkce vektorů. V každé fázi dochází k selekci jedinců v populaci další generace s pravděpodobnostmi úměrnými jejich zdatnosti a také mutace jedinců – náhodné ekvipravděpodobné záměny složek vektoru.

Sizer model v nejjednodušším případě uvažuje systém tří typů makromolekul : polynukleotidový templát a translační a replikační enzymy kódované tímto templátem. Polynukleotidová matrice je jako paměťové zařízení, které ukládá informace o funkčních jednotkách měřiče - enzymech. Translační enzym zajišťuje "výrobu" libovolného enzymu podle informací zaznamenaných v matrici. Replikační enzym zajišťuje kopírování polynukleotidového templátu. K vlastnímu rozmnožování stačí kleště . Zařazením dalších enzymů kódovaných polynukleotidovým templátem do schématu měřiče je možné zajistit měřiče jakékoli vlastnosti, například schopnost regulovat syntézu určitých enzymů a přizpůsobovat se změnám vnějšího prostředí. [osm]

Aplikace v problémech funkční optimalizace

Evolutionary computing (EC) se často používá k organizaci stochastického vyhledávání, zejména v případě multimodálních problémů, kdy deterministické optimalizační metody nebo jednodušší stochastické metody neumožňují studovat chování objektivní funkce mimo oblasti lokálního optima. EV metody nezaručují nalezení globálního optima v polynomiálním čase. Praktický zájem o ně je dán tím, že tyto metody, jak ukazuje praxe, umožňují najít lepší (nebo „dost dobré“) řešení velmi obtížných vyhledávacích problémů za kratší dobu než jiné metody obvykle používané v těchto případech. Typickým omezením jejich použití je nutnost (k sestavení dobrého řešení) opakovaně počítat účelovou funkci (slovo „opakovaně“ obvykle znamená čísla od stovek do milionů). Přesto se metody EV ukázaly jako docela efektivní pro řešení řady skutečných problémů v inženýrském návrhu, plánování, směrování a umístění, správě portfolia, hledání optimálních energetických stavů chemických a molekulárních struktur, jakož i v mnoha dalších oblastech, které umožňují vhodný soubor reprezentací, operátorů, objemů a struktur populací atd.

Evoluční modelování jako výzkumná metoda v informatice

Protože se zdá, že základem mechanismu zpracování informací v přírodních systémech je evoluce, výzkumníci se snaží vytvořit teoretické a počítačové modely, které skutečně vysvětlují principy tohoto mechanismu (viz „ Přírodní informatika “). Výzkum v této oblasti se vyznačuje pochopením, že modely by měly obsahovat nejen zrození a smrt populací, ale také něco mezi tím. Nejčastěji se jedná o následující koncepty.

Swarm intelligence popisuje kolektivní  chování decentralizovaného samoorganizujícího se systému. V teorii umělé inteligence je považována za optimalizační metodu. Termín zavedli Gerardo Beni a Wang Jing v roce 1989 v kontextu systému celulárních robotů [9] . Rojové zpravodajské systémy se zpravidla skládají ze sady agentů ( Multi-agent system ) lokálně interagujících mezi sebou a s prostředím. Samotní agenti jsou obvykle docela prostí, ale všichni dohromady, lokálně interagující, vytvářejí takzvanou inteligenci roje. Příkladem v přírodě je kolonie mravenců , roj včel , hejno ptáků, ryb...

Kolektivní inteligence  je termín, který se objevil v sociologii v polovině 80. let při studiu procesu kolektivního rozhodování. Výzkumníci z NJIT definovali kolektivní inteligenci jako schopnost skupiny nacházet řešení problémů, která jsou lepší než nejlepší individuální řešení v dané skupině.

Sociologický směr - jelikož lidská společnost je skutečný, navíc dobře pozorovatelný a dokumentovaný (na rozdíl od lidského mozku), nástroj pro zpracování informací, sociologické metafory a reminiscence jsou v pracích o kybernetice a příbuzných oblastech přítomny již od jejich vzniku. Pokud je rojová inteligence zaměřena na získávání komplexního chování v systému z jednoduchých prvků, tento přístup naopak zkoumá konstrukci jednoduchých a speciálních objektů na základě složitých a univerzálních: „stát je hloupější než většina jeho členů “ [10] . Tento směr se vyznačuje touhou dávat definice sociologických pojmů z oblasti informatiky. Takže v [11] je elita definována jako nositel určitého soukromého modelu reálného světa a základ (tedy lid) hraje roli arbitra mezi elitami. Evoluční proces spočívá v generování a smrti elit. Základ není schopen pochopit podstatu myšlenek a modelů prezentovaných elitami a neklade si takový úkol. Právě díky své neangažovanosti si však zachovává schopnost jasného emočního posouzení, což mu umožňuje snadno odlišit charismatické elity od těch chátrajících, které se snaží udržet si svá privilegia, uvědomujíc si, že jejich představa či model se nepotvrdil.

Velké konference

Poznámky

  1. ↑ Fraser AS Monte Carlo analýzy genetických modelů   // Příroda . - 1958. - Sv. 181 , č.p. 4603 . - S. 208-209 . - doi : 10.1038/181208a0 . — PMID 13504138 .
  2. ↑ Rechenberg, Ingo. Evolutionsstrategie - Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD práce)  (německy) . Fromman-Holzboog, 1973.
  3. ↑ Holland, John H. Adaptace v přírodních a umělých systémech  . - University of Michigan Press , 1975. - ISBN 0-262-58111-6 .
  4. ↑ Koza, John R. Genetické programování  (neurčité) . - MIT Press , 1992. - ISBN 0-262-11170-5 .
  5. ↑ Jamshidi M. Nástroje pro inteligentní řízení: fuzzy regulátory, neuronové sítě a genetické algoritmy  (anglicky)  // Filosofické transakce. Řada A, Matematické, fyzikální a inženýrské vědy : deník. - 2003. - Sv. 361 , č.p. 1809 . - S. 1781-1808 . doi : 10.1098 / rsta.2003.1225 . — PMID 12952685 .
  6. ↑ Eigen M., Schuster P. Hypercyklus. Principy organizace makromolekul / Per. z angličtiny. vyd. M. V. Volkenstein a D. S. Chernavsky. — M.: Mir, 1982. — 270 s.
  7. ↑ Ratner V. A., Shamin V. Sizers: modelování základních rysů molekulárně biologické organizace. Korespondence společných vlastností a konstrukčních znaků skupin makromolekul // Zh. celkový biologie. - 1983. - T.44. Ne. 1. - c.51-61.
  8. ↑ Arutsev A. A., Ermolaev B. V., Kutateladze I. O., Slutsky M. S. Koncepty moderní přírodní vědy. Tutorial. - M., 2007.
  9. ↑ Beni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. Pokročilý seminář NATO o robotech a biologických systémech, Toskánsko, Itálie, 26. až 30. června (1989)
  10. ↑ Wiener N. Kybernetika aneb Řízení a komunikace u zvířete a stroje. / Per. z angličtiny. I. V. Solovjov a G. N. Povarov; Ed. G. N. Povařová. — 2. vydání. — M.: Nauka; Hlavní vydání publikací pro zahraničí, 1983. - 344 s.
  11. ↑ Igor Weisband. 5000 let informatiky. M. - "Černá veverka", 2010
  12. ↑ Mezinárodní konference o evoluční výpočetní teorii a aplikacích (nepřístupný odkaz) . ECTA. Získáno 29. dubna 2013. Archivováno z originálu 10. května 2013. 
  13. ↑ Special Interest Group on Genetic and Evolutionary Computation (odkaz není dostupný) . SIGEVO. Získáno 29. dubna 2013. Archivováno z originálu 15. července 2012. 
  14. ↑ Paralelní řešení problémů z přírody (downlink) . Získáno 6. března 2012. Archivováno z originálu dne 4. května 2012. 

Literatura

  Přejděte na položku Wikidata  Slovníky a encyklopedie
V bibliografických katalozích