Představte si, že existuje daný počet měst. A mezi nimi jsou silnice o daných délkách. Vaším úkolem je najít nejkratší možnou trasu, vycházející z jednoho z měst, procházející všemi městy a vracející se nazpět do výchozího města. To je Problém obchodního cestujícího (TSP, podle anglického Travelling Salesman Problem) v kostce.
Zní to docela jednoduše. Ve skutečnosti je to ale obtížný optimalizační problém, který patří mezi takzvané NP-těžké úlohy. Pro malý počet měst je to velice snadné, prostě prozkoumáte všechny možnosti a najdete nejkratší cestu. S rostoucím počtem měst ale velice rychle vzrůstá počet možných řešení a záhy dojdou výpočetní síly i dnešním superpočítačům. Pro představu, pro čtyři města existují tři možné cesty. Pro osm měst už ale počet možných cest vzroste na 2520.
Jak říká Wikipedie, u takových úloh není obecně známo jak pro každý vstup nalézt přesné řešení v rozumném čase, ani to, zda vůbec může existovat algoritmus, který takové řešení najde v čase úměrném nějaké mocnině počtu uzlů. Takové úlohy se v praxi řeší pouze přibližně, heuristickými algoritmy, které rezignují na optimální řešení.
Masashi Aono z japonské Keio University v Tokiu a jeho tým pojali šílený nápad, že nechají Problém obchodního cestujícího počítat hlenky. Ve skutečnosti k tomu samozřejmě měli dobré důvody a navazovali na dřívější výzkum, ale z pohledu nadšeného laika je to pozoruhodná šílenost. K výzkumu si najali hlenky vápenky mnohohlavé (Physarum polycephalum), tedy mikroskopické eukaryotní organismy s komplikovaným životním cyklem, které tráví život v podobě améb, plazmódií, cyst i bičíkovců. Ve vlhkých koutech lesů bývají viditelné pouhým okem a připomínají oranžové plivance.
Aby Aono a spol. mohli zapojit do výzkumu hlenky, tak samozřejmě museli postavit důmyslně uspořádaný experiment. Vápenky se účastnily experimentu v podobě plazmódia o hmotnosti cca 12 mg, které si pochutnávalo na ovesných vločkách a sedělo ve speciálním čipu. Díky tomuto experimentu vědci zjistili, že hlenky najdou rozumný, tedy optimálnímu řešení blízký výsledek Problému obchodního cestujícího velmi rychle. Když vzroste počet měst v TSP problému ze čtyř na osm, tak čas, který hlenky potřebují k řešení, vzroste jen lineárně.
Je pravda, že konvenční počítače při tomhle počtu měst také naleznou heuristická řešení v lineárním času. Hlenky to ale dělají úplně jinak, než tradiční lidské algoritmy. Počítače řeší Problém obchodního cestujícího mnohem rychleji než améby, zvláště pro malý počet měst. Postup, který používají hlenky, je ale pozoruhodný, a mohl by se stát základem pro nové algoritmy a výpočetní postupy, s nimiž bude možné hledat přibližná řešení výpočetně náročných problémů v lineárním, čili rozumném čase.
Video: Physarum: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism
Video: Traveling Salesman Problem - Visualized Algorithms
Literatura
Phys.org 20. 12. 2018, Royal Society Open Science online 19. 12. 2018.
Hlenky si pamatují
Autor: Jaroslav Petr (06.02.2008)
Hlenky a jejich důmyslná strategie přežití
Autor: Dagmar Gregorová (12.07.2010)
Hlenky sahají po rostlinných sedativech
Autor: Dagmar Gregorová (17.06.2011)
V rychlostním souboji tváří v tvář zvítězil kvantový počítač
Autor: Stanislav Mihulka (10.05.2013)
Diskuze:
Novák Jiří,2018-12-28 11:29:10
Jak to teda ty hlenky dělají? Dá se to nějak snadno shrnout? To horní video jsem vůbec nepochopil, krom toho že je jaksi stimulovali světlem a v tom dolním videu jsou myslím si věci docela známé... Ještě tedy vím o optimalizaci na základě genetického algoritmu, což se tomu dolnímu trochu podobá. Ale co hlenky? :-)
Re:
Milan Krnic,2018-12-28 13:37:05
Zvládáte to anglicky?
https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html
Re:
Milan Krnic,2018-12-28 20:25:55
Zajímavé je, že jak to ta hlenka dělá, nikdo neví.
Zde je dobré podotknout, že nejen, že netušíme, jak funguje mozek, a ani jak fungují námi vytvořené neuronové sítě.
Biologické čtvrtky ve Viničné; J. Romportl: Umělá inteligence v přirozeném světě; přednáška
https://www.youtube.com/watch?v=WiGqIVWhlfM
následovaná diskuzí
https://www.youtube.com/watch?v=rQ-XURKOH28
Re: Re:
Novák Jiří,2018-12-28 21:30:16
Ale jo, anglicky není problém, ale ten lenoch ve mě doufal, že tu bude někdo, kdo mi to v krátkosti vysvětlí (když to v článku nebylo). No neva, díky za odkaz.
Sranda je, že ani přesná funkce převodní soustavy srdeční není tak úplně jasná. Natož pak neurony.
Re: Re: Re:
Milan Krnic,2018-12-28 21:50:29
Natož pak hlenky, chuděrky, týrané vědci.
V krátkosti to jde jedině tak, jak jsem napsal :)
Sranda je právě to, že rozumíme tomu, jak je to zadrátované, ale té funkci, která běží nad tím, už nikoli. Odkazovanou přednášku fakt doporučuji ... jen tedy ten zvuk, no :-/...
Zkoušíme to nějak uchopit, ale nemyslím si, že můžeme uchopit sami sebe (je asi jedno, zda sebe, nebo hlenku, nebo "AI", principy jsou stejné), a tedy že to nezvládnou ani ty stroje. V tomto je si každý roven, bych řekl.
Re: Re:
Novák Jiří,2018-12-28 21:42:09
No ani tak mi to není moc jasný. K čemu tam tu amébu vůbec potřebujou? To by přece mělo jít simulovat přimo nějakým programem. A místo osvětlování kanálků prostě přiřazovat prměnné. Nebo jsem to celé jenom nepochopil.
Re: Re: Re:
Milan Krnic,2018-12-28 22:02:13
Primárně kašlem na hlenku, důležité je to pro neuronové sítě. Čekáme na nějakou revoluci (snad to nebude, jako z fyzikou). :)
Dál to chtějí vyzkoušet na vyšším počtu a uvidí se.
Re:
Jaroslav Lesák,2018-12-29 00:55:51
Nemohu se zbavit dojmu, že jde o aprílový žert, i když máme konec prosince. Pokud z videa mohu soudit, žádnou výpočetní schopnost hlenky tam nevidím, zrovna tak dobře by posloužil generátor náhodných čísel. Jakési optimalizace se dosahuje tím svícením, to je ale popsané dost vágně. Naopak jsem si ve videu všiml několika věcí, které celou věc dále zpochybňují.
1. testovací úlohy jsou takové, že optimální řešení je vidět na první pohled
2. délky dílčích cest mají takové rozdělení, že je umění najít hodně špatnou cestu
3. algoritmus najde několik výhodných dílčích sekvencí, ale neřeší jejich navázání
Takže nejspíš apríl!
Re: Re:
Milan Krnic,2018-12-29 01:29:01
Výpočetní schopnost hlenky nevidíte proto, že ta nepočítá. Nepočítá dokonce ani neuronová síť. Dojmy jsou pěkné, těch se držte.
1) a 2) I pokud by to tak bylo, je to jedno, protože jde o učení NS.
3) Jaký algoritmus? O žádném algoritmu studie nepojednává, zejména proto, že NS provádí modelování.
Re: Re: Re:
Jaroslav Lesák,2018-12-29 11:57:25
Asi jsme četli každý nějaký jiný článek. V tom článku, co jsem četl já, se slovní spojení "neuronová síť" vůbec nevyskytuje. Ale je tam napsáno ...vědci zjistili, že hlenky najdou rozumný, tedy optimálnímu řešení blízký výsledek ... a také ...Postup, který používají hlenky, je ale pozoruhodný, a mohl by se stát základem pro nové algoritmy ...
Re: Re: Re: Re:
Milan Krnic,2018-12-29 16:05:55
Tento článek je napsaný poněkud zjednodušeně, tedy co se zkusit podívat do diskuze?
Jinak pokud je někde spojka, měl byste citovat, což se tedy dělá v uvozovkách, včetně. "nové algoritmy a výpočetní postupy". A tam kupodivu NS zapadá.
Re: Re: Re:
David Nečas,2019-01-02 16:48:37
Pakliže hlenka nepočítá, tedy neřeší tu optimalizační úlohu, vracíme se k původní otázce: Co hlenka dělá, co by nezvládl generátor náhodných čísel (a zřejmě mnohem efektivněji)? A není-li hlenka nezbytná, tak k čemu tam je? Aby to celé vypadalo zajímavě a hrozně vědecky?
Re: Re: Re: Re:
Milan Krnic,2019-01-03 13:29:19
Myslím, že je jasné, že améba nic nepočítá, té je naše matematika ukradená.
Generátor náhodných čísel nedokáže bažit po potravě, distribuovat živiny po těle a bát se světla.
Pokud nemáme uspokojivé numerické řešení, pozorujeme, jak si s takovým problémem poradí příroda, a snažíme se poučit od ní.
Re: Re: Re: Re: Re:
David Nečas,2019-01-08 09:02:06
Buď mluvím do zdi, nebo jste cílová skupina přesně takovýchto článků, která se snadno nechá unést tím, jak je to celé vědecky komplikované, a neptá se, zda to dává sebemenší smysl...
O čem konkrétně se od přírody (hlenky) poučujeme ohledně řešení toho optimalizačního problému?
Re: Re: Re: Re: Re: Re:
Milan Krnic,2019-01-08 13:05:10
Už jsem psal, že nevíme, jak funguje hlenka. Tedy můžeme těžko odpovědět na otázku, v čem konkrétně se poučujeme. Ale to není nic zvláštního, nevíme ani, jak funguje neuronová síť. To, jak to funguje, není podstatné v případě, že nám to dává uspokojivý výsledek. Na nějaká videa, která vám můžou pomoci to pochopit, jsem odkazoval výše.
Dojmy a pocity jsou věc užitečná, obzvláště v diskuzi, těch se držte :)
Diskuze je otevřená pouze 7dní od zvěřejnění příspěvku nebo na povolení redakce
