遺伝的アルゴリズムとは

遺伝的アルゴリズムというのは、解空間があまりに広大で全探索が通用しないような問題に対して、
近似解を求めるための手法です。

名前からも分かるようにダーウィンの進化論に基づく生物界の 「遺伝の法則」を模倣したモデルとなっています。その内容は自然淘汰による最適遺伝子の生存です。つまり環境に適応できる優秀な個体は次世代に子孫を残せるが、適応できない個体は絶滅してしまうというメカニズムなのです。

なお遺伝的アルゴリズムは英語で"Genetic Algorithm"と呼ばれるところからよくGAと略されます。（以後は遺伝的アルゴリズをGAと表記することにします）

目次へ

GAの基本的な流れ

　　　1.初期集団の生成
　　　　↓
　　　2.適応度の評価
　　　　↓
　　　3.選択
　　　　↓
　　　4.交叉
　　　　↓
　　　5.突然変異
　　　　↓
　　　6.終了条件判定

　（親となるデータを乱数で生成）
　　　　
　（個体の適応度を調べる）
　　　　
　（評価の高い個体を選び出す）
　　　　
　（次世代の作成）
　　　　
　（多様性の保持）
　　　　
　（終了条件に満たない場合 "2" に戻る）

"2～5"までを1サイクルと考えて、これを設定した世代数分だけ繰り返します。

目次へ

初期集団の生成

単純な方法として乱数で染色体を作ってみましょう。

染色体というのは遺伝子の集まりのことです。本来遺伝子は、アデニン・グアニン・シトシン・チミンの４つの塩基配列から成っているのですが、 GAでは 0 と 1 の２つの情報で遺伝子を構成 します。

これだと情報量は減ってしまいますが、コンピュータにとっては遺伝子情報は 0 と 1 の２つだけの方が動作原理とマッチしていて扱いやすいのです。またGAのメカニズム上都合が良いともいえます。

プログラム上、染色体は２種類の表現方法があります。

①２進数で表現する場合

これは染色体を遺伝子の配列として表現する方法です。まず染色体のための配列を用意し、その配列に対し順々に 0 か 1 の数値を入力していきます。配列に 0 と 1 どっちの情報を入れるかは乱数によって決定します。

②10進数で表現する場合

染色体が10進数の数値として表現されます。10進数の数値といっても人間にとってそう見えるだけであり、コンピュータにとってはただの２進数の集まりにすぎません。人がコンピュータにとっての2進数を直接操作する場合、ビット演算を使う必要があります。

それではこの２つの方法のうちどちらを使えば良いのでしょうか？

まず、あなたがどのプログラミング言語を使用するかによって制約があります。基本的に①の方法はVBでもJavaでもCでも可能です。

しかし②の方法はビット演算が可能なプログラミング言語でなければなりません。VBではビット演算ができませんので必然的に①の方法を選択することになります。

両方の方法がOKな言語の場合どちらの方法を使うのが良いのかというと、これはもう個人の好みで選択して良いのではないかと思うのですが、私としては②の方法を使ったほうがデータの扱いが楽のような気がします。①では個体（染色体）のデータを配列で管理しなければなりませんが、 ②では整数型の変数を1つ用意するだけで済みますのでデータ管理が楽チンです。という訳でできるだけ②の方法を使うようにしましょう。

C言語でのプログラム例をこちらに載せときます。

(２進数で表現する場合のソース) 　　 (10進数で表現する場合のソース)

目次へ

次回の予定

何にしようかな

目次へ

遺伝的アルゴリズムTopへ