遺伝的交叉を用いた 並列シミュレーテッドアニーリング 同志社大学工学部／大学院 廣安知之，三木光範，○小掠真貴 May 16th 2000 遺伝的交叉を用いた 並列シミュレーテッドアニーリング Parallel Simulated Annealing using Genetic Crossover タイトル 同志社大学工学部／大学院 廣安知之，三木光範，○小掠真貴 Intelligent Systems Design Laboratory

研究背景 シミュレーテッドアニーリング（ＳＡ） 組み合わせ最適化問題に対して有効 探索が最適解へ収束する保証をもつ 解を得るまでの計算量が非常に多い ＳＡは最適化問題を解く近似法の１つであり，多くの組み合わせ最適化問題に対して有効である．ＳＡの探索は最適解へ収束するという保証を持つが，解を得るまでの計算量が非常に多いという短所がある．連続最適化問題を対象とした場合，特に多くの計算時間が必要であり，実用的でない．そのため，逐次処理であるＳＡを並列化し高速化する研究や，他の手法とのハイブリッド化によって適用範囲を拡張する研究が行われている． ‐連続最適化問題 ＳＡの並列化，ハイブリッド化 Intelligent Systems Design Laboratory

研究背景 ＳＡの並列化 ‐温度並列シミュレーテッドアニーリング ＳＡのハイブリッド化 （小西, 瀧ら 1995） ＳＡのハイブリッド化 ‐Parallel Recombinative Simulated Annealing ＳＡを並列化する研究にはさまざまな方法があり，その１つにＴＰＳＡが挙げられる．またＳＡと遺伝的アルゴリズム（ＧＡ）とのハイブリッド手法にはこの２つが挙げられる．ＰＲＳＡはＧＡの選択演算時にＳＡのメトロポリス基準を用いるものであり，ＴＤＧＡは選択演算時に熱力学的なエントロピーと温度の概念を取り入れた手法である．しかし，ＳＡのアニーリングを行っている途中でＧＡのオペレータを組み込むという手法はない． [PRSAは交叉した後，親２個体・子２個体間でボルツマン分布に従って選択を行う．TDSAは選択演算のときに熱力学的なエントロピーと温度の概念を取り入れた手法．] （Mahfoud, Goldbergら 1992） ‐熱力学的遺伝アルゴリズム　（森, 喜多ら 1996） Intelligent Systems Design Laboratory

本研究の目的 並列ＳＡ 遺伝的交叉（ＧＡオペレータ） ＋ 比較的少ない計算量で良好な解を得るアルゴリズム ＳＡの適用範囲を拡張 そこで本研究では，連続最適化問題を対象とする場合でも比較的少ない計算量で良好な解を得るアルゴリズムとして，並列ＳＡにＧＡオペレータを組み込んだハイブリッド手法を提案する．提案手法は並列に複数実行しているＳＡの解の伝達時にＧＡオペレータである交叉を用いたものである．局所探索が得意なＳＡに大域探索が得意でかつ部分解の組み合わせで最適解が得られるＧＡオペレータを取り入れることでＳＡの適用範囲を拡張することができる．また，提案するアルゴリズムをテスト関数に適用し，その有効性を検証する．本手法はＧＡのオペレータを用いたＳＡであるため，ＳＡの並列数を個体数，アニーリングステップを世代数とよぶ． 提案するアルゴリズムをテスト関数に適用し， その有効性を検討 Intelligent Systems Design Laboratory

遺伝的交叉を用いた並列ＳＡ 並列ＳＡの解の情報交換に遺伝的交叉を用いる手法 n n ・・・ n high temperature SA n:crossover interval n ・・・ low temperature n 本研究で提案する遺伝的交叉を用いた並列ＳＡは，並列ＳＡの解の情報交換に遺伝的交叉を用いる手法である．複数のプロセス上でそれぞれＳＡの操作が行われ，一定間隔のアニーリングを行った後，ランダムに２個体ずつをペアにして遺伝的交叉を行う．交叉によって得られた個体からまた一定間隔のアニーリングを行い交叉を行う．この操作を温度が十分低くなるまで繰り返し，終了条件を満たすところで終了する．この遺伝的交叉の部分を Intelligent Systems Design Laboratory

