温度並列シミュレーテッドアニーリング
における重要温度
窪田 耕明
（同志社大学大学院）
TPSA
T1
・各プロセスは一定温度
・解自身が温度を選択
・逐次SAより精度が良い
Temparature
・一定間隔で解交換
T2
T3
T4
T5
T6
Time
TPSAの解の精度がいいのはなぜ？
一定温度でのアニーリングが有効？
Temparature
各温度での解の精度の違い
T1
T2
T3
T4
T5
T6
各温度で得られた
解の精度を比較
Time
各温度における解の精度の違いを検証
巡回セールスマン問題（TSP）
eil51（５１都市，最適解：４２６）
初期解
最適解
80
80
70
70
60
60
50
50
40
40
30
30
20
20
10
10
0
0
0
10
20
30
40
50
60
70
80
0
10
20
30
40
50
60
70
80
実験結果
eil51　(TSPLIB)
750
700
経路長
650
600
550
500
450
最適解
400
1.0E-02
1.0E-01 1.0E+00 1.0E+01 1.0E+02 1.0E+03 1.0E+04 1.0E+05 1.0E+06
温度
TPSAにおける重要温度
T1
無駄な探索
Temparature
T2
T3
効率の良い探索
（重要温度）
T4
T5
局所解に収束
T6
Time
重要温度の存在を確認できた
問題による重要温度の違い
メトロポリス基準
exp
－ΔE
Ｔemperature
問題によって，経路長分布は異なる
組み換えで生じる改悪エネルギーが異なる
問題によって重要温度が異なる
これからの研究
・TSPには重要温度がある
他の対象問題について検証
・問題によって重要温度が違う
適応的に重要温度を見つける手法の提案
新しいヒューリスティック手法の提案
補足資料
SAの基本アルゴリズム
SA：焼きなましのアナロジーを模倣
・生成処理
・受理判定
減少
エネルギーが
・温度のクーリング
小
の確率で受理
SAの欠点
大
Energy
増加
必ず受理
－(Ｅnext－Ｅcurrent)
exp
Ｔemperature
・計算時間がかかる
・温度設定が困難
局所解
最適解
温度並列SA（TPSA）
T1
Temparature
TPSA
SA
・生成処理
・受理判定
・解交換
T2
T3
T4
T5
T6
Time
各プロセスに温度を割り当てる
TPSAの利点
・並列処理との親和性が高い
・温度スケジュールの自動化
温度パラメータの設定が重要
Temparature
TPSA
T1
T2
T3
T4
T5
T6
Time
重要温度
Temparature
一定温度でのアニーリングが有効
T1
T2
T3
T4
T5
T6
研究目的
無駄な探索
効率の良い探索
（重要温度）
局所解に収束
Time
・巡回セールスマン問題において重要温度の存在を確認する．
・重要温度の規則性を検証する．
TPSAの適切な温度パラメータ設定が可能！