最適化

以前勉強した事を自分の中でどれ位腹落ちしているか把握するために少し書いてみます。

早速ですが、少し話をプログラミングから変えます。

最適化が一番重要視される学問と言えば、僕の知っている限り工学系の分野だと思います。

自然などを相手に理論武装しながらスマートにアプローチをしていく理学とは違い、工学はどちらかというと人間臭く、愚直に良い答えを見つけ出していくようなイメージを最近持ってきました。

例えていうなら高次方程式の最小解を理学ならば微分したりして求めていくのに対し、工学では適当に何千回も繰り返して、その中で最小解を見つけるのです。もちろん工学の場合は適当な解を求めているので、厳密には最適解ではありません。ですが、ある程度の良い解は得られるようになっているのです。そんな考え方がとても自分に合っているので工学的アプローチの方が好きです。（ただ単に数学が嫌いというのは秘密です）

その工学の中で一番重要となってくる最適化にも色々な方法があります。

例えば上に記したランダムサンプリング法。
ある関数の最小解を知りたいときに、「まぁまず１０００個ほど解もとめて、その解の中から良いの選ぼう」ってやつですね。とても簡単です。しかしかなり適当な分、そこまで良い精度は得られないのが現実です。

次に説明したいのが模擬アニーリング法。
これはもともと鉄鋼の分野で得られた考え方で、一言で言うと「鉄は熱いうちに打て」だと思います。
まずは以下の図のようなアップダウンが何回も繰り返される関数を考えてみてください。

この関数の最小解を見つけるために、まずはランダムにスタート地点を決めます。
スタート地点を緑色の点にしたとします。
次に、左右に少しだけ移動する時に値が最適解に近づくかどうかを考えます。そしてより最適解に近づく方を新しい解として迎え入れます。
しかし、今よりも悪い解になってしまう場合でも一定の確率で受け入れてしまおうという大局観を持ったアルゴリズムがこの模擬アニーリング法なのです。
その理由は図を見てもらうと分かると思いますが、緑の地点で局所的最小解は得られますが、そこから大局的最小解を得るにはいったん値を増やして坂を昇らなければいけません。
もちろん、悪い方に進む場合の確率も常に1/2ではなく、解が最適になればなるほど悪い方にいける確率は下がってしまいます。「悪さをするなら20代までに」ってことですね。

最後にもう一つ説明したいのが、遺伝的アルゴリズムです。
これは人間の進化過程をもとに考え出された手法です。初期の解はランダムサンプリング法と同じで、一定数の解をランダムに定めます。そしてこれらのサンプルを以下の２つの方法で進化させます。①と②がどの位の頻度で起こるかは、場合によって変えるべきでしょう。

①交配
得られた解の中で優れた解（エリート）を抽出して、エリート同士で交配させるのです。そうすると、更なるエリートが生まれる確率は、エリートでないもの同士を交配させるよりも圧倒的に高いでしょう。
例としては６変数を説明変数として持つ目的関数があったとします。その最適解の上位２つが(2,4,3,6,7,1)と(3,2,7,9,2,4)だったとしましょう。交配させるということは、これらをランダムに混ぜるということなので、子供は(2,4,3,9,2,4)となったり(2,2,7,9,2,4)となったりします。

②突然変異
これは交配とは違い、ひとつの解で自己完結型で行われるメソッドです。上記のような６変数の値の内、一つがランダムに適当な値に変わるというものです。

ここで紹介した最適化手法以外にも、無数の手法があります。ぜひ他の手法も探してみてください。
ちなみに具体的なアルゴリズムなどはあえて、紹介しませんでした。もちろんコードなりを読んだほうが理解できる人はその方が分かりやすいのですが、そうでない人にも最適化手法について知って欲しかったのでそうしました。

次のエントリーでは、これらの手法をpythonというプログラミング言語を使って実際のデータなどに対して最適化手法を行ってみたいと思います。