Ant Colony Optimization 知能情報工学Ｍ１銭孝孝蟻コロニー最適化（ありコロニーさいてきか、ACO）とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー（＝群れ）から食物までの経路を見つける際の挙動からヒントを得たものである。蟻コロニー最適化アルゴリズムは、巡回セールスマン問題に近似最適解を生み出すために用いられた。この手法はグラフが動的に変化する場合に焼きなまし法や遺伝的アルゴリズムよりも有効である。蟻コロニー最適化アルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、ネットワークのルーティングや都市交通システムでの応用が考えられる。 http://www.aco-metaheuristic.org/aco-code/public-software.html アルゴリズムの流れ ACO の基本的なアルゴリズムは以下の通りである。１２３ • エージェント（アリ）とフェロモンの初期化である。 • 終了条件を満たすまで以下の処理を繰り返す。(a.各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。b.各エージェントが分泌するフェロモンを計算する。c.フェロモン情報の更新である。) • 最も良い成績のエージェントの解を出力する。例をとして挙げる：解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。次にエージェント k はいくつかの都市を訪問し、現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 j と i に対して以下のような評価値を計算する。ここで、Tij(t) は時点 t での都市 i から j への経路に蓄積されたフェロモンである。 ηij は都市 i から j へヒューリスティックな情報であり、 Dorigo は距離の逆数を使用している。α、β はフェロモンとヒューリスティック情報のどちらを優先させるかという定数である。Ωの全ての都市に対して上記の評価値を計算し都市を一つ選択する。例えば都市 m が選択される確率は以下のようになる。この選択をΩが空集合になるまで繰り返す。各エージェントに対して以上の操作を行い時点 t における各巡回路を作成する。各巡回路が作成されたら、次にフェロモンの計算が行われる。これはエージェント k が作成した巡回路を Tk(t) とし、その長さを Lk(t) としたとき、エージェント k は各経路に対して以下のように分泌するフェロモンを決定する。ここで Q は正の定数である。この値により時点 t+1 のフェロモン情報は以下の式で更新される。ここで ρ は 0 以上 1 以下の定数であり、フェロモンの蒸発率を表している。また m はエージェントの最大数である。以上の式を定められた時点まで繰り返すことによって解を得ることができる。今後の予定：今はここまで勉強しました。問題点としては、「最も良い成績のエージェントの解を出力する。」中の解の意味はまたはっきり分からないである。例えば、「解」の数は具体個数ですか、集合の意味ですか。今後は蟻コロニー最適化の具体的な例をとして勉強すると考えられる。参考文献 1.Dorigo, M. (1992). "Optimization, Learning and Natural Algorithms", Ph.D. Thesis, Politecnico di Milano, Italy. 2.Dorigo, M. and Gambardella, L. M. (1999). "Ant Algorithms for Discreate Optimization", Artificial Life Vol.5 No. 2, pp.137-172.PDF 3.伊庭斉志『進化論的計算手法 (知の科学)』、人工知能学会編、オーム社、 2005年、ISBN 4-274-20018-3 ご清聴ありがとうございました。