遺伝的交叉を用いた 並列シミュレーテッドアニーリングの検討 小掠 真貴 廣安 知之 三木 光範 角 美智子 岡本 祐幸 同志社大学大学院 小掠　真貴 同志社大学工学部 廣安　知之 三木　光範 同志社大学工学部（学） 角　美智子 岡崎国立共同研究機構分子科学研究所 岡本　祐幸 March 16 , 2001

研究背景 タンパク質の立体構造の研究 タンパク質の立体構造 生物学的機能と密接な関係 新薬の開発 病理の発現機構の解明 アミノ酸配列（一次構造） 立体構造 Doshisha University

研究背景 アミノ酸配列情報からの立体構造解析 Simulated Annealing (SA) 焼きなまし（アニーリング）を計算機上でシミュレート 最適化問題に有効なヒューリスティック手法 アルゴリズム 1. 生成 2. 受理判定 Metropolis基準　 P = 3. クーリング －(Enext－Ecurrent) T exp ＳＡは最適化問題を解く近似法の１つであり，多くの組み合わせ最適化問題に対して有効である．ＳＡの探索は最適解へ収束するという保証を持つが，解を得るまでの計算量が非常に多いという短所がある．連続最適化問題を対象とした場合，特に多くの計算時間が必要であり，実用的でない．そのため，逐次処理であるＳＡを並列化し高速化する研究や，他の手法とのハイブリッド化によって適用範囲を拡張する研究が行われている． Doshisha University

研究背景 SAによるタンパク質の構造解析 エネルギー関数は， 局所的に無数の極小値， 大域的にもいくつかの 極小値をもつ タンパク質のエネルギー関数 局所探索に優れるSAに，大域探索の要素をもたせることで，効率化を図る ＳＡだけでも時間をかければ最適解に到達するが，大域的探索の要素を取り入れれば効率的に探索が行えるはず． SAと遺伝的アルゴリズム(Genetic Algorithm : GA)の オペレーションとのハイブリッド手法 Doshisha University

研究背景 SAとGAのハイブリッド手法 Parallel Recombinative Simulated Annealing （Mahfoud, Goldbergら 1992） 熱力学的遺伝アルゴリズム　（森, 喜多ら 1996） またＳＡと遺伝的アルゴリズム（ＧＡ）とのハイブリッド手法にはこの２つが挙げられる．ＰＲＳＡはＧＡの選択演算時にＳＡのメトロポリス基準を用いるものであり，ＴＤＧＡは選択演算時に熱力学的なエントロピーと温度の概念を取り入れた手法である．アニーリングは逐次ＳＡにＧＡの交叉を用いて，探索の領域を絞り込む手法である．しかし，ＳＡのアニーリングを行っている途中でＧＡのオペレータを組み込むという手法は少なく，特に並列モデルはない． [PRSAは交叉した後，親２個体・子２個体間でボルツマン分布に従って選択を行う．TDSAは選択演算のときに熱力学的なエントロピーと温度の概念を取り入れた手法．] 遺伝的状態生成処理を取り入れた 改良型アニーリング　　 　（小圷, 須貝, 平田 1991） Doshisha University

本研究の目的 並列SAにGAオペレーションを用いた手法の提案 遺伝的交叉を用いた並列シミュレーテッドアニーリング SA 局所探索に優れる タンパク質のエネルギー関数 GA　大域探索に優れる SAとGAオペレーションとのハイブリッド手法は 局所探索だけでなく 大域探索にも有効 局所探索能力をもつＳＡをメインに，大域探索を得意とするＧＡのオペレーションを用いる． 遺伝的交叉を用いた並列シミュレーテッドアニーリング (Parallel Simulated Annealing using Genetic Crossover : PSA/GAc) Doshisha University

本研究の目的 遺伝的交叉を用いた並列SA(PSA/GAc)を タンパク質の構造解析に適用し， 現在用いられているSAよりも高い性能を得る 遺伝的交叉を用いることの有効性の検証 テスト関数にPSA/GAcを適用し，交叉を用いることの有効性を検証． また他のアルゴリズムとの解探索能力の比較． 本手法はGAのオペレータを用いたＳＡであるため，SAの探索点を個体，SAの並列数を個体数，アニーリングステップ数を世代数とよぶ． 他のアルゴリズムとの解探索能力の比較 タンパク質の構造解析への適用，有効性の検証 Doshisha University

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

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

