蟻コロニー最適化
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/05/26 03:35 UTC 版)

蟻コロニー最適化(ありコロニーさいてきか、Ant Colony Optimization、ACO)とは、Marco Dorigo が 1992年の博士論文で提案したアルゴリズムであり、グラフを使ってよい経路を探すことで単純化できるような計算問題の確率的解法である。これはアリがコロニー(=群れ)から食物までの経路を見つける際の挙動からヒントを得たものである。
概要
実世界では、アリは始めランダムにうろつき、食物を見つけるとフェロモンの跡を付けながらコロニーへ戻る。他のアリがその経路を見つけると、アリはランダムな彷徨を止めてその跡を辿り始め、食物を見つけると経路を補強しながら戻る。
しかし、時間とともにフェロモンの痕跡は蒸発しはじめ、その吸引力がなくなっていく。その経路が長いほどフェロモンは蒸発しやすい。それに対して、経路が短ければ行進にも時間がかからず、フェロモンが蒸発するよりも早く補強されるため、フェロモン濃度は高いまま保たれる。
従って、あるアリがコロニーから食料源までの良い(すなわち短い)経路を見つけると、他のアリもその経路を辿る可能性が高くなり、正のフィードバック効果によって結局すべてのアリが1つの経路を辿ることになる。蟻コロニー最適化アルゴリズムの考え方は、解決すべき問題を表しているグラフを歩き回る「シミュレーションされたアリ」によってこの行動を真似ることである。
蟻コロニー最適化アルゴリズムは、巡回セールスマン問題に近似最適解を生み出すために用いられた。この手法はグラフが動的に変化する場合に焼きなまし法や遺伝的アルゴリズムよりも有効である。蟻コロニー最適化アルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、ネットワークのルーティングや都市交通システムでの応用が考えられる。
アルゴリズムの流れ
ACO の基本的なアルゴリズムは以下の通りである。
- エージェント(アリ)とフェロモンの初期化
- 終了条件を満たすまで以下の処理を繰り返す。
- 各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。
- 各エージェントが分泌するフェロモンを計算する。
- フェロモン情報の更新
- 最も良い成績のエージェントの解を出力する。
解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。
今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。 次にエージェント k はいくつかの都市を訪問し現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 j と i に対して以下のような評価値を計算する。
一般 | |
---|---|
微分可能 |
凸最小化 | |||||||
---|---|---|---|---|---|---|---|
線形 および 二次 |
|
系列範例 (Paradigms) |
|||||
---|---|---|---|---|---|
グラフ理論 |
|
||||
ネットワークフロー (最大流問題) |
蟻コロニー最適化
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/06/18 16:06 UTC 版)
蟻コロニー最適化(ACO)は難しい組み合わせ最適化問題の近似解を探索するのに使われるメタヒューリスティックな最適化アルゴリズムである。ACOでは、現実の蟻を真似た人工蟻が問題のグラフ上を移動することで解を構築しようとする。このとき、グラフ上に人工のフェロモンを置くことでその後の人工蟻がよりよい解を探索できるようにする。ACOは多数の最適化問題で効力を発揮してきた。
※この「蟻コロニー最適化」の解説は、「群知能」の解説の一部です。
「蟻コロニー最適化」を含む「群知能」の記事については、「群知能」の概要を参照ください。
蟻コロニー最適化と同じ種類の言葉
- 蟻コロニー最適化のページへのリンク