蟻コロニー最適化

出典: フリー百科事典『ウィキペディア（Wikipedia）』

蟻コロニー最適化の概念図

蟻コロニー最適化(ありころにーさいてきか、Ant Colony Optimization, ACO)とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー(＝群れ)から食物までの経路を見つける際の挙動からヒントを得たものである。

[編集] 概要

実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。

しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発するよりも早く補強されるため、フェロモン濃度は高いまま保たれる。

従って、あるアリがコロニーから食料源までの良い(すなわち短い)経路を見つけると、他のアリもその経路を辿る可能性が高くなり、正のフィードバック効果によって結局すべてのアリが1つの経路を辿ることになる。蟻コロニー最適化アルゴリズムの考え方は、解決すべき問題を表しているグラフを歩き回る「シミュレーションされたアリ」によってこの行動を真似ることである。

蟻コロニー最適化アルゴリズムは、巡回セールスマン問題に近似最適解を生み出すために用いられた。この手法はグラフが動的に変化する場合に焼きなまし法や遺伝的アルゴリズムよりも有効である。蟻コロニー最適化アルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、ネットワークのルーティングや都市交通システムでの応用が考えられる。

[編集] 関連する手法

焼きなまし法(SA)は、現在の解の近傍解を生成することで探索空間を探し回る大域的最適化技術である。よりよい近傍解は常に選択される。よくない近傍解はその性質と温度パラメータに基づいて確率的に選択される。温度パラメータは探索の進行に伴って、変化する。

タブーサーチ(TS)は、焼きなまし法に似ている。こちらも個別の解の変異をテストしながら探索を行う。焼きなまし法ではひとつの変異解を生成したが、タブーサーチではいくつもの変異解を生成して最もよい解を選択する。堂々巡りを避けて局所最適解に陥らないようにするため、既にテストした解をタブーリストとして保持する。タブーリストに含まれる要素を持つ解は禁じられており、タブーリストは解の探索を通じて更新される。

遺伝的アルゴリズム(GA)は、複数の解のプールを管理する。よりよい解の探索は進化を真似た手法で行われ、解の「突然変異」や「交叉」によって解のプールを変化させ、よくない解を捨てていく。