適応的温度調節機能を持つ温度並列シミュレーテッドアニーリング Adaptive Temperature Parallel Simulated Annealing 同志社大学工学部知識工学科三木光範廣安知之 ○輪湖純也吉田武史最適化とは • 与えられた条件の下で、対象とする問題の中から最も良いものを探すこと最適化問題 ■ 組合せ最適化問題・スケジューリング問題・タンパク質の立体構造予測 ■ 連続最適化問題ヒューリスティック探索 • 遺伝的アルゴリズム（GA） • シミュレーテッドアニーリング（SA） Simulated Annealing (SA) 高温 • SAのアルゴリズム 1.解の生成 2.エネルギーと温度から受理判定 ΔE ≦ 0 1 受理確率：P = exp - ΔE 温度 ( ) ΔE=Enext - Ecurrent ΔE ＞ 0 低温 3.推移 4.温度パラメータを減少（クーリング）特徴温度パラメータと，解の動きが密接に関係ジョブショップスケジューリング問題（JSP） • n個の仕事（Job）をm台の機械（Machine）で処理 • 制約条件：各仕事を処理する機械の順序（技術的順序） • すべての仕事を完成させるまでの時間（Makespan）を最小にするスケジュールを求めるジョブショップスケジューリング問題（JSP） • n個の仕事（Job）をm台の機械（Machine）で処理 • 制約条件：各仕事を処理する機械の順序（技術的順序） • すべての仕事を完成させるまでの時間（Makespan）を最小にするスケジュールを求める温度パラメータ • 組合せ最適化問題にSAを適用した時の問題点 (1) 計算コストが高い (2) 温度スケジュールの設定が困難 • 組合せ最適化問題にSAを適用した時，特定の温度のみの解探索で良好な解を得ることができる [Connolly ‘90,Mark ‘00] 重要温度領域実験対象問題をJSPとして一定温度SAで得られる解精度を比較 JSPにおける重要温度領域 FT10 ABZ9 JSPにも重要温度領域が存在することを確認 •重要温度領域は，問題によって値，範囲が異なる •重要温度領域を特定するには多くの予備実験が必要研究目的 ■最適な温度スケジュール温度スケジュールの設定を自動化重要温度領域を集中的に探索することで性能向上重要温度領域を自律的に探索するメカニズムを考案 ■SAの並列化計算時間の短縮を図る温度並列SA（TPSA）は並列処理に適したモデル適応的温度調節機能を持つ温度並列SA Adaptive Temperature Parallel Simulated Annealing (ATPSA) Temperature Parallel SA (TPSA) 高温度低 1 P= •並列処理との高い親和性 exp( - ΔT・ΔE T・T’ ΔT・ΔE＜0 ) otherwise Temperature Parallel SA (TPSA) 高温度低 •温度スケジュールの設定を自動化 Temperature Parallel SA (TPSA) 高温度低 •温度スケジュールの設定を自動化適応的TPSA (ATPSA) 高温度低適応的温度調節メカニズム温度が適切 → 温度を維持温度が高い → 温度を下げる温度が低い → 温度を上げる適応的TPSA (ATPSA) 高温度低重要温度領域重要温度領域に探索温度範囲を集中させる重要温度領域の特徴 • 高温度，重要温度，低温度の一定温度SAの解の動きを比較 ×（102 ）重要温度領域の特徴 (1) 解品質が良好な範囲に存在 (2) 解の改善を多く生成重要温度指数 • 解の動きを評価する値：改善方向への遷移時に，解のエネルギー（Makespan）と基準値との差を加算 • 基準値は各プロセスが持つ解のエネルギー平均重要温度指数の特徴 (1)解品質が良好な領域に存在 (2)よく解が動く重要温度指数は正になる重要温度指数 • 温度と解の推移は密接に関係 • 重要温度領域での探索は，解品質が良好な領域でよく動く重要温度指数 • 温度によって，重要温度指数の符号が異なる • 重要温度での探索では，重要温度指数は正になる改善を生成しないため値が計算されない適応的TPSA (ATPSA) 高温度低適応的温度調節メカニズム温度が適切 → 温度を維持温度が高い → 温度を下げる温度が低い → 温度を上げる次周期の温度割り当て • 最高温度，最低温度のプロセスが持つ重要温度指数の符号によって次周期の温度範囲を設定 • 最高温度と最低温度の間は等比的に割り当て適応的TPSA (ATPSA) 高温度低適応的温度調節メカニズム温度が適切 → 温度を維持温度が高い → 温度を下げる温度が低い → 温度を上げる適応的TPSA (ATPSA) 高温度低重要温度領域重要温度領域に探索温度範囲を集中させる数値実験 • 解探索能力の比較 • 対象問題：JSP（FT10，ORB1，LA21，LA40，ABZ9）比較手法－ ATPSA（提案手法）－逐次SA（Sequential SA:SSA）高温から低温へクーリングを行う－ PSA（Parallel SA）複数のプロセスが独立に逐次SAを実行－ TPSA 各プロセスに異なる温度を与え，一定周期で解交換パラメータ ATPSA TPSA PSA SSA 生成処理（近傍構造）クリティカルブロック近傍 [ 山田 '94 ] 解の修正 GT法 [ Giffer and Tompson '60 ] 総探索数 1024000 プロセス数解交換（クーリング）周期 64 32 1 1000 32000 最高温度改悪方向への遷移で増加するエネルギーの最大値を50%の確率で受理する温度最低温度クーリング周期で最低1回は改悪方向への遷移を受理する温度温度推移（FT10） ATPSA（提案手法） TPSA ATPSA ：温度が特定範囲に収束 TPSA ：解によって，推移する温度が異なる PSA，SSA ：高温から低温まで一定割合で減少 PSA 温度推移（FT10） ATPSA（提案手法） TPSA ATPSA ：温度が特定範囲に収束 TPSA ：解によって，推移する温度が異なる PSA，SSA ：高温から低温まで一定割合で減少 PSA 温度推移（FT10） ATPSA（提案手法） TPSA PSA ATPSAは重要温度領域に探索温度範囲が集中解探索履歴 • ATPSA，TPSA，PSAの解探索の履歴 FT10 ORB1 • ATPSAの解収束はTPSA，PSAに比べて早い実験結果最適解からの誤差 (30回試行の平均－最適解) 30 25 20 SSA PSA TPSA ATPSA(提案手法) 15 10 5 0 FT10 ORB1 LA21 LA40 ABZ9 対象問題提案手法であるATPSAは，全ての問題に対して他の手法より良好な性能を得るまとめ提案手法：適応的温度調節機能を持つ温度並列SA（ATPSA）提案手法の特徴 •並列処理に適した並列SAモデル •重要温度指数に基づく温度範囲設定 •探索温度範囲が重要温度領域に集中数値実験結果 •JSPを対象問題として解探索能力を比較 •ATPSAはTPSA，PSA，逐次SAよりも良好な性能を示す：提案手法の設定する温度スケジュールは他の手法より優れている