[研究レポート] 局所探索レーダー

[研究レポート] 局所探索レーダー

局所探索レーダー

 局所探索レーダー (LSR : Local Search Radar) は拡散式パワーレーダーの機能を拡張したレーダーで、勾配降下法を使わずに単独で最小値を見つけ出すアルゴリズムです。

局所探索レーダーの仕組み

 局所探索レーダー はランダムに選んだ複数地点の高度を同時測定し、その中から最も低い地点の 1.0 × 1.0 四方をメッシュして各格子点の高度を測ります。

Python エリアレーダーの仕組み

 最小値を「点」ではなく「面」で探そうというコンセプトで設計しました。
 以下に局所探索レーダーの機能を関数にまとめておきます。

# https://python.atelierkobato.com/area/
# リストR6-A-1 Local Search Radar

import numpy as np

# ランダム平面格子生成関数
def r_mesh(xr, yr, n):
    x = np.random.uniform(xr[0], xr[1], (n, n))
    y = np.random.uniform(yr[0], yr[1], (n, n))
    X, Y = np.array([x, y])
    return X, Y

# 局所探索レーダー
def area_search(xr, yr, n, tmax, pt, func):
    zt = func(pt[0], pt[1])
    for t in range(tmax):
        Xs, Ys = r_mesh(xr, yr, n)
        Zs = func(Xs, Ys)
        Zs_min = np.min(Zs)

        if zt > Zs_min:
            Xs_min = Xs[Zs == Zs_min][0]
            Ys_min = Ys[Zs == Zs_min][0]
            pt = [Xs_min, Ys_min]
            zt = func(pt[0], pt[1])

        xr2 = [pt[0] - 0.5, pt[0] + 0.5]
        yr2 = [pt[1] - 0.5, pt[1] + 0.5]
        Xs2, Ys2 = r_mesh(xr2, yr2, 129)
        Zs2 = func(Xs2, Ys2)
        Zs2_min = np.min(Zs2)
        
        if zt > Zs2_min:
            Xs_min = Xs2[Zs2 == Zs2_min][0]
            Ys_min = Ys2[Zs2 == Zs2_min][0]
            pt = [Xs_min, Ys_min]
            zt = func(pt[0], pt[1])

    return pt, zt

 

局所探索レーダーによる最小値の探索

 局所探索レーダーは、学習率を 0.01 ぐらいに設定した拡散式パワーレーダー付勾配降下法よりも高速です。たとえば、前回記事で扱った関数
 
\[z=\cos x\sin(\sqrt{2}y)+\frac{1}{24}\sin(\sqrt{3}xy)\]
であれば、10 ループもあれば最小値を探し当てます(処理時間は 30 ms ほどです)。

# https://python.atelierkobato.com/area/
# リストR6-A-2  Local Search Radar

np.random.seed(0)

# テスト関数を定義
def func(x, y):
    sin = np.sin
    cos = np.cos
    sqrt = np.sqrt
    z = cos(x) * sin(sqrt(2)*y) + sin(sqrt(3)*x*y/24)
    return z

# 初期地点を設定
pt = [8, 4]

# 初期地点の高度
zt = func(pt[0], pt[1])

# ループの最大数と最小数
t_max = 10

# 探索範囲を設定
xr = [0, 16]
yr = [0, 8]

# 局所探索レーダーによる最小値の探索
s = area_search(xr, yr, 16, t_max, pt, func)

pt = np.round(s[0], 3)
zt = np.round(s[1], 3)

print("(x, y, z) = ({0:.3f}, {1:.3f}, {2:.3f})".format(pt[0], pt[1], zt))
(x, y, z) = (9.698, 5.782, -1.700)

 さらに、このレーダーの威力を試すために、

pt = [5000, 5000]
t_max = 100
xr = [0, 10000]
yr = [0, 10000]

のように設定し直して実行してみてください。約 0.2 秒で最小値

(x, y, z) = (1002.176, 996.328, -2.000)

を見つけるはずです。