GAとは
生物の自然淘汰における遺伝と適者生存の仕組みを用いて,複雑な問題の最適解を求める手法のこと.
複数の個体が選択と交叉/突然変異を繰り返しながら,適応度の高い個体集団に世代交代していくことで最適な個体を見出せる.
- 言葉の定義
- 個体・・・設計変数のまとまりこと.
- 遺伝子・・・１つの設計変数のこと.
- 適応度・・・各個体の目的関数の値のこと.
- 選択・・・個体の適応度に基づいて個体を減らすこと.
- 交叉・・・選ばれた2個体の遺伝子の一部を入れ替える操作.
- 突然変異・・・個体の遺伝子の一部をランダムに変化させること.
解の記法
- バイナリエンコーディング
- 各遺伝子を0,1のビットとして表現する方法.
- 順序エンコーディング
- 各遺伝子を順序を示す数字として表現する方法.
- 実数値エンコーディング
- 各遺伝子を数値/文字として表現する方法.
- 木構造エンコーディング
- 遺伝子構造を配列ではなく木構造として表現する方法.
選択
- ルーレット方式
- 集団をルーレット版に見立て,適応度とルーレットの面積を比例させることで,ランダムな選択を行う方式.
- 適応度の差が大きいと,局所的な最適解に早期に収束してしまう原因になりがち.
- ランキング方式
- 上記のルーレット方式の早期収束を防ぐため,適応度の序列に合わせた選択確率をあらかじめ決めておく方式.
- トーナメント方式
- あらかじめ決めた個体数をランダムに抽出し,その中でもっとも適応度の高い個体を選ぶ方式.
- エリート方式
- 適応度の高い順に選ぶ方式. 解の多様性はなくなる.
交叉
- 一点交叉
- 遺伝子が交叉する場所をランダムに選び,それより後ろの遺伝子を全て入れ替える.
- 効率が低いためほぼ使われない.
- 二点交叉
- ２つの交叉点をランダムに選び,その間にある遺伝子を入れ替える.
- 多点交叉
- 3つ以上の交差点をもつ.
- 一点交叉/二点交叉より効果が出ないためほぼ使われない.
- 一様交叉
- 各遺伝子を所定の確率（通常は1/2）で入れ替える.
この他にも、循環交叉や順序交叉など,多数の交叉方法がある.
突然変異
- 置換
- ランダムな遺伝子を対立遺伝子に置き換える.
- 摂動
- ランダムな遺伝子の値を微小変化させる.
- 交換
- ランダムな２つの遺伝子を入れ替える.
- 逆位
- ランダムな2つの遺伝子の間の順序を逆にする.
- 攪拌
- ランダムな2つの遺伝子の間をランダムに並べ換える.
- 転座
- ランダムな2つの遺伝子の間の遺伝子全てを別の遺伝子間に移動する.
- 重複
- ランダムな2つの遺伝子の間の遺伝子全てを別の遺伝子間に複製する.
- 挿入
- ランダムな場所にランダムな遺伝子を挿入する.
- 欠失
- ランダムな遺伝子を削除する.
世代交代モデル
- 離散世代モデル
- 全ての個体が世代交代し,現世代全ての個体が次世代個体に置き換えられるモデル.
- 連続世代モデル
- 現世代の一定の割合のみが世代交代するモデル．
実装
GitHubにソースコードをあげています。
選択はエリート方式、繁殖は二点交叉と置換の突然変異を混ぜて実装しました。
局所解にハマってしまったので、時間があればアルゴリズムを改善する予定です。
参考