ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける 48
ストーリー by hylom
花の数が増えたらどうなるかは気になる 部門より
花の数が増えたらどうなるかは気になる 部門より
capra 曰く、
ミツバチは複数の花を最短ルートで移動していることが、ロンドン大学クイーン・メアリー校および同大学ロイヤルホロウェイ校の共同研究で分かったそうだ(ロンドン大学クイーン・メアリー校発表、本家/.)。
複数地点を一度ずつ巡り出発点に戻る最短ルートを求める問題は通称「巡回セールスマン問題」と呼ばれており、ミツバチはこの問題を解くことができることが発見された初めての種であるという。
研究ではコンピュータで制御された人工の花を使い、ミツバチがこの花を「発見した順」に巡るのか、それとも「最短ルート」を見つけ出すのかを検証した。その結果、ミツバチはそれぞれの花の場所を探索したあと最短ルートを飛行するようになったという。
コンピュータでは解くのに何日もかかるこの問題をミツバチが短時間でどう処理しているかを調べることで、複雑な問題の解決に必要な最小限の神経回路を解明できるかもしれないとのことだ。
をいをい (スコア:3, 興味深い)
なんと大人気ない! (スコア:5, おもしろおかしい)
マルハナバチ相手に、なにムキになってるんですか。
このあたりの比較条件としてもってくるコンピュータは、ハチマルマルハチか、せめてハチマルハチマルあたりを使うのが公平ってもんでしょう。
Re:なんと大人気ない! (スコア:2)
せめてと言うがハチマルハチマルの方がハチマルマルハチより高性能な件
Re:なんと大人気ない! (スコア:2)
「マルハナバチ相手にヒトが本気出しちゃうなんてwww。ここは万物の霊長として太っ腹なところを見せて、条件を下げるべきだよねー」という文脈ですよ。
Re: (スコア:0)
つハチマルマルハチ
この微妙な違いがめちゃくちゃバスのハンドリングの悪さだとわかるのはおじちゃんです、ええおじちゃんですとも~OTL
Re:をいをい (スコア:1, すばらしい洞察)
Re:をいをい (スコア:1)
一番近い花に移動していくだけで最短距離を満たしそうな感じが…。
元記事にも詳細は書いてありませんね。 (スコア:0)
元記事によると今週のThe American Naturistに掲載されるそうですから、それを待つしかないでしょう。無料で読めるか知りませんけど。
Re: (スコア:0)
単純な巡回サラリーマン問題ではないとか?
3次元的な花の配置であったり、ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり…
Re:をいをい (スコア:3, おもしろおかしい)
働きバチはみんな女の子だから、サラリーマンじゃない!ってことで、このあたり
> ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり
をちょっと詳しく知る必要が…
Re:をいをい (スコア:2, 興味深い)
普通の巡回セールスマン問題は、都市間移動の「重み」の付け方に制約はありません。さすがにゼロとか負の重みはな無かったと思いますが。 「3次元的な花の配置」での距離だと「三角不等式を満たす重み」ということで、制約のある(やや易しい)巡回セールスマン問題になります。どっちにしても厳密解をもとめるのはNP困難です。ただ三角不等式を満たす巡回セールスマン問題は多項式時間近似アルゴリズムが多くあるそうです。
運べる蜜の量の制約条件を足すと、難しくなりますね。
Re:をいをい (スコア:1)
巣に住む嫁という名の女王蜂のために働く働き蜂ということですねわかります。
まあ実際には働き蜂はOLらしいですけど。
Re: (スコア:0)
Re:をいをい (スコア:1)
あやかりたいものです
#でも働き蜂でいいから女王様でも嫁でも(略)
Re: (スコア:0)
Re: (スコア:0)
Re:をいをい (スコア:1)
同意見です。
実際、近似解じゃないですかね。
Re: (スコア:0)
Traveling Salesman Problem 問題?
Re: (スコア:0)
>Traveling Salesman Problem 問題?
Traveling Salesman Problem Issue
# 文系では「これは問題だけど解決可能だぜ!力を合わせて解決しようぜ!」という「問題」を issue と呼ぶようです
ミツバチじゃないよ (スコア:2, 参考になる)
マルハナバチ(bumblebee)ですよ。細かいことですが。
あとジャーナルはThe American Naturalistです。
ちなみにThe American Naturalistは生態学・進化生物学の一流誌の一つです。
多分論文はこれ。
http://dx.doi.org/10.1086/657042 [doi.org]
筑波大からは読めませんでした。
それにしても「コンピュータでは解くのに何日もかかるこの問題」って・・・。
そんな規模の話じゃない。
Re:ミツバチじゃないよ (スコア:5, 参考になる)
本文へのリンクがあったので何となくここにぶらさげる。
実験の規模は上のほうでも書いてあるように巣と4箇所の人工花だけです。
実験の手法は、
1. 初め 1 箇所に 4 つの花をまとめておいておく
2. 花を二つ動かして 2コ*2箇所 に置く。(残り 2 コはそのまま)
3. 2*2 から 1*2 + 1 + 1 にする。
4. 中略。最後は 4 箇所にバラバラにする。
なお、この際の置き場所はTarZ氏の日記 [srad.jp]にあるように、順番にたどると飛行距離が長くなるように設定する。
んで、"ある一匹のハチ"が 1-4 の状態でどのような経路で花をまわるか調べる。
条件は以下。
○ハチが花に香りか何かでマークするのは邪魔してない。
○あと、人工花には砂糖水があるのだけど、その量は 4 つ全部まわっても
一匹のハチの採集許容量を超えないようにあらかじめ調節。
○実験は 11 匹のハチについてそれぞれ行っている。集団によるコミュニケーション
みたいのは入らないようにしている。
○人工花に蜜を補給するのは 4 つ全部が回収された後だけ。
(巣に近い一ヶ所だけで蜜を採集されるのを防ぐって意味だと思う)
ほかにも色々気をつけてたと思う。けど忘れた。
以下結果(4コバラバラ時がメイン)
初めは花を発見した順に回る(無駄が多い)んだけど、時間の経過
(というか試行回数の増加?)に従って、移動距離が最適になるような経路を
だんだん多く選択するようになってくるのがわかったらしい。ただし、これには
限界があって、常に最短な経路を飛ぶようになるということではない。
あくまで最短の経路を選ぶ可能性がある確率まで上がっていくだけ。
ハチは元々空間認識能力があるって話があったと思うけど、それに加えて
学習して効率の良い経路を探すことができる知能(的な何か)があるという
ことか? ハチすげぇ。(ここは私見; 論文中にあるかは知らん)
ついでに日を改めて実験すると、前日の記憶が残っているらしく、初めから
割と効率の良い経路を選ぶようになっている。記憶まであるのか、ハチすげぇ。
が、当然ながら常に最短とかにはならない。前日のパフォーマンスを大きく
上回ったりもしてないみたい。
ちなみに巡回するときに最適な経路だけではなく、効率悪そうな経路も使うのは
よりよい経路の発見につながってるんじゃないか、という著者の意見がどっかに
あった気がする。勘違いかも。
長文ごめんなさい。あと間違ってても知らない。
Re:ミツバチじゃないよ (スコア:1, すばらしい洞察)
なるほど
人間のセールスマンと同程度の賢さだな
Re: (スコア:0)
> 常に最短な経路を飛ぶようになるということではない。
> あくまで最短の経路を選ぶ可能性がある確率まで上がっていくだけ。
近似解でよければ、効率的な探索方法はハチに教わるまでもなくすでにいくつも発明されてるよね。
Re: (スコア:0)
Re:ミツバチじゃないよ (スコア:1)
うちからも full paper は読めませんでした。24時間有効な full paper 閲覧権が 15 ドル。
科学の世界を平等にするには、著者負担でオープンアクセスにするのがいいのか、雑誌掲載はノーコストでできるようにして読みたい人が払うのがいいのか…
ま、今は両者ともそれなりに払う形式が多いわけですがね。
イグノーベル賞 (スコア:2)
評価関数は距離? (スコア:1)
ちゃんと遠い花から蜜を集めるのかな?
無駄足にならないように営業担当は
ちゃんと個別orチームで振り分けできるのかな?
面白いなぁこれ。
というわけでオフィシャルな論文が出る前に妄想… (スコア:1)
何匹かのハチで並列探索した結果が統合されるというのはどうか。
子供の頃は (スコア:1, 興味深い)
子供の頃は働きアリが自分より大きなものを運んでいたり、働き蜂が飛び回っているのを見て単純に羨ましいなあと思って憧れの目で見ていました。
でも大人になって見ると、「ああ、かわいそうに一生こき使われるんだろうなあ」としか思わなくなった。
もうまさに”働き蜂”って感じの能力ですね。
種の発展、甥っ子や姪っ子、そしてその子供たちのためのはかない命。
世界は知れば知るほど深い。
Re:子供の頃は (スコア:2)
群体ですから「手足と消化器と生殖器と(中略)どれが得?」みたいな話ですね
女王は子宮、雄は精嚢
外界を見て回れるだけワーカーのほうがマシかも
Re: (スコア:0)
オスは何もせず、女王蜂が成虫した時に交尾->直後に即死だそうです。
Re: (スコア:0)
働きアリ・働き蜂は、意外と働いていないそうです。
真相(?) (スコア:1, すばらしい洞察)
最初はいろいろなハチがそれぞれ好きな順番で花をめぐります。
効率が悪いコースを選択したハチは疲れて休みます。
効率のよいコースを選択したハチは仕事を続けます。
おお、ハチが最適化問題を解いている! ←今ココ
Re: (スコア:0)
Re: (スコア:0)
到達時の疲労度が高いほどミツをより甘く感じる。
次回は甘かったと思う順に探索。
ルートが変わったことで甘く感じた順が変動。
しばらく試行錯誤すると最適ルートに収束。
とか。
もっと時間掛ってます (スコア:1)
Re:もっと時間掛ってます (スコア:2)
私は、計算機科学としても、生物学としても非常に面白いと思います。
なぜなら「知能って何だっけ?」という議論の土台になるからです。
たとえば
本当にこう言い切れますか?なぜ対応できるようになったのか具体的に説明できますか?
Re:もっと時間掛ってます (スコア:1)
>なぜなら「知能って何だっけ?」という議論の土台になるからです。
私が鈍いだけなのかもしれませんが、
今回の報告を土台とした「知能って何だっけ?」という議論が計算科学的に面白いとは思えません。
なぜこの議論が計算科学的に面白いのかご説明頂けますでしょうか?
>> 進化の過程でこの問題に対応できる様になっているので
> 本当にこう言い切れますか?
はい、言い切れます。少なくとも原核生物にはこの課題は不可能ですので。
> なぜ対応できるようになったのか具体的に説明できますか?
今のところ生物学では説明できないでしょう。
ところでなぜ対応できるようになったのかは、生物学的興味だと思いますが。
念の為、「進化の過程でこの問題に対応できる様になっているので」は、「もっと時間掛ってます」に係ってます。
Re: (スコア:0)
えっと、「巡回セールスマン問題の近似解を求めるアルゴリズムの開発にかかった時間」は「そのアルゴリズムで近似解を得るためにかかる時間」とは無関係なんじゃないかと。
Re:もっと時間掛ってます (スコア:2)
DNAに未知のアルゴリズムが隠されているというなら大変に面白いと思います
Re:もっと時間掛ってます (スコア:1)
DNAは解読されたけど、未知のアルゴリズムだらけで研究競争真っ最中。
the.ACount
ミツバチ曰く (スコア:0)
「オラ、ただうまそうな花を目指して飛んでるだけだ」
単純なルールが複雑さをつくる、らしい。
粘菌は? (スコア:0)
一時期話題だった粘菌は解けないのかな、
と思ったら、
そっちは最小全域木(のようなもの)になるのかな?
ミツバチなりマルハナバチにだって、
一度も巣に戻らずに回れる花の数には限度があるのでTSPなんか解けないでしょうが。
(我が家に来るハチを観察しても、隣り合う花をすべて回ったりしませんし)
働き蜂から (スコア:0)
どっちもイヤかも^^;
まぁ難問ですから (スコア:0)
つまりホモ=サピエンスは解けないということですね。
ホモ=サピエンス <<<(越えられない壁)<<< コンピュータ < ミツバチ
という理解でOK?
コンピュータより早く、じゃね? (スコア:0)
蜂の歴史って何千年とか何万年とかでしょ。コンピュータは 60年とかそこらd
Re:コンピュータより早く、じゃね? (スコア:1)
じゃあなんでフェルマーの最終定理を証明したのは、4000年の歴史を誇る中国人じゃなかったんだ?
1を聞いて0を知れ!
Re: (スコア:0)
その頃はもう欧米主導だったかと
まあ中国算術そして和算なんかも
なかなかにシブいんですけど