【巡回セールスマン問題】アメーバを使って数学の難問を解くことに成功

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

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

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

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

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

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


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

続きはソースで


GIGAZINE
https://gigazine.net/news/20181225-amoeba-solves-hard-math-problem/

【恐怖】脳喰いアメーバの御姿がこちら →画像

http://2ch-matomenews.com/643812/

【性別実験】研究『女の子の玩具か男の子の玩具か』試してみた　

http://2ch-matomenews.com/633412/

【衝撃】ロシアが20世紀に行っていた『犬体実験』がこちら →動画像

http://2ch-matomenews.com/349810/

【なんて鳴く？】世界各国の人々に『犬と猫の鳴き声』をマネしてもらった結果

http://2ch-matomenews.com/690974/

【美少女】可愛かった女子小学生は成長しても美人なのか確かめてみた →画像

http://2ch-matomenews.com/350898/

7: 2018/12/25(火) 17:11:13.36

こういう生き物の力を借りるのって面白いよな。

日本地図の入れ物を作って、大都市部分にエサおいて、ベムベラベロか何かアメーバ状の生き物に 道すじを描かせて鉄道や道路の参考にすんだろ。

23: 2018/12/25(火) 18:58:17.39

「巡回セールスマン問題」は量子コンピュータのテーマだよね。

68: 2018/12/26(水) 10:47:24.25

ナビにこの機能つけないのはなぜかと思っていたが、そもそも解けてないのか

2: 2018/12/25(火) 16:51:50.83

> 研究チームは星形プレートのルートを選択的に光で照らすことができる装置を開発し、狙ったルートからモジホコリを後退させることができるようになっていました。

人為が介入してる時点で意味ないじゃん

3: 2018/12/25(火) 17:00:47.15

光は立ち入りを禁止するためであり、数学における「ただし～とする」という条件に相当する。

8: 2018/12/25(火) 17:15:03.59

>>1
まぁ解けたといっても近似解を見つけることができたということだな。難問で解法はまだ知られていない。

9: 2018/12/25(火) 17:19:36.44

9割くらいの確率で最適解を出すのか

13: 2018/12/25(火) 17:26:27.51

こういう方向性での知的生命体ってのが宇宙にはいるかもしれないな 進歩や思考速度は恐ろしくゆっくりだろうが

10: 2018/12/25(火) 17:20:42.08

アメーバ　にもできるのにおまいらって…

16: 2018/12/25(火) 17:43:48.86

>>1
アメーバ >>> AI >>> 人類　ってことですねよくわかりました

19: 2018/12/25(火) 18:08:49.87

知能ってなんなんだろ

20: 2018/12/25(火) 18:35:02.38

こういうのは知能とは全く関係ない。
例えば、ランダムな凹みのある平面に水を流し込めば 水はキッチリ全ての凹みを埋めていくが、 水はその凹みの深さを知っている訳では無いし、体積を知っている訳でもない。

単に物理的必然に従ったに過ぎない。
量子焼鈍しコンピュータなんかも原理は同様。 最も安定した状態に収束しようとする物理法則の力を借りているだけ。 つまり、アメーバさんはそういう自然現象に近い存在だって事だな。

22: 2018/12/25(火) 18:58:08.27

原始的だとか馬鹿にするけど、襟鞭毛虫の仲間が人間に進化するのと同じ時間を過ごしているんやで。

特務士官が兵学校出たての少尉より技能に優れているのはむしろ当たり前やろ。

24: 2018/12/25(火) 19:05:22.96

>>1
面白い
人が楽をしたいという感情をアメーバの無駄なことをしないという性質に置き換えたのか 気持ちの問題として気持ちで解く 感情の原点が見えるようだ

37: 2018/12/25(火) 19:55:23.29

考えるってのは脳ではなくて別のところでやってるのかもね。脳はあくまで受信機であると。

39: 2018/12/25(火) 20:01:28.60

考えてるわけないだろう
先っちょが本能というか物理法則に従ってるだけで

45: 2018/12/25(火) 21:14:22.39

多細胞生物から見た難問も単細胞生物から見ればごく簡単な問題に過ぎない。不思議の国のアリスのような話だが、知性という物の奥深さを垣間見る思いだ。

28: 2018/12/25(火) 19:11:00.37

>>1
これか？
日本全国のルーター　最短経路候補

27: 2018/12/25(火) 19:09:46.25

>>1
ずいぶん昔に、粘菌か何かで迷路を解く実験なかったっけ？ あれの猿真似に思えるんだけど

29: 2018/12/25(火) 19:13:45.24

平成初期に　ミトコンドリアは学習能力があるんじゃね？という発見があったような

それを題材にしたのがパラサイトイブ

48: 2018/12/25(火) 22:39:30.92

ちょうど１０年前に同じようなことでイグノーベル賞が取られているよ それを踏まえた上での発展形じゃないのかなこれ

50: 2018/12/25(火) 23:45:16.49

粘菌だろ。３回目のイグ・ノーベル賞受賞確定かな。粘菌にも永世イグ・ノーベル賞を与えて欲しい。

57: 2018/12/26(水) 06:28:14.94

距離が遠いルートほど光が当たって仮足を後退させるらしいけど このアルゴリズムならアメーバを使うまでもなくシミュレーションできそうな気も…？

59: 2018/12/26(水) 07:02:48.36

ソースだとまだn=8程度だし
このシステムだとn^2本の通路が必要だから 大規模化にも限度がありそうな… 面白い話だし研究の進展には期待してるけども

79: 2018/12/27(木) 05:07:14.19

ずーっと前に粘菌でやってた奴の二番煎じ 物理現象を利用して全ルート検索すると、ってこと 最短距離の確定値計算は出来ない

粘菌にもアメーバにも知性は無いよ
現代的なパソコンならほぼ最短距離なら高速に計算出来る カーナビにも入ってるよね 確定値を計算するには計算量が爆発的に増えるので量子コンピュータが期待されてる

なお暗号に使う素数だけど、ほぼ素数だろう、で計算を簡略化してる。確実に素数かを検証するのは時間かかるので。それでも実用的に使える

85: 2018/12/27(木) 15:14:27.39

粘菌は、仮足で何か所か栄養素をとらえたら、広がる力と栄養素を最短で運ぼう とする力の拮抗で、迷路の最短経路を解く。

巡回セールスマン問題では、迷路の壁をあらかじめ設置できないため、光で 道筋を制限したけど、粘菌に問題を解かせる際の行動原理は全く一緒だと思われる。

ちなみに、モジホコリは粘菌である。
粘菌がアメーバの一種であるのか否かについては、まだ判然としない。粘菌は子実体を生成して胞子で増殖する。

82: 2018/12/27(木) 08:44:25.90

うむ！
ぜんぜんわからん！

14: 2018/12/25(火) 17:32:52.03

帰りぐらいグリーン車に乗せてくれよ