アメーバの一種「モジホコリ」を使って数学の難問「巡回セールスマン問題」を解くことができると判明

by The Lazy Artist Gallery

アメーバはべん毛や繊毛を持たず、細胞質を突出させた仮足を用いて移動する原生生物の総称です。日本の研究チームがモジホコリというアメーバの一種を使い、数学の難問として知られる「巡回セールスマン問題」を解くことに成功したと発表しています。

Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism | Royal Society Open Science
https://royalsocietypublishing.org/doi/full/10.1098/rsos.180396

Amoeba finds approximate solutions to NP-hard problem in linear time
https://phys.org/news/2018-12-amoeba-approximate-solutions-np-hard-problem.html

An Amoeba-Based Computer Calculated Approximate Solutions to a Very Hard Math Problem - Motherboard
https://motherboard.vice.com/en_us/article/gy7994/an-amoeba-based-computer-calculated-approximate-solutions-to-a-very-hard-math-problem

慶應義塾大学の環境情報学部准教授である青野真士氏らの研究チームは、原形質流動によって移動して落ち葉や朽ち木の表面などに生息するアメーバの一種「モジホコリ」を使い、巡回セールスマン問題の解決に当たらせるという実験を行いました。モジホコリは脳を持たないにもかかわらず、高度な知能に匹敵するような記憶力・判断力を持っていることで知られる単細胞生物です。

脳や神経がないのに迷路を解き、融合することで記憶を共有する黄色いスライム「モジホコリ」の不思議な力 - GIGAZINE

巡回セールスマン問題とは組合わせ最適化問題の一種であり、同じ都市を2度訪問せずに複数の都市全てを訪問し、出発点に戻ってくる最短ルートを導き出すというもの。巡回セールスマン問題は巡回するべき都市の数が増えるにつれて、コンピューターが問題を解決するのに必要な時間が指数関数的に増えることで知られています。たとえば訪問都市が4つである場合は最適解のルートが3つしかありませんが、訪問都市が8つに増えた場合、最適解のルートが2520個にまで増加してしまいます。

研究チームは計64個の狭いルートを持つ星形プレートの下にモジホコリの栄養源となる寒天プレートを置き、その上にモジホコリをのせました。実験では研究チームがモジホコリに「巡回セールスマン問題を解くアルゴリズム」を与え、モジホコリはそのアルゴリズムに従って解を導き出すという一種のコンピューター的役割を果たしています。実験をまとめたムービーがこれ。

Physarum: Remarkable problem-solving ability of unicellular amoeboid organism and its mechanism


モジホコリは秒速1mmのスピードで原形質を動かして仮足を伸ばし、プレート上を自由に動くことが可能です。モジホコリはなるべく多くの面積を寒天プレートと接触することで栄養を最大限吸収しようとしますが、光を嫌う性質を持っているために光で照らされた部分に体を広げることはできません。研究チームは星形プレートのルートを選択的に光で照らすことができる装置を開発し、狙ったルートからモジホコリを後退させることができるようになっていました。

実験ではそれぞれのルートに「A1」～「H8」までの番号が振られました。

モジホコリが仮足を新たに伸ばした部分を赤、仮足を引っ込めた部分を青で示すとこんな感じ。

栄養を最大限摂取するべくルートに足を伸ばすモジホコリですが、研究チームは巡回セールスマン問題を解かせるために「光を嫌う」というモジホコリの性質を利用しています。研究チームはカメラでモジホコリの様子をフィードバックして、ルートに対する光の照射を6秒ごとに切り替えています。

たとえばモジホコリが「A3」というルートを占有した場合、A1・A2・A4～A8のルートに光が照射されてモジホコリが侵入できなくなります。また、B3・D3……H3のルートにも光が照射されてモジホコリの侵入を防ぐため、モジホコリはB～Hのうち、それぞれ1・2、4～8の番号のいずれかを選ぶことになります。

このアルゴリズムによってモジホコリはA～Hのアルファベットと1～8の数字の組み合わせにおいて、それぞれ1回ずつしか使わない組み合わせ(例：B1-D2-H3-A4-C5-G6-F7-E8)に仮足を伸ばすことになります。つまりアルファベットは訪問する都市を、番号は訪問する順序を表しており、それぞれ1回しか使われないということはモジホコリによる同じ都市への訪問は一度しか行われないということを示しています。

さらに研究チームは都市間の距離を表すため、「モジホコリがルート『B2』を占有し、さらに『C3』および『D3』に同様のペースで仮足を伸ばした場合、都市Bからの距離が遠いと設定された都市Cのルートに対しては光を照射する」といった操作を行いました。これにより、ルートC3からは光によって仮足が後退するものの、Bからの距離が近いD3へはこれまで通り仮足を伸ばすことが可能。

モジホコリの動きに対応して特定のルートに対して光を当てることで、モジホコリは全ての都市を訪問する最短距離のルートを見つけ出すことが可能になります。これが研究チームがモジホコリに与えるアルゴリズムであり、アルゴリズムに従ってモジホコリが移動を行うことで巡回セールスマン問題の近似値を導き出すことができます。

また、巡回セールスマン問題では都市の数が増えるにつれて問題の複雑さが指数関数的に増大しますが、モジホコリが巡回セールスマン問題を解くスピードは都市数が増えても指数関数的に増大することはありませんでした。

今のところ少ない都市数ではアメーバよりもコンピューターの方がはるかに早く問題を解くことが可能ですが、研究チームは今後もアメーバのコンピューティング能力を向上させていくとしています。将来的には大規模なアメーバコンピューターを製造することで、何百もの都市を用いた巡回セールスマン問題を解決できるようになると研究者は期待しています。