初めに
まずは遺伝的アルゴリズムの基本概念から説明します。
全体の流れ
- 染色体をランダムに生成します
- 染色体の適応度と選択される確率を計算します
- 交差を行う。N-M個染色体を生成します
- 上で生成したN-M個染色体を変異させます
- 複製操作により、M個適応度のいい染色体を次の世代にコピーします
- 2~5の操作を繰り返します
遺伝子と染色体
数学問題を考えよう
x+2y+3z<0
こういう不等式が複数の解をもつ場合が多いです。一つの解が一つの染色体となります。その染色体の中のx,y,zは遺伝子と呼ばれます。
適応度関数
自然淘汰や増殖のため、染色体ごとに評価するものが適応度関数と呼ばれます。世代交代のたびに、新たな染色体が生成し、評価されます。点数の高い染色体だけ残します。
交差
前の世代の染色体の中から二つ選び、ある位置から分割し、分割されたものを組み合わせすると、新しい染色体になります。
例えば
親1: 2 3 4 5 6 7 -> 2 3 + 4 5 6 7
親2: 1 5 9 3 5 2 -> 1 5 + 9 3 5 2
子: 2 3 9 3 5 2
染色体選択はランダムではなく、ルーレットで親染色体を選びます。
世代交代という過程が進化と呼び、進化するたびに、染色体の適応度を計算し、以下の式で 選択される確率を計算します。適応度が高いほど、選択される確率が高いです。これがいい染色体が残られる理由です。
染色体aが選択される確率 =染色体aの適応度/同世代すべて染色体の適応度の和
突然変異
交差だけでは、染色体の組み合わせで、局所最適解にたどり着けますけど、全域最適解を見つけるため、新たな染色体の遺伝子を書き換えて、探索範囲を広くすします。こうすると、全域最適解の探索に有利になります。
複製
進化たびに、前の世代のいい染色体をそのまま次の世代にコピーする必要があります。
進化ごとにN個染色体が必要だとすると、交差で生成する染色体がN-M個。残りのM個が前の世代の適応度の高いものをそのまま複製してきます。
python 実装については以下のリンクに参照できる 。http://darden.hatenablog.com/entry/2017/03/29/213948
終わりに
GAは組み合わせ最適化問題にふさわしいものであり、ほかのアルゴリズムとの組み合わせで、精度上げることができます。でもすべての最適化問題がGAを使えるわけではありません。
次回はGAの欠点について、改良版GAを紹介します。
