May 16th 2000
遺伝的交叉を用いた
並列シミュレーテッドアニーリング
Parallel Simulated Annealing using Genetic Crossover
同志社大学工学部/大学院
廣安知之,三木光範,○小掠真貴
Intelligent Systems Design Laboratory
研究背景
シミュレーテッドアニーリング(S
A)
組み合わせ最適化問題に対して有効
探索が最適解へ収束する保証をもつ
解を得るまでの計算量が非常に多い
‐連続最適化問題
SAの並列化,ハイブリッド化
Intelligent Systems Design Laboratory
研究背景
SAの並列化
‐温度並列シミュレーテッドアニーリング
(小西, 瀧ら 1995)
SAのハイブリッド化
‐Parallel Recombinative Simulated Annealing
(Mahfoud, Goldbergら 1992)
‐熱力学的遺伝アルゴリズム (森, 喜多ら 1996)
Intelligent Systems Design Laboratory
本研究の目的
比較的少ない計算量で良好な解を得るアルゴリズム
並列SA + 遺伝的交叉(GAオペレータ)
SAの適用範囲を拡張
提案するアルゴリズムをテスト関数に適用し,
その有効性を検討
Intelligent Systems Design Laboratory
遺伝的交叉を用いた並列SA
並列SAの解の情報交換に遺伝的交叉を用いる手法
n n:crossover interval
n
n
SA
SA
・・・
SA
SA
high
temperature
low
temperature
Intelligent Systems
Design Laboratory
遺伝的交叉を用いた並列SA
e.g. 3設計変数の連続関数最小化問題
evaluation rank
parent1 x1 x2 x3
-2.0
4
parent2 x1 x2 x3
-1.1
1
next
search point
x1 x2 x3
crossover
x1 x2 x3
child1
x1 x2 x3
-1.8
3
child2
x1 x2 x3
-1.3
2
Intelligent Systems Design Laboratory
数値実験の概要
対象:連続関数最小化問題
GAオペレータを用いた3種の並列SAとの比較
GAオペレータのうち,
遺伝的交叉を用いることの有効性を検証
遺伝的交叉を用いた並列SAの解探索能力
逐次SA,分散GAとの解探索能力の比較
Intelligent Systems Design Laboratory
GAオペレータを用いた
3種の並列SAとの比較
エリート選択を用いた並列SA(elitePSA)
ルーレット選択を用いた並列SA(roulettePSA)
エリート保存を含むルーレット選択を用いた
並列SA(e‐roulettePSA)
Intelligent Systems Design Laboratory
パラメータ
parameter
value
個体数
20 , 200
初期温度
5 , 10 , 20 , 30
クーリング率
0.93
解情報交換周期
32
終了条件
解の値の変化が 1.0e-4 以下でしかおこらず,
それを満たす摂動が連続して100世代おこること
Intelligent Systems Design Laboratory
対象問題
Rastrigin関数 [2dimensions]
Rastrigin function
n
2
f依存関係なし,大域探索

10
n

(
x
 i  10cos(2xi ))
Rastrigin
i 1
Griewank関数 [2dimensions]
n
  xi  
xi2
 cos  
f依存関係あり,局所探索

1




Griewank
 i 
i 1 4000
i 1 
n
Griewank function
Intelligent Systems Design Laboratory
実験結果[Rastrigin]
[population size 20, 10trials Average]
1.0E+00
Energy
1.0E-02
crossoverPSA
elitePSA
1.0E-04
roulettePSA
e-roulettePSA
1.0E-06
1.0E-08
5
10
20
Initial temperature
30
Intelligent Systems Design Laboratory
実験結果[Griewank]
[population size 200, 10trials Average]
1.0E+00
Energy
1.0E-02
crossoverPSA
1.0E-04
elitePSA
roulettePSA
1.0E-06
e-roulettePSA
1.0E-08
5
10
20
Initial temperature
30
Intelligent Systems Design Laboratory
遺伝的交叉を用いた並列SAの
解探索能力
遺伝的交叉を用いた並列SAのパラメータ
parameter
value
個体数
400
初期温度
10
クーリング率
0.93
交叉周期
32
Intelligent Systems Design Laboratory
遺伝的交叉を用いた並列SAの
解探索能力
逐次SA‐long(SSA‐long)
3,200,000世代(8,000世代×400個体相当)の
計算を実行
逐次SA‐short(SSA‐short)
8,000世代の計算を独立に400回実行
分散GA
20個体×20島(400個体)による
8,000世代の計算を実行
Intelligent Systems Design Laboratory
対象問題
Rastrigin関数 [10 , 30dimensions]
n
2
f依存関係なし,大域探索
Rastrigin  10n   ( xi  10 cos(2xi ))
i 1
Griewank関数 [10 , 30dimensions]
n
  x 
xi2
依存関係あり,局所探索
f Griewank  1  
   cos i  
 i 
i 1 4000
i 1 
n
Rosenbrock関数 [10 , 30dimensions]
n 1
f Rosenbrock  [100( xi 1 xi2 ) 2  ( xi  1) 2 ]
強い依存関係あり
i 1
Rosenbrock function
Intelligent Systems Design Laboratory
実験結果[Rastrigin]
10
設計
変数
30
設計
変数
提案手法
SSA‐long
SSA‐short
分散GA
10
0
0
10
( 0.0000 )
( 12.85 )
( 21.21 )
( 0.0000 )
3,034,881
3,200,000
3,200,000
773,940
0
0
0
1
( 0.9950 )
( 199.9 )
( 190.6 )
( 0.0000 )
3,117,641
3,200,000
3,200,000
3,181,940
良好な解を得た回数 [10trials]
評価計算回数 [10trials Average]
Intelligent Systems Design Laboratory
実験結果[Griewank]
10
設計
変数
30
設計
変数
提案手法
SSA‐long
SSA‐short
分散GA
9
0
0
0
( 0.0000 )
( 1.642 )
( 0.1512 )
( 0.0074 )
3,008,201
3,200,000
3,200,000
3,200,400
10
0
0
7
( 0.0000 )
( 0.3994 )
( 0.4666 )
( 0.0000 )
3,118,041
3,200,000
3,200,000
2,922,120
良好な解を得た回数 [10trials]
評価計算回数 [10trials Average]
Intelligent Systems Design Laboratory
実験結果[Rosenbrock]
10
設計
変数
30
設計
変数
提案手法
SSA‐long
SSA‐short
分散GA
10
1
1
0
( 0.0000 )
( 0.0000 )
( 0.0000 )
( 0.0004 )
2,750,721
3,200,000
3,200,000
3,200,400
10
0
0
0
( 0.0000 )
( 0.0005 )
( 0.0001 )
( 18.79 )
2,723,441
3,200,000
3,200,000
3,200,400
良好な解を得た回数 [10trials]
評価計算回数 [10trials Average]
Intelligent Systems Design Laboratory
結論
遺伝的交叉を用いた並列シミュレーテッド
アニーリングを提案
並列SAに遺伝的交叉を用いることで
適用範囲の拡張,探索能力の向上
提案手法の解探索能力を検証
Intelligent Systems Design Laboratory
結論と今後の課題
連続最適化問題を対象として,
遺伝的交叉を用いた並列SAの解探索能力を比較
GAオペレータを用いた3種の並列SA
逐次SA
すべての対象問題において,提案手法が有効
分散GA
GAが苦手とする問題に対して,提案手法が有効
既存のハイブリッド手法との比較
Intelligent Systems Design Laboratory
ダウンロード

N - 同志社大学