エドナちゃんになっちゃった・・・。

前期アニメやってたテイルズのエドナちゃんが可愛すぎてエドナちゃんになっちゃった・・・。(画像はゲーム(現在アニメ視聴中))

PS4とテイルズのソフトが欲しくなってしまったのでこのモチベで貯金していくやつやろう。

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

前話していたアリさんのお話をけんきうしつで暇だったので考えてみた。

本によるとアリさんのアルゴリズムは単純で

1. アリさんは餌を持つとフェロモンを出す。
2. フェロモンは揮発性かつ誘因性物質。

これだけらしい。これに揺らぎ、一種のランダムネスを導入することで経路が最適化されるという話らしい。なんで最適化されていくかのヒントは考えたいかもしれないからヒントを反転させて以下に書いておきます。

・先頭のアリがある経路を見つけ、餌を見つける。そしてフェロモンを出す。

・揺らぎにより他の経路を通るアリもいる。

・フェロモンは揮発性であるので・・・。

普通によくできてるなぁ～～って思った。

ここからは実際的な仕様を考える。若干粗削りなので改善できるところがあれば教えてください。

1.最初のルート決め

• 今回はy方向に+1ずつ、x方向に±1ずつ進むことにする。
• 最初のルートは上の条件のランダムウォークでゴール(エサがあるところ)まで決め、また境界は反射するものとする。(周期境界だとよくわからない経路になりそう)
• この時格子点のラベリングにフェロモン濃度の要素を足して+1とかにしておく

2.進行方向

• １のアリのラベリングに進行方向のベクトルを導入、正方格子の最近接から来た道を除外(次の進行方向との内積の値とかで判断すればよさそう)

3.進行

• フェロモンの値は時間発展とともに減衰させる。
• アリさんはフェロモンの濃い方に決まった確率で移動。

この2,3を繰り返していくとなんかうまくいきそう。

上に書いたことの理由とかまだ迷ってるところ

1.アリさんが通った道のフェロモン濃度の値を1にしていいのか

　→減衰と1匹のアリが通った場合の増加の値については再考の余地あり。しかし現実問題として、揮発性フェロモンを知覚しているならば、少なくとも最大値は1と設定して問題なさそう。(飽和的に)

2.進行経路の選択について濃度と確率をどう結び付けるか。

　→基本的に濃い方に行くようにするが濃度0の経路も揺らぎにより選択させる。この時の確立と濃度の関係はまだ考える余地あり。(濃度の差に関係なく揺らがせるのも案外正しそう。)

3.揮発の速さ

　→まったくわからない、回してみて係数を変えていくくらいか・・・。

4.正方格子上の一点(また、1領域)の最短経路は手計算したほうが早い。

　→実際そう。しかし目的地点の数を増やしたときには数値計算が現実的。(俗にいう巡回セールスマン問題)

5.ではランダムに経路を選び続けて選択したほうが

　→この場合すべての経路について考える必要があるので非現実的。アリの経路選択でもこの議論は成り立つが、恐らく歩行距離はある値(最短距離)に平衡化(緩和)していくと考えられるので最悪最短距離でなくとも最短距離に近い経路は見つけることができる。(総当たりでは一般的な場合を考えるのにこの判断が難しいと思われる。)

ここまで考えて、思ったのがこれはMC法(上も一種のMCだがもっと言うとメトロポリス法)で解決できそうと思った。

格子点上のフェロモンの濃度と歩行距離を最近接の相互作用の強さ(強磁性的な)とエネルギー(コスト)にすり替えればなにかうまくいきそうな予感がする。問題はある状態からある状態への遷移確率が現在の状況だけで決まるのか(マルコフ連鎖)また詳細つり合い(遷移確率のことで確実に緩和をするには加えて逆の状態も実現可能でなくてはならない)によって使えるかどうかが決まるが、進行方向とは逆に行けなかったりする上の条件では詳細つり合いの条件を満たせていない。結論的にはそれを無くして遷移確率を濃度の関数で一意に決めると条件がすべて満たされる・・・とおもう。のでこちらも並行してやっていきたい。

 とりあえず素組みしてみてうまくいかなかったら二度とこの話はしなくなりそう