Дослідники продемонстрували, що амеба - одноклітинний організм, що складається в основному з гелеобразної протоплазми - володіє унікальними обчислювальними здібностями, які одного разу можуть запропонувати конкурентоспроможну альтернативу методам, що використовуються в звичайних комп'ютерах.
Вчені на чолі з Масасі Аоно з Університету Кейо призначили амебу для вирішення завдання комівояжера (TSP). TSP - це завдання оптимізації, мета якого полягає в тому, щоб знайти найкоротший маршрут між кількома містами, щоб кожне місто відвідувалося рівно один раз, а початкова і кінцева точки збігалися.
Проблема пошуку складна, і це означає, що з ростом числа міст час, необхідний комп'ютеру для її вирішення, зростає в геометричній прогресії. Складність обумовлена великою кількістю можливих рішень. Наприклад, для чотирьох міст існує тільки три можливих маршрути. Але для восьми міст число можливих маршрутів збільшується вже до 2520.
У новому дослідженні вчені виявили, що амеба може знайти розумні (майже оптимальні) рішення для TSP за проміжок часу, який зростає тільки лінійно, так як число міст збільшується від чотирьох до восьми. Хоча звичайні комп'ютери також можуть знаходити наближені рішення за лінійний час, підхід амеби повністю відрізняється від традиційних алгоритмів. Як пояснюють вчені, амеба досліджує простір розчину шляхом безперервного перерозподілу гелю в його аморфному тілі з постійною швидкістю, а також шляхом обробки оптичного зворотного зв'язку паралельно, а не послідовно.
Хоча звичайний комп'ютер все ще може вирішувати TSP набагато швидше, ніж амеба, особливо для невеликих завдань, нові результати є інтригуючими і можуть призвести до розробки нових аналогових комп'ютерів, які отримують наближені рішення складних завдань набагато більших розмірів в лінійній час.
Як це влаштовано
Специфічним типом амеби, яку використовували вчені, був плазмодій або «справжня слизова цвіль», який важить близько 12 мг і споживає вівсяні пластівці. Ця амеба постійно деформує своє аморфне тіло, багаторазово подаючи і видаляючи гель зі швидкістю близько 1 мм/секунду, створюючи псевдоподібні придатки.
У своїх експериментах дослідники помістили амебу в центр зірчастого чіпа, який являє собою круглу пластину з 64 вузькими каналами, що виступають назовні, а потім помістили чіп поверх пластини з агаром. Амеба знаходиться всередині чіпа, але все ще може рухатися в 64 канали.
Щоб максимізувати поглинання поживних речовин, амеба намагається розширюватися всередині чіпа, щоб увійти в контакт з якомога більшою кількістю агара. Однак амеба не любить світло. Оскільки кожен канал може бути вибірково висвітлений світлом, можна змусити амебу відступити від освітлених каналів.
Щоб змоделювати TSP, кожен канал в зірковому чіпі являє собою впорядковане місто на маршруті продавця. Наприклад, у випадку з чотирма містами, позначеними A-D, якщо амеба займає канали A4, B2, C1 і D3, то відповідним рішенням для TSP є C, B, D, A, C.
Щоб направити амебу до оптимального або майже оптимального рішення, ключ полягає в управлінні світлом. Для цього дослідники використовують модель нейронної мережі, в якій кожні шість секунд система оновлює, які канали підсвічуються. Модель включає інформацію про відстані між кожною парою міст, а також зворотний зв'язок від поточної позиції амеби в каналах.
Модель гарантує, що амеба знайде правильне рішення для TSP кількома способами. Наприклад, як тільки амеба зайняла певну частину певного каналу, скажімо, A3, канали A1, A2 і всі інші канали «A» підсвічуються, щоб заборонити відвідування міста A двічі. Крім того, B3, C3, D3 і всі інші «3» канали підсвічуються, щоб заборонити одночасні відвідування декількох міст.
Модель враховує відстані між містами, спрощуючи освітлення каналів, що представляють міста з більш довгими відстанями, ніж з більш короткими відстанями. Наприклад, скажімо, амеба займає канал B2 і почала вторгатися в канали C3 і D3 в рівних заходах, а відстань між містами B і C дорівнює 100, а відстань між містами B і D дорівнює 50. Більша відстань між B і C зрештою змушує систему висвітлювати канал C3, викликаючи відступ амеби з цього каналу, але дозволяючи їй продовжувати рух в D3.
В цілому, моделювання TSP за допомогою амеби використовує природну тенденцію амеби до пошуку стабільної рівноваги. Оскільки канали, що представляють більш короткі маршрути, з меншою ймовірністю будуть освітлені, амеба може поширюватися в цих каналах і продовжувати досліджувати інші неосвітлені канали, щоб максимізувати площу своєї поверхні на пластині агара.
Дослідники також розробили комп'ютерну симуляцію під назвою AmoebaTSP, яка імітує деякі основні особливості того, як амеба вирішує проблему, в тому числі безперервний рух гелю, коли він подається з постійною швидкістю і виводиться з різних каналів.
У майбутньому дослідники планують ще більше поліпшити обчислювальні здібності амеби.
«Ми розглянемо далі, як ці складні просторово-часові коливальні динаміки підвищують обчислювальну продуктивність при пошуку рішень більш високої якості за більш короткий час», - сказав співавтор роботи Сонг-Джу Кім в університеті Кейо. «Якщо це можна уточнити, знання сприятимуть створенню нових аналогових комп'ютерів, які використовують просторово-часову динаміку електричного струму в його ланцюгу».
"Звичайно, запускаючи деякі інші алгоритми на традиційних цифрових комп'ютерах для лінійного часу, ми можемо отримати приблизні рішення для TSP. З іншого боку, при запуску наших імітаційних моделей (AmoebaTSP або його розроблених версій) на традиційних комп'ютерах, як ми це робили в цьому дослідження, аналогова і паралельна просторово-часова динаміка вимагають нелінійного часу для моделювання їх як цифрових і послідовних процесів, тому ми намагаємося отримати набагато більш якісні рішення, ніж ті, які отримані з традиційних, запустивши наші моделі на аналогових комп'ютерах для лінійного часу ".
Дослідники також очікують, що, виготовивши більш велику мікросхему, амеба зможе вирішити проблеми TSP з сотнями міст, хоча для цього будуть потрібні десятки тисяч каналів.