温度並列シミュレーテッドアニーリングの 巡回セールスマン問題への適用と 温度設定に関する考察 知的システムデザイン研究室 16960038 窪田 耕明 研究背景 ヒューリスティック探索手法 -シミュレーテッドアニーリング（SA）， 遺伝的アルゴリズム（GA），etc. 高い計算負荷で並列化は必須 並列アルゴリズム -並列SA，分散GA，etc. 温度並列SA（TPSA） Simulated Annealing (SA) • 物理現象のモデル化 – 金属の焼きなまし(アニーリング)を計算機上で シミュレート 温度 高 温度 低 ゆっくり冷やす エネルギー 高 エネルギー 低 最適化に利用 SAの基本アルゴリズム ・生成処理 ・受理判定 減少 エネルギーEが 増加 ・温度のクーリング 確率1.0で摂動を受理 －(Ｅnext－Ｅcurrent) 確率 exp Ｔ で摂動を受理 温度 E：高 局所解 E：低 最適解 SAの並列化 SAの長所 複雑な問題が解ける SAの短所 計算時間が長い． クーリングスケジュール決定困難 新しい手法 温度並列SA（TPSA） 温度並列 SA(TPSA) 逐次SA法 アルゴリズム ・生成処理 ・受理判定 ・解交換 TPSA法 Temperature 逐次SA：クーリング TPSA：解交換 T1 T2 T3 Initial Solution T4 T5 T6 t on Proc1 t on Proc2 t on Proc3 t on Proc4 t on Proc5 t on Proc6 Time TPSAの利点 ・並列処理との親和性が高い ・温度スケジュールを自動化できる しかし， それぞれのプロセスに与える温度を 最初に決定しなければならない！ 温度パラメータの設定が重要 研究目的 温度パラメータの解の精度への 影響を検証する 手段： TPSAを巡回セールスマン問題（TSP）に適用する TPSAのTSPへの適用 対象問題 TPSAを詳細に評価するには ・最適解が既知 ・比較すべきアルゴリズムの実装方法が明確かつ容易 TSP 問題pr76 厳密解 : 1.08E+05 従来の一般的なパラメータの決定 最高温度： 最大の改悪となる状態遷移が 50%の確率で受理されるような温度 最高温度 : 31500 最低温度： 最小の改悪となる状態遷移が解交換周期内に 少なくとも一回は受理されるような温度 最低温度 : 25.3 温度数： 32温度 温度の振り分け： 最高温度と最低温度の間を 等比的に割り当てる 重要な温度 32個の温度の中で一番良い探索を している温度が存在するはず 重要な温度 実験 重要な温度を見つける実験 プロセス番号 最高温度 32 31 30 ・ ・ 解交換を行わず 独立に処理 最低温度 3 2 1 ・ ・ 出力された 解を比較 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 拡大 温度 低 温度 高 実験結果 重要な温度は プロセス10(200度)からプロセス14(502度)付近 重要な温度とTPSAの関係 最高温度と 最低温度を変化 最高温度を変化 重要温度 局所探索 最低温度でも 収束しない なぜ解の精度が いいのか？ 最低温度を変化 重要温度 重要な温度を挟んだTPSA 不適切な高温 重要な温度付近で 良質な解が求まる ・ ・ ・ 重要な温度 解交換によって 最低温度から出力 不適切な低温 最高温度と最低温度の間に 重要な温度を持つプロセスが存在すれば 比較的良質な解を求められる！ 重要な温度の影響 検証 （1）解は重要な温度付近のみから 得られているのではないか？ （2）重要な温度付近のプロセスが増加すれば 解の精度は良くなるか？ 手法1：従来のTPSA 手法2：温度調節を行ったTPSA 手法3：重要温度に固定したPSA 手法2：温度調節を行ったTPSA 最低温度の解の精度と同等の 解の精度のプロセスの温度を 最高温度とするTPSA 最高温度 ・ ・ 重要な温度 最低温度 このプロセスの 温度を最高温度とする 手法2：温度調節を行ったTPSA 最低温度の解の精度と同等の 解の精度のプロセスの温度を 最高温度とするTPSA 最高温度 重要な温度 最低温度 このプロセスの 温度を最高温度とする 手法3：重要温度に固定したPSA 解の精度が一番良いプロセスの 温度を全てのプロセスに配り， 独立に探索するPSA 最高温度 ・ ・ 重要な温度 最低温度 このプロセスの温度を 32個のプロセスに配る 手法3：重要温度に固定したPSA 解の精度が一番良いプロセスの 温度を全てのプロセスに配り， 独立に探索するPSA 重要な温度 ×３２ このプロセスの温度を 32個のプロセスに配る 実験結果 下界からの距離 ＝ 100× Steps 手法1 巡回路長 下界値（最適解） 手法2 -1 手法3 Temp. 250 400 500 10000 0.42 0.37 0.01 0.23 0.80 20000 0.26 0.21 0.00 0.22 0.32 50000 0.02 0.03 0.00 0.10 0.24 実験結果 下界からの距離 ＝ 100× Steps 手法1 巡回路長 下界値（最適解） 手法2 -1 手法3 Temp. 250 400 500 10000 0.42 0.37 0.01 0.23 0.80 20000 0.26 0.21 0.00 0.22 0.32 50000 0.02 0.03 0.00 0.10 0.24 実験結果 下界からの距離 ＝ 100× Steps 手法1 巡回路長 下界値（最適解） 手法2 -1 手法3 Temp. 250 400 500 10000 0.42 0.37 0.01 0.23 0.80 20000 0.26 0.21 0.00 0.22 0.32 50000 0.02 0.03 0.00 0.10 0.24 まとめ 温度パラメータの設定について考察 ・解の精度を良質にする 重要な温度が存在する ・重要な温度を含んだTPSAならば， どんな最高温度，最低温度でも 比較的良質な解を得ることができる ・重要な温度を持つプロセスが 多いほど解の精度が良くなる 今後の課題 重要温度だけで構成されるPSAは 最も性能が良い 重要温度を調べ，わかった時点でその温度を 全てのプロセスに配り独立に探索を行うようなTPSA Time 最高温度 重要温度 最低温度 0 t t+1 付録 概要 ・研究背景 ・逐次SA，温度並列SAについて ・本研究の目的 ・対象問題（TSP） ・温度パラメータの設定に関する考察 ・まとめ 2-opt近傍 e e f f a e1 d a e3 e2 c b c d e4 b データ構造 e K-d木 f a e1 d e2 c b 重要な温度 最大温度を変化 重要な温度 最大温度を変化 重要な温度 最低温度を変化 重要な温度 最低温度を変化 終了条件 最大温度を変化 終了条件を短くしても 最低温度を変化 影響が現われない 実験結果 下界からの距離 ＝ 100× TPSA Data Best pr76 巡回路長 下界値（最適解） Short SA Ave. Worst Best -1 Long SA Ave. Worst Best Ave. Worst 0.00 0.02 0.22 0.00 0.40 0.97 0.00 0.01 0.11 kroA100 0.00 0.00 0.00 0.00 0.52 1.09 0.00 0.15 0.40 lin105 0.00 0.00 0.00 0.00 0.43 1.37 0.00 0.00 0.00 ch150 0.00 0.05 0.27 0.04 0.60 1.29 0.04 0.30 0.53 tsp225 0.00 0.07 0.21 0.42 1.61 3.73 0.06 0.15 0.28 重要な温度とTPSAの関係 最大温度を変化 重要な温度とTPSAの関係 最低温度を変化 実験結果 下界からの距離 ＝ 100× Steps 10000 20000 50000 100000 巡回路長 下界値（最適解） 手法1 手法2 0.42 0.26 0.02 0.02 0.37 0.21 0.03 0.01 -1 手法3 Temp. 200 0.04 0.00 0.00 0.00 250 0.01 0.00 0.00 0.00 320 0.04 0.00 0.00 0.00 400 0.23 0.22 0.10 0.07 500 0.80 0.32 0.24 0.17 200000 0.02 0.00 0.00 0.00 0.00 0.00 0.16 kroA100 Maximum kroA100 Minimum lin105 Maximum lin105 Minimum ch150 Maximum ch150 Minimum tsp225 Maximum tsp225 Minimum
© Copyright 2024 ExpyDoc
