シミュレーテッドアニーリング概説 Intelligent Systems Design Lab. 36990706 36000719 池内 智悟 窪田 耕明 研究背景 最適化問題 ヒューリスティック探索手法 -シミュレーテッドアニーリング（SA）， 遺伝的アルゴリズム（GA），etc. 高い計算負荷で並列化は必須 並列SA Simulated Annealing (SA) • 物理現象のモデル化 – 金属の焼きなまし(アニーリング)を計算機上で シミュレート 温度 高 温度 低 ゆっくり冷やす エネルギー 大 エネルギー 小 最適化に利用 SAの基本アルゴリズム ・生成処理 ・受理判定 ・クーリング 生成処理 現在の状態をもとに 次に推移すべき状態を生成 Energy：大 現在の状態 局所解 Energy：小 次の状態 最適解 受理判定 確率1.0で摂動を受理 減少 エネルギーEが －(Ｅnext－Ｅcurrent) 確率 exp Ｔ で摂動を受理 増加 温度 Energy：大 局所解 Energy：小 最適解 クーリング クーリング判定 NO YES クーリング クーリングが早いとき クーリングが遅いとき 山を越えられない なかなか収束しない SAの並列化 SAの短所 ・計算時間が長い． 並列シミュレーテッドアニーリング ・クーリングスケジュール決定困難 温度並列SA （TPSA） SAの並列化 AartsとKorstらによって明らかにされた並列SA 完全独立型 定期同期型 受理時同期型 適応型 非同期型 その他の並列SA Systolic型 PCクラスタにおけるPSAの検討 完全独立型 定期同期型 受理時同期型 Systolic型 連続設計変数空間最適化問題では 最適値は得られなかった． 組合せ最適化問題への適用 PCクラスタにおけるPSAの検討 完全独立型 生成，受理，クーリングを繰り返すSA 一つのプロセッサが担当 最適解 PCクラスタにおけるPSAの検討 定期同期型 最 も 良 い 解 を 分 配 一定期間アニーリング 最 も 良 い 解 を 分 配 最適解 PCクラスタにおけるPSAの検討 受理時同期型 は じ め に 受 理 が 起 こ っ た 解 を 分 配 は じ め に 受 理 が 起 こ っ た 解 を 分 配 最適解 PCクラスタにおけるPSAの検討 Systolic型 生成，受理，クーリングを繰り返すSA 最高温度 高温 低温 最低温度 1プロセッサが担当 PCクラスタにおけるPSAの検討 Systolic型 start 最適解 SAの並列化 SAの短所 ・計算時間が長い 並列シミュレーテッドアニーリング ・クーリングスケジュール決定困難 温度並列SA （TPSA） 温度並列 SA(TPSA) 確率的に良質な解が低温に移動 解交換 最高温 解摂動 受理判定 逐次SA法 解交換 解交換 最低温 低温 高温 解摂動 受理判定 解摂動 受理判定 解摂動 受理判定 TPSA法 Temperature Initial Solution T1 T2 T3 T4 T5 T6 t on Proc1 t on Proc2 t on Proc3 t on Proc4 t on Proc5 t on Proc6 TPSAの利点 ・並列処理との親和性が高い ・温度スケジュールを自動化できる しかし， それぞれのプロセスに与える温度を 最初に決定しなければならない！ 温度パラメータの設定が重要 昨年度の研究目的 温度パラメータの解の精度への 影響を検証する 手段： TPSAを巡回セールスマン問題（TSP）に適用する 32個の温度の中で一番良い探索を している温度が存在するはず 重要な温度 重要な温度を調べる実験 プロセス番号 最高温度 32 31 30 ・ ・ 解交換を行わず 独立に処理 最低温度 3 2 1 ・ ・ 出力された 解を比較 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 温度 低 温度 高 実験結果 拡大 温度 低 温度 高 実験結果 重要な温度は プロセス10からプロセス14付近 重要な温度の影響 検証 （1）重要な温度付近のプロセスが増加すれば 解の精度は良くなるか？ 手法1：従来のTPSA 手法2：温度調節を行ったTPSA 手法3：重要温度に固定したPSA 手法2：温度調節を行ったTPSA このプロセスの 温度を最高温度とする 最高温度 ・ ・ 重要な温度 最低温度 手法2：温度調節を行ったTPSA このプロセスの 温度を最高温度とする 最高温度 重要な温度 最低温度 手法3：重要温度に固定したPSA このプロセスの温度を 32個のプロセスに配る 最高温度 ・ ・ 重要な温度 最低温度 手法3：重要温度に固定したPSA このプロセスの温度を 32個のプロセスに配る 重要な温度 ×３２ 重要な温度の影響 手法1：従来のTPSA 手法2：温度調節を行ったTPSA 手法3：重要温度に固定したPSA １位： 手法3：重要温度に固定したPSA ２位： 手法2：温度調節を行ったTPSA ３位： 手法1：従来のTPSA TPSAは重要な温度を担当している プロセス数が多いほど性能が良い 今後の課題 池内 ・PCクラスタにおける並列SA手法の検討 ・PCクラスタにより有効である並列SA手法の提案 窪田 ・重要な温度のより厳密な調査 ・処理の途中で重要温度を発見し，そこから 重要温度のPSAに切り替える適応的TPSAの提案 付録 TPSAのTSPへの適用 問題pr76 厳密解 : 1.08E+05 温度パラメータ : TPSAで一般的に使用される 従来の方法で決定 重要な温度を挟んだTPSA 不適切な高温 重要な温度付近で 良質な解が求まる ・ ・ ・ 重要な温度 解交換によって 最低温度から出力 不適切な低温 最高温度と最低温度の間に 重要な温度を持つプロセスが存在すれば 比較的良質な解を求められる！ 重要な温度とTPSAの関係 最高温度と 最低温度を変化 最高温度を変化 重要温度 局所探索 最低温度でも 収束しない なぜ解の精度が いいのか？ 最低温度を変化 重要温度 従来の一般的なパラメータの決定 最高温度： 最大の改悪となる状態遷移が 50%の確率で受理されるような温度 最高温度 : 31500 最低温度： 最小の改悪となる状態遷移が解交換周期内に 少なくとも一回は受理されるような温度 最低温度 : 25.3 温度数： 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 終了条件 最大温度を変化 終了条件を短くしても 最低温度を変化 影響が現われない 実験結果 下界からの距離 ＝ 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 生成 x1 Solution x2 SAの基本アルゴリズム No 初 期 設 定 生 成 処 理 受 理 判 定 YES No 推 移 ク YES ク ー ー リ ン リ グ ン 判 グ 定 停 止 条 件 No YES 停 止
© Copyright 2024 ExpyDoc
