遺伝的アルゴリズム(GA)
効率的に近似解を求めよう


目次

 1ページ目
 第0話 遺伝的アルゴリズムとは
 第1話 GAの基本的な流れ
 第2話 初期集団の生成
 第3話 次回の予定

 関連ページ
 アルゴリズムの話


現在リニューアル中です。アルゴリズムの話の更新が一段落したら、 こちらの更新も再開したいと思います。(2010/03/22)


遺伝的アルゴリズムとは


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

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

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


GAの基本的な流れ


   1.初期集団の生成
    ↓
   2.適応度の評価
    ↓
   3.選択
    ↓
   4.交叉
    ↓
   5.突然変異
    ↓
   6.終了条件判定
 (親となるデータを乱数で生成)
    
 (個体の適応度を調べる)
    
 (評価の高い個体を選び出す)
    
 (次世代の作成)
    
 (多様性の保持)
    
 (終了条件に満たない場合 "2" に戻る)


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

初期集団の生成


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

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

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


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


@2進数で表現する場合

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


A10進数で表現する場合

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


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

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

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

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


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

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



次回の予定


何にしようかな





遺伝的アルゴリズムTopへ