遺伝的アルゴリズム


言葉の説明
交叉
突然変異

1.遺伝的アルゴリズム

 遺伝的アルゴリズム(Genetic Algrithms:以下GAと略す)は生物の遺伝現象を模擬

してシステムの最適化をおこなうアルゴリズムであり,1970年代からシステム最適

化アルゴリズムとして提唱されているが,最近その有効性が様々な分野で実証され,注

目されている.



 生物の進化を動かしているメカニズムとして,遺伝子(gene)を単位とする染色体

(chromosome)を翻訳する過程で1個体の生物が作成されるということが理解されてい

る.生物の進化は以下の特徴がある.



(1)進化は生命体そのものでなく,それを符号化した染色体に対して操作を行う過程か

  らなる.

(2)自然淘汰は,染色体から翻訳された生物の環境への適応度に結びつけられる.自然

  淘汰により適応に成功した生物の染色体が頻繁に再生される(個体が増殖する).

(3)突然変異により子の染色体は親と異なったものになる.また交叉の過程により両親

  の染色体の構成要素が組み合わされ,親と異なったものになる.

(4)生物の個体に関するすべての適応性の情報は遺伝子の組み合わせとしての染色体に

  ある.



 この生物の進化を計算機上に再現し,ある問題に関してその解の優秀性を環境への適

応度と読み換えることによって組み合わせ最適化問題を解くのが遺伝的アルゴリズムで

ある.





2.具体例

 GAを問題に結びつけるには,問題の解を染色体上に翻訳する手続きと問題設定とし

ての染色体の優秀さを評価する部分の機構を考える必要がある.例えば,ある関数f(x)

のf(x)=0(0≦x≦1)の解をGAで求めるとしよう.実際には,解は0〜1までの

範囲の連続した実数である.しかしGAでは離散化が必用である.そのため,0〜1ま

でを255等分(間隔 0.003921568627451)すると,それぞれの数字は8bitで表さ

れる.例えばタイプA:00001001は9×0.00392156862745=0.0352941176470

であり,タイプB:10100101は165×0.003921568627451= 0.6470588235294で

ある.この1か0かの数字の8個の列を染色体と考える.タイプAとBは異なる個体を

表す.個体の優秀さはそれぞれを10進数に変換し,さらに実数に変換した実数XA,

XBをf(x)に代入し,0に近い方の個体が優秀であるということで評価できる.

 このように問題を遺伝子,染色体とその評価関数に置き換えると,後は生物の遺伝進

化と同じメカニズムによって,優秀な個体が多くの子孫を残せるようにしておくだけで

世代交代が進むにつれて自然に最適解に漸近してゆく.一つの世代には数10から数

100の個体を作成し,その中から優秀さに応じて交叉を行い,次世代に子孫を残す.

現世代と次世代とを完全に分離する(次世代には子孫だけが生存する)場合と親が混合

する場合がある.このアルゴリズムは以下のようになる.

(1)染色体の集団を初期化する(乱数).

(2)染色体を評価する(f(x)=0に代入).

(3)集団の中から優秀さに応じて染色体を2つづつ選択し,ある確率で交配させ,子孫

 を残す.子孫は親の遺伝子を交叉させることで作成する.

(4)次世代全体ができるまで上記の操作を繰り返す.

(5)全ての染色体において特定の発生確率で突然変異によって一部の遺伝子を変える.

(6)上記(2)へジャンプする

 このようにGAには明確な計算終了はなく,ユーザーが適当に終了させる(最優秀の

組み合わせが変化しなくなったら終了とか,100世代目で終了など)必用がある.



 GAによる解の探索はこのように,確率に基づく探索であり,突然変位確率が高い場

合にはランダムサーチと同じになる.他の最適化手法と大きく異なる点は交叉によって

優秀な個体の情報は集団に広がっていくことである.つまり,優秀そうな領域を次第に

集中的に探索するように自動的にできている.しかも,突然変異によって異なる解空間

も適宜探索する仕組みになっている.このようにパラメータ(交叉確率,突然変異確率,

個体数)や詳細な手続き(親を残すか否かなど)を適当に選択すれば効率よく最適解を

探索してくれるのがこのGAである.




GAソフトのダウンロード


もどる