遺伝的交叉を用いた並列ＳＡ e.g. ３設計変数の連続関数最小化問題 -2.0 -1.1 x1 x2 x3 2 1 3 4 x1 x2 x3 evaluation -2.0 -1.1 parent1 parent2 x1 x2 x3 rank 2 1 3 4 next search point x1 x2 x3 -1.8 -1.3 crossover child1 child2 x1 x2 x3 ３設計変数の連続関数最小化問題を例にして説明する．並列に実行しているＳＡからランダムにこのような２個体が親として選ばれ，評価値が～だったとする．この親からランダムに交叉点を決定し，子を生成．これら４個体のうち表価値の高い２個体を次の探索点とする．この操作はすべての個体に対して行われる．ある設計変数の最適値が求まっている場合，遺伝的交叉によってその設計変数の最適値を他のＳＡ探索に伝達することができるため，アニーリングの収束をはやめることができる． Intelligent Systems Design Laboratory

数値実験の概要 対象：連続関数最小化問題 ＧＡオペレータを用いた３種の並列ＳＡとの比較 遺伝的交叉を用いた並列ＳＡの解探索能力 ＧＡオペレータのうち， 遺伝的交叉を用いることの有効性を検証 遺伝的交叉を用いた並列ＳＡの解探索能力 逐次ＳＡ，分散ＧＡとの解探索能力の比較 Intelligent Systems Design Laboratory

ＧＡオペレータを用いた ３種の並列ＳＡとの比較 エリート選択を用いた並列ＳＡ（ｅｌｉｔｅＰＳＡ） ルーレット選択を用いた並列ＳＡ（ｒｏｕｌｅｔｔｅＰＳＡ） エリート保存を含むルーレット選択を用いた 並列ＳＡ（ｅ‐ｒｏｕｌｅｔｔｅＰＳＡ） Intelligent Systems Design Laboratory

パラメータ 20 , 200 5 , 10 , 20 , 30 0.93 32 parameter value 個体数 初期温度 20 , 200 5 , 10 , 20 , 30 0.93 32 parameter value 個体数 初期温度 クーリング率 解情報交換周期 パラメータはこのように設定した． 初期温度は予備実験により，十分高いと思われる３０を最高温度，低いと思われる５を最低温度とした． その他のパラメータも予備実験により決定した． 終了条件は，解の値の変化が1.0*10-4以下でしかおこらないこととした． この終了条件により，本実験では1.0*10-4以下の解を良好な解と定義する． 終了条件 解の値の変化が 1.0e-4 以下でしかおこらず， それを満たす摂動が連続して100世代おこること Intelligent Systems Design Laboratory

対象問題 Rastrigin関数 [2dimensions] Griewank関数 [2dimensions] 依存関係なし，大域探索 Rastrigin function 依存関係なし，大域探索 依存関係あり，局所探索 Griewank関数 [2dimensions] 対象問題として２設計変数のＲとＧを用いた．Ｒは大域的に解があり，部分解の組み合わせで最適解が求められる．変数間に依存関係のない関数である．Ｇは大域的に見るとなだらかな景観だが，部分的に見ると解を多く持つ関数である．これらは２つとも各設計変数の値が0のとき，最小値0をとる関数である． Griewank function Intelligent Systems Design Laboratory

実験結果［Ｒａｓｔｒｉｇｉｎ］ [population size 20, 10trials Average] 個体数を２０としてＲを解いた結果．縦軸はエネルギー，つまり解の値．最適解は0なので下にいくほど良い解だといえる．今回は終了条件の設定から1.0*10-4未満の値を良好な解とする．横軸は初期温度を示している．赤のグラフが提案する遺伝的交叉を用いた並列ＳＡの結果だが，他の３つの手法では全く良好な解を求められなかったが，遺では常に良好な解を得られた． 各並列ＳＡの個体数を１０倍の２００としてＲを解いた場合４つの手法すべてで最適解が得られた． Intelligent Systems Design Laboratory

実験結果［Ｇｒｉｅｗａｎｋ］ [population size 200, 10trials Average] Intelligent Systems Design Laboratory

