蛋白質の同定

Ishikawa, Toya, Totoki [19] は DNA/RNA の配列から蛋白質を同定する 問題に対して, 並列GA探索と山登り探索のハイブリッド探索を適用し, 並列 best-first 探索, 並列山登り探索と比較した.

一つのプロセッサにつき一つの解候補を持つが, 複数のプロセッサでサブ集団を構成す る island GA である. サブ集団内では選択と交配が行なわれるだけでなく, DPマッチ ングを用いた局所探索が併用されている. このためGAは良質の初期探索点の生成に使わ れていると考えられる.

この並列GAの最大の特徴は, サブ集団ごとに異なる選択確率パラメータを採用している ことである(図5.9). 選択確率とはサブ集団中で次の世代に生き 残れる個体の比率であり, 0%, 30%, 60%, 90% の4つのサブ集団が存在する. 移住 は選択確率が低いサブ集団から高いサブ集団へ順に行なわれる. 移住が発生するのは次 の集団の最高値より良い個体が出現したときである. 局所探索で局所最適解に陥った個 体は除去される. このような段階的な選択確率を採用することによって, より適応度の 高い解候補の周辺を効率的に探索すると同時に, 新たな探索ポイントを供給するメカニ ズムも提供することができる.

並列論理プログラミング言語 KL-1 で記述し, 255プロセッサの論理型並列計算機 PIM 上で実行した.

図5.9 異なる選択確率を持つサブ集団[19]