メインコンテンツまでスキップ

局所探索（山登り法）とは？

概要 (画像は、Geminiで作成されたものです)

局所探索の概要​

局所探索（Local Search）、特にその代表的でシンプルなアルゴリズムである 山登り法（Hill Climbing） は、組み合わせ最適化問題に対する直感的で強力な近似解法の一つです。

配送ルートの最適化（巡回セールスマン問題）や、シフトスケジューリングなど、実社会の課題の多くは「組み合わせ最適化問題」として定式化されます。しかし、これらの問題は要素数が増えると組み合わせの数が爆発的に増加（組み合わせ爆発）するため、すべてのパターンを計算して完璧な正解を見つける「全探索（Exhaustive Search）」では、スーパーコンピュータを使っても宇宙の寿命以上の時間がかかってしまうという大きな課題がありました。

この課題を解決するため、必ずしも「厳密な最適解（大域的最適解）」でなくとも、実用上十分な「良い解」を高速に見つけ出す手法としてヒューリスティクス（近似解法）が発展しました。その基礎となるのが局所探索です。

山登り法は、「現在の解の『すぐ近く（近傍）』を少しだけ探索し、今より良い解があればそちらに移動する」という操作を繰り返す手法です。実装が非常にシンプルでありながら、初期解から高速に解を改善できるというメリットがあります。しかし、「現在の位置から見て上り坂（改善方向）」しか見ないため、小さな山の頂上（局所的最適解：Local Optimum）に到達すると、そこからもっと高い山（大域的最適解）が遠くにあっても探索が止まってしまうという弱点を持っています。この弱点を克服するために、後に「焼きなまし法（Simulated Annealing）」や「タブー探索（Tabu Search）」といった高度なメタヒューリスティクスへと発展していくことになります。

各探索アルゴリズムの比較​

最適化したい評価関数（目的関数）を f(x)f(x) とし、その値を最大化することを目的とします。現在の解 xx に対して、少しだけ変更を加えた解の集合を近傍 N(x)N(x) とします。各探索手法がどのように解を決定するかを見ます。

① 全探索 (Exhaustive Search)​

取りうるすべての解の集合 XX に対して f(x)f(x) を計算し、最大となる x∗x^* を見つけます。

  • 探索方針:
    x∗=arg⁡max⁡x∈Xf(x)x^* = \arg\max_{x \in X} f(x)

確実に最適な解が見つかりますが、解の空間 XX が大きくなると計算量が O(∣X∣)O(\vert{}X\vert{}) となり、現実的な時間で終了しなくなるという致命的な弱点があります。

② ランダム探索 (Random Search)​

解の集合 XX からランダムに複数の解を生成・評価し、これまでに見つかった最大の f(x)f(x) を保持します。

  • 探索方針:
    xbest=arg⁡max⁡{f(x1),f(x2),…,f(xk)}x_{best} = \arg\max \{ f(x_1), f(x_2), \dots, f(x_k) \}

完全に運任せの探索となるため、特定の局所解に捕らわれることはありませんが、膨大な空間の中から「たまたま」良い解を引き当てる確率は低く、探索効率は非常に悪いです。

③ 局所探索 / 山登り法 (Hill Climbing)​

