シミュレーティッドアニーリング

最近は疲れているせいか、平日は仕事以外の思考が停止している。
考えるとなると仕事のことになるので、結局のところ思考が止まる。
まあ、そんなもんだ。
そんなわけで、どうでもいいことを書いておこう。

---

思考といえば、シミュレーション。
組込み現場でも、シミュレーションは大切だ。
実装して動かさないとわからない、というものはある。
あるのだけど、理論的なことは動かす前に推測できなくてはならない。
まあ、だいたい出てくるのはMATLABなのだけど、大御所だけに個人ではちょっと買えない。
個人でなくても、小規模ではちょっと無理だ。
んで、SciLabってのがあったので、動かしているところ。
正直なところ、この分野はよくわからないけど、こういうのがちゃちゃっと動かせると格好がいいではないか。
まあ、動かせるようになれるかどうかわからないけど、もう少しやってみよう。

---

シミュレーションといえば、思い出すのは「シミュレーティッドアニーリング」。
日本語では「焼き鈍し法」って呼ばれてるんじゃなかったっけ。
といっても、私は内容をよく知らない。すまん。
なんでこの言葉を知っているかというと、学校での研究課題が「遺伝的アルゴリズム」だったからだ。
すごそうな名前だけど、私が知っているやり方はすごく適当。

求めたい値があるけれども、それを得るためのパラメータがたくさんある、という状況を考えてほしい。
数学っぽくいえば、多項式、というのかな。
式と解はあるけど、パラメータが多くてよくわからん、という状況。
正直にプログラムで求めようとすると、for文をそれぞれのパラメータ範囲で行った多重for文ができあがる。
3つパラメータがあって、それぞれ100パターンあるなら、100のループが3つで100万ループだ。
それくらいならまだ現実的だけど、これが16bit値だったり32bit値だったりすると、もういつ終わるかわからん。
なので、この手の解を求めるやり方がいくつかある。
あっさりいえば、「このくらい解に近いんだから、もう解としてしまおう」というような考え方だ。
正解よりも、現実的な解を求めるというやり方だ。
この方法の難しいところは「どこら辺が解としてしまっていい範囲なのか」だろう。
例えば、0となる解が、ある変数の組み合わせで0.00000001となったとしよう。
この値が果たして正統なのか、これよりももっと最適な変数値の組み合わせがあるかどうか、その組み合わせが見つかるかどうかを判定するまでの時間をどのくらいまで許容するか・・・などなど。
これの面白いところは、精度が時代によって変わってくるということだ。
マシンスペックや、計算に要していい時間などの要因がおおきいということ。
例えば先ほどの100万ループ。
もし1ループ1秒かかるなら100万秒、11.5日くらいだ。
でも1ループ1マイクロ秒なら、1秒で終わってしまう。
実際のところ、このくらいのペースで処理速度が向上していっているので、かなりの部分は力業で全パターン計算してしまえばいいような気がする。

とはいっても、今の時点で得られるマシンスペックで最適な解を得なくては意味がない。
そこで生まれた(と私は思っている)のが、遺伝的アルゴリズムだ。

---

いっておかねばならないが、私は遺伝的アルゴリズム(Genetic Algorithm、以下GA)の権威でもなんでもなく、「私はGAをこんなのだと思ってやってました」という話だから、ちゃんとした人に確認した方がいい。

まず、遺伝子の形を決める。
これは、構造体になってしまうけれども、イメージとしては単なるバイトデータ列だ。
何が入っているかというと、計算に使うパラメータたち。
遺伝子１つに対して、解が１つあると思ってもらえばよいかな。

これを、複数個作成する。
できるだけ数多くだ。
この数は固定とし、最後まで数は維持する。
つまり、解がたくさんある状況。

評価関数があるので、解を突っ込むと、理論値とどれだけ離れているのかという値が求まる。
もちろん、距離が近い方がよい遺伝子となる。

最初は、遺伝子をランダムで作成する。
評価がいいも悪いも気にせず、とにかく決めた数だけ作成する。
んで、評価が一番いいものは上位からいくつか残して、残りを交配させる。
「交配」っていうとものものしいが、ランダムにバイトデータの位置を決め、そこから下を交換するだけ。
構造体のデータ構造などまったく気にせず、データ長からランダムで決めるだけだ。
そして再度評価して、評価の順序を決めて、また交配していく。
これを繰り返していくと、評価がいいものが結構早く求まるのだ。
遺伝子が凝り固まらないよう、ときどきビット単位で「突然変異」を起こすなどして、遺伝子がなるべく流動的になるよう取りはからったりもする。

---

私がこれを学んだ際、「シミュレーティッドアニーリングでは近似解に落ち込むことがある」と習った。
どういうことかというと、終了条件だ。
細かいことは忘れたが、シミュレーティッドアニーリングもGAも、近似解を求める方法である。
だから、どこで計算をやめるか、という判断が必要になる。
シミュレーティッドアニーリングの場合、徐々に解に近づいていくため、「解の谷」にはまってしまうと、それ以上良い解に行く前に計算を終えてしまうのだ。
あまりうまく説明できないが、解が0のときに+0.001の解が出てしまうと、本当は+0.000001の解があっても計算を終えてしまうという話だ。
まあ、近似解で終わらせるんだから仕方ないんだけどね。

GAの場合、解への近づき方が線形的ではない。
適当な位置でパラメータをよくわからないまま入れ替えているので、ランダムなのだ。
ただ、ある程度の良質な遺伝子が残っていくので、自然と解へ近くなっていく。
線形ではないので、突然解に近寄ったりしていくので「解の谷」にはまりにくい。

---

そんなのをやってたのだ。
解を求めるためにランダム値を用いるというのは、けっこう抵抗があるものだったんだけど、しばらくやっていると感覚的に受け入れられるようになっていた。
不思議なものである。

これが今の仕事に役立っているかというと、直接にはないな。
でも、考えの柔軟さの幅は広がったと思う。
精密な計算のためにランダムを取り入れる、という考え方だ。
矛盾しているようなところがおもしろい。