Algorithm:GA)とは、近似解を探索するためのアルゴリズムの一つです。データを個体(遺伝子)のように見立て、淘汰や交叉、突然変異など、生命の進化を模した処理を行いながら、適応度の高い(最適解に近い値)を探し出します。用語まずは簡単に用語を整理しておきます。個体群それぞれに固有の遺伝子(データ)を持つ個体の集団。世代を重ねるごとに、優秀な個体が残るようになります。個体の性質を表す情報のことです。ビット列で表すことがあります。個体がどの程度優秀か(環境に適応しているか)を示す指標です。適応度関数によって求められます。選択(淘汰)現世代個体から適応度の高い個体が生き残り、次世代にその遺伝子を残す過程の処理です。適応度の低い個体は淘汰されていくので、次世代の個体群は現世代より優秀な個体が残るようになります。親となる個体から、子孫を生成する処理を指します。遺伝的操作の一つで非常に重要な処理です。個体に対しての遺伝的操作で、生物に見られる遺伝子の突然変異をモデル化したものです。個体の遺伝子の一部が一定確率で変化します。これにより局所的な最適解に陥ることが防がれますが、突然変異の確率が高すぎると、収束しにくくなります。アルゴリズムまずはアルゴリズムの手順を示します。現世代個体群と次世代個体群を表すリスト(N個分)を用意します。ランダムな初期個体群を生成し、現世代とします。ある確率で次のいずれかの処理を行い、次世代個体群に追加します。親となる個体を2つ選び、交叉して子となる個体を作成します。現世代から1個体を選択し、そのまま複製します。1個体選択し、遺伝子の一部を突然変異させます。処理を繰り返し、次世代個体N個を作成し、現世代に移行します。最大世代数になるまで繰り返し、最終世代で最も適応度の高い個体を「解」とします。難しいイメージを持つかもしれませんが、GAは比較的実装が容易なのですぐに試すことができます。)の処理にはいくつかの種類があり、どのような種類を選択するかによってうまくいったりいかなかったりします。現世代の個体群の中から優秀な個体を選択し、次世代にその遺伝子を残す必要がありますが、問題はどのように個体を選択するかという点にあります。単純に最も適応度の高い個体だけを選択すると、解の多様性が失われて局所解しか得られなくなってしまいます。以下の適用度を持つ個体群から2個体選択するとします。25エリート選択これは単純に最も適応度の高い個体を確実に選択する方法です。選ばれた個体を次世代に残すことで確実に現世代よりも適応度が同等以上の個体を維持てきます。エリートの遺伝子が広がりすぎることで解の多様性が失われる可能性もあります。例:常に適応度の高い個体、「個体A」「個体B」が選択されます。個体Aの選択される確率を、全個体の適応度の総和を分母、個体Aの適応度を分子として求めた値とします。個体間の適応度の差が選択される確率に反映される方法です。したがって適応度の差が極端に大きいと、選択確率にも大きく影響します。各個体に対し適応度での順位付けを行います。順位ごとにあらかじめ決められた確率を決めておき、その確率で選択を行います。...」といった具合です。この方法は適応度の差の大きさが確立影響しない点でルーレット選択と異なります。どれだけ差があろうと、順位ごとに確率は決められた値を用います。逆にほとんど差のない適応度であったとしても、明順位の差により選択確率への影響が大きくります。例:各個体を以下の確率で選択します。100%トーナメント選択あらかじめトーナメントサイズを決めておき、個体群からランダムにサイズ分取り出し、その中から最も適応度の高い個体を選択する方法です。トーナメントサイズにより淘汰の具合を調整できます。個体C)が選択されます。親として選択された2個体の遺伝子を掛け合わせ、子となる個体を生成する処理です。親となる個体のデータの交叉点(分割点)をランダムに決定します。交叉点で遺伝子データを分割し、後半部分を入れ替えることで遺伝子を子に引き継ぎます。具体的には以下のようになります。0一般に効率な方法ではないとされ、今ではあまり利用されません。親となる個体のデータの交叉点(分割点)をランダムに2点決定します。交叉点で遺伝子データを3分割し、真ん中部分を入れ替えることで遺伝子を子に引き継ぎます。具体的には以下のようになります。あれば、当然三点あるいはN点でも交叉を行えます。二点交叉や一様交叉よりも良い値が出ることはないとされ、利用されることはありません。生物の突然変異をモデル化したものです。変異は個体の遺伝子データの一部を変化させる操作を行います。程度の確率で発生させるようにします。変異の確率が高すぎるとランダム探索に近くなる、つまり解が収束しにくくなってしまいます。一般的に突然変異の遺伝子操作は、ランダムな遺伝子を対立する遺伝子に置き換えます。ビット型であれば反転させます。遺伝的アルゴリズムの最初の実装としては、OneMax問題を扱うのがよいでしょう。何も難しい問題ではありません。個数が最大となるビット列を求めるという問題です。言うまでもなく、最大となるなるのはすべて"1"のときです。個体を8桁のビット列とすると、個体の遺伝子データを以下のようなビット列で定義します。いうデータを求めたい実装にはまずルール(設定)決めが必要です。=4」として処理を処理を行うこととします。上位2個体をそのまま次世代に移行し、さらにその個体同士を交差した2個体の子も次世代個体とします。次世代個体には5%の確率で突然変異でランダム位置のビットを反転します。設定の如何によって結果に差が出ます。裁量で決めて動かしてみるのがよいでしょう。