遺伝的交叉を用いた並列ＳＡの解探索能力 遺伝的交叉を用いた並列ＳＡのパラメータ 400 10 0.93 32 parameter value 個体数 初期温度 クーリング率 交叉周期 Intelligent Systems Design Laboratory

遺伝的交叉を用いた並列ＳＡの解探索能力 逐次ＳＡ‐ｌｏｎｇ（ＳＳＡ‐ｌｏｎｇ） 逐次ＳＡ‐ｓｈｏｒｔ（ＳＳＡ‐ｓｈｏｒｔ） 分散ＧＡ ３,２００,０００世代（８,０００世代×４００個体相当）の 計算を実行 逐次ＳＡ‐ｓｈｏｒｔ（ＳＳＡ‐ｓｈｏｒｔ） ８,０００世代の計算を独立に４００回実行 分散ＧＡ ２０個体×２０島（４００個体）による ８,０００世代の計算を実行 Intelligent Systems Design Laboratory

対象問題 Rastrigin関数 [10 , 30dimensions] Griewank関数 [10 , 30dimensions] 強い依存関係あり 依存関係なし，大域探索 依存関係あり，局所探索 Griewank関数 [10 , 30dimensions] Rosenbrock関数 [10 , 30dimensions] Rosenbrock function Intelligent Systems Design Laboratory

実験結果［Ｒａｓｔｒｉｇｉｎ］ 分散ＧＡ ＳＳＡ‐ｓｈｏｒｔ ＳＳＡ‐ｌｏｎｇ 提案手法 10 ( 0.0000 ) 3,034,881 773,940 ( 0.9950 ) 1 3,117,641 3,181,940 １０ 設計 変数 ３０ ( 12.85 ) ( 21.21 ) 3,200,000 ( 199.9 ) ( 190.6 ) [10trials] 良好な解を得た回数 評価計算回数 [10trials Average] Intelligent Systems Design Laboratory

実験結果［Ｇｒｉｅｗａｎｋ］ 分散ＧＡ ＳＳＡ‐ｓｈｏｒｔ ＳＳＡ‐ｌｏｎｇ 提案手法 9 ( 0.0000 ) ( 0.0074 ) 10 7 １０ 設計 変数 ３０ ( 1.642 ) ( 0.1512 ) ( 0.3994 ) ( 0.4666 ) 3,008,201 3,200,400 3,200,000 3,118,041 2,922,120 [10trials] 良好な解を得た回数 評価計算回数 [10trials Average] Intelligent Systems Design Laboratory

実験結果［Ｒｏｓｅｎｂｒｏｃｋ］ 分散ＧＡ ＳＳＡ‐ｓｈｏｒｔ ＳＳＡ‐ｌｏｎｇ 提案手法 10 ( 0.0000 ) ( 0.0004 ) ( 18.79 ) １０ 設計 変数 ３０ 1 ( 0.0005 ) ( 0.0001 ) 2,750,721 3,200,400 2,723,441 3,200,000 これらの結果から，単にSAのアニーリング時間や回数を増加させただけでは結果が向上しないことが明らかになった．またGAが苦手な問題に対して有効な結果を示した． [10trials] 良好な解を得た回数 評価計算回数 [10trials Average] Intelligent Systems Design Laboratory

結論 遺伝的交叉を用いた並列シミュレーテッドアニーリングを提案 並列ＳＡに遺伝的交叉を用いることで適用範囲の拡張，探索能力の向上 本実験では遺伝的交叉を用いた並列SAを提案した．局所探索が得意なＳＡに大域探索が得意でかつ部分解の組み合わせで最適解が得られるＧＡオペレータを取り入れることでＳＡの適用範囲を拡張することができた．また，提案手法の解探索能力の検証も行った． 提案手法の解探索能力を検証 Intelligent Systems Design Laboratory

結論と今後の課題 連続最適化問題を対象として， 遺伝的交叉を用いた並列ＳＡの解探索能力を比較 ＧＡオペレータを用いた３種の並列ＳＡ 逐次ＳＡ すべての対象問題において，提案手法が有効 分散ＧＡ ＧＡが苦手とする問題に対して，提案手法が有効 既存のハイブリッド手法との比較 Intelligent Systems Design Laboratory