蟻コロニー最適化

ウィキペディア

蟻コロニー最適化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/05/26 03:35 UTC 版)

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

蟻コロニー最適化（ありコロニーさいてきか、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 }}}$

Optimization computes maxima and minima.

非線形（制約付き）

凸最適化

組合せ最適化

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略・遺伝的アルゴリズム）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• 群知能（ACO・PSO）
• ベイスンホッピング法
• 量子焼きなまし法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア