Credit: Zhu et al.
Point
■「巡回セールスマン問題」は、巡回先が増えることで計算量が爆発的に増える問題として知られる
■迷路を解く知性のあるアメーバを利用して、「巡回セールスマン問題」を解かせるようにデザインされた実験が行なわれる
■その結果、巡回先が増えても解を出すのにかかった時間は、線形的にしか増えなかった

どんどん、生き物とコンピューターの垣根が取り払われていくようです。

単純な単細胞生物で、体のほとんどがゼラチン状の原形質でできているアメーバ。このアメーバが、多くの計算力を要する巡回サラリーマン問題の適切な解を効率的に導けることが分かりました。研究を率いているのは慶応大学の青野真士准教授で、論文は「Royal Society Open Science」で発表されています。

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

巡回セールスマン問題とは

Credit: Saurabh.harsh / 巡回セールスマン問題を総当たりで解く場合のイメージ。左側で一つずつ探していき、より効率のいいルートが見つかった場合、右側のグラフが更新される

巡回セールスマン問題(TSP)とは、複数の町を重複することなく一周する経路を見つけるという問題で、なるだけ短い距離になるような解を見つけるのが目的です。つまり、巡回する町の数が増えると、指数関数的に必要となる計算量が増えます。例えば、4つの町を巡回する場合は、組み合わせは3通りしかありませんが、これが8つの町に増えると組み合わせは2520通りにまで増えてしまうのです。

新たな研究でわかったのは、アメーバがTSPの適切な（ほぼ最適な）解を見つけることができ、町の数が増えた際にかかる計算時間が町の数に比例する程度にしか増加しなかったということです。通常のコンピューターによるアルゴリズムの中には比例時間で解を見つけるものもありますが、その方法とアメーバによる解法は全く異なるものです。

研究に使われたのは、アメーバであるモジホコリ。モジホコリにはある種の知性があることが示されており、迷路において最短経路を見つけることができます。飼育も容易で、オートミールを含む寒天培地で育てられます。不定形の体を常に変形させながら、一秒間に1mmの速さで、仮足を伸ばしたり引っ込めたりして動く可愛い生物です。

アメーバがTSPの適切な解を導く

実験には、64本の狭い通路が放射状に並んだテンプレートが使われました。これで、アメーバのいる寒天培地を覆って、その動きをチャンバーと通路内に限定します。アメーバは中央のチャンバー内で飽和しますが、64本の細い通路に仮足を伸ばすことはできます。

アメーバは寒天からの栄養摂取を最大するため、できるだけ広がって通路に伸びようとします。しかし、アメーバには光を嫌う性質があります。通路には選択的に光が差すような仕掛けがしてあり、アメーバの足を意図的に退縮させることができるようになっています。

この実験装置において、TSPを解くために次のような割当がなされました。例えば町が4つの場合、通路にはAからDまでが割り振られます。もし、アメーバの足が最終的に、A4、B2、C1、D3のように伸びた場合、数字は訪れた順番を表すため、アメーバの選んだ巡回ルートの解はC->B->D->A->Cのようになります。

ここで、適切な解をアメーバに出させるために重要になってくるのが、通路に当てる光のコントロールです。光のコントロールにはニューラルネットワークが適応され、6秒ごとにアップデートが行われました。通路を照らす条件は次のようなものです。もしA3をアメーバが占めている場合、A1やA2といった他のすべてのAが照らされ、侵入できなくなります。それによって、セールスマンは同じ町に再び訪れることはなくなります。また、B3、C3、D3といった同じ数字の通路も照らされ、セールスマンが同時に他の街に現れないようにします。

そして、町の間には距離のパラメーターが割り振られています。もし、アメーバがB2の通路を専有して、次にC3とD3に同時に足を伸ばしている場合を見てみましょう。ここで、町Bと町Cの距離に100、町Bと町Dの距離に50の数値が割り振られているとします。この場合、距離の長いC3の通路が照らされることで、D3の通路が選ばれるようになります。

このような操作を施すことで、アメーバの自然の探索運動が安定したときには、TSPの解が示されていることになります。短い経路を示す通路は光っていないので、自然とアメーバは足を伸ばすことになり、それによって、示された解は最適解に近いものとなるのです。

こうしてアメーバにTSPを解かせるのですが、そのときに要した時間は街の数が多くなった場合も、街の数に比例した程度の増加しか見られませんでした。これは必要とされると見込まれる計算量から考えると非常に早いといえます。また、その違いはもっと町の数が増えたときに顕著となるでしょう。

研究者たちはまた、このアメーバの特性を取り込んだ、TSPの解を導くシミュレーション「AmoebaTSP」を開発。そこで、問題を解く際にかかる時間における法則性を見出しています。しかし、アメーバが提示する解が最適に近いものになる理由は、今のところ分かっていません。

 

アメーバをコンピューター代わりに使って問題を解決するというのは面白い発想です。もっと町の数を増やしてTPSを解かせると、コンピューターとのスピード勝負で勝てるかもしれません。一見、その時の通路の数を考えると不可能そうですが、モジホコリは培養するとなんと最大5m2にもなるそうです。あれ、もしかして可能…？

 

「生物学的なウィルス」を活用した高速コンピューターを開発

 

referenced: Phys.Org / written by SENPAI / edited by Nazoloy staff

 

コンピューター顔負け！？ 「アメーバ」が難問「巡回セールスマン問題」を解明！