ACOにおける多様性調節の効果

ACOにおける多様性維持の効果
名古屋大学大学院人間情報学研究科
○中道義之有田隆也
はじめに

組み合わせ最適化問題



最適解を求めることが極めて困難
精度の高い解であれば実用上問題がない
TSP(Traveling Salesman Problem)

何ヶ所かの都市と、その都市間の距離が与えられ
たとき、すべての都市を巡り元に戻る最短の順回
路を求める問題
ACOとは

メタヒューリスティック


ACO、 NN、SA、GA等
ACO(Ant Colony Optimization)




Ant System[Dorigo1992]
蟻の群れの振る舞いを模した
フェロモンコミュニケーション
問題によってはの他のメタヒューリスティックと
比べても非常によい成績
ASの基本的なアルゴリズム
1.
2.
初期化
終了条件(反復回数)を満たすまで
1.
すべてのエージェントについて
1.
解(巡回路)を獲得するまで
1.
2.
2.
3.
フェロモン情報に基づいた確率的な枝選択
過去の行動の記憶の更新
解を評価しフェロモンの情報を更新
最了解を出力し終了
ASにおける枝選択
フェロモン
 ij (t )
都市jを選択
する確率
pijk (t ) 
[ ij (t )] [ jl ]


[

(
t
)]
[

]
 il
il
lN ik
j  Nik
ij  1 dij
ヒューリスティックな情報
フェロモンの分泌と更新

フェロモンの分泌
k
k

Q L (t ) if (i, j )  T (t )
k
 ij (t )  
k
if (i, j )  T (t )
 0

フェロモンの情報の更新
m
 ij (t  1)  ij (t )    (t )
k 1
k
ij
ポジティブフィードバック
フェロモンによる枝選択
↓
巡回路の獲得
巡回路への
フェロモンの分泌
多様性
メタヒューリスティックにおける多様性
 集中化(intensification)


よい解の近くを集中的に探索
多様化(diversification)

構造の異なる解を探索
両者をどのようにバランスするか？
 ＧＡでは突然変異という連続的かつ明示的に多
様性を制御することができるパラメータがある
目的
ACOに多様性を調整する機構を導入し、
その効果を検討する。
ランダム選択
ランダム選択率rの確率で、フェロモンに
よる枝選択を行わず、未訪問都市の中か
ら都市をランダムに選択するという操作
ランダム選択
ASrankへの適用



ASrank[Bullnheimer1999]
きわめて優秀な成績をあげている最新の
ACOの1つ
多様性不足に基づくと思われる性能の限
界
ASrankの特徴

ランク付けによるフェロモンの分泌
(   ) Q L
 ij  
0




if (i, j )  T

if (i, j )  T
それまでの時点における最良の巡回路へ
のフェロモンの分泌
*


Q
L
(
t
)
if
(
i
,
j
)

T
(t )
*

 ij (t )  
*
0
if (i, j )  T (t )

フェロモンの重み
  6, m  51の場合
その時点の最良
ランク1
ランク2
ランク3
ランク4
ランク5
ランク6～51
0
2
4
重み
6
8
数値実験




51都市のTSP(TSPLIBのeil51)
各パラメータはそれぞれの論文で良いと主
張されている値
ランダム選択率は0.01～0.10
10000ターンを1試行とし、10試行
結果(巡回路長)
現在発表されている結果[Stüzle2000等]の中では最も良い
結果(標準偏差)
ユニークな巡回路数の推移
ASrank
Asrank+ランダム選択(0.01)
ユニークな巡回路数の推移
Asrank+ランダム選択(0.10)
Asrank+ランダム選択(0.05)
生み出される多様性


フェロモンの濃度に応じた枝選択から逃れ
るという意味での探索(巡回路)に関する多
様性
集中化しようとしている枝ではない別の良
い枝にもフェロモンを分泌するという意味
でのフェロモン分布に関する多様性
メカニズム
確率的なランダム選択を含
むフェロモンによる枝選択
→ 巡回路の獲得
巡
回
路
の
良
さ
(3)
(1)
巡回路への
フェロモンの分泌
(2)
エリートによる巡回路
ランダム選択による巡回路
ポジティブフィードバックが内部から壊れ
た結果としてより良い解が求まる。
終わりに




多様性を明示的かつ連続的に調節するランダム
選択をACOに導入する手法を提案
ランダム選択率を適切に設定することにより、性
能を向上させることが可能であることを提示
探索の多様化とフェロモンの多様化の両者を利
用してポジティブフィードバックを内側から壊す形
で最適解に至るというメカニズムの出現
他の問題(70都市)でも同様の結果を得ている

Download Report