The 10th Mathematical Modeling and Problem Solving 並列シミュレーテッドアニーリングにおける 近傍の適応的調節メカニズム 同志社大学大学院 知的システムデザイン研究室 三木 光範 廣安 知之 ○ 伏見 俊彦 発表の流れ 1. はじめに 2. シミュレーテッドアニ－リング 3. 研究目的 4. 提案手法 5. 数値実験 6. まとめ 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- はじめに① 最適化： ある制約条件のもとで，目的となる関数の最小値（最 大値）を求めること． 最適化問題 連続最適化問題 タンパク質の立体構造予測 タンパク質の構造予測 エネルギーが最も安定する状態 組合せ最適化問題 LSI配置問題 低コスト，高性能化 LSI配置問題 探索空間の拡大により実用的な計算コストで解くことが困難． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- はじめに② 最適化問題の大規模，複雑化に伴い効率的な探索が必要． ヒューリスティック手法 •ニューラルネットワーク •遺伝的アルゴリズム（GA） ボルツマンマシン 生物の進化を模倣 •シミュレーテッドアニーリング（SA） 金属の焼き鈍しを模倣 問題点 1. 膨大な計算量 2. パラメータ調節の困難さ 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- シミュレーテッドアニーリング high 1．生成処理 2．受理判定 Energy アルゴリズム 改悪方向 low 改良方向 最適解 3．推移 4．クーリング 2003.10.23 設計空間 Metropolis基準 改良方向 1 改悪方向 Exp( -⊿E ) Temperature (⊿E = Enext - Enow) 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- シミュレーテッドアニーリング high 高温状態 1．生成処理 2．受理判定 Energy アルゴリズム low 最適解 3．推移 4．クーリング 2003.10.23 設計空間 Metropolis基準 改良方向 1 改悪方向 Exp( -⊿E ) Temperature (⊿E = Enext - Enow) 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- シミュレーテッドアニーリング high 低温状態 1．生成処理 2．受理判定 Energy アルゴリズム low 最適解 3．推移 4．クーリング 2003.10.23 設計空間 Metropolis基準 改良方向 1 改悪方向 Exp( -⊿E ) Temperature (⊿E = Enext - Enow) 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- SAにおける近傍幅 連続最適化問題では次状態を生成する範囲を近傍と呼ぶ． 近傍が大きすぎる． •効率的な探索が行えない． •解精度が悪い． 近傍が小さすぎる． •局所解に陥りやすい． •探索に時間を要する． Global optimum 適応的な近傍調節が重要 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 研究背景 •適応的近傍を持つシミュレーテッドアニーリング 受理率を0.5に保つように近傍を調節． [Corana 1987] •最適な受理率を目標とする適応的近傍を持つ シミュレーテッドアニーリング [三木 2002] 最適な受理率は0.1～0.2であることを明らかにした． このような受理率は問題に依存している可能性がある． 新たな適応的近傍調節メカニズムを提案 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 研究目的 目的 1. 並列化による計算時間の短縮 2. 近傍パラメータの適応的な調節 1. 並列化 並列シミュレーテッドアニーリング 2. 適応的な近傍幅調節 遺伝的アルゴリズムを用いて近傍幅を調節 並列SAにおいて近傍幅を適応的に調節するメカニズムを提 案する． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 近傍幅の影響 近傍幅が解に与える影響を調べるため，複数の近傍幅に対して， SAを適用する． 近傍幅 探索領域 Neighborhood range large 各々の近傍幅で得られた 解の品質を比較する． 各々の近傍幅の解探索 能力が得られる． small 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 対象問題 数学的最小化問題 Rastrigin 2003.10.23 Griewangk Rosenbrock 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 適切な近傍幅(Rastrigin) 近傍幅は解の品質に大きく影響する． Rastrigin 適切な近傍幅 2003.10.23 良好な解 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 適切な近傍幅(Griewangk) 近傍幅は解の品質に大きく影響する． 適切な近傍幅 Griewangk 良好な解 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 適切な近傍幅(Rosenbrock) 近傍幅は解の品質に大きく影響する． 適切な近傍幅 Rosenbrock 良好な解 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 提案手法のコンセプト •SAにおける適切な近傍幅は問題に大きく依存している． •それらの近傍幅を見つけるためには多くの予備実験が必要． •近傍幅をGAを用いることにより，探索過程において自動的に 適切な近傍幅を決定するメカニズムを考案する． •並列SAに実装することで計算時間の短縮も行える． 問題点 解決策 1. 膨大な計算量 2. パラメータ調節が困難 2003.10.23 1. 並列化 2. GAによる適応的調節 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 提案手法 複数のSAプロセスが異なる近傍幅で探索を行う． 近傍幅に対してGAオペレータを適用し，近傍幅を変化させる． Neighborhood range large small 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- アルゴリズム 1. 生成処理 2. 受理判定 3. 状態遷移 SAと同様 4. クーリング処理時にすべてのプロ セスが同期をとる． GAにより近傍幅が決定される 各プロセスの近傍幅を個体を見立て，それらの個 体に対して遺伝的操作を行い，良好な結果を得 ている個体が選択される． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- GAオペレータ 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 実験概要 従来より提案されている並列モデルSAと比較実験を行う． 比較手法 最適な固定近傍幅 •独立型並列SA(PSA/FN) •温度並列SA(TPSA/FN) 適応的に近傍を調節 •最適な受理確率を目標とするTPSA(TPSA/AN) 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- パラメータ 関数名 Rastrigin Griewangk Rosenbrock 最高温度 10 20 1 最低温度 0.01 0.001 0.001 102400 307200 3072 3 3 3 冷却率 0.8 0.7 0.8 最適な固定近傍幅 1.0 5.5 0.3 アニーリング数 設計変数 プロセス数 2003.10.23 32 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 解探索性能 提案手法 提案手法が全ての問題に対して良好な結果を示した． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 近傍幅の推移① 各SAプロセスが持つ近傍幅の推移． Rastrigin •近傍幅がGAにより適応的に調節されている． •適切な近傍幅は探索状況に応じて動的に変化する． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 近傍幅の推移② 各SAプロセスが持つ近傍幅の推移． Griewank 2003.10.23 Rosenbrock 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- エネルギー推移（Rastrigin） 提案手法 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- エネルギー推移（Griewangk） 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- エネルギー推移（Rosenbrock） 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 多峰性関数（Schwefel） 局所解の間隔が一定でない 多峰性の関数 Schwefel関数 適切な固定近傍幅が存在しない 適切な近傍幅が未知な問題 探索開始時 近傍幅：大 探索終了時 近傍幅：小 温度パラメータにより調節 探索領域 ×√温度 近傍幅＝ √最高温度 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 近傍幅とエネルギー推移（Schwefel） 近傍幅推移 並列SA 提案手法 エネルギー推移 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 並列効果 最適解領域までに要したアニーリング数 を比較． Rastrigin 並列効果32倍 提案手法 解探索性能の向上により，より少ない計算 回数で良好な解を得ることができる． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- まとめ 適応的な近傍調節メカニズムをもつ新たな並列シミュレーテッドアニ －リングの提案を行った． GAを用いて適応的な近傍調節を実現 代表的な数学的最小化問題を用いて解探索性能と並列効果に ついて検証を行った． 適切な近傍幅は探索状況に応じて動的に変化する． 提案手法は動的に近傍を調節 •従来の並列手法よりも良好な結果を示した． •解探索性能の向上により高速に解を探索することが可能． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 今後の課題 GA処理に用いている評価値の検討． GAの特性である部分解の組み合わせを有効にするため 設計変数毎に近傍パラメータを設定し，それらをGAを 用いて最適化する． 他の連続最適化問題に適用し，本手法の有効性の確認． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム -- 最適解領域到達率 最適解領域への到達率を比較． 提案手法 全ての問題において安定した最適解到達 率を得ることができている． 2003.10.23 第10回MPSシンポジウム--並列・分散処理による問題解決シンポジウム --
© Copyright 2024 ExpyDoc
