「機械学習と深層学習」をやってみる(5. 進化的手法)

「機械学習と深層学習」の続きをやる。今回は3.2章の進化的手法、いわゆる遺伝的アルゴリズムというものだ。

機械学習と深層学習 ―C言語によるシミュレーション―

遺伝的アルゴリズムは、学生の時に初めて勉強した学習アルゴリズムなのでよく知っている。遺伝的アルゴリズムは、以下の3つの要素を組み合わせて、染色体群を最適化していく手法となる。

• 交叉(crossover) : 2つの染色体を組み合わせて子供の染色体を作り出す。交差の方法によっていくつか種類がある。
• 突然変異(mutation) : 染色体の情報をランダムに書き換える。例えば、ビット列を反転させる(flip bit)などの方法があり得る。
• 選択(selection) : 染色体の評価値に基づいて染色体を選り分ける。これにより、新しい世代の染色体を選別する。ただし局所解に入らないために、ε-greedy方などの確率的な方式を導入する必要がある。

この遺伝的アルゴリズムを使って、ナップサック問題を解いてみるというのが今回の課題だ。 荷物は30種類あり、その中で最も評価値の高くなる荷物を選択してナップサックに入れる。これを遺伝的アルゴリズムにより最適解を探していく。

まず、各荷物について、ナップサックに入れる場合を1、入れない場合を0として配列を作り出す。この配列を複数(今回は30個)用意し、これらを染色体とする。 この染色体に対して上記の遺伝的操作を繰り返し、進化させていくという具合だ。

github.com

これにより染色体の最適値は、世代に応じて以下のように変化していく。

総当たりの方式に対して、短時間で最適解の9割程度の評価解を得ることができる。このあたりが遺伝的アルゴリズムの特徴だ。 この結果、本書では遺伝的アルゴリズムは、「まずまずの評価」を「素早く」導くことができる手法と結論付けている。