曲がった迷路その22 - 最小値探索と迷路完成の判断

前回までである区間の中に単峰的に最小値があることがわかっている場合には、その最小値の位置ははさみうち法なり黄金分割法なりで求めればいい。では最小値が含まれている区間を求めるのはどうするのか。一般的には非常に難しい。その中で単峰性を保証するのはさらに難しい。

おおまかな探索

最小値の探索は、極小値が求まるだけで大域的な最小値を求めるのは結構難しい。効率よくやるにはシミュレーテドアニーリングのような方法をとる必要がある。どんなアルゴリズムを使うにしても大域的な最適化は定義域をある程度、絨毯爆撃的に探索する必要があって、可能性の低そうなところの探索をいかに減らすか、でアルゴリズムの効率が決まると言っていい。

しかし今回のような場合

• ポテンシャルの山谷の大きさ（スペックルパターンの粒度）は決まっている
• 壁の長さも山谷の大きさと同程度
• 所詮お遊びであり、最小値を保証する必要はない

という特徴を持っているのでかなり簡単化できる。

山谷の大きさがだいたいLぐらいだとすると、半径Lの円周上には山が2個谷が2個ていどになる。
そうすると、まず円周上で4点（例えば東西南北）の値を見てその4つの中での最小値は実際の最小値に近いはずである。従ってそこからさらに低い場所を探せば最小値にたどり着ける可能性が高いのでそこから黄金分割法で最小値を求めよう。ようするに絨毯爆撃を4点だけで終わらそうと言うものである。

この方法の場合、もちろん極小値しか求まらない可能性もあるが、今回の場合許すことにする。これによって探索の開始点が決まったとする。

アルゴリズムをまとめると

1. 壁の固定端を決める。これは既存の壁のどちらかの端をランダムに取り出すことになる
2. 壁の長さを決める。レイリー分布に従った乱数を発生させる
3. 固定端からその長さの円周上の4点のポテンシャル値を調べ、最も小さいものを取り出す
4. そこから円周上の最もポテンシャルの低い場所をはさみうち法で探す
   はさみうちのもう一方は残り3点の中から微係数で選ぶ
5. そこのポテンシャル値が閾値より低ければ壁の解放端をそこに決める
6. ポテンシャルに衝突回避のポテンシャルを足す
7. もし、ポテンシャル値が閾値より高ければ全部をキャンセルして最初に戻る

となる。

迷路完成の判断

新しい壁を作れるようなポテンシャルの低いところがなくなればそれで終わりだけど、低いところがなくなったかどうかを調べるのはなかなか難しい。結局ポテンシャルを全部見なければいけない。

どんどん壁を作っていくと、ポテンシャルが高くなって新しい壁を作ろうとしても失敗が多くなる。例えば閾値より低いポテンシャルの場所が一カ所しか無くて、それまでに壁をK個作っていたとしたら、新しい壁を作る可能性のあるところはK箇所あって実際に作れるところは1カ所だけとなってK回失敗する、いやもっと多いか、とにかく最後の1カ所を引き当てるのはかなりの回数失敗した後になる。こういうのどうやって計算するんだっけ？

1からKまでの整数のうちランダムにひとつ取るということをしてK回連続で1以外を引く確率は((K-1)/K)^Kだから1/eに収束するのか。2K回連続で1以外を引く確率は1/e²に収束するので、壁の数の2倍試してもうまくいかない確率は、壁の数が増えると10%以上あることになる。

これは非常に効率が悪い。

適当なところでけりをつけるなり、ポテンシャルの低いところが少なくなってきたら、新しい壁を作るのはランダムではなく、その周辺で探すようにする、とかの工夫が必要である。

さて、こういうのはどうするか。