現在の解 xx の近傍 N(x)N(x) の中から最も良い解 x′x' を探し、それが現在の解より良ければ移動します。

  • 探索方針（評価関数の差分）: Δf=f(x′)−f(x)wherex′∈N(x)\Delta f = f(x') - f(x) \quad \text{where} \quad x' \in N(x)

  • 更新条件:
    x←x′ifΔf>0x \leftarrow x' \quad \text{if} \quad \Delta f > 0

現在の状態から「常に良くなる方向」のみへ進みます。近傍 N(x)N(x) 内のすべての解について Δf≤0\Delta f \le 0 となった場合（どこへ移動しても悪くなる場合）、その地点を頂上（局所的最適解）とみなして探索を終了します。過去の履歴を保持する必要がなく、メモリ消費も最小限で済みます。

コードによる挙動の確認​

Pythonのコードを使って、シンプルな1次元関数の最大化問題を例に、それぞれのアルゴリズムがどのように解を探索するのかを見ていきましょう。

今回は、複数の山（局所的最適解）と一番高い山（大域的最適解）を持つ関数 f(x)=sin⁡(x)+cos⁡(0.5x)f(x) = \sin(x) + \cos(0.5x) を最大化する問題を設定します。

import math
import random
import matplotlib.pyplot as plt
import japanize_matplotlib  # グラフの日本語表示用。事前に pip install japanize-matplotlib が必要です

# 評価関数（目的関数）：最大化したい対象の関数
# 複数の山（局所的最適解）と、1つの最も高い山（大域的最適解）を持っています
def f(x):
    return math.sin(x) + math.cos(0.5 * x)

# 探索空間の設定（0.0 から 10.0 の範囲を探索）
x_min, x_max = 0.0, 10.0
step_size = 0.1  # 探索のステップ幅（近傍への移動距離）

print("--- 準備 ---")
print(f"探索範囲: {x_min} から {x_max}")

# --- 可視化のためのデータ生成 ---

# 探索範囲内を step_size 刻みで分割した x の値のリストを作成
x_vals = []
current_x = x_min
while current_x <= x_max:
    x_vals.append(current_x)
    current_x += step_size

# 作成した各 x に対する評価関数 f(x) の値を計算してリストに格納
y_vals = [f(x) for x in x_vals]

# グラフの描画設定
plt.figure(figsize=(10, 6))
plt.plot(x_vals, y_vals, color='#1f77b4', linewidth=2, label='目的関数 f(x)')

# グラフのタイトルと軸ラベルの設定
plt.title("評価関数 f(x) = sin(x) + cos(0.5x) の形状", fontsize=14, fontweight='bold')
plt.xlabel("変数 x", fontsize=12)
plt.ylabel("評価値 f(x)", fontsize=12)

# グリッド（補助線）と凡例を表示
plt.grid(True, linestyle='--', alpha=0.6)
plt.legend()

# グラフを画面に出力
plt.show()

この準備コードでは、最大化の対象となる評価関数 f(x)=sin⁡(x)+cos⁡(0.5x)f(x) = \sin(x) + \cos(0.5x) の定義と、その形状を可視化するための設定を行っています。

まず、目的関数として def f(x) を定義し、探索範囲を x_min（0.0）から x_max（10.0）に設定しています。 可視化の処理では、while ループを使用して step_size（0.1）刻みで xx のリスト（x_vals）を生成し、リスト内包表記を用いて対応する関数の出力値のリスト（y_vals）を計算しています。 最後に、Matplotlibライブラリを用いてグラフを描画しています。グラフ上の日本語が文字化けしないよう、japanize_matplotlib をインポートして描画処理をサポートしている点もポイントです。

実行結果​

--- 準備 ---
探索範囲: 0.0 から 10.0

評価関数

このプロットからわかるように、評価関数 f(x)f(x) には複数の盛り上がり（山）が存在しています。 具体的には、x≈1.7x \approx 1.7 付近に最も高い「大域的最適解（グローバル最適解）」があり、x≈8.3x \approx 8.3 付近にそれよりは低い「局所的最適解（ローカル最適解、あるいは局所解）」が存在します。 ここからは、全探索、ランダム探索、そして山登り法（局所探索）が、この空間をどのように探索していくかを具体的に見ていきます。

以下のコードでは、指定された範囲を細かいステップで全て網羅し、最も高い値を見つけます。

# 最適解を保持する変数。初期値として探索範囲の最小値（x_min）とそのスコアを設定します
best_x = x_min
best_score = f(best_x)

# 探索範囲内（x_min から x_max）を step_size 刻みですべて調べる（全探索）
current_x = x_min
while current_x <= x_max:
    score = f(current_x)
    # これまでに見つかったスコアよりも高い値が見つかれば、最適解を更新
    if score > best_score:
        best_score = score
        best_x = current_x
    # 次の探索地点へ進む
    current_x += step_size
    
print(f"全探索の最適解: x = {best_x:.2f}, スコア = {best_score:.4f}")
print("⭕ 利点: 確実に一番高い山（大域的最適解）を見つけられる。")
print("❌ 課題: 次元が増え空間が広くなると計算が終わらない。\n")

この全探索の実装では、探索空間（0.0 から 10.0）を step_size（0.1）刻みで隈なくスキャンしています。

ループ開始前に、best_x と best_score に初期状態の解を代入しておき、while ループの各ステップで評価関数 f(current_x) を評価します。 もしその時点のスコア（score）がこれまでの最高スコア（best_score）を上回った場合は、best_score と best_x をその地点の値で上書きします。これを探索範囲の上限まで繰り返すことで、確実に最も高い山の頂上（大域的最適解）を見つけ出すことができます。

実行結果​

全探索の最適解: x = 1.70, スコア = 1.6485
⭕ 利点: 確実に一番高い山（大域的最適解）を見つけられる。
❌ 課題: 次元が増え空間が広くなると計算が終わらない。

current_x を 0.0 から 10.0 まで、0.1 刻みで全て計算して評価しています。1次元であれば一瞬で終わりますが、実問題で変数が数千〜数万になると、このループ回数は天文学的な数字になります。

以下のコードでは、ランダムに数点だけピックアップし、その中で最も良いものを選びます。簡易化のため、探索回数を10回に制限しています。

# 乱数のシード値を固定（結果の再現性を保つため）
random.seed(42)

# 初期のランダム探索地点を1点決定し、そのスコアを初期の暫定最適値とします
best_x_rand = random.uniform(x_min, x_max)
best_score_rand = f(best_x_rand)

# ランダムに10回だけ探索（試行回数を10回に制限）
for _ in range(10):
    # 探索空間（x_min から x_max）内から、一様分布に従ってランダムな実数 x を生成
    x_rand = random.uniform(x_min, x_max)
    score = f(x_rand)
    
    # より良いスコアが見つかれば、暫定最適解を更新
    if score > best_score_rand:
        best_score_rand = score
        best_x_rand = x_rand
        
print(f"ランダム探索の最適解: x = {best_x_rand:.2f}, スコア = {best_score_rand:.4f}")
print("⭕ 利点: 局所解に捕らわれず、計算手順もシンプル。")
print("❌ 課題: 全く見当違いの場所を探すことが多く、精度が著しく低い。\n")

このランダム探索の実装では、探索空間全体からランダムにサンプリングして評価を行っています。

まず、再現性を確保するために random.seed(42) で乱数シードを固定します。 そして、random.uniform(x_min, x_max) を用いて範囲内から一様にランダムな実数 xx を生成し、初期解を設定します。 その後、for ループを使用して10回ランダムに xx をサンプリング（x_rand）し、その都度評価関数を計算しています。 全探索とは異なり、評価回数をあらかじめ決めた回数（今回は10回）に制限できるため計算量は抑えられますが、完全に運任せの探索となるため精度は保証されません。

実行結果​

ランダム探索の最適解: x = 2.50, スコア = 0.9135
⭕ 利点: 局所解に捕らわれず、計算手順もシンプル。
❌ 課題: 全く見当違いの場所を探すことが多く、精度が著しく低い。

random.uniform を用いて無作為に選んだ座標を評価しています。大域的最適解である 1.701.70 とは離れた場所しか探索できておらず、スコアも低いままとなっています。このように、限られた試行回数の中では、ランダム探索のみで高い精度の解を見つけ出すのは非常に困難です。

局所探索 / 山登り法 (Hill Climbing)​

以下のコードでは、適当な初期位置からスタートし、左右（近傍）を見て高い方へ移動し続ける山登り法を実装します。

初期値が3.0の場合​

# 初期解（スタート地点を 3.0 に設定）
current_x_hc = 3.0

while True:
    # 近傍の生成：現在の位置から左右にステップ幅（step_size = 0.1）だけ移動した2つの候補点
    neighbors = [current_x_hc - step_size, current_x_hc + step_size]
    
    # 探索空間の範囲内（x_min から x_max）に収まっている候補点のみにフィルタリング
    valid_neighbors = [nx for nx in neighbors if x_min <= nx <= x_max]
    
    # 暫定の最良候補を現在の位置に設定
    best_neighbor = current_x_hc
    best_neighbor_score = f(current_x_hc)
    
    # 有効な近傍候補点を順番に評価
    for nx in valid_neighbors:
        score = f(nx)
        # 現在保持している最高スコアよりも高い値を持つ近傍があれば更新
        if score > best_neighbor_score:
            best_neighbor_score = score
            best_neighbor = nx
            
    # 近傍のどれを探索しても改善しない（頂上、すなわち局所最適解に達した）場合は終了
    if best_neighbor_score <= f(current_x_hc):
        break
        
    # 現在地を最も高かった近傍（best_neighbor）に更新し、探索を繰り返す
    current_x_hc = best_neighbor

print(f"山登り法の解: x = {current_x_hc:.2f}, スコア = {f(current_x_hc):.4f}")
print("⭕ 利点: 高速に解を改善できる。")

この山登り法の実装では、「現在地から最も評価が良くなる方向（上り坂）に一歩ずつ進む」という貪欲な探索プロセスを実現しています。

無限ループ while True の中で、現在の解 current_x_hc の両隣の2点（current_x_hc - step_size, current_x_hc + step_size）を近傍候補（neighbors）として生成します。 次に、リスト内包表記を用いて、これらの候補点が探索空間 x_min と x_max の範囲内に収まっているかをチェックしています（valid_neighbors）。 そして、for ループを用いて近傍候補の中で最もスコアが高い地点（best_neighbor）を特定します。もし、この最良候補のスコアが現在地のスコア以下（best_neighbor_score <= f(current_x_hc)）であれば、「周囲を見渡しても今より高い場所はない」と判断して break により探索を終了します。改善できる場合は、現在地を更新して探索を継続します。

実行結果​

山登り法の解: x = 1.30, スコア = 1.7596
⭕ 利点: 高速に解を改善できる。

初期解を 3.03.0 とした場合、山登り法は x=1.30x = 1.30、スコア 1.75961.7596 に到達しました。 これは全探索で見つけた 1.701.70（スコア 1.64851.6485）に極めて近い、大域的最適解付近の山の頂上を、ごく少数のステップ数で高速に発見できていることを意味します。 このように、初期解が良い位置にあれば、山登り法は非常に強力で効率的なアルゴリズムとして機能します。

初期値が8.0の場合​

# 初期解（少し意地悪なスタート地点として 8.0 に設定）
current_x_hc = 8.0 

while True:
    # 近傍の生成：現在の位置から左右にステップ幅だけ移動した2つの候補点
    neighbors = [current_x_hc - step_size, current_x_hc + step_size]
    
    # 探索空間の範囲内に収まっている候補点のみにフィルタリング
    valid_neighbors = [nx for nx in neighbors if x_min <= nx <= x_max]
    
    # 暫定の最良候補を現在の位置に設定
    best_neighbor = current_x_hc
    best_neighbor_score = f(current_x_hc)
    
    # 有効な近傍候補点を順番に評価
    for nx in valid_neighbors:
        score = f(nx)
        # より良いスコアが見つかれば最良近傍候補を更新
        if score > best_neighbor_score:
            best_neighbor_score = score
            best_neighbor = nx
            
    # 近傍のどれを探索しても改善しない場合は終了
    if best_neighbor_score <= f(current_x_hc):
        break
        
    # 現在地を最良近傍に更新
    current_x_hc = best_neighbor

print(f"山登り法の解: x = {current_x_hc:.2f}, スコア = {f(current_x_hc):.4f}")
print("❌ 課題: スタート地点によっては小さな山の頂上で止まってしまう。")

この実装のロジックは初期解が 3.03.0 の場合と全く同じですが、初期解 current_x_hc を 8.08.0 に変更して実行しています。

初期解（スタート地点）が異なるだけで、アルゴリズムがどのように異なる「頂上」に収束してしまうか、その挙動の違いを確認するための検証コードです。

実行結果​

山登り法の解: x = 8.30, スコア = 0.3690
❌ 課題: スタート地点によっては小さな山の頂上で止まってしまう。

neighbors = [current_x_hc - step_size, current_x_hc + step_size] によって、現在の位置のすぐ両隣だけを評価します。もし隣の方が値が高ければ、current_x_hc = best_neighbor で位置を更新します。しかし結果を見ると、大域的最適解である 1.701.70 ではなく、8.308.30 という中途半端な解（局所的最適解）で探索が止まってしまっています。これが、山登り法における「局所解の罠」と呼ばれる決定的な弱点です。

探索軌跡の可視化と局所解の罠​

上記の山登り法が、どのように「局所的最適解」に陥ってしまうのかをグラフで確認します。

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib

# NumPy用の評価関数の定義（ベクトル演算に対応させるため）
def f_np(x):
    return np.sin(x) + np.cos(0.5 * x)

# 1. 関数の全体形状を描画するためのデータを生成
# 0.0 から 10.0 の間を均等に 200 分割した配列を作成
x_vals = np.linspace(0, 10, 200)
y_vals = f_np(x_vals)

# 2. 初期位置と山登り法のシミュレーション（軌跡を記録）
start_x = 8.0
path_x = [start_x]  # 探索した x 座標の履歴を保存するリスト
current_x = start_x
step = 0.1

while True:
    neighbors = [current_x - step, current_x + step]
    best_n = current_x
    best_score = f_np(current_x)
    
    # 左右の近傍を評価してより高い方を探す
    for nx in neighbors:
        if 0 <= nx <= 10 and f_np(nx) > best_score:
            best_score = f_np(nx)
            best_n = nx
            
    # 改善がなければ終了
    if best_score <= f_np(current_x):
        break
        
    current_x = best_n
    path_x.append(current_x)

# 探索軌跡の f(x) の値を算出
path_y = [f_np(x) for x in path_x]

# 3. グラフの描画
plt.figure(figsize=(10, 6))
# 元の評価関数の曲線を青線でプロット
plt.plot(x_vals, y_vals, color='#1f77b4', linewidth=2, label='目的関数 f(x)')
# 山登り法の探索の軌跡を赤丸と点線でプロット
plt.plot(path_x, path_y, marker='o', color='red', markersize=5, linestyle='--', label='山登り法の軌跡')

# グラフ上に「スタート地点」「局所的最適解」「大域的最適解」の注釈を矢印付きで追加
plt.annotate('スタート地点', xy=(path_x[0], path_y[0]), xytext=(7.5, 0.5),
             arrowprops=dict(facecolor='black', shrink=0.05, width=1, headwidth=6))
plt.annotate('局所的最適解で\n探索がストップ', xy=(path_x[-1], path_y[-1]), xytext=(5.5, 1.2),
             arrowprops=dict(facecolor='black', shrink=0.05, width=1, headwidth=6))
plt.annotate('本当の最高地点\n（大域的最適解）', xy=(1.7, f_np(1.7)), xytext=(2.2, 0.5),
             arrowprops=dict(facecolor='red', shrink=0.05, width=1, headwidth=6))

# タイトル、軸ラベル、凡例、グリッドを設定
plt.title("山登り法の探索プロセスと局所解への収束", fontsize=14, fontweight='bold')
plt.xlabel("変数 x", fontsize=12)
plt.ylabel("評価値 f(x)", fontsize=12)
plt.legend()
plt.grid(True, linestyle='--', alpha=0.6)
plt.show()

この可視化コードでは、実際に山登り法が探索を進める軌跡（パス）を算出し、評価関数の形状の上に重ねてプロットしています。

まず、NumPy の np.linspace(0, 10, 200) を使用して評価関数の高解像度なプロット用データを生成します。 次に、初期位置 start_x = 8.0 から山登り法を開始し、探索した xx 座標の遷移をリスト path_x に順次追加（append）して軌跡を記憶させています。 探索終了後、記憶した各座標に対する関数値 path_y を計算し、Matplotlib の plt.plot で赤色の点線として描画しています。 また、探索プロセスの理解を助けるために、plt.annotate を用いて「スタート地点」や「局所的最適解」、「大域的最適解」などの各重要ポイントに説明文と矢印（arrowprops）を追加しているのも特徴です。

探索軌跡

このコードブロックでは、山登り法の最大の特徴であり弱点でもある「局所的最適解（Local Optima）への収束」をシミュレーションし、グラフ化しています。上記コードを実行すると、次のようなグラフが描画されます。

軌跡グラフからわかる山登り法の限界​

  • 近傍探索による着実な改善: 赤い点線が山登り法の軌跡です。スタート地点（x=8.0x=8.0）から始まり、関数が大きくなる方向（上り坂）に向かって一歩ずつ着実に進んでいることがわかります。
  • 局所的最適解（Local Optima）の罠: 探索は小さな山の頂上（x≈8.3x \approx 8.3 付近）に到達するとストップしてしまいます。なぜなら、その頂上から見て「右に行っても左に行っても値が下がる（Δf≤0\Delta f \le 0）」ため、アルゴリズムは「ここが最も高い場所だ」と判断してしまうからです。
  • 大域的最適解への未到達: グラフ全体を見ると、x≈1.7x \approx 1.7 付近により高い山（大域的最適解）が存在することがわかります。しかし、山登り法は「一時的に谷を下る（一時的にスコアの悪化を許容する）」ことができないため、この本当の最高地点にたどり着くことができません。

まとめ​

本記事では、組み合わせ最適化アルゴリズムの基礎となる局所探索（山登り法）について、その理論的背景から具体的な挙動までを解説しました。

本記事では、以下の点について解説しました。

  • 山登り法のコアコンセプトの理解: 全探索やランダム探索と比較して、「近くのより良い解へ移動し続ける」というシンプルかつ高速なアイデアを学びました。

  • Pythonによる挙動の比較検証: 各探索アルゴリズムをコードでシミュレートし、山登り法が確実にスコアを改善できる一方で、初期位置に依存するという特性を確認しました。

  • 探索プロセスと局所解の可視化: グラフを通じて、上り坂のみを進む性質ゆえに、「小さな山の頂上」で探索が終了してしまうという最大の課題を直感的に理解しました。

山登り法は、実装が容易でありながら強力なベースラインとなるアルゴリズムです。実社会の複雑な問題では局所解に陥るリスクが高いため、この「谷を下れない」弱点を克服するために、一時的な改悪を許容する焼きなまし法（Simulated Annealing） や、過去の探索履歴を記憶するタブー探索（Tabu Search） といった発展的な手法が考案されています。まずはこの山登り法のメカニズムをしっかり理解することが、高度な最適化手法を学ぶための第一歩となります。

本記事の文章・構成の一部に生成AIを使用しています。