|
|
|
|
|
遺伝的アルゴリズムでは複数の個体からなる集団の進化過程を通じて、もっとも適応度（評価関数）の高い個体（解）を探す。進化過程とは突然変異と交叉により新しい個体が誕生し、それが集団の中で生き残るかどうか選択される過程である。各個体はビット列で表現され、それは染色体と呼ばれる。いま具体的な例としてＲＮＡの構造エネルギーを遺伝的アルゴリズムで最小化して、立体構造モデリングを行うことを考えてみよう。ＲＮＡの１つのヌクレオチド単位のコンフォメーション（構造）は二面角を用いて７つの変数で表現できるので、それぞれの変数を n ビットでコード化すると、k 残基のＲＮＡのコンフォメーションは k ･ 7 n ビットの染色体で表現されることになる。ここでビット列への変換にはグレイコード（Gray code）がしばしば用いられる。十進数を１桁ずつ４ビットの二進数で表すと、16 の可能性の中から 10 個を選ぶことになるが、十進の数字の値が１だけ変わることがビット列の１カ所のみの変化になるような選び方をするのがグレイコードである。
具体的な手続きは例えば以下のようにする。N個の個体からなる集団を考え、まずN個のコピーを作る。コピーの中からランダムに個体を選び、染色体上のランダムな位置のビットを変換する（突然変異）。この操作を一定回繰り返し、2N個の個体を得る。次に１組の染色体ペアを選び、変数の切れ目に相当するビット列の位置で、染色体の組換えを行う（交叉）。この操作をM回行い、合計で2N + M個の個体を得る。この中から評価関数に従ってN個を選び、次の世代とする（選択）。遺伝的アルゴリズムでの評価関数はフィットネス関数とも呼ばれ、ＲＮＡ立体構造モデリングの場合、各ヌクレオチドがあらかじめ指定された構造（例えば理想的なＡ型構造）の近傍にあるとする局所的な制約、ベースペアやスタッキングによる遠距離の束縛条件、それに原子間の反発などを考慮して作ることができる。選択を評価関数の値だけで上からとっていくと、集団の多様性が失われるので、下の方からも選択するとよりよい最適解が得られるとの考え方もある。