数値実験の概要 PSA/GAcの有効性をテスト関数により検証 PSA/GAcをタンパク質の構造解析に適用 GAオペレータを用いた3種の並列SAとの比較 逐次SA，分散GAとの解探索能力の比較 PSA/GAcをタンパク質の構造解析に適用 構造解析に用いられているSAとの解探索能力の比較 GAオペレータのうち，遺伝的交叉を用いることの有効性を検証 PSA/GAcの解探索能力を検証するため 5つのアミノ酸からなるタンパク質の構造解析に適用 Doshisha University

GAオペレータを用いた 3種の並列SAとの比較 遺伝的交叉を用いることの有効性を検証 エリート選択を用いた並列SA (elitePSA) ルーレット選択を用いた並列SA (roulettePSA) エリート保存を含むルーレット選択を用いた 並列SA (e-roulettePSA) Doshisha University

3種のGAオペレータ GAにおいて，次の探索点を生成する処理 エリート選択 ルーレット選択 エリート保存を含むルーレット選択 Doshisha University

3種のGAオペレータ GAにおいて，次の探索点を生成する処理 エリート選択 ルーレット選択 エリート保存を含むルーレット選択 -1.3 searching points energy -1.8 -1.3 -0.9 -0.1 next searching points Doshisha University

3種のGAオペレータ GAにおいて，次の探索点を生成する処理 エリート選択 ルーレット選択 エリート保存を含むルーレット選択 -1.3 searching points energy -1.8 -1.3 -0.9 -0.1 next searching points Doshisha University

3種のGAオペレータ GAにおいて，次の探索点を生成する処理 エリート選択 ルーレット選択 エリート保存を含むルーレット選択 -1.3 searching points energy -1.8 -1.3 -0.9 -0.1 next searching points Doshisha University

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

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

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

実験結果 [Griewank] [200population, Average of 10 trials] Doshisha University

逐次SA，分散GAとの解探索能力の比較 一般的なヒューリスティック手法との比較 逐次SA-long (SSA-long) 逐次SA-short (SSA-short) 分散GA (DGA) Doshisha University

PSA/GAcと逐次SA，分散GAのパラメータ 400 8000 10 0.93 32 SSA-long 1 3200000 10 0.93 --- SSA-short 400 8000 10 0.93 --- DGA 400 8000 --- 5 個体数 世代数 評価計算回数 8000*400 初期温度 クーリング率 解の伝達周期 Doshisha University

対象問題 連続値最小化問題 Rastrigin関数 [10, 30dimensions] 大域的に多くの極小値 局所的に無数の極小値 Griewank関数 [10, 30dimensions] Rosenbrock関数 [10, 30dimensions] Rosenbrock function Doshisha University

実験結果 [Rastrigin] SSA-short SSA-long PSA/GAc DGA dimensions 10 30 1.0 ( 0.0000 ) 0.00 ( 12.85 ) 0.00 ( 21.21 ) 1.0 ( 0.0000 ) 3,034,881 3,200,000 3,200,000 773,940 0.00 ( 0.9950 ) 0.00 ( 199.9 ) 0.00 ( 190.6 ) 0.10 ( 0.0000 ) 3,117,641 3,200,000 3,200,000 3,181,940 Success rate [Out of 10 trials] Evaluations [Average of 10 trials] Doshisha University

実験結果 [Griewank] SSA-short SSA-long PSA/GAc DGA dimensions 10 30 0.90 ( 0.0000 ) 0.00 ( 1.642 ) 0.00 ( 0.1512 ) 0.00 ( 0.0074 ) 3,008,201 3,200,000 3,200,000 3,200,400 1.0 ( 0.0000 ) 0.00 ( 0.3994 ) 0.00 ( 0.4666 ) 0.70 ( 0.0000 ) 3,118,041 3,200,000 3,200,000 2,922,120 Success rate [Out of 10 trials] Evaluations [Average of 10 trials] Doshisha University

