温度並列シミュレーテッドアニーリング における温度範囲の自律的最適化 同志社大学大学院 知的システムデザイン研究室 三木光範 廣安知之 ○吉田武史 最適化問題とは 目的関数の最小化(最大化) ・連続最適化問題 ・組み合わせ最適化問題 LSI配置問題 トラス構造物 タンパク質 の構造解析 スケジュー リング問題 探索空間の拡大により実用的な計算コストで解くことが困難 研究背景 • 最適化問題の複雑化 • ヒューリスティック探索 – 遺伝的アルゴリズム(GA) 生物の進化を模倣 – ニューラルネットワーク ボルツマンマシン – シミュレーテッドアニーリング(SA) 金属の焼き鈍しを模倣 良好な解を短時間で求めることが重要 シミュレーテッドアニーリング 焼き鈍し : 金属をゆっくり冷却し，良質な結晶を生成 SAアルゴリズム 1. 生 成 処 理 2. 受 理 判 定 1 (改良方向) 受理確率P exp ( - ΔE ) 温度 (改悪方向) ΔE=Enext - Enow 3. クーリング 解の動きと温度パラメータが密接に関係 シミュレーテッドアニーリング 焼き鈍し : 金属をゆっくり冷却し，良質な結晶を生成 SAアルゴリズム 高温 1. 生 成 処 理 2. 受 理 判 定 1 (改良方向) 受理確率P exp ( - ΔE ) 温度 (改悪方向) ΔE=Enext - Enow 3. クーリング 解の動きと温度パラメータが密接に関係 低温 温度パラメータ - SA実行中の温度の推移 : 温度スケジュール - 温度スケジュールと解の品質が大きく関係 Temperature 最高温度 クーリング率 高温から低温へ 緩慢に冷却 クーリング周期 最低温度 SA Time ・パラメータチューニング の必要性 ・膨大な計算量 SAの並列化 温度並列SA 並列SA : SAを並列実行し，計算時間を短縮 • • • 独立型並列SA 同期型並列SA 非同期型並列SA 解交換による解精度向上 温度スケジュールは全プロセス同じ 温度並列SA(Temperature Parallel SA : TPSA) High Temp • • 温度スケジュールの自動化 並列処理との高い親和性 ×適切な初期温度設定が困難 ×高温プロセスの効果 Low Temp 研究目的 High Temp Low Temp 解探索過程で 温度範囲を変更 重要な温度領域 温度並列SA 自律的に探索する温度領域が ＋ （ＴＰS A ） 変化するメカニズム 適応的TPSA(Adaptive TPSA : ATPSA) 対象問題 巡回セールスマン問題 Traveling Salesman Problem : TSP • • 代表的な組み合わせ 最適化問題 全ての都市を巡回する 最短の経路を発見 ch150 eil51 gil262 kroA100 pr152 6528 426 2378 21282 73682 温度による解の動きの比較 Temperature 一定温度SAの実験結果(kroA100) SA SA SA SA SA SA 重要な温度領域 Time 一定温度で解探索を行い， 温度と解の関係を検証 それぞれの温度での解の動きを検証 温度による解の動きの比較 温度によって解の動きが大きく異なる 高温度 低温度 低温度 重要な温度 重要な温度 重要な温度領域では他の温度と比べ良好な範囲で解が動く 評価値 解の動きから重要な温度領域を探索するためには 基準となる値と解の 差が大きい温度ほど 重要な温度領域に近い 基準値 差の大きさを示す値 として評価値を導入 評価値 評 価 値：解の動きを評価する値 基 準 値：解探索中にこの値を下回ることで評価値が加算 評価値 = Σ(基準値 - 解) 評価値：大 良好な範囲で解が動く 重要な温度領域を 発見できる 適応的TPSA 解探索 + 評価値計算 同 期 • 探索温度範囲の設定 • 次の周期の基準値決定 • 解交換 適応的TPSA 解探索 + 評価値計算 重要な温度領域 評価値 同 期 温度 前周期の温度範囲 次周期の温度範囲 適応的TPSA 解探索 + 評価値計算 同 期 • 探索温度範囲の設定 • 次の周期の基準値決定 • 解交換 適応的TPSA 解探索 + 評価値計算 同 期 • 探索温度範囲の設定 • 次の周期の基準値決定 • 解交換 重要な温度領域 実験概要 適応的TPSA(ATPSA)とTPSAの性能比較実験 初期最高温度 最大改悪を50%の確率で受理する温度 初期最低温度 最小改悪を解交換周期で1回は受理する温度 総アニーリング数 解交換周期 × 160 解交換周期 都市数 × 20 試行回数 20 実験結果 TPSAにおける温度推移(kroA100) ・重要な温度領域で解探索 するプロセスが少ない ・高温部のみで解交換を 行い，温度プロセスに よって解の品質が大き く異なる 実験結果 ATPSAにおける温度推移(kroA100) ・重要な温度領域に 多くのプロセスが集中 ・解交換が頻繁に行われ， 全プロセスが良好な解 を持つ 実験結果 解探索能力 最適解発見率 適応的TPSA TPSA 結 論 SAにおける温度パラメータの検討 解探索を効率的に行える重要な温度の存在 SAの並列化 温度スケジュールを自動化する温度並列SA(TPSA) 自律的に重要な温度領域を探索する適応的TPSAの提案 • 解の動きを評価する評価値の導入 • 重要温度領域に各プロセスの温度が集中 従来のTPSAから解探索能力を向上することができた 重要温度領域 Temperature 重要温度領域 一定温度で解探索することで 良好な解が得られる温度領域 重要温度領域 ・対象問題によって大きさが 異なる ・重要温度領域を決定するた めに膨大な予備実験が必要 Time 重要温度領域の特徴 一定温度SA 高温から 低温へ Time 重要温度領域の特徴 ・良好な範囲で解が動く 高温度 Temperature Temperature 逐次SA 一定温度で アニーリング Time 高温度 ・低温と比較して 解の動きが激しい 重要温度領域 低温度 低温度 重要温度領域 適応的TPSA 解探索+評価値計算 初期解と 初期温度を 各プロセスに設定 Solution Evaluation 適応的TPSA Master Masterに各プロセスの 評価値と温度を集める 評価値 重要温度領域 温度 Slave 評価値から次の周期の 探索温度範囲を決定する 評価値 適応的TPSA 温度 Slave Master上で 各プロセスの 温度を決定 Master Slaveにそれぞれ に割り当てた温度を送信
© Copyright 2024 ExpyDoc
