パスワードを忘れた? アカウント作成
267500 story

ミツバチはコンピュータよりも速く巡回セールスマン問題を解ける 48

ストーリー by hylom
花の数が増えたらどうなるかは気になる 部門より

capra 曰く、

ミツバチは複数の花を最短ルートで移動していることが、ロンドン大学クイーン・メアリー校および同大学ロイヤルホロウェイ校の共同研究で分かったそうだ(ロンドン大学クイーン・メアリー校発表本家/.)。

複数地点を一度ずつ巡り出発点に戻る最短ルートを求める問題は通称「巡回セールスマン問題」と呼ばれており、ミツバチはこの問題を解くことができることが発見された初めての種であるという。

研究ではコンピュータで制御された人工の花を使い、ミツバチがこの花を「発見した順」に巡るのか、それとも「最短ルート」を見つけ出すのかを検証した。その結果、ミツバチはそれぞれの花の場所を探索したあと最短ルートを飛行するようになったという。

コンピュータでは解くのに何日もかかるこの問題をミツバチが短時間でどう処理しているかを調べることで、複雑な問題の解決に必要な最小限の神経回路を解明できるかもしれないとのことだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • をいをい (スコア:3, 興味深い)

    by saitoh (10803) on 2010年10月26日 18時17分 (#1847849)
    「コンピュータでは解くのに何日もかかる」って、一体何都市のTSP問題なんだ。 数1000都市くらいなら1日で解けるらしいし。 ミツバチが廻る花が何10箇所くらいなら、コンピュータでだって,あっという間に解けると思うがなぁ。
    • なんと大人気ない! (スコア:5, おもしろおかしい)

      by TarZ (28055) on 2010年10月26日 20時08分 (#1847898) 日記

      マルハナバチ相手に、なにムキになってるんですか。

      このあたりの比較条件としてもってくるコンピュータは、ハチマルマルハチか、せめてハチマルハチマルあたりを使うのが公平ってもんでしょう。

      親コメント
      • by ksada (4435) on 2010年10月27日 22時40分 (#1848622)

        せめてと言うがハチマルハチマルの方がハチマルマルハチより高性能な件

        親コメント
      • by Anonymous Coward

        このあたりの比較条件としてもってくるコンピュータは、ハチマルマルハチか、せめてハチマルハチマルあたりを使うのが公平ってもんでしょう。

        ハチマルマルハチ
        この微妙な違いがめちゃくちゃバスのハンドリングの悪さだとわかるのはおじちゃんです、ええおじちゃんですとも~OTL

    • Re:をいをい (スコア:1, すばらしい洞察)

      by Anonymous Coward on 2010年10月26日 18時36分 (#1847860)
      たしかに自分もそう思いましたが、でも いちめんの花畑の一つ一つの花を最適解で廻っているとしたなら、それはそれですごいことだね。 どういう条件か見極めてから判断しないと。
      親コメント
    • by mnk (40844) on 2010年10月26日 18時52分 (#1847868)
      論文を読んでみると、花は4箇所(+巣1箇所)みたいですね。
      一番近い花に移動していくだけで最短距離を満たしそうな感じが…。
      親コメント
    • 論文自体がまだ公開されてないようですし。
      元記事によると今週のThe American Naturistに掲載されるそうですから、それを待つしかないでしょう。無料で読めるか知りませんけど。
    • by Anonymous Coward

      単純な巡回サラリーマン問題ではないとか?
      3次元的な花の配置であったり、ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり…

      • Re:をいをい (スコア:3, おもしろおかしい)

        by flutist (16098) on 2010年10月26日 21時06分 (#1847924)

        働きバチはみんな女の子だから、サラリーマンじゃない!ってことで、このあたり

        > ハチが運べる蜜の量だったり、花の蜜が溜まるまでの時間であったり

        をちょっと詳しく知る必要が…

        親コメント
      • Re:をいをい (スコア:2, 興味深い)

        by saitoh (10803) on 2010年10月27日 10時59分 (#1848148)
        対象が三次元だと普通の巡回セールスマン問題より難しくなるとおもっておられる感じですが。

        普通の巡回セールスマン問題は、都市間移動の「重み」の付け方に制約はありません。さすがにゼロとか負の重みはな無かったと思いますが。 「3次元的な花の配置」での距離だと「三角不等式を満たす重み」ということで、制約のある(やや易しい)巡回セールスマン問題になります。どっちにしても厳密解をもとめるのはNP困難です。ただ三角不等式を満たす巡回セールスマン問題は多項式時間近似アルゴリズムが多くあるそうです。

        運べる蜜の量の制約条件を足すと、難しくなりますね。

        親コメント
      • 単純な巡回サラリーマン

        巣に住む嫁という名の女王蜂のために働く働き蜂ということですねわかります。
        まあ実際には働き蜂はOLらしいですけど。

        親コメント
      • by Anonymous Coward
        いや、セールスマンだから
    • by Anonymous Coward
      何千も花があったら最適解じゃなくても良くって、近似解を選びそうだなぁ。
    • by Anonymous Coward
      > TSP問題
      Traveling Salesman Problem 問題?
      • by Anonymous Coward

        >Traveling Salesman Problem 問題?

        Traveling Salesman Problem Issue

        # 文系では「これは問題だけど解決可能だぜ!力を合わせて解決しようぜ!」という「問題」を issue と呼ぶようです

  • by shimotsuki (2505) on 2010年10月26日 19時10分 (#1847878) ホームページ

    マルハナバチ(bumblebee)ですよ。細かいことですが。
    あとジャーナルはThe American Naturalistです。
    ちなみにThe American Naturalistは生態学・進化生物学の一流誌の一つです。
    多分論文はこれ。
    http://dx.doi.org/10.1086/657042 [doi.org]
    筑波大からは読めませんでした。

    それにしても「コンピュータでは解くのに何日もかかるこの問題」って・・・。
    そんな規模の話じゃない。

    • by tamanegi (38323) on 2010年10月26日 21時08分 (#1847926) 日記

      本文へのリンクがあったので何となくここにぶらさげる。
      実験の規模は上のほうでも書いてあるように巣と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, すばらしい洞察)

        by Anonymous Coward on 2010年10月26日 23時21分 (#1847989)

        なるほど
        人間のセールスマンと同程度の賢さだな

        親コメント
      • by Anonymous Coward

        > 常に最短な経路を飛ぶようになるということではない。
        > あくまで最短の経路を選ぶ可能性がある確率まで上がっていくだけ。
        近似解でよければ、効率的な探索方法はハチに教わるまでもなくすでにいくつも発明されてるよね。

      • by Anonymous Coward
        確率が上がる事で解が得られるって、量子コンピュータみたい
    • by flutist (16098) on 2010年10月26日 20時38分 (#1847906)

      うちからも full paper は読めませんでした。24時間有効な full paper 閲覧権が 15 ドル。

      科学の世界を平等にするには、著者負担でオープンアクセスにするのがいいのか、雑誌掲載はノーコストでできるようにして読みたい人が払うのがいいのか…

      ま、今は両者ともそれなりに払う形式が多いわけですがね。

      親コメント
  • by NOBAX (21937) on 2010年10月26日 19時20分 (#1847881)
    狙ってるわけですね
  • by strad (40393) on 2010年10月26日 18時49分 (#1847866)
    巣から一直線上に花が並んでいた場合、
    ちゃんと遠い花から蜜を集めるのかな?

    無駄足にならないように営業担当は
    ちゃんと個別orチームで振り分けできるのかな?
    面白いなぁこれ。
  • 何匹かのハチで並列探索した結果が統合されるというのはどうか。

  • 子供の頃は (スコア:1, 興味深い)

    by Anonymous Coward on 2010年10月26日 21時11分 (#1847927)

    子供の頃は働きアリが自分より大きなものを運んでいたり、働き蜂が飛び回っているのを見て単純に羨ましいなあと思って憧れの目で見ていました。
    でも大人になって見ると、「ああ、かわいそうに一生こき使われるんだろうなあ」としか思わなくなった。
    もうまさに”働き蜂”って感じの能力ですね。
    種の発展、甥っ子や姪っ子、そしてその子供たちのためのはかない命。
    世界は知れば知るほど深い。

    • by ksada (4435) on 2010年10月27日 22時35分 (#1848619)

      群体ですから「手足と消化器と生殖器と(中略)どれが得?」みたいな話ですね
      女王は子宮、雄は精嚢
      外界を見て回れるだけワーカーのほうがマシかも

      親コメント
    • by Anonymous Coward
      働き蜂はメスだそうです。
      オスは何もせず、女王蜂が成虫した時に交尾->直後に即死だそうです。
    • by Anonymous Coward

      働きアリ・働き蜂は、意外と働いていないそうです。

  • 真相(?) (スコア:1, すばらしい洞察)

    by Anonymous Coward on 2010年10月26日 22時04分 (#1847946)

    最初はいろいろなハチがそれぞれ好きな順番で花をめぐります。

    効率が悪いコースを選択したハチは疲れて休みます。

    効率のよいコースを選択したハチは仕事を続けます。

    おお、ハチが最適化問題を解いている! ←今ココ

    • by Anonymous Coward
      それって「粘菌が迷路を解いてる」とまるで同じ…
    • by Anonymous Coward

      到達時の疲労度が高いほどミツをより甘く感じる。
      次回は甘かったと思う順に探索。
      ルートが変わったことで甘く感じた順が変動。
      しばらく試行錯誤すると最適ルートに収束。

      とか。

  • by hrk!uw (36581) on 2010年10月27日 4時51分 (#1848067)
    進化の過程でこの問題に対応できる様になっているので。(DNAに方略が書き込まれている) それと解の距離が近い場合は確率的でしょう。(精度の低さの問題) 一般受けが良さそうな話ですが、現時点では計算機科学的には特に面白くないです。 生物学的にはどうなんでしょう。
    • 私は、計算機科学としても、生物学としても非常に面白いと思います。
      なぜなら「知能って何だっけ?」という議論の土台になるからです。

      たとえば

      進化の過程でこの問題に対応できる様になっているので

      本当にこう言い切れますか?なぜ対応できるようになったのか具体的に説明できますか?

      親コメント
      • >なぜなら「知能って何だっけ?」という議論の土台になるからです。
        私が鈍いだけなのかもしれませんが、
        今回の報告を土台とした「知能って何だっけ?」という議論が計算科学的に面白いとは思えません。
        なぜこの議論が計算科学的に面白いのかご説明頂けますでしょうか?

        >> 進化の過程でこの問題に対応できる様になっているので
        > 本当にこう言い切れますか?
        はい、言い切れます。少なくとも原核生物にはこの課題は不可能ですので。

        > なぜ対応できるようになったのか具体的に説明できますか?
        今のところ生物学では説明できないでしょう。
        ところでなぜ対応できるようになったのかは、生物学的興味だと思いますが。

        念の為、「進化の過程でこの問題に対応できる様になっているので」は、「もっと時間掛ってます」に係ってます。

        親コメント
        • by Anonymous Coward

          念の為、「進化の過程でこの問題に対応できる様になっているので」は、「もっと時間掛ってます」に係ってます。

          えっと、「巡回セールスマン問題の近似解を求めるアルゴリズムの開発にかかった時間」は「そのアルゴリズムで近似解を得るためにかかる時間」とは無関係なんじゃないかと。

    • by ksada (4435) on 2010年10月27日 22時28分 (#1848612)

      DNAに未知のアルゴリズムが隠されているというなら大変に面白いと思います

      親コメント
  • by Anonymous Coward on 2010年10月26日 19時08分 (#1847876)

    「オラ、ただうまそうな花を目指して飛んでるだけだ」

    単純なルールが複雑さをつくる、らしい。

  • by Anonymous Coward on 2010年10月26日 20時37分 (#1847904)

    一時期話題だった粘菌は解けないのかな、
    と思ったら、
    そっちは最小全域木(のようなもの)になるのかな?

    ミツバチなりマルハナバチにだって、
    一度も巣に戻らずに回れる花の数には限度があるのでTSPなんか解けないでしょうが。
    (我が家に来るハチを観察しても、隣り合う花をすべて回ったりしませんし)

  • by Anonymous Coward on 2010年10月26日 20時52分 (#1847916)
    巡回サラリーマンにクラスチェンジ?

    どっちもイヤかも^^;
  • by Anonymous Coward on 2010年10月26日 21時54分 (#1847942)
    > ミツバチはこの問題を解くことができることが発見された初めての種

    つまりホモ=サピエンスは解けないということですね。

    ホモ=サピエンス <<<(越えられない壁)<<< コンピュータ < ミツバチ
    という理解でOK?
  • by Anonymous Coward on 2010年10月27日 0時12分 (#1848020)

    蜂の歴史って何千年とか何万年とかでしょ。コンピュータは 60年とかそこらd

typodupeerror

吾輩はリファレンスである。名前はまだ無い -- perlの中の人

読み込み中...