並列・分散処理による問題解決シンポジウム

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シンポジウム--並列・分散処理による問題解決シンポジウム --