進化的アルゴリズム学習帳

この記事は

なんか、大学院で配属された研究室が進化的アルゴリズム? とか遺伝的アルゴリズム? みたいなのをやってるっぽいのでお勉強しようかなーって。 メモにまとめるぐらいならブログ記事にしちゃうか! ぐらいのゆるい日常を淡々と描いたものです。過度な期待はしないでください。*1

そもそも進化的アルゴリズム(Evolutionary Algorithm)って?

要するに最適化アルゴリズムの1つ。生物の突然変異とか進化とかの考え方をアルゴリズムに組み込んでやろうというもの。 進化的アルゴリズムは大まかに次の4つに分類される。

似たような名前でややこしいんじゃ(半ギレ)。
この中で、たぶん一番有名だし色々使われてるのが遺伝的アルゴリズムっぽい。 僕は「進化的アルゴリズム遺伝的アルゴリズム」ぐらいに考えてたんだけど、実際には、「進化的アルゴリズム遺伝的アルゴリズム」らしい。

歴史的には、どうやら最初に進化的アルゴリズムがあってそこから分化したというわけではなく、複数の分野が同時期にぽこぽこ発生して最終的に進化的アルゴリズムにまとめられたりしたらしい。

それぞれについて詳しくどんな感じか調べた。

遺伝的アルゴリズム

遺伝的アルゴリズムの概要

遺伝的アルゴリズムでは、個体を進化させて問題に対する所望の解を求める。 具体的には個体は1つ以上の遺伝子を持ち、それによってデータを表現する。この遺伝子の列は基本的には数値の配列で表され、これを遺伝子型(GTYPE)とか呼ぶ。 この遺伝子型が表現する解を表現型(PTYPE)とか言う。*2 めっちゃ具体的に言うと、たとえば、個体A=[0, 1, 1, 1, 0, 0]、個体B=[1, 0, 1, 1, 1, 0]みたいな感じで表現する。これが遺伝子型。これを元に問題の解となるような形に表し直したらそれは表現型になる。

で、この遺伝子配列を持った個体に対して、選択、交叉、突然変異といった様々なオペレーションをかけていき、最終的に所望の表現型になるような遺伝子型を得る。 この選択の仕方とか交叉の仕方にいろんなやり方があって、それによって精度とか計算速度が結構違ったりする。 生物の進化っぽいことをやっているだけで、実際にやっていることは最適化問題を(近似的に)解いているだけ。

遺伝的アルゴリズムは、「広い探索は得意だが、局所探索は苦手」という特性がある。選択とか交叉とか突然変異といったオペレーションは、最適化問題における確率的な探索に相当するが、その仕組み上割とおおざっぱな探索になってしまう。もちろん、厳密解が出ることも多いが、局所解に落ち込んだり、全然最適解に落ち着かなかったり、最適化関数の鞍点が苦手だったりする。局所探索を行うアルゴリズム焼きなまし法とか、山登り法とか)と一緒に使うことでこれらを解決することも多い。

でも、おおざっぱな探索をするので逆に大きな問題に対しては割と強かったりする。例えば、ナップザック問題みたいにNP完全だったり困難だったりする問題は、案外いい(近似)解が早く得られる。もちろん、確率的な探索なので最悪計算量はO(∞)だけど。

どんな問題を解くの?

最適化問題を解く。ナップザック問題とか、巡回セールスマン問題みたいな問題を解くのに使ったりする。たとえば、ナップザック問題だったら、i番目の荷物を入れるかどうかを1bitで表現して、遺伝子配列を作る。これを計算すると、ヒューリスティックな探索よりシュっと計算結果が出る。

遺伝的プログラミング

遺伝的プログラミングの概要

ほとんど遺伝的アルゴリズムと一緒。違うのは遺伝子型を配列ではなく、木構造で表すことだけ。 遺伝子を気構造で表すことで、プログラムのソースコードだったり数式などの木構造をもったものを扱える。 強いて遺伝的アルゴリズムとの違いを挙げるなら、遺伝子型が木構造なので、交叉とか突然変異の操作が、配列のときと微妙に違う。

どんな問題を解くの?

所望の数式とかソースコードを生成するみたいなときに使う。ロボットを制御するコードを進化的に生成するとか、メタプログラミングとかやったりする。

進化戦略

進化戦略の概要

遺伝的ほげほげと同時期に別の場所で研究がなされていた分野。目的は、解析的には求めづらいある関数 f(x) の最大値を求めること。 その解として、 ベクトル x があり、その x を1つの個体とみなしてこいつを f(x) が最大となるような x に近づけていく。 更新の際に、ベクトルの各要素を次の式で更新する。

f:id:hilinker:20190423223038p:plain
更新時の数式

ここで、Nは分散σ2に従う正規分布なのだが、これが大きすぎると最大値を行き過ぎてしまったり、小さすぎると局所的最大値にとらわれてしまったりする。 そのため、x を更新し続けて探索を行いながら、 σ を調整していくことで最適解を求める。 つまり、進化させるべきはベクトル x ではなく、 σ の方である。 これが、遺伝的アプローチとの大きな違いだろう。

どんな問題を解くの?

お好きな非線形最適化問題をどうぞ。

進化的プログラミング

進化的プログラミングの概要

調べてみましたが、よくわかりませんでした! いかがでしたか?*3

*1:みなみけは1期と3期と4期があるのに2期がない珍しい作品

*2:RTYPEはないんですかね

*3:ちゃんと調べたら書きます