Elektronická hlenka našla řešení „obchodního cestujícího“ v rozumném čase  
Hlenky jsou skvělé optimalizátorky. Bravurně řeší neblaze proslulý Problém obchodního cestujícího. Japonský tým užasl natolik, že postavil biomorfní elektronickou hlenku. A jak se zdá, tak to trefili. Optimalizuje jako divá. Do budoucna by se elektronické hlenky mohly rozlézt do počítačů a do Internetu věcí.
Elektronická hlenka. V jednoduchosti je síla. Kredit: Amoeba Energy.
Elektronická hlenka. V jednoduchosti je síla. Kredit: Amoeba Energy.

Téměř přesně před dvěma lety ohromil svět japonský tým, který vedl Masashi Aono z Keio University v Tokiu, když nechal živé hlenky vápenky mnohohlavé počítat slavný Problém obchodního cestujícího (TSP, Travelling Salesman Problem). Je to slavná úloha a zároveň záludný a těžký optimalizační problém, kdy hledáte co nejkratší trasu při daném počtu měst, tak abyste vyšli z jednoho města, prošli všechny ostatní města a vrátili se zpět. Vypadá to úplně jednoduše, ale s rostoucím počtem měst extrémně stoupá počet možných cest, které je nutné prověřit. Poměrně brzy kapitulují i superpočítače první ligy.

 

Jednobuněčná hlenka mnohohlavá umí makroskopické struktury. Kredit: Masashi Aono.
Jednobuněčná hlenka mnohohlavá umí makroskopické struktury. Kredit: Masashi Aono.

Šikovné hlenky, což jsou jednobuněčné organismy, očividně v Japonsku udělaly dojem. Po dvou letech se tenhle výzkum vrací v překvapivém, řekněme biomorfním obratu. Seiya Kasai z Hokkaido University a jeho kolegové totiž postavili elektronickou hlenku. Je to analogový počítač, jehož struktura je inspirovaná hlenkou a jejím chováním. S tímto analogovým počítačem dokázali napodobit optimalizační dynamiku hlenky, která je skvělá ve vyladění příjmu potravy, aby z toho měla co největší zisk.

 

Elektronickou hlenku tvoří hlenkové jádro (amoeba core), které hledá řešení v elektronickém prostředím, plus platforma s nastavenými hodnotami odporu (resistance crossbar), které vyjadřují omezení a požadavky dané Problémem obchodního cestujícího. Díky této platformě je možné jednoduše měnit podobu zadání problémů, aniž by bylo nutné složitě předělávat celou elektronickou hlenku.

 

Výkony elektronické hlenky. Kredit: Masashi Aono.
Výkony elektronické hlenky. Kredit: Masashi Aono.

Ačkoliv je to bezesporu šílená záležitost, elektronická hlenka si vede skvěle. Když změřila síly s typickým algoritmem pro řešení Problému obchodního cestujícího, který nese označení „2-opt“, tak byla o maličko pozadu při zadáním s nejmenším počtem měst. Jakmile ale počet měst stoupl, tak elektronická hlenka naprosto dominovala. Jak říká Kasai, optimalizační mistrovství hlenky, které jí nadělil přírodní výběr, zaslouží uznání. A můžeme ho využít.

 

Souhlasí s ním i Masashi Aono, který teď vede společnost Amoeba Energy. Jejich cílem je podporovat vývoj i praktické využití hlenkových výpočetních technologií. Podle Aonoa by analogové počítače s hlenkovou architekturou mohly řešit řadu reálných problémů podobného charakteru.

 

Video: Amoeba-inspired Analog Electronic Computing System for Solving the Travelling Salesman Problem

 

Literatura

Hokkaido University 10. 12. 2020.

Scientific Reports 10: 20772.

Datum: 12.12.2020
Tisk článku

Zvěrolékař na cestách - Cranston Jonathan
 
 
cena původní: 299 Kč
cena: 239 Kč
Zvěrolékař na cestách
Cranston Jonathan
Související články:

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)
Hlenky řeší Problém obchodního cestujícího neobyčejným způsobem     Autor: Stanislav Mihulka (27.12.2018)
Unikátní escherovský čip simuluje interakce částic v hyperbolické geometrii     Autor: Stanislav Mihulka (15.07.2019)
Experimentální fotonický čip dosáhl ďábelské přenosové rychlosti 44,2 Tb/s     Autor: Stanislav Mihulka (23.05.2020)
Počítač s největším čipem porazil superpočítač Joule v rychlosti výpočtů     Autor: Stanislav Mihulka (29.11.2020)



Diskuze:

Analógový počítač

Vladimír Bzdušek,2020-12-15 23:03:06

Spred 40 rokov si z cvičení z anológových počítačov si matne pamätám, že
analógový počítač rieši statický problém (rovnicu) okamžite, v reálnom čase,
diferenciálnu rovnicu rieši v redukovanom-normalizovanom čase.

Ak je možné zostaviť (elektronický) model TSP, tak riešenie by malo byť okamžité,
bez ohľadu na počet miest,
a s okamžitou reakciou na zmenu koeficientov, t.j. zmenu polohy jednotlivých miest,
hoci by sa menili aj všetky odrazu.

Odpovědět

Optimalizace

Josef Šoltes,2020-12-14 10:41:51

A jak to ta hlenka dělá, to se asi nedozvíme, že? Respektive je to BLACK BOX.

Odpovědět



Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace