遺伝的アルゴリズム
目次
はじめに
機械学習では重みの最適化に勾配降下法が一般的に採用されているようですが、なぜだろう?と前から疑問に思っていました。
確かに勾配降下法はコスト関数の勾配方向に向かって重みを更新するだけなので、非常に簡単に実装できるのですが、学習率をうまく調整しないと発散したり、逆に学習が中々進まなかったりという問題があります。
極値解にも落ち入り易く、またコスト関数が複雑すぎて勾配が計算できない場合には使えません。
あくまで今の私にとってですが、勾配降下法はあまりいい印象が無いです。
そこで遺伝的アルゴリズムを使って重みを最適化したらどうかな?というのが今回の趣旨です。
遺伝的アルゴリズム
昔仕事で遺伝的アルゴリズム使ったことがあるのですが、中々に凄まじいアルゴリズムです。英語(Genetic algorithm)の頭文字をとってGAと呼ばれています。
遺伝的アルゴリズムは、設計変数を遺伝子と見立てて、ランダムに選んだ設計変数の集合から、選択(淘汰)、交叉(交配)、突然変異の操作を繰り返してやると、いつの間にか最適解が求まるというもので、目的関数がブラックボックスであろうが、また複数ある多目的最適化であっても関係なく最適解が出てきます。
よくわからないですがとにかく凄い!という印象があります。
なぜこのアルゴリズムで、最適解が求まるかという数学的な証明は非常に難しいですが、アルゴリズム自体はそれ程複雑ではありません。
用語説明
遺伝的アルゴリズムで使う用語は、一般的な最適化アルゴリズムで使う用語と少し異なるので確認しておきます。機械用語が生物用語に置き替わります。
- 遺伝子(gene) : 一つの設計変数のこと。
- 個体(individual) : 設計変数の1セット。
- 個体集合(population) : 個体を集めたセット。現世代(population)と次世代(offspring)の2つを用意する必要があります。
- 世代(generation) : 現世代と次世代を包括した個体集合の表現。
- 適応度(fitness) : 各個体に対する目的関数の値。
- 選択(selection) : 現世代から次世代への淘汰のこと。適応度の高いものを優先的に選択します。
- 交叉(crossover) : 2個体間の遺伝子の入れ替えのこと。生物が交配によって子孫を残すことをモデル化したもの。
- 突然変異(mutation) : 個体の遺伝子をランダムに変化させること。
英語でカッコ書きしたのは、プログラムを書くときに変数名に使いたいからです。
アルゴリズムの流れを、ステップ別で見ていきましょう。
ステップ1(初期世代の作成)
先ずは個の個体をランダムに生成し、最初の現世代となる個体集合を作ってやります。
その後、それぞれの個体で適応度を計算しておきます。
ステップ2 (選択)
現世代からランダムに個の個体を取り出し、一番適応度が高い個体を1つ選び空の次世代プールに追加します。次世代の個体数が現世代と同じ個になるまでこの操作を繰り返します。
この方法はトーナメント選択と呼ばれており、をトーナメントサイズと呼びます。
ステップ3 (交叉)
ステップ2で作成した次世代プール中の個体を2つのグループに分割します。グループ分けした後の次世代プールは空にしておきます。
それぞれのグループで1個体ずつ、計2個体取り出し、確率でこの2個体同士で遺伝子の入れ替えを行い、空の次世代プールに戻していきます。この確率の事を交叉率と呼びます。
交叉が発生しない場合は、そのまま2個体を次世代プールに戻す形になります。
遺伝子の入れ替え方法は、個体の遺伝子列内にランダムで交叉点を二つ入れてやり、二つの交叉点に挟まれている部分を入れ換えてやります。2点交叉と呼ばれています。
ステップ4 (突然変異)
ステップ3でアップデートした次世代プールから確率 (個体突然変異率)で突然変異が発生する個体を選びます。
選んだ個体の各遺伝子を確率 (遺伝子突然変異率)でランダムに変更します。
その後、次世代を現世代に上書きしステップ2に戻ります。
ステップ2からステップ4を繰り返すといつの間にか最適解が求まるというわけです。
Pythonで実装
遺伝子が取り得る値を0、1とし、個体内の遺伝子の和を最大化するテストスクリプトを書いてみました。
言わずもなが、個体内の全ての遺伝子が1になる物が最適解です。
遺伝子の個数は100個とし、世代内の個体の個数は300個で40世代繰り返します。
個体の遺伝子を入れるコンテナとして、numpyのndarrayを継承して新しくIndividualというクラスを作りました。(少しハマりました。。)
個体の適応度を保存するfitnessというメンバ変数を追加しています。
その他は特に工夫した点は無いかな?。上に書いたアルゴリズムのとおりです。
実行結果
スクリプトでは各世代ごとに、個体集合内の適応度の最大値を出力しています。
Generation loop start. Generation: 0. Best fitness: 64 Generation: 1. Best fitness: 65 Generation: 2. Best fitness: 70 Generation: 3. Best fitness: 68 Generation: 4. Best fitness: 73 Generation: 5. Best fitness: 73 ... ... ... Generation: 34. Best fitness: 98 Generation: 35. Best fitness: 99 Generation: 36. Best fitness: 99 Generation: 37. Best fitness: 100 Generation: 38. Best fitness: 100 Generation: 39. Best fitness: 100 Generation: 40. Best fitness: 100 Generation loop ended. The best individual: [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
37回目のループで最適解が得られています。すごいですね。ちゃんと遺伝子が全部1になってますね。
上記のコードでmain関数内のStep3かStep4をコメントアウトして試してみると分かるのですが、この交叉と突然変異のどちらかが抜けた場合は、最適化の効率が悪くなってしまいます。(選択を抜いてしまうと最適化は全く進みません)
突然変異が重要なファクターになっているのはなんとなくわかりますが、交叉がどういう理由で最適化につながるのか不思議です。
適応度が高い個体同士の遺伝子を入れ替えると、更に適応度が高い個体が生まれる確率が高いということでしょうか?。なんというか。生命の神秘ですね。
ちなみに上述のコードは、Pythonの進化的計算フレームワークであるDEAPのソースコードをかなり参考にしています。
次回はDEAPを使ってGAを実装していきたいと思います。