いろいろな所で進化計算について話をする機会があったんで備忘録も兼ねて。
図も交えて細かく説明したスライドはこちらから
進化計算についての話となっていますが、今回は遺伝的アルゴリズムメインで。
#遺伝的アルゴリズムとは
- 生命の進化をモデルにした組み合わせ最適化の手法
- 必ずしも最適な解を得られるとは限らない
#遺伝的アルゴリズムの流れ
- 終了条件を設定する
- 初期個体群を生成する
- 個体群の中から親となる個体を選ぶ（選択）
- 親個体を掛け合わせて子個体を生み出す（交叉）
- 生まれた個体を突然変異させる（突然変異）
- 子個体と親個体をマージ、適合度が高いものを残す（淘汰）
- 終了条件を満たすまで3~6を繰り返す
※2番目以降および個体については後述
#個体とは
- 最適化するための遺伝子(genotype)と遺伝子に対して問題となる関数を適用した適合度(phenotype)を適用したもの
ex) 0と1のバイナリ記号列中に含まれる1の数の総和を返す関数を適応関数として"00101"というバイナリ記号列は"00101"というgenotypeとなり、含まれる1の総和は2となる。この遺伝子と適応した値を持つクラスのインスタンスを個体といい、それが複数存在するものを個体群という。 - genotypeはいろいろな表現ができ、上記の0と1の記号列以外にも、実数値や木構造で表すこともできる。木構造でgenotypeを表現する場合、遺伝的プログラミングという。
#それぞれの操作
- 選択:各個体の中から最大化問題であれば高い適合度（最小化問題であれば低い適合度)の個体を選ぶ操作。ルーレット選択やトーナメント戦略がある。
- 交叉: 親として選んだ個体の遺伝子を混ぜ、子供を作り出す操作。交叉そのもののアルゴリズムはgenotypeに応じて変える。0と1のバイナリ記号列であれば2点交叉や一様交叉、実数値であればBLX-αやSBXなど
- 突然変異: 生まれた子供の遺伝子を一定の確率で変化させる。こちらもアルゴリズム自体はgenotypeの表現に依存
#その他
- 必ずしも最適な解を得られるとは限らず、また、得意な分野と苦手な分野がある
→問題に応じて適切なパラメータチューニングが必要、また、状況によってはほかのアルゴリズムを使用することを検討する必要あり - 広域探索が得意…とよく言われている
#最後に
色々ライブラリはありますが私もPythonでライブラリ作成しています。
こちらのリポジトリとなります。まだまだできていないところもありますが、よろしければいろいろご教授いただけると助かります。