実験結果 [Rosenbrock] SSA-short SSA-long PSA/GAc DGA dimensions 10 30 1.0 ( 0.0000 ) 0.10 ( 0.0000 ) 0.10 ( 0.0000 ) 0.00 ( 0.0004 ) 2,750,721 3,200,000 3,200,000 3,200,400 1.0 ( 0.0000 ) 0.00 ( 0.0005 ) 0.00 ( 0.0001 ) 0.00 ( 18.79 ) 2,723,441 3,200,000 3,200,000 3,200,400 これらの結果から，単にSAのアニーリング時間や回数を増加させただけでは結果が向上しないことが明らかになった．またGAが苦手な問題に対して有効な結果を示した． Success rate [Out of 10 trials] Evaluations [Average of 10 trials] Doshisha University

テスト関数による数値実験のまとめ 遺伝的交叉を用いた並列SA (PSA/GAc) GAオペレータを用いた3種の並列SAと 解探索能力を比較 遺伝的交叉を用いることは有効である 逐次SA，分散GAと解探索能力を比較 いずれの問題でも逐次SAより高い探索能力を示す GAが苦手とする問題に対しても有効である GAオペレータのうち遺伝的交叉を用いること 特にGriewankに強いから大丈夫だ Doshisha University

テスト関数による数値実験のまとめ 遺伝的交叉を用いた並列SA (PSA/GAc) 遺伝的交叉を用いることは有効である タンパク質のエネルギー関数 大域的に極小値がある関数(Rastrigin)でも， 局所的に極小値がある関数(Griewank)でも 有効な探索が行える GAオペレータのうち遺伝的交叉を用いること 特にGriewankに強いから大丈夫だ タンパク質の構造解析にPSA/GAcを適用し， 現在用いられているSAよりも高い性能を得る Doshisha University

タンパク質の立体構造解析 構造解析に用いられているSAとの解探索能力の比較 5つのアミノ酸からなるタンパク質Met-enkephalin 最小エネルギー構造 E < -11 kcal/mol Met-enkephalin 設計変数　19個の二面角 1MCsweepによって 19回のアニーリングの処理 アニーリングステップ数を世代数とよぶ． Doshisha University

PSA/GAcと逐次SAのパラメータ 20 2.0 1.0 32 4976 , 4992 99684*19 , 100005*19 1 個体数 MCsweep数 評価計算回数 初期温度 最終温度 交叉周期 PSA/GAc 20 2.0 1.0 32 4976 , 4992 99684*19 , 100005*19 SSA 1 100000 --- 100000*19 Doshisha University

実験結果 [Met-enkephalin] SSA PSA/GAc 100000*19 Success rate Evaluations 100005*19 99684*19 0.80 0.90 0.50 [Out of 10 trials] Doshisha University

PSA/GAcによるタンパク質の構造解析 5つのアミノ酸からなるタンパク質Met-enkephalin 現在タンパク質の構造解析に用いられているSAと 比較して，PSA/GAcの解探索能力は優れている 遺伝的交叉によって 大域探索を効率よく行っている Met-enkephalin GAオペレータのうち遺伝的交叉を用いること 特にGriewankに強いから大丈夫だ Doshisha University

結論 遺伝的交叉を用いた並列シミュレーテッドアニーリング(PSA/GAc)を提案 SAの優れた局所探索能力を保持し， 遺伝的交叉によって 遺伝的交叉を用いることは有効である 局所探索と大域探索を効率的に行うことができる SAの優れた局所探索能力を保持し， 遺伝的交叉によって GAの大域探索能力を獲得 テスト関数にPSA/GAcを適用し，交叉を用いることの有効性を検証． また他のアルゴリズムとの解探索能力の比較． Doshisha University

結論 遺伝的交叉を用いた並列シミュレーテッドアニーリング(PSA/GAc)によるタンパク質の構造解析 現在用いられている逐次SAよりも 優れた探索を行うことができる PSA/GAcを用いて 大規模なタンパク質の構造解析を行い， 良好な結果を得ること Doshisha University