Články

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.

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.

Š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.

Článek pokračuje zde.