温度並列シミュレーテッドアニーリングにおける 重要温度と改悪エネルギー 知的システムデザイン研究室 16970128 吉田武史 Intelligent Systems Design Lab. 研究背景 実社会での最適化問題 スケジュール管理 荷物運搬の効率化 問題の複雑化 ヒューリスティック手法の適用 シミュレーテッドアニーリング(SA) 遺伝的アルゴリズム(GA) -etc 膨大な計算量 ヒューリスティック手法の並列化 様々なアルゴリズムの研究が行われている Intelligent Systems Design Lab. Simulated Annealing (SA) Intelligent Systems Design Lab. SAにおける温度スケジュール 温度の移り変わり ＝温度スケジュール 解の精度と密接に関係 パラメータの設定が困難 膨大な計算時間 ＳＡの並列化 Intelligent Systems Design Lab. 温度並列ＳＡ(TPSA) • • 各プロセスが一定温度でアニーリング 確率的に解交換を行い温度スケジュールを自動化 Intelligent Systems Design Lab. 重要温度とは ＳＡにおいて重要温度が存在する 解探索を最も効率的に行う温度 Intelligent Systems Design Lab. 重要温度とは 激しく活動する人 冷静かつ活発な人 ＳＡにおいては効率的に解を探索できる 消極的な人 Intelligent Systems Design Lab. 重要温度とは 解探索を最も効率的に行う温度 ＴＰＳＡにおいて，この温度を含むことで 良好な解を得る Intelligent Systems Design Lab. 重要温度の確認 解交換を行わないＴＰＳＡ 最も良好な解を得たプロセスの温度が重要温度 Intelligent Systems Design Lab. 巡回セールスマン問題（ＴＳ Ｐ） 代表的な組合せ最適化問題 すべての町を一度通過する経路を導く 最短の経路長を見つける ＴＳＰのスケールや形が 異なる問題を選択 eil51 kroA100 pr76 通り Intelligent Systems Design Lab. 重要温度の確認 eil51 eil51における 重要温度は２付近 Intelligent Systems Design Lab. 各問題での重要温度 問題名 最適解 重要温度 eil51 429 1.8～2.2 kroA100 21282 pr76 eil51 40～60 問題のスケールや形に よって重要温度が異なる 重要温度には幅がある 108159 250～400 kroA100 pr76 Intelligent Systems Design Lab. 研究目的 ＳＡにおける重要温度の原理を解明 ＴＰＳＡにおいて重要温度付近で多くの解探索が 行えるパラメータ設定に Intelligent Systems Design Lab. 温度とΔＥ 改良では受理して状態遷移 改悪ではΔＥと温度より受理判定 ＥＸ） exp 温度が１０の時 -(120-110) 10 = 0.367 この受理確率で改悪を受理する 温度を用いない受理基準 受理するΔＥによる解の精度の比較 改悪エネルギー(ΔＥ)と温度 は密接に関係 Intelligent Systems Design Lab. 実験結果 特定の大きさ以下のΔＥ を受理することで良好な 解を得る Intelligent Systems Design Lab. 重要温度と改悪 温度と共に受理確率が変化する 重要温度は重要ΔＥ周辺まで の改悪を適度に受理する温度 重要ΔＥを適度な確率で受理 する温度を用いてＴＰＳＡの パラメータ設定が行える Intelligent Systems Design Lab. 最後に まとめ ＴＳＰを解くためには，ある大きさの改悪ΔＥを 受理しなくてはならない 重要温度はそれぞれの問題における重要な改悪を 適度に受理する温度である 今後の課題 適応的なパラメータ設定方法を用いた ＴＰＳＡの精度を検証する ＴＳＰ以外の問題において重要温度が存在するか確認する Intelligent Systems Design Lab. Intelligent Systems Design Lab. SAにおける温度スケジュール 高い温度から低い温度へ ゆっくりと冷却して 良好な解を得る パラメータの設定が困難 膨大な計算時間 重要な温度 最も解探索を 効率的に行う温度 一定温度の解探索で 良好な解を得る Intelligent Systems Design Lab. TSPにSAを適用 ①解を生成 ②状態を変えるか判定（受理判定） ③温度を下げる（クーリング） 問題点 経路長 パラメータの設定が困難 計算時間が膨大 一定温度で良好な解が見つかる 重要な温度が存在する 大 温度 小 Intelligent Systems Design Lab. 重要温度の確認 450 対象問題 eil51 51 429 445 440 経路長 都市数 最適解 435 430 重要温度 ２ 最適解 425 1.E-01 1.E+00 1.E+01 各プロセスが持つ温度 Intelligent Systems Design Lab. 実験結果 ある大きさ以下の改悪を受理する ことのみで最適解を見つける 500 Method-1(h=0.2) Method-1(h=2) Method-2 経路長 480 460 440 最適解 420 0 2 4 ΔE 6 8 10 0 の大きさ Intelligent Systems Design Lab. 受理確率と改悪ΔＥ Intelligent Systems Design Lab. ΔEに関する検証 受理基準の異なるアルゴリズム Metropolis基準 exp -ΔE 温度T Method-1 ΔE Method-2 ΔE 0 ＜ 0 ＜ ΔE ＜ΔE 0+h 0 ＜ΔE ＜ ΔE 0 ΔE 受理 各ＴＳＰでΔＥ ０を変化させて 解の精度を比較する Intelligent Systems Design Lab. TPSAのパラメータ設定 考察より 重要温度と改悪が密接に関係する ある大きさの改悪を受理すれば，良好な解を得る 研究目的 重要温度を割り当てるプロセスが多いパラメータを設定する 最高温度 各プロセスのΔＥを検証する 生成するΔＥ 受理するΔＥ 重要温度 受理する改悪ΔＥ 最低温度 Intelligent Systems Design Lab. SAにおける温度 受理判定に温度は影響 改良方向 次状態を受理して解を遷移 100 改悪方向 Metropolis基準で受理確率を出す その確率で次状態を 受理するか決定する 経路長 110 現状態 120 次状態 exp -ΔE 温度T = exp -(120-110) 温度T Intelligent Systems Design Lab. 温度によるΔＥの比較 770 12 温度が低いプロセス 温度が高いプロセス 8 700 経路長 ΔＥの大きさ 4 630 0 560 -4 eil51の最適解 490 -8 420 -12 1.E-02 1.E-02 1.E+00 1.E+00 1.E+02 1.E+04 1.E+06 各プロセスが持つ温度 生成するΔＥ 受理するΔＥ 受理する改悪ΔＥ Intelligent Systems Design Lab. 局所解からの改悪 最適解 局所解 最適解と局所解の形が近似してる 局所解を脱出するための改悪を検証 局所解からの最大改悪ΔＥ 経路長として 半径の２倍大きくなる 半径は平均経路長 （経路長／都市数）に近似 局所解からの改悪ΔＥの最大値は 平均経路長の２倍に近似できる Intelligent Systems Design Lab. TPSAのパラメータ設定 最高温度 効率的なパラメータ設定 最高温度と最低温度の間に 重要温度が幅広く設定される 平均経路長 最低温度 Intelligent Systems Design Lab.
© Copyright 2024 ExpyDoc
