早わかりアントコロニー最適化 (Ant Colony Optimization)

Presentation on theme: "早わかりアントコロニー最適化 (Ant Colony Optimization)"— Presentation transcript:

1 早わかりアントコロニー最適化 (Ant Colony Optimization)

2 ACOとは ここでは，ACO手法の概要を解説する。
アントコロニー最適化(Ant Colony Optimization, ACO)は、実際のアリの採餌行動の際の経路生成過程にヒントを得た探索手法であり、多くの組合せ最適化問題に適用され、有効な結果が得られている。 アリはフェロモンを介したコミュニケーションを行いながら群れで行動し、ある種の秩序を形成する。ACOでは、この秩序形成過程を探索に用いる。

3 アリが最短経路を見つける方法 アリは通過した経路にフェロモンを排出し、フェロモンに誘引されて経路を選択する。まず、図aのように、A-E間に経路が形成される。そして、図bのように、障害物が置かれていた場合、まず、アリはどちらの経路の方が短いかについて知る手立てを持っていないため、経路の選択はランダムになる。 図cは、その後の経過である。アリは経路にフェロモンを排出して移動するため、短い経路の方が長い経路よりもフェロモン濃度が高くなる。そのため、アリは短い経路を選ぶ度合が高くなる。 フェロモンは蒸発する性質 があるので、少数のアリし か通らなくなった長い経路 は最終的にフェロモンが なくなり、最短経路が確立 される。 (a) (b) (c)

4 巡回セールスマン問題(TSP) 　都市の集合と各都市間の移動コストが与えられ、全ての都市を一度ずつ巡り出発地に戻る時、総移動距離が最小のものを求める組合せ最適化問題である。問題例の大きさは、都市の数で表わされる。

5 ＡＣＯのTSPの解法への応用原理 フェロモン濃度tの更新式 フェロモンによる経路選択確率 t01 t02 t06 t03 t04 t05 1
1 6 2 4 5 3

6 代表的なＡＣＯ手法 Ａｎｔ Ｓｙｓｔｅｍ （ＡＳ） ［Ｄｏｒｉｇｏ ９６］
Ａｎｔ　Ｓｙｓｔｅｍ　（ＡＳ）　［Ｄｏｒｉｇｏ　９６］ ACOの基本アルゴリズム Ａｎｔ　Ｃｏｌｏｎｙ　Ｓｙｓｔｅｍ　(ＡＣＳ）　［Ｄｏｒｉｇｏ　９７] 最良解を最良エージェントのみがフェロモンを放出 フェロモンの多様性を維持するＬｏｃａｌ　Ｕｐｄａｔｅを導入 Ｍａｘ　Ｍｉｎ　Ａｎｔ　Ｓｙｓｔｅｍ　(ＭＭＡＳ)　[Ｓｔｕｔｚｌｅ　００］ フェロモン軌跡濃度を最小濃度と最大濃度の区間に限定 cunning Ant System (cAS)[Tsutsui 96] 経路生成にフェロモン濃度の利用に加えて，他エージェントの部分解を借用 これにより，探索過程での多様性維持の効果が得られる

7 cASと他のACOとの比較① cASをACOの中で優れた性能を持つMMASおよびACSの結果と比較する。
一般に大きな問題を解くには、ベースとするアルゴリズムにローカルサーチを組み合わせるのが一般的であり、これはACOにおいても同様である。ここでは、cASにTSPのローカルサーチとして最も強力な一つであるLin-Kernighan法(LK法)を組み合わせる。

8 cASと他のACOとの比較② ローカル サーチ あり ローカル サーチ なし

9 ACOの応用 ACOアルゴリズムは継続的に実行されるので、リアルタイムで変化に適応することができる。このことから、 ネットワークの経路制御
都市交通システム 　での応用が考えられる。