遺伝的アルゴリズムを用いた 適応的温度スケジュールを持つ並列シミュレーテッド アニーリング 同志社大学大学院 工学研究科 知識工学専攻 ○輪湖 純也, 三木 光範, 廣安 知之 MPS symposium 2004 Doshisha University, Kyoto, Japan 研究対象 最適化とは • 与えられた条件の下で， 対象とする問題の中から最も良いものを探すこと． LSI配置問題 最適化問題 ■ 組合せ最適化問題 ・巡回セールスマン問題 ・スケジューリング問題 ■ 連続最適化問題 ・タンパク質の立体構造予測 巡回セールスマン問題 ヒューリスティック探索 • 遺伝的アルゴリズム（GA） • シミュレーテッドアニーリング（SA） MPS symposium 2004 タンパク質立体構造予測 Doshisha University, Kyoto, Japan Simulated Annealing (SA) • 組合せ最適化問題に有効な汎用近似解法 • 金属を緩慢に冷却する「焼き鈍し」を模倣 アルゴリズム 1. 初期状態の生成 2. 次状態の生成 3. エネルギー差と温度から受理判定 E 0 1 P ( Enext Ecurrent ) exp E 0 Tem perature High temperature Local minimum Low temperature Global minimum 4. 状態推移 5. 温度パラメータを減少（クーリング） • 温度スケジュール : SA試行中の温度T の推移 • SAの欠点 : 温度スケジュールを決定するのは容易でない 緩慢な冷却により多くの計算量が必要 MPS symposium 2004 Doshisha University, Kyoto, Japan SAの温度パラメータと温度スケジュール SAの温度パラメータ Temperature •最高温度（初期温度） •最低温度（終了温度） •クーリング周期 •クーリング回数 •クーリング率 Max Temperature Min Temperature Time • 高い温度から指数的に緩慢に冷却する方法が最も一般的 多くの予備実験からのパラメータチューニングが必要 • 特定の温度のみの解探索で良好な結果が得られる [Mark 2000] この特定温度(重要温度)を特定することは容易でない MPS symposium 2004 Doshisha University, Kyoto, Japan SAの温度パラメータと温度スケジュール SAの温度パラメータ Temperature •最高温度（初期温度） •最低温度（終了温度） •クーリング周期 •クーリング回数 •クーリング率 Max Temperature Min Temperature Time • 高い温度から指数的に緩慢に冷却する方法が最も一般的 多くの予備実験からのパラメータチューニングが必要 • 特定の温度のみの解探索で良好な結果が得られる [Mark 2000] この特定温度(重要温度)を決定することは容易でない MPS symposium 2004 Doshisha University, Kyoto, Japan 重要温度領域（巡回セールスマン問題） - eil101 TSP Optimum eil101 629 1.1 ~ 2.5 kroA200 29368 27 ~ 53 lin318 42029 20 ~ 39 pr439 107217 44 ~ 72 rat575 6773 1.7 ~ 3.9 48912 14 ~ 27 d657 Topt region • 巡回セールスマン問題には，重要温度領域が存在する． ただし，この値や範囲は問題毎に異なる． MPS symposium 2004 Doshisha University, Kyoto, Japan 研究目的 • 温度スケジュールの自動化を可能にする新たなSAの開発 • 問題毎に異なる重要温度を適応的に特定 遺伝的アルゴリズム(GA)により，重要温度を特定する． 並列化による多点探索が必要． Parallel SA + GA for Temperature Parallel SA with Adaptive Temperature determined by Genetic Algorithm (PSA/AT(GA)) MPS symposium 2004 Doshisha University, Kyoto, Japan PSA/AT(GA)のアルゴリズム SA L : 温度交換周期 SA L L SA Solution SA Temperature（個 体） 0 1 2 3 GA operation SAの1プロセスにGAの1個体(温度)を割当て SAの実行 + GAの適合度計算 同期後，GAにより新たな温度を生成 各SAプロセスに温度を設定 MPS symposium 2004 Doshisha University, Kyoto, Japan 解の動きと温度の関係 - eil101 - 最高温度 最低温度 重要温度 一定温度SA • 重要温度領域での解の特徴 – 解品質が良好な領域で，比較的良く動く • 解の動きを評価することで，温度の良し悪しを判定できる MPS symposium 2004 Doshisha University, Kyoto, Japan 適合度計算 • 適合度(Fitness)は，解の動きを評価する値 • 適合度計算は，同期周期L までの間， 基準値E とエネルギー値Ek との差を加算して算出 • ただし，適合度計算は，受理時のみ • 基準値は，全プロセスのエネルギーの平均値 L k 1 Solution Energy Fitness ( E E k ) Average Annealing Steps: k MPS symposium 2004 Doshisha University, Kyoto, Japan Genetic Algorithm (GA) • 生物の進化を模倣した進化的計算手法 • 同期毎にGAを適用し，新たな個体(温度)を生成 • 実数値GA [Eshelman93] を使用 GAオペレータ Individual Population MPS symposium 2004 Selection 適合度の高い個体が 生き残る Crossover 個体間の情報交換 Mutation 個体情報の変更 Doshisha University, Kyoto, Japan 選択(Selection) • 温度と解の動きは密接に関係している． • 適合度は，解の動きを評価する指標である． Energy Steps Fitness : low Low temperature Energy Important temperature Energy High temperature Steps Fitness : high Baseline Steps Fitness : low • 重要温度での探索では，適合度が高くなるように設計． • 重要温度で探索するSAプロセスは， GAによって次世代にも生き残る確率が高い． MPS symposium 2004 Doshisha University, Kyoto, Japan 交叉(Crossover) • BLX-αを用いた実数値GAを採用 BLX-α 親個体（p1,p2）の区間d から両側にαd だけ拡張した 区間から一様分布で子個体を生成 指数型クーリングに対応するため， 温度T を 対数にした値X を用いる． X log10 T MPS symposium 2004 Doshisha University, Kyoto, Japan 突然変異(Mutation) • 正規分布を用いて， 良好な子個体の付近に，突然変異個体を発生させる． 生成確率 平均μ ：子個体の温度 標準偏差σ：β・ｄ (0<β<1) (子個体) d MPS symposium 2004 Doshisha University, Kyoto, Japan GAのパラメータ 値 パラメータ 個体数(プロセス 数) 32 選択方法 トーナメント選択（サイズ：2） 交叉方法 BLX-α α値 0.5 交叉率 0.3 突然変異方法 β値 突然変異率 MPS symposium 2004 子個体を中心とした正規分布 0.05 0.03125(1/32) Doshisha University, Kyoto, Japan PSA/AT(GA)のアルゴリズム SA SA SA Solution SA Temperature（個 体） 0 1 2 3 GA operation SAの1プロセスにGAの1個体を割当て SAの実行 + GAの適合度計算 同期後，GAにより新たな温度を生成 各SAプロセスに温度を設定 L L L : 温度交換周期 重要温度領域に探索温度範囲を収束させる MPS symposium 2004 Doshisha University, Kyoto, Japan 数値実験 • 対象問題： ・巡回セールスマン問題（TSP） ・ジョブショップスケジューリング問題（JSP） • 比較手法： ・PSA/AT(GA)（提案手法） ・完全独立型並列SA（Parallel SA：PSA） ・温度並列SA（Temperature Parallel SA : TPSA） • 比較項目： ・解探索能力 ：最適解との誤差率(%) ・解の収束速度：良好な解に到達するまでの探索数 MPS symposium 2004 Doshisha University, Kyoto, Japan 比較手法 Max Temperature ・複数のプロセスが独立に 逐次SAを行なう ・全プロセスが 同じ温度スケジュール ・全プロセスの中から最良解を選択 • 温度並列SA（TPSA） Temperature • 完全独立型並列SA（PSA） Min Temperature Steps High T ・各プロセスに異なる温度を割当て， 解探索途中で解交換を行う ・温度スケジュールの自動化 ・並列処理との高い親和性 Low T Steps MPS symposium 2004 Doshisha University, Kyoto, Japan パラメータ パラメータ TSP JSP プロセス数 同期周期 1プロセスの評価計算回数 32 都市数×20 1000 同期周期×160 32000 試行回数 50 最高温度 最大となる改悪を 50%の確率で受理する温度 最低温度 最小の改悪を 同期周期中に1回は受理する温度 MPS symposium 2004 Doshisha University, Kyoto, Japan 解探索能力に関する実験結果(TSP) 2.5 Error ratio(%) 2 PSA/AT(GA) PSA TPSA 1.5 1 0.5 0 eil101 kroA200 lin318 pr439 rat573 d657 TSP Problems 提案手法であるPSA/AT(GA)は， 全ての問題に対してTPSAより良好，PSAとほぼ同等の性能を有する MPS symposium 2004 Doshisha University, Kyoto, Japan 解の収束速度に関する実験結果 PSA： 最終段階に到達した時に はじめて良好な解を得ることができる - pr439 - Error ratio(%) TPSA： 解の収束速度は速いが， 解探索能力が弱い PSA/AT(GA)： 解の収束速度，解探索能力ともに良好 Num. of annealing steps(×10 5 ) MPS symposium 2004 Doshisha University, Kyoto, Japan 温度スケジュール(全プロセス) Temperature - eil101 - Num. of annealing steps Num. of annealing steps Num. of annealing steps PSA/AT(GA)：温度が特定範囲に収束 TPSA : 解によって，推移する温度が異なる PSA ：高温から低温まで一定割合で減少 MPS symposium 2004 Doshisha University, Kyoto, Japan 温度スケジュール(最良解のプロセスのみ) Temperature - eil101 - Num. of annealing steps Num. of annealing steps Num. of annealing steps PSA/AT(GA)：温度が特定範囲に収束 TPSA : 解によって，推移する温度が異なる PSA ：高温から低温まで一定割合で減少 MPS symposium 2004 Doshisha University, Kyoto, Japan 温度スケジュール(最良解のプロセスのみ) Temperature - eil101 - Num. of annealing steps Num. of annealing steps Num. of annealing steps PSA/AT(GA)の収束温度範囲は，重要温度領域と一致 MPS symposium 2004 Doshisha University, Kyoto, Japan 解探索能力に関する実験結果(JSP) 3 PSA/AT(GA) PSA TPSA Error ratio(%) 2.5 2 1.5 1 0.5 0 FT10 FT20 ORB1 ORB3 LA21 LA40 JSP Problems 提案手法であるPSA/AT(GA)の 高い探索能力が，JSPについても確認できる． MPS symposium 2004 Doshisha University, Kyoto, Japan まとめ 提案手法： 遺伝的アルゴリズムを用いた適応的温度スケジュール持つ 並列シミュレーテッドアニーリング(PSA/AT(GA)) PSA/AT(GA)の特徴 • 並列に実行するSAの温度をGAを用いて決定 • 温度スケジュールの設定を自動化する 数値実験 • TSP，JSPを対象問題として解探索能力，解の収束速度を比較 • PSA/AT(GA)は， • PSAと同等，TPSAより良好な解探索能力を有する • PSAより解の収束速度が速い 提案手法の重要温度領域に収束する 温度スケジュールは，解探索に有効である． MPS symposium 2004 Doshisha University, Kyoto, Japan MPS symposium 2004 Doshisha University, Kyoto, Japan 研究目的 • SAの研究に求められていること ・パラメータ(温度スケジュール)設定の簡単化 ・アルゴリズムの高速化 ・解探索能力の向上 • パラメータ設定の簡単化 （=温度スケジュールの自動化） MPS symposium 2004 Doshisha University, Kyoto, Japan ジョブショップスケジューリング問題（JSP） • n個の仕事（Job）をm台の機械（Machine）で処理 • 制約条件 ：各仕事を処理する機械の順序（技術的順序） • すべての仕事を完成させるまでの時間（Makespan） を最小にするスケジュールを求める MPS symposium 2004 Doshisha University, Kyoto, Japan ジョブショップスケジューリング問題（JSP） • n個の仕事（Job）をm台の機械（Machine）で処理 • 制約条件 ：各仕事を処理する機械の順序（技術的順序） • すべての仕事を完成させるまでの時間（Makespan） を最小にするスケジュールを求める MPS symposium 2004 Doshisha University, Kyoto, Japan GAのパラメータ（β値） - kroA200 0.8 Error ratio(%) 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0.01 0.05 0.1 0.3 0.5 β β値は，0.05程度が適切 MPS symposium 2004 Doshisha University, Kyoto, Japan GAのパラメータ（交叉率） - kroA200 1.6 Error ratio(%) 1.4 1.2 1 0.8 0.6 0.4 0.2 0 0 0.2 0.3 0.4 0.6 0.8 1 Crossover ratio 交叉率は，0.3程度が適切 MPS symposium 2004 Doshisha University, Kyoto, Japan GAのパラメータ（突然変異率） - kroA200 1.6 Error ratio(%) 1.4 1.2 1 0.8 0.6 0.4 0.2 0 1 2 4 8 16 Mutation ratio (X/32) 突然変異率は，1/32程度が適切 MPS symposium 2004 Doshisha University, Kyoto, Japan GAのパラメータ（プロセス数） - kroA200 4 Error ratio(%) 3.5 3 2.5 2 1.5 1 0.5 0 4 8 16 24 32 36 42 Num. of processes プロセス数は，32程度が適切 MPS symposium 2004 Doshisha University, Kyoto, Japan Coding of temperature • PSA/AT(GA) uses GA to optimize the cooling schedule. • Individual : Temperature on each processor • Design variable : The exponent of temperature function, X Real Value Bit Array Encoding X Temperature = 10 X Decoding • The expression of temperature in PSA/AT(GA) is suitable for the exponential cooling schedule in SA. MPS symposium 2004 SA cooling method Tn1 Tn ( 1.0) Doshisha University, Kyoto, Japan Cooling schedule (eil101) - PSA/AT(GA) - - TPSA 100 Temperature Temperature 100 10 1 0.1 10 1 0.1 0 20000 40000 60000 Num. of annealing steps 80000 0 20000 40000 60000 80000 Num. of annealing steps A line : a cooling schedule on one SA. PSA/AT(GA) : Convergence on the important temperature region TPSA : All processes can’t always have good search. The cooling schedule of PSA/AT(GA) is more proper than TPSA’s. MPS symposium 2004 Doshisha University, Kyoto, Japan Experimental results (Error Rate) in TSPs Error Rate (%) 2.5 2 PSA/AT(GA)(binary-coding) PSA/AT(GA)(real-coding) PSA TPSA 1.5 1 0.5 0 eil101 kroA200 lin318 pr439 rat575 d657 TSP Problems MPS symposium 2004 Doshisha University, Kyoto, Japan SAの並列化 • 並列SAの分類 [D.R.Greening,1990] - Serial-Like : 部分解を異なるプロセッサで解探索するモデル． 多くの通信が必要 - Altered generation : 複数の逐次SAを同時実行し, 同期をとって通信 するモデル - Asynchronous : 非同期の通信を行うモデル Serial-Like Altered generation Asynchronous - 計算時間の短縮，解探索能力の向上 - 温度スケジュールは逐次SAと同じ MPS symposium 2004 Doshisha University, Kyoto, Japan 温度のコーディング 個体：各プロセスが持つ温度 遺伝子型 1 0 0 1 0 1 1 0 1 0 ビット列で 指数部を表現 温度 = 10 X 602 ビット長が 10ビット 2 =1024 範囲 [-2,6] 2.703 10 2.703 PSA/AT(GA)で探索する温度範囲 最高温度と最低温度が定義域 最高温度 : 10000 最低温度 : 0.01 MPS symposium 2004 ビット列が表現する 範囲 : [-2,4] Temperature 温度 表現型(温度) 10 = 504.66 Max Temperature Min Temperature Time Doshisha University, Kyoto, Japan SA GA MPS symposium 2004 Doshisha University, Kyoto, Japan MPS symposium 2004 Doshisha University, Kyoto, Japan MPS symposium 2004 Doshisha University, Kyoto, Japan
© Copyright 2024 ExpyDoc
