SoftComputing lab.
 
Googleでサイト内検索:

Fuzzy Theory
ファジィ理論
Neural Network
ニューラルネットワーク
Chaos
カオス
Artifical Intelligence <AI>
人工知能
Genetic Algorithm <GA>
遺伝的アルゴリズム
お勧めの本

遺伝的アルゴリズム 用語集


遺伝的アルゴリズム(GA) Genetic Algorithm

遺伝的アルゴリズムとは、生物の進化の過程をまねることでソフトウェアの最適化を図る手法です。考え方としては、遺伝と、自然淘汰を繰り返すことによって、より優秀なアルゴリズムを導き出そうというものです。

遺伝的アルゴリズムは、はじめに異なった遺伝子を持ついくつかの初期集団を用意し、そのなかで、選択(selection)、交差(crossover)、突然変異(mutation)の3つのプロセスを行います。選択とは、集団の中から優秀なものを選び出すことです。交差とは、選び出された集団のなかでランダムに遺伝子の一部を交換を行うことです。突然変異とは、低い確率で起こり、遺伝子情報の一部をランダムに書き換えることです。具体的には、以下のような流れになります。

1.もとになるアルゴリズムをいくつか用意する。
2.個体ごとに適応度を計算する。
3.条件に合えば終了。合わなければ4へ進む。
4.優秀な個体の集団の中でランダムに選んだ個体の遺伝子の交差を行う。
5.突然変異が起きるか判定を行い、それに従って突然変異を行う。
6.2へ戻る

つまり、初期の集団から自然淘汰と生殖活動を行うことにより、より優秀な遺伝子を持つ個体だけを選び出していくわけです。工学的には最適解をランダムかつ速やかに探索する手法となります。

遺伝的アルゴリズムの応用範囲は非常に広く、広い範囲における探索、最適化問題、機械の学習問題など実に多岐にわたります。また、他の様々な手法とも相性もよく組み合わせて使うこともできます。

1999/09/10

進化的計算手法 Evolutionary Computation : EC

ダーウィンの進化論をもとにした、各種問題解決戦略(手法)の総称で、自然選択と、有性生殖をもとにしています。遺伝的アルゴリズム(Genetic Algorithm : GA)もこの中に含まれます。その他には、遺伝的プログラミング(Genetic Programming : GP)、進化的プログラミング(Evolutionary Programming : EP)、進化的戦略(Evolutionary Strategy : ES)などもあります。これらのアルゴリズムは、進化的アルゴリズム(Evolutionary Algorithm : EA)と呼ばれることもあります。

1999/09/10

進化的プログラミング Evolutionary Programming : EP

EPは確率的なトーナメントを使った解の変化を強調した手法です。確率的なトーナメントでは、個体がお互いに、次の世代に選択される過程を直接計算します。そのため、低い適用度を1つ持つ個体は、もしあいての個体がさらに低い適用度を持っていれば選択される可能性が高まります。具体的には以下の流れになります。

1.初期化
親ベクトルを実行範囲からランダムに選んで初期値とする。
2.突然変異
子ベクトルを、親ベクトルの構成に対するガウシアンのランダムな変化を加えることで生成する。
3.評価
親ベクトルと子ベクトルの評価を行う。
4.競合
いくつかの競争者を親ベクトルと子ベクトルからランダムに選び、各個体と競争相手の適用度を比較して、重み係数を計算する。
5.選択
4で求めた重みにより次の世代の親を選択する。

2から5を解が収束するまで繰り返す。

1999/09/10

進化的戦略 Evolutionary Strategy : ES

ESは無性生殖の有機体の発達をシミュレートしたものです。GAが交差手法による解の再結合であるのに対して、ESは突然変異と選択手続きだけを使います。また、ESはGAと違い実パラメータを使います。いかに手法の一つを紹介します。

1.初期化
親ベクトルを実行範囲からランダムに選んで初期値とする。
2.突然変異
子ベクトルを、親ベクトルの構成に対するガウシアンのランダムな変化を加えることで生成する。
3.評価
親ベクトルと子ベクトルの評価を行う。
4.選択
次世代の親ベクトルをそれらの適用度をもとにした個体集団から選択する。

2から4を解が収束するまで繰り返す。
1999/09/10

遺伝子

各個体の特性を現す情報のことです。異なる性質の個体は必ず遺伝子も異なります。

1999/10/26

遺伝子座

遺伝子の要素が格納される枠のことです。2つの異なる性質を持つ個体の遺伝子座は2つあります。たとえば、「髪の色」「目の色」という、二つの特性を現すには、二つの遺伝子座が必要になります。

1999/10/26

対立遺伝子

同じ遺伝子座に収まる異なる遺伝子のことです。たとえば、「髪の色」という遺伝子座に収まる、(金髪)と(黒髪)は対立遺伝子になります。

1999/10/26

遺伝子型

個体の遺伝子を「001100100・・・」などのコードとして表現する方式のことです。

1999/10/26

表現型

個体の遺伝子を、数値や、記号など直接その性質を現す方法で表現する方式のことです。

1999/10/26

世代 generation

遺伝子を持つ個体の選定一回のステップのことです。遺伝的アルゴリズムでは、この世代を重ねて行くことで、優秀な遺伝子を選定して行きます。

1999/10/04

個体群 population of individuals

それぞれに固有の遺伝子を持つ集団。ただし、同じ遺伝子を持つ個体が含まれる可能性もある。世代を重ねるごとに、個体群には優秀な遺伝子だけが残って行きます。

1999/10/04

適応度 fitness value

各個体の評価指標のことです。一般に、各遺伝子の優劣をつけるための評価関数で個体ごとに求められます。適応度の低い個体は淘汰されて行きます。

1999/10/04

増殖と淘汰 reproduction & selection

各個体は適応度によって評価され、適応度の低い個体は淘汰され、消えます。また、適応度の高い個体からは、次の世代の個体群が重複を許して選ばれます。(つまりいくつか同じ遺伝子があるということです)これを増殖といいます。

1999/10/04

交叉 crossover

個体に対する遺伝子操作(genetic operators)の一つで、個体群の中から特定の遺伝子対を選び、その特定の部分を入れ換える操作を言います。遺伝子を入れ換える手法は様々なものが提唱されています。1点で入れ換える方法、2点を選びその間にある部分を丸ごと入れ換える方法、すべての遺伝子についてランダムに場所を選び入れ換えてしまう方法など様々です。

1999/10/04

突然変異 mutation

個体に対する遺伝子操作の一つで、遺伝子情報の一部をある確率で変化させることです。突然変異を起こすことによって、個体群が局所安定に陥りにくくなります。突然変異は、あらかじめ決めておいた生起確率に従って、各遺伝子ごとに起こります。また、この生起確率が高過ぎると、良い性質を持つ遺伝子も突然変異で壊れてしまう可能性があるので、小さめの値を選ぶほうがいいようです。

1999/10/04

ハミング距離

適応変異という、突然変異の手法で用いられる尺度で、二つの親の一致しない度合です。つまり、二つの親が似ている場合は、ハミング距離は近く、似ていない場合はハミング距離は遠くなります。

適応変異では、ハミング距離が近いほど、突然変異が起こりやすく、遠くなると突然変異は起こりにくくなります。つまり親の類似度によって、突然変異の起こる確率が変化するというわけです。この手法は、個体群の多様性が無くなり局所解に陥るのをある程度防ぐ効果があると言われています。

1999/10/26