1. 遺伝的アルゴリズムとは
遺伝的アルゴリズム（Genetic Algorithm、GA）は、生物の進化をヒントにした最適化手法です。一つの点だけを更新するのではなく、複数の解候補の集団を持ち、評価の良い候補を残しながら新しい候補を作ります。
目的関数の微分を必要としないため、形が複雑な関数や、組み合わせを選ぶ問題にも応用できます。ただし、問題に合った候補の表現方法と評価方法を設計する必要があります。
2. 一世代の処理
各候補を目的関数で評価し、良い候補を選択します。選ばれた親の情報を混ぜる交叉と、ランダムな変化を加える突然変異で次世代を作ります。最良候補を確実に残す「エリート保存」を加えることもあります。
- 初期集団候補を複数作る
- 評価目的関数で採点
- 選択良い親を選ぶ
- 交叉・突然変異新しい候補を作る
- 次世代集団を更新する
終了条件を満たすまで「評価 → 選択 → 交叉・突然変異 → 次世代」を繰り返します。
最小化問題なら目的関数の値が小さい候補ほど有望です。ただし、良い候補だけに偏ると集団の多様性を失うため、選択の強さと突然変異の量の調整が重要です。
3. 解候補はどう変わるか
一変数の例として、次の関数を区間内で最小化します。二乗項と周期的な凹凸があり、最小値は x = 1 で f(x) = 0 です。
f(x) = (x − 1)2 + 0.7 sin2(4(x − 1)), −0.7 ≤ x ≤ 2.7
下の図は、18個の実数値の候補を使った固定乱数の計算例です。各世代では3候補から良い親を選ぶトーナメント選択、親の加重平均による交叉、ガウス分布に従う突然変異、最良候補1個の保存を使いました。
この例では改善が見られますが、毎回同じ結果になるわけではありません。初期集団や乱数の違いによって、探索の経過は変わります。
4. 強みと注意点
- 強み：微分を使わずに探索でき、複数の領域を同時に調べられます。実数値だけでなく、順序や組み合わせを表す候補にも使えます。
- 計算量：集団の全候補を世代ごとに評価するため、目的関数の計算が高価な場合は負担が大きくなります。
- 多様性：似た候補だけになると、局所的に良い解へ早く集まりすぎることがあります。突然変異や選択圧を調整します。
- 保証：最良値が改善しても、大域的な最適解に到達した保証はありません。複数回の試行や、別の手法との比較が有効です。
GAを評価するときは、最良の目的関数値だけでなく、世代ごとの改善と候補の広がりを一緒に見ることが大切です。探索が進んでいるのか、単に同じ場所へ集まっているだけなのかを区別できます。