アリコロニー最適化についてまとめ

今日は小説とかじゃないです。

最近アリコロニー最適化について勉強していて、知識を定着させたいのでまとめる。自分向け。Qiitaとかに書いた方がいい。

アリコロニー最適化とは？

アリコロニー最適化(Ant Colony Optimization 以下”ACO”と表記)は、群知能アルゴリズム(生物の集団心理、集団行動を模して問題解決を行うアルゴリズム)の一種。

アリはエサなどの目的物を発見した際に、コロニーと目的物間を往復して少しずつ持ち帰る。
その過程で道中にフェロモンを残すことで、他の個体とルートを共有し、往復を繰り返すうちに段々と最短の経路を通るようになっていく。
この習性を応用したアルゴリズムがACO。

特性上ネットワークやグラフの探索に向いており、交通流整理やTSP(巡回セールスマン問題)・最短経路探索に多く用いられる。

結局どういう動作をするのか

こういうグラフがあるとする。
各点(ノード)間を移動する時、結ぶ線に書かれている分のコストがかかる。

これからノード１を始点、ノード５を終点としてACOを適用するとどうなるかを見ていく。

１．事前準備
経路探索を始める前に、アリを用意しなければならない。
とりあえず2匹のアリがいるとしておく。
他にも試行回数(アリが何往復するか)とか、フェロモンの蒸発率(後述)とかを用意しなければならない。

２．第1回試行

2匹のアリに、始点から終点までの道を探させる。
一度も行ったことがないからまだどう行けば良いのか全くわからないので、とりあえず完全にランダムで道を選んで進む。ランダムと言っても後戻りはしない。明らかに無駄手間でしかないのでね。

アリさんに道を決めてもらった(体で自分で決めました)。
今後青い矢印をアリA、赤い矢印をアリBとします。
アリAは1→2→3→4→5(コスト12)、アリBは1→3→4→5(コスト6)の道を通ったようだ。
ここで通った道のうち一番コストが少ない、アリBの道を暫定的な最短経路として保存しておく(今回は最短を出してしまったのでもう更新はされません)。

最後に、それぞれのルートにフェロモンを残しながらコロニーへ帰る。
コストが少ないほど多くのフェロモンを残すようにしたいので、1/コストとかにするのがいいだろう。

アリAのルートにフェロモンを1/12、アリBのルートにフェロモンを1/6、両方が通ったルートにフェロモンを1/4(1/12 + 1/6)残した。
これで1回目の試行は終わり。

第2回以降の試行

2回目以降は同じことの繰り返しなのでまとめて。
とりあえず2回目として説明する。
また始点から終点までの道を探索するが、前回は全くのランダムで道を選択したが、今回は1回目の試行で残したフェロモンを考慮して選択をします。伏線回収ってやつです。
今回始点(ノード１)から伸びている道はノード２・ノード３に向かう道がある。
ノード２への道(道２)には1/12、ノード３への道(道３)には1/6のフェロモンが残っている。
ここで単純に多い方を選択するようにすると、前回の最短経路を辿るだけになってしまい、もっと短い道があったとしてもそこを見つけることができない。なので、フェロモンを考慮しつつもあくまで確率による選択をします。
道２と道３のフェロモン量比は１:２になっているので、道３の方が倍選ばれやすいようにする。
道２が選択される確率は1/3、道３が選択される確率は2/3ってこと。
本当はもうちょっと複雑な式で確率をいじってると思うよ。多分。

そうすることで、暫定的な最短経路に近いルート上を多く通るようになる。
だからなんだというと、明らかに遠くなるようなルートの排除とより近いルートの探索を両立することができる。
この無駄な試行の排除というのはとても重要で、今回はノードが5個しかないから全部調べるのにも大した時間はかからないが、もっと多くのノードについて調べなくてはならなくなった時、全部見ているととてつもない時間がかかるし、なんならコンピュータが動作をやめてしまう。
ましてコンピュータの利点は高速かつ正確な演算でもあるので、計算量を必要最小限に抑えて、実行速度と精度を両立させることはとても大事なのだ。

このトレードオフ的な観点でいうとACOはとても優れているように見える。

話が逸れたがフェロモンを考慮した確率選択で終点まで向かい、暫定的な最短経路を更新した場合は前回のルートを破棄しそちらを保存する。
そして最後に前回同様フェロモンを残す。

ただ、フェロモンを毎回残していくとフェロモン量がとんでもない桁になってしまうし、ルートの偏りが激しくなりすぎてしまう(仮に途中で新しくより早く辿り着けるルートが発生しても、フェロモンが溜まっていないのでそこを選択することが出来なくなる)。
なので、フェロモンを一定期間で蒸発するようにする必要がある。
事前準備の際に蒸発率を設定すると書いたが、ここで活きてくる。伏線回収その2。
たとえば蒸発率を0.9に設定すると、毎試行毎に古いフェロモンを0.9倍するようになる。
これによって、序盤に多く通られたルートを選ぶことが減り、直近での結果に注目するようになる。

こんな感じ。新しいフェロモンの比重が大きくなってるのがわかるかな。
こういう風に「確率による探索→フェロモン分泌→フェロモン蒸発」を一定回数繰り返して最適解(近似解)を見つける。

まとめ
いろいろ要素を省いているし、そこまで深く理解しているわけじゃないので正確ではないと思うけど、大体こんなのがACOです。
結構面白いし便利なので海外の研究にはよく使われてるらしいけど、日本ではそこまでって感じ。面白いよ。

これを3~5分くらいで人に説明しないといけないんだけど無理じゃないですか？？？