Pheromone Trail

フェロモントレイルは、アントクラスタリングと同様に、蟻の生態をモデル化したものです。最短経路を探索するアルゴリズムとして、ネットのトラフィックの最適化などに応用されています。





シミュレーションの方法
巣(中央の青い円)から出た蟻は、フードフェロモン(緑)が最も濃い方向へ進みます。フェロモンが全くない場合はランダムです。一歩進む毎に地面にホームフェロモン(赤)を落としますが、フェロモンは徐々に蒸発して薄くなります。

餌(黄)に到達した蟻は、餌を持っている状態(緑)になり、ホームフェロモンの濃い方へ進みます。この状態の時はフードフェロモンを落とします。

複数の蟻がフェロモンを落とす事で、経路がより強化されていきます。



効率を高めるために
今回作成したプログラムでは、フェロモンの濃度に100%従います。環境が変わらない場合は効率的ですが、餌の位置が変わったり障害物があらわれたりすると、非常に効率が落ちます。ある程度ばらつきを持たせる方が、冗長性が生まれ、長期的な効率を上げる事ができるようです。

また、今回のプログラムは、実際の蟻の巣に比較的近い表現となっていますが、巡回セールスマン問題などの最短経路探索として利用する場合には、各ノード間の距離に比例したフェロモンを落とすというように、より抽象化して実装するそうです。
Previous
Next Post »