蟻コロニー最適化
ACO の基本的なアルゴリズムは以下の通りである。
エージェント(アリ)とフェロモンの初期化
終了条件を満たすまで以下の処理を繰り返す。 各エージェントに対して、フェロモンとヒューリスティックな情報に基づいて確率的な解の選択を行う。 各エージェントが分泌するフェロモンを計算する。 フェロモン情報の更新
最も良い成績のエージェントの解を出力する。
解の選択は様々なものが考えられるが Marco Dorigo が巡回セールスマン問題に適用した論文では以下のような方法がとられている。
今、繰り返し回数 t 時点でのエージェント k が巡回路を作成することを考える。まずスタート地点となる都市を適当に選択する。 次にエージェント k はいくつかの都市を訪問し現在、都市 i にいるとする。このとき k がまだ訪問していない都市の集合を Ω で表し、Ωに属する都市 j と i に対して以下のような評価値を計算する。
a i j k ( t ) = [ τ i j ( t ) ] α [ η i j ] β ∑ l ∈ Ω [ τ i l ( t ) ] α [ η i l ] β {\displaystyle a_{ij}^{k}(t)={\frac {[\tau _{ij}(t)]^{\alpha }[\eta _{ij}]^{\beta }}{\sum _{l\in \Omega }[\tau _{il}(t)]^{\alpha }[\eta _{il}]^{\beta }}}}