局所探索と近傍｜数理最適化

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：局所最適と大域最適・凸性の役割・計算複雑性とNP困難の地図　|　関連：焼きなまし法

要点（BLUF）

局所探索は 「今の解の近傍を見て、良くなる方へ動く」 を繰り返す最も素朴な探索。
近傍の定義（どこを「隣」とみなすか）が解法の質を決める。
山登りは 局所最適で必ず止まる。非凸（局所最適と大域最適・凸性の役割）では初期点依存で、大域最適を逃す。脱出の工夫が次節以降。

概念 ── 近傍と改善移動

メタヒューリスティクスの土台は 局所探索（local search）。現在の解 $x$ の近傍 $N(x)$ （少し変えた解の集合）を調べ、より良い解へ移る。

連続なら「少し動かした点」、組合せなら「1要素を入れ替えた解」「2都市を交換した巡回路（2-opt）」などが近傍。
山登り法（hill climbing）：近傍に改善解があれば移動、なければ停止。
- 最急上昇：近傍で最良の解へ。最初の改善：最初に見つけた改善解へ。

graph TD
  A["初期解 x"] --> B["近傍 N(x) を調べる"]
  B --> C{"改善する隣がある?"}
  C -->|"ある"| D["その隣へ移動"]
  D --> B
  C -->|"ない"| E["局所最適 = 停止"]

局所最適の罠

山登りは「下る隣が無くなった」ら止まる ── それが 局所最適であって大域最適とは限らない。非凸関数（局所最適と大域最適・凸性の役割）には谷が複数あり、どの谷に落ちるかは 初期解で決まる。これが局所探索の根本的な限界で、メタヒューリスティクス全体の出発点（この罠をどう抜けるか）になる。

Pythonで罠を可視化

多峰関数 $f(x)=0.1x^2 + 2\sin x$ （グリッド上）。山登りを3つの初期点から走らせると、別々の局所最適に捕まる。

import numpy as np

xs = np.linspace(-15, 15, 601)        # 解の候補(グリッド)
def f(x): return 0.1*x**2 + 2*np.sin(x)
fvals = f(xs)

def hill_climb(start_idx):
    i = start_idx
    while True:
        best = i
        for j in (i-1, i+1):           # 近傍 = グリッド上の左右の点
            if 0 <= j < len(xs) and fvals[j] < fvals[best]:
                best = j
        if best == i:                  # 改善する隣が無い -> 局所最適
            return i
        i = best                       # 良くなる方へ移動

print(f"参照(全探索)最小: x={xs[np.argmin(fvals)]:.3f}, f={fvals.min():.4f}")
for s in [60, 300, 540]:               # 異なる初期点
    r = hill_climb(s)
    print(f"初期 x={xs[s]:+.1f} -> 収束 x={xs[r]:+.3f}, f={fvals[r]:.4f}")

実行結果：

参照(全探索)最小: x=-1.450, f=-1.7752
初期 x=-12.0 -> 収束 x=-7.050, f=3.5826
初期 x=+0.0 -> 収束 x=-1.450, f=-1.7752
初期 x=+12.0 -> 収束 x=+9.700, f=8.8655

初期点 $0$ から始めると運良く大域最適 $x=-1.45$ （ $f=-1.78$ ）に着くが、 $-12$ からだと局所最適 $-7.05$ （ $f=3.58$ ）、 $+12$ からだと別の局所最適 $9.7$ （ $f=8.87$ ）に捕まる。山登りは「足元の谷」しか見ない。この弱点を、確率（焼きなまし法）・記憶（タブー探索）・集団（遺伝的アルゴリズム）で補うのがメタヒューリスティクス。

数式の直観的意味

局所探索の本質は「目的関数の地形を、近傍という局所情報だけで降りる」こと。これは勾配法（無制約最適化）の離散版で、勾配が使えない組合せ問題でも適用できるのが強み。だが局所情報しか使わない以上、視界の外の深い谷は見えない ── 凸（凸集合と凸関数）なら谷が1つなので局所探索で大域最適に届くが、非凸では届かない。脱出戦略はすべて「一時的に悪化を許す（確率・記憶）」か「複数地点から探す（集団）」のどちらかに分類できる。近傍の設計（広すぎると遅い、狭すぎると罠が多い）が、探索の効率と質のトレードオフを支配する。

⚠️ よくある誤解・落とし穴

山登り＝大域最適ではない。停止＝局所最適。非凸では初期点依存。
近傍の設計が命：狭い近傍は局所最適が増え、広い近傍は1反復が重い。問題構造に合わせる。
**多スタート（random restart）**は最も簡単な改善：複数初期点で山登りし最良を採る。だが保証は無い。
「改善が無い＝最適」ではなく「改善が無い＝近傍内に改善が無い」。近傍を変えれば動けることも。