いろいろな所で進化計算について話をする機会があったんで備忘録も兼ねて。

図も交えて細かく説明したスライドはこちらから

進化計算についての話となっていますが、今回は遺伝的アルゴリズムメインで。

#遺伝的アルゴリズムとは

#遺伝的アルゴリズムの流れ

※2番目以降および個体については後述

#個体とは

最適化するための遺伝子(genotype)と遺伝子に対して問題となる関数を適用した適合度(phenotype)を適用したもの

ex) 0と1のバイナリ記号列中に含まれる1の数の総和を返す関数を適応関数として"00101"というバイナリ記号列は"00101"というgenotypeとなり、含まれる1の総和は2となる。この遺伝子と適応した値を持つクラスのインスタンスを個体といい、それが複数存在するものを個体群という。
genotypeはいろいろな表現ができ、上記の0と1の記号列以外にも、実数値や木構造で表すこともできる。木構造でgenotypeを表現する場合、遺伝的プログラミングという。

#それぞれの操作

選択:各個体の中から最大化問題であれば高い適合度（最小化問題であれば低い適合度)の個体を選ぶ操作。ルーレット選択やトーナメント戦略がある。
交叉: 親として選んだ個体の遺伝子を混ぜ、子供を作り出す操作。交叉そのもののアルゴリズムはgenotypeに応じて変える。0と1のバイナリ記号列であれば2点交叉や一様交叉、実数値であればBLX-αやSBXなど
突然変異: 生まれた子供の遺伝子を一定の確率で変化させる。こちらもアルゴリズム自体はgenotypeの表現に依存

#その他

必ずしも最適な解を得られるとは限らず、また、得意な分野と苦手な分野がある
→問題に応じて適切なパラメータチューニングが必要、また、状況によってはほかのアルゴリズムを使用することを検討する必要あり
広域探索が得意…とよく言われている

#最後に
色々ライブラリはありますが私もPythonでライブラリ作成しています。
こちらのリポジトリとなります。まだまだできていないところもありますが、よろしければいろいろご教授いただけると助かります。