研究のまとめ:アントコロニー最適化 (Ant Colony Optimization: ACO)
アリの摂食行動から着想を得たアルゴリズム。
フェロモンという揮発性物質を模したパラメータを最適化する。
組合せ最適化やネットワークルーティングなどに応用。
ここでは巡回セールスマン問題など組合せ最適化問題を解く手法を記載。
Ant System (AS)
Ant system: optimization by a colony of cooperating agents - IEEE Journals & Magazine
もっとも基本となるアルゴリズム。巡回セールスマン問題を解く。
性能はあまり高くないが、アリのアナロジーを始めて取り入れたエポックメイキングな手法。
Elitist Ant System (ASelite)
Ant system: optimization by a colony of cooperating agents - IEEE Journals & Magazine
もっとも良い解に追加でフェロモンを分泌する。
Rank based Ant System (ASrank)
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.4735
評価順位が高い解ほどフェロモンが多く分泌される。
MAX-MIN Ant System (MMAS)
MAX-MIN Ant system
アルゴリズム実行中に発見した最良解、もしくは一定の確率で反復中に発見した最良解にフェロモンを分泌する。
フェロモン量に上下限値を設定することで生成される解の多様性を維持。
フェロモン量の偏り度合い(λ-branching factor)に応じてフェロモン量を再初期化。
性能高く、応用事例も多い。
Ant Colony System (ACS)
Ant colony system: a cooperative learning approach to the traveling salesman problem - IEEE Journals & Magazine
アルゴリズム実行中に発見した最良解にフェロモンを分泌。
解を生成するときに通った経路のフェロモン量を減少させる局所更新。
こちらも性能高い。
Hyper-Cube ACO (HC-ACO)
The hyper-cube framework for ant colony optimization - IEEE Journals & Magazine
生成した解の評価値の総和により正規化した値を分泌する。
正規化により問題の規模に対してロバストになる。
上記の手法と組み合わせて使える。(HC-ASrank、HC-MMASなどなど)
特定の分布推定アルゴリズム(Population based Incremental Learning、compact Genetic Algorithm)とほぼ等価。
Ant Colony Optimization
ACOを考案したMarco Dorigo先生のページ。
重要な論文、プログラムが公開されている。
Ant Colony Optimization (A Bradford Book)
- 作者: Marco Dorigo,Thomas Stuetzle
- 出版社/メーカー: A Bradford Book
- 発売日: 2004/06/04
- メディア: ハードカバー
- クリック: 78回
- この商品を含むブログ (1件) を見る
2004年なので内容が少し不足してきたかも?