蟻コロニー最適化

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

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

概要

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

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

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

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

アルゴリズムの流れ

ACO の基本的なアルゴリズムは以下の通りである。

1. エージェント（アリ）とフェロモンの初期化
2. 終了条件を満たすまで以下の処理を繰り返す。
   1. 各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。
   2. 各エージェントが分泌するフェロモンを計算する。
   3. フェロモン情報の更新
3. 最も良い成績のエージェントの解を出力する。

解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。

今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。 次にエージェント k はいくつかの都市を訪問し現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 j と i に対して以下のような評価値を計算する。

$a_{ij}^{k}(t)={\frac {[\tau _{ij}(t)]^{\alpha }[\eta _{ij}]^{\beta }}{\sum _{l\in \Omega }[\tau _{il}(t)]^{\alpha }[\eta _{il}]^{\beta }}}$

ここで、τ_ij(t) は時点 t での都市 i から j への経路に蓄積されたフェロモンである。η_ij は都市 i から j へヒューリスティックな情報であり、 Dorigo は距離の逆数を使用している。α、β はフェロモンとヒューリスティック情報のどちらを優先させるかという定数である。Ωの全ての都市に対して上記の評価値を計算し都市を一つ選択する。例えば都市 m が選択される確率は以下のようになる。

$p_{im}^{k}(t)={\frac {a_{im}^{k}(t)}{\sum _{n\in \Omega }a_{in}(t)}}$

この選択をΩが空集合になるまで繰り返す。各エージェントに対して以上の操作を行い時点 t における各巡回路を作成する。

各巡回路が作成されたら、次にフェロモンの計算が行われる。これはエージェント k が作成した巡回路を T_k(t) としその長さを L_k(t) としたとき、エージェント k は各経路に対して以下のように分泌するフェロモンを決定する。

$\Delta \tau _{ij}^{k}(t)={\begin{cases}Q/L_{k}(t),&{\mbox{if }}(i,j)\in T_{k}(t)\\0,&else\end{cases}}$

ここで Q は正の定数である。この値により時点 t+1 のフェロモン情報は以下の式で更新される。

$\tau _{ij}(t+1)=\rho \tau _{ij}(t)+\sum _{k=1}^{m}\Delta \tau _{ij}^{k}(t)$

ここで ρ は 0 以上 1 以下の定数であり、フェロモンの蒸発率を表している。また m はエージェントの最大数である。以上の式を定められた時点まで繰り返すことによって解を得ることができる。

関連する手法

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

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

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

参考文献

• Dorigo, M. (1992). "Optimization, Learning and Natural Algorithms", Ph.D. Thesis, Politecnico di Milano, Italy.
• Dorigo, M. and Gambardella, L. M. (1999). "Ant Algorithms for Discreate Optimization", Artificial Life Vol.5 No. 2, pp.137-172.PDF
• 伊庭斉志 『進化論的計算手法 (知の科学)』、人工知能学会編、オーム社、2005年、ISBN 4-274-20018-3

関連項目

• 粒子群最適化

外部リンク

以下、英文。

• 蟻コロニー最適化 Home Page
• 蟻コロニー最適化に関連した学位論文のリスト
• Ant Colony Optimization （英語） - スカラーペディア百科事典「蟻コロニー最適化」の項目。
• MIDACO-SOLVER 蟻コロニー最適化 を用いた汎用最適化ソフトウェア(Matlab, C/C++, R, C#, Fortran, Python：日本語あり)