遺伝的アルゴリズム（Genetic Algorithm：GA）とは？
ダーウィンの「自然淘汰説」によれば，種は，自然淘汰が作用した結果生
じたものであり，ある地域の環境条件に最も適応している種が生き残り，
さらに進化する可能性を秘めているとされている．つまり，進化の結果変
異した個体がその環境から拒まれれば「悪く」，その個体は淘汰される．
一方，その個体が環境に受け入れられれば「正しく」，その環境の資源を
有効に利用でき，最も多くの子孫を残すことができるのである．このダー
ウィンの進化に関する考え方は，進化の総合説と呼ばれている．
DNA はすべての遺伝情報の担い手であり，アデニン，チミン，グアニン，
シトシンの 4 種類の塩基を並べた 2 重螺旋構造をとっている．遺伝情報
はこれら塩基の並びによって記述され，その情報は正確に子孫に複写，伝
達されるが，高等生物の増殖は有性生殖であり，この場合は父方と母方の
遺伝情報を混ぜ合わせたものを子孫が受け継ぐことになる．この過程は
「交叉」と呼ばれている．また，まれに複写ミスが生じることがあり，こ
れを「突然変異」という．突然変異は生物の進化の過程で重要な意味を持っ
ており，ほとんどの場合は環境に適応できない個体を生成する．しかし，
まれに幸運な突然変異を起こす場合があり，その個体は子孫を増やし，つ
いには集団のなかに広まっていく．
交叉や突然変異の結果生じた個体を次世代の集団として世代が進むと，環
境への適応度が高い遺伝情報は優先的に伝えられ，適応度の低い遺伝情報
は自然淘汰される．つまり集団の中には，適応度の高い個体が増殖してい
くことになる．これが遺伝と進化の基本原理である．
遺伝的アルゴリズムは，この「初期世代では様々な DNA をもつ個体の集
団が，複製や交叉，突然変異を繰り返しながら世代が進むうちに，環境に
最も適した個体が集団の中に誕生する」という過程を計算機上でシミュレー
トするアルゴリズムである．
GA の流れ
計算機を用いても解くことが難しい問題とは？
簡単には，「すべての場合を調べあげる方法以外の解法が知られていない 問題」である．例えば，次のような部分和問題が挙げられる．
具体的には，以下のような問題となる．正整数の集合 S と 1 個の正整数 a が与えられた時， S の要素を適当に組み合わせてその和を a に等しくする ことができるかどうか．
この問題の場合，考えられる組み合わせは以下のようになる．S = {1，2，6，7}，a = 11
| No. | 組み合わせ | 和 | No. | 組み合わせ | 和 |
|---|---|---|---|---|---|
| 1 | φ | 0 | 9 | {2，6} | 8 |
| 2 | {1} | 1 | 10 | {2，7} | 9 |
| 3 | {2} | 2 | 11 | {6，7} | 13 |
| 4 | {6} | 6 | 12 | {1，2，6} | 9 |
| 5 | {7} | 7 | 13 | {1，2，7} | 10 |
| 6 | {1，2} | 3 | 14 | {1，6，7} | 14 |
| 7 | {1，6} | 7 | 15 | {2，6，7} | 15 |
| 8 | {1，7} | 8 | 16 | {1，2，6，7} | 16 |
この程度の大きさの集合 S であれば，その組み合わせ数は 16 通 りしかないため，計算機を用いれば短時間で解を求めることは可能である． しかし S が大きくなった時，組み合わせ数は爆発的に増加する．
n を S の要素数とした時，一般に S の部分和集 合数は 2n で表される．S が大きくなった時， すなわち n が大きくなった時，その組み合わせ数は以下のように なる．
| n | 組み合わせ数 |
|---|---|
| 4 | 24 ＝ 16 |
| 10 | 210 ≒ 103 |
| 100 | 2100 ≒ 1030 |
| 1000 | 21000 ≒ 10300 |
となる．さらに，2100 × 10-9 秒 ≒ 1030 × 10-9 秒 ＝ 1021 秒
であるので，およそ 30 兆年かかることになる．1021 秒 ≒ 3 × 1013 年