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

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


Diskuze je otevřená pouze 7dní od zvěřejnění příspěvku nebo na povolení redakce








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