温度並列シミュレーテッドアニーリング における重要温度 窪田 耕明 (同志社大学大学院) TPSA T1 ・各プロセスは一定温度 ・解自身が温度を選択 ・逐次SAより精度が良い Temparature ・一定間隔で解交換 T2 T3 T4 T5 T6 Time TPSAの解の精度がいいのはなぜ? 一定温度でのアニーリングが有効? Temparature 各温度での解の精度の違い T1 T2 T3 T4 T5 T6 各温度で得られた 解の精度を比較 Time 各温度における解の精度の違いを検証 巡回セールスマン問題(TSP) eil51(51都市,最適解:426) 初期解 最適解 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 Temperature 問題によって,経路長分布は異なる 組み換えで生じる改悪エネルギーが異なる 問題によって重要温度が異なる これからの研究 ・TSPには重要温度がある 他の対象問題について検証 ・問題によって重要温度が違う 適応的に重要温度を見つける手法の提案 新しいヒューリスティック手法の提案 補足資料 SAの基本アルゴリズム SA:焼きなましのアナロジーを模倣 ・生成処理 ・受理判定 減少 エネルギーが ・温度のクーリング 小 の確率で受理 SAの欠点 大 Energy 増加 必ず受理 -(Enext-Ecurrent) exp Temperature ・計算時間がかかる ・温度設定が困難 局所解 最適解 温度並列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の適切な温度パラメータ設定が可能!
© Copyright 2025 ExpyDoc