数式とPython実装から理解する局所探索法

局所探索法とは何か

局所探索法は、最適化問題を解くための手法の一つで、特に大規模な問題や複雑な問題に対して効果的です。大まかに言うと、「現在の解の近く（局所）にあるより良い解を探しながら、最適解に近づいていく」方法です。初心者にもわかりやすく言えば、「少しずつ解を改善していく試行錯誤の過程」と言えます。

例えば、ある評価関数 \( f(x) \) を最小化したいとします。局所探索法では、現在の解を \( x \) とし、周辺の解（近傍解）を考えます。近傍解 \( x’ \) が今の解よりも評価関数の値が良ければ（例えば、\( f(x’) < f(x) \) なら）、その解に移動します。この操作を繰り返し、改善が見られなくなるまで続けます。

数式で表すと、局所探索法の基本的な更新ルールは以下のようになります。

ここで、\( x_t \) はステップ \( t \) の解、\( x’ \) はその近傍解の一つです。評価関数 \( f \) の値が改善されれば新しい解に移動し、そうでなければ現在の解を維持します。

局所探索法はシンプルですが、局所最適解に陥りやすいという欠点があります。つまり、少し改善できる範囲では最善の解でも、全体で見た最適解とは異なることがあります。それでも、多くの現実問題で十分な解を高速に求められるため、よく使われる手法です。

以下にPythonでの簡単な局所探索法の例を示します。ここでは、1次元の関数 \( f(x) = (x-3)^2 \) の最小値を探します。初期解から少しずつ近くの値に移動し、評価関数が改善する方向に更新しています。

import numpy as np

def f(x):
    return (x - 3) ** 2

def local_search(x_start, step=0.1, max_iter=100):
    x_current = x_start
    for _ in range(max_iter):
        neighbors = [x_current - step, x_current + step]
        neighbors_values = [f(n) for n in neighbors]
        min_value = min(neighbors_values)
        if min_value < f(x_current):
            x_current = neighbors[neighbors_values.index(min_value)]
        else:
            break
    return x_current

result = local_search(x_start=0.0)
print(f"最適解の近似値: {result:.4f}, 評価関数の値: {f(result):.4f}")

このコードでは、現在の解の近傍として小さなステップ幅の左右を調べ、評価関数が改善されたら解を更新します。改善がなければ探索を終了し、最適解の近似値を返します。

このように局所探索法は、複雑な問題でも直感的に理解しやすく、実装もシンプルなのが特徴です。次のセクションでは、局所探索法の応用例や改良手法について解説します。

局所探索法の基本的な考え方

局所探索法は、最適化問題を解くためのシンプルで効果的なアルゴリズムの一つです。特に大規模な問題や複雑な探索空間において、全ての可能性を網羅的に調べるのが難しい場合に有効です。局所探索法は「現在の解の近傍から少しずつ改善を繰り返す」ことで、良い解を見つけていきます。

具体的には、まず初期解を設定し、その周辺の「近傍解」を評価します。近傍解とは、現在の解から少しだけ異なる解のことを指します。もし近傍解の中に現在の解よりも評価関数の値が良いものがあれば、その解に移動します。これを繰り返すことで、局所的に最適な解（局所最適解）に到達します。

局所探索法の評価関数を \( f(x) \) とすると、現在の解を \( x \)、近傍解を \( x’ \) とした場合、以下の条件で解を更新します。

\[
f(x’) < f(x) \]

この式は「新しい解の評価値が現在の解よりも良ければ更新する」という意味です。局所探索法は単純で直感的ですが、局所最適解に陥るリスクがあります。そのため、改良版として様々な手法が存在しますが、まずは基本の局所探索の流れを理解することが重要です。

以下は、Pythonでの局所探索法の簡単な実装例です。ここでは、1次元の関数 \( f(x) = (x – 3)^2 \) を最小化する問題を考えます。

def f(x):
    return (x - 3) ** 2

def local_search(initial_x, step=0.1, max_iter=100):
    current_x = initial_x
    for _ in range(max_iter):
        # 近傍探索：current_x の前後 step ずつ移動して評価
        neighbors = [current_x - step, current_x + step]
        next_x = current_x
        for x in neighbors:
            if f(x) < f(next_x):
                next_x = x
        if next_x == current_x:
            break  # 改善がなければ終了
        current_x = next_x
    return current_x

result = local_search(initial_x=0)
print(f"最適解の近似値: {result}, 関数値: {f(result)}")

このコードでは、初期値から少しずつ関数値を下げる方向へ移動し、改善がなくなるまで繰り返します。初心者の方は、まずはこのような単純な局所探索法を動かしてみて、どのように解が改善されていくか体感してみることをおすすめします。

局所探索法のメリットとデメリット

局所探索法は、最適化問題を解くためのシンプルかつ実用的な手法です。ここでは、初心者の方にも分かりやすく、局所探索法のメリットとデメリットを整理します。

メリット

• 実装が簡単
  局所探索法は初期解からスタートし、近傍の解を順に探索していくため、複雑な数学的理論を必要とせず、Pythonなどのプログラミング言語でも簡単に実装できます。
• 計算コストが比較的低い
  解空間が非常に大きい場合でも、全探索よりも効率的に良い解を見つけやすいです。
• 幅広い問題に適用可能
  組合せ最適化や連続最適化など、多様な問題に柔軟に対応できます。

デメリット

• 局所最適解に陥りやすい
  局所探索法は近傍の改善を繰り返すため、最終的にグローバル最適解ではなく局所最適解に止まってしまうことがあります。
• 探索の初期解に依存
  初期解の選び方によって、探索の結果が大きく変わるため、解の質にバラつきが出やすいです。
• 大規模問題では収束に時間がかかる場合もある
  解空間が広すぎると、改善の余地が少なくなるまで探索に時間がかかることがあります。

局所探索法の基本的な数式例とPythonコード

局所探索法では、評価関数 \( f(x) \) を最小化（または最大化）する解 \( x \) を探索します。解の近傍を \( N(x) \) と表すと、次のように更新を行います。

\[
x_{\text{new}} = \arg\min_{y \in N(x)} f(y)
\]

つまり、現在の解 \( x \) の近傍 \( N(x) \) の中で最も評価値が良い解 \( x_{\text{new}} \) を選んで更新します。もし新しい解の評価値が悪化する場合は探索を止めるか、別の戦略で対応します。

def local_search(initial_solution, evaluate, neighbors):
    current = initial_solution
    current_score = evaluate(current)

    while True:
        next_solution = None
        next_score = current_score

        for neighbor in neighbors(current):
            score = evaluate(neighbor)
            if score < next_score:
                next_solution = neighbor
                next_score = score

        if next_solution is None:
            break

        current = next_solution
        current_score = next_score

    return current, current_score

このコードは、評価関数 evaluate と近傍生成関数 neighbors を受け取り、評価値を改善し続けられなくなるまで繰り返します。シンプルですが、局所探索法の基本的な動きを示しています。

局所探索法の数式による定義

局所探索法は、最適化問題において「現在の解の近傍（隣接解）を探索し、より良い解を見つけていく」方法です。これを数式で表すと、以下のようになります。

まず、探索空間を集合 \( S \)、現在の解を \( s \in S \)、目的関数（評価関数）を \( f: S \rightarrow \mathbb{R} \) と定義します。局所探索法の基本的なステップは次の通りです。

• 現在の解 \( s \) の近傍解の集合を \( N(s) \subseteq S \) とする。
• 近傍解の中から目的関数の値が改善する解（例えば、最小化問題なら \( \min_{s’ \in N(s)} f(s’) < f(s) \) ）を選ぶ。
• 改善解があれば、その解に移動し、なければ探索を終了する。

つまり、局所探索法は以下のように表現できます。

\[
s \leftarrow s’ \quad \text{where} \quad s’ = \arg \min_{x \in N(s)} f(x), \quad \text{if} \quad f(s’) < f(s) \]

この式は「近傍解の中で最も良い解 \( s’ \) に更新する。ただし目的関数が改善される場合のみ」と解釈できます。改善がない場合は、その時点で局所最適解に到達したと判断し、探索を終わります。

次に、Pythonでの簡単な局所探索法の実装例を示します。ここでは1次元の関数を最小化する例です。

def objective(x):
    return (x - 3) ** 2 + 1  # 最小値は x=3 で 1

def neighborhood(x, step=0.1):
    return [x - step, x + step]

def local_search(initial_x, max_iter=100):
    current_x = initial_x
    current_val = objective(current_x)
    for _ in range(max_iter):
        neighbors = neighborhood(current_x)
        next_x = current_x
        next_val = current_val
        for x in neighbors:
            val = objective(x)
            if val < next_val:
                next_x = x
                next_val = val
        if next_val < current_val:
            current_x = next_x
            current_val = next_val
        else:
            break  # 改善なしで終了
    return current_x, current_val

result = local_search(0.0)
print(f"局所探索法の結果: x={result[0]}, f(x)={result[1]}")

このコードでは、初期解から左右に小さく動いた点を近傍として評価し、目的関数の値が下がる方向に移動します。改善が見られなくなった時点で探索を終了し、局所最適解を返します。

この数式とコードの対応を理解することで、局所探索法がどのように動作しているか、初心者でもイメージしやすくなるでしょう。

代表的な局所探索法のアルゴリズム

局所探索法は、最適解を目指して現在の解の近傍を探索し続ける手法です。代表的なアルゴリズムには「単純局所探索法」「焼きなまし法」「タブー探索」などがあり、それぞれ特徴的な工夫を持っています。ここでは初心者向けに基本的なアルゴリズムを数式とPythonコードで解説します。

単純局所探索法（Simple Local Search）

単純局所探索法は、現在の解 \(x\) から近傍解 \(x’\) を探索し、評価関数 \(f(x)\) の値が改善される場合に解を更新します。つまり、以下のルールで進めます。

探索ステップ：

\[
x’ \in N(x) \quad \text{で} \quad f(x’) < f(x) \quad \Rightarrow \quad x \leftarrow x' \]

ここで、\(N(x)\) は解 \(x\) の近傍集合を示します。改善が見られない場合は探索を終了します。

Pythonコード例：

def local_search(f, initial_x, neighborhood):
    x = initial_x
    while True:
        candidates = [x_new for x_new in neighborhood(x) if f(x_new) < f(x)]
        if not candidates:
            break
        x = min(candidates, key=f)
    return x

このコードでは、評価関数 f、初期解 initial_x、近傍を生成する関数 neighborhood を引数に取り、改善する解が見つからなくなるまで探索を続けます。

焼きなまし法（Simulated Annealing）

焼きなまし法は、単純局所探索の弱点である局所最適解への陥りを防ぐため、確率的に悪化する解も受け入れる手法です。確率は現在の温度 \(T\) に依存し、温度が下がるにつれて悪化解の受け入れ確率は減少します。

遷移確率は以下の通りです：

\[
P = \begin{cases}
1 & \text{if } f(x’) < f(x) \\ \exp\left(-\frac{f(x') - f(x)}{T}\right) & \text{if } f(x') \geq f(x) \end{cases} \]

ここで、\(\exp\) は自然指数関数です。

Pythonコード例：

import math
import random

def simulated_annealing(f, initial_x, neighborhood, initial_T, cooling_rate):
    x = initial_x
    T = initial_T
    while T > 1e-3:
        x_new = random.choice(neighborhood(x))
        delta = f(x_new) - f(x)
        if delta < 0 or random.random() < math.exp(-delta / T):
            x = x_new
        T *= cooling_rate
    return x

焼きなまし法は、温度を徐々に下げながら探索し、局所解からの脱出を試みるため、複雑な問題にも適用しやすいです。

このように代表的な局所探索法は、それぞれの特徴を理解し適切に使い分けることで、より良い最適化結果が期待できます。

隣接解の定義と探索方法

局所探索法では、現在の解の「隣接解（近傍解）」を探索し、より良い解を見つけていきます。隣接解とは、現在の解から少しだけ変更を加えた解のことで、探索空間の中で隣り合う解のことを指します。適切な隣接解の定義が、局所探索法の性能を左右すると言っても過言ではありません。

例えば、組合せ問題における解 \( x \) がベクトルで表されるとき、隣接解は次のように定義できます。

隣接解 \( x’ \) は、元の解 \( x \) と一部の要素が異なる解であり、距離関数 \( d(x, x’) \) が小さいものとします。よく使われる距離関数の一つはハミング距離で、これは異なる要素の数を表します。

\[
d(x, x’) = \sum_{i=1}^n \delta(x_i, x’_i), \quad \delta(a,b) = \begin{cases} 0 & a = b \\ 1 & a \neq b \end{cases}
\]

この定義で「隣接解」は距離が1の解、つまり「1つの要素だけが異なる解」となります。局所探索法では、現在の解からこの隣接解群を順に評価し、目的関数の値が改善する解があればその解に移動します。

Pythonでの隣接解の例として、1次元リストの要素を1つだけ入れ替える操作を考えます。以下のコードは、与えられた解から隣接解を生成する簡単な例です。

def generate_neighbors(solution):
    neighbors = []
    n = len(solution)
    for i in range(n):
        for j in range(i+1, n):
            neighbor = solution.copy()
            # i番目とj番目の要素を入れ替える
            neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
            neighbors.append(neighbor)
    return neighbors

# 例：解の例
current_solution = [1, 2, 3, 4]
neighbors = generate_neighbors(current_solution)
print(neighbors)

この関数は、リスト内の2つの要素を入れ替えることで隣接解を生成しています。ここでの「隣接」の定義は「1回のスワップ操作で得られる解」です。探索時にはこの隣接解群の中から評価関数（目的関数）の値が良いものを選び、探索を進めていきます。

まとめると、局所探索法における隣接解とは「現在の解から少しだけ変化させた解」であり、数式で距離関数を用いて定義され、実装では近傍生成関数として表現されます。この隣接解の探索方法が、局所探索法の効率と精度に大きく影響します。

評価関数の役割

局所探索法において「評価関数」は、探索の方向性を決める非常に重要な役割を持っています。評価関数とは、現在の解（候補解）がどれだけ良いかを数値で示す関数のことです。これにより、アルゴリズムはどの解を次に選ぶべきか判断でき、より良い解を目指して探索を進めることが可能になります。

局所探索法の基本的な流れは、ある初期解からスタートし、近傍の解の中で評価関数の値が改善される方向に移動していくというものです。ここで評価関数を \( f(x) \) と表すと、解 \( x \) の良さを数値で表し、探索はこの関数の最小化または最大化を目指します。

例えば、最小化問題の場合は以下の数式が評価関数の基本形です。

\[
\min_{x \in S} f(x)
\]

ここで、\( S \) は解の集合（探索空間）を表します。局所探索法では、現在の解 \( x \) から近い位置にある解 \( x’ \in N(x) \)（近傍解）を考え、

\[
f(x’) < f(x) \]

を満たす解があれば、より良い解として \( x’ \) に移動します。これを繰り返すことで、局所的に最適な解を見つけることができます。

Pythonでの簡単な評価関数の例として、1変数の関数 \( f(x) = (x-3)^2 \) を考えてみましょう。これは \( x=3 \) で最小値0を取る関数です。

def evaluate(x):
    return (x - 3) ** 2

この関数を使い、例えば現在の解が \( x=5 \) の場合、評価値は

\[
f(5) = (5 – 3)^2 = 4
\]

となります。より良い解を探すために、近傍の解として \( x=4 \) を評価すると、

\[
f(4) = (4 – 3)^2 = 1
\]

と評価値が小さくなっており、改善が見られます。このように評価関数は解の良し悪しを数値化し、局所探索法が効果的に解を改善していく指標となるのです。

Pythonでの局所探索法の基本実装

局所探索法は、ある初期解からスタートし、その周辺の解を徐々に探索していく手法です。最も基本的な考え方は「現在の解よりも改善された解が見つかればそちらに移動する」というものです。これにより、局所的な最適解を見つけることができます。

具体的には、解をパラメータのベクトル \( \mathbf{x} \) とし、評価関数（目的関数）を \( f(\mathbf{x}) \) と表します。局所探索法では、現在の解 \( \mathbf{x}_{current} \) の近傍解 \( \mathbf{x}_{neighbor} \) を生成し、

評価関数が改善されれば移動します：

\[
f(\mathbf{x}_{neighbor}) < f(\mathbf{x}_{current}) \implies \mathbf{x}_{current} \leftarrow \mathbf{x}_{neighbor} \]

これを繰り返し、改善できなくなった時点で探索を終了します。

以下は、シンプルな1次元関数の最小化を例にしたPython実装です。評価関数として \( f(x) = (x-3)^2 \) を用い、初期解をランダムに設定し、隣接点を±0.1ずつ変化させて探索します。

import random

def objective_function(x):
    return (x - 3) ** 2

def local_search(initial_x, step=0.1, max_iter=100):
    current_x = initial_x
    current_val = objective_function(current_x)
    
    for _ in range(max_iter):
        # 近傍解の候補を生成
        neighbors = [current_x - step, current_x + step]
        # 近傍解の中で最も良い解を探す
        neighbor_vals = [objective_function(x) for x in neighbors]
        min_val = min(neighbor_vals)
        min_index = neighbor_vals.index(min_val)
        if min_val < current_val:
            current_x = neighbors[min_index]
            current_val = min_val
        else:
            # 改善がなければ終了
            break
    return current_x, current_val

# 初期解をランダムに設定
initial_solution = random.uniform(-10, 10)
optimal_x, optimal_val = local_search(initial_solution)

print(f"初期解: {initial_solution:.4f}")
print(f"探索後の解: {optimal_x:.4f}")
print(f"評価関数の値: {optimal_val:.4f}")

この例では、評価関数の値が小さくなる方向に少しずつ移動しながら最適解を探索しています。局所探索法は単純ながら、多くの実問題に適用でき、特に大規模な組合せ最適化問題や関数の連続的最適化において強力なツールです。

サンプル問題：巡回セールスマン問題への適用

局所探索法は、組合せ最適化問題の代表例である「巡回セールスマン問題（TSP）」にも効果的に適用できます。TSPは複数の都市を一度ずつ訪問し、最短の巡回路を見つける問題です。都市数が増えると全探索が困難になるため、局所探索法のようなヒューリスティック手法が有用です。

まず、TSPの目的関数を数式で表現しましょう。都市の集合を \( \{1, 2, \ldots, n\} \)、都市間の距離を \( d_{ij} \) とすると、巡回路の経路を順序付きリスト \( \pi = (\pi_1, \pi_2, \ldots, \pi_n) \) として、巡回路の総距離は以下のように定義されます。

\[
f(\pi) = \sum_{k=1}^{n-1} d_{\pi_k \pi_{k+1}} + d_{\pi_n \pi_1}
\]

局所探索法では、この関数 \( f(\pi) \) を最小化するために、現在の解 \( \pi \) の「近傍解」を探索します。近傍解の一例として、2-opt法があります。これは、巡回路の一部の辺を入れ替えて新しい経路を作り、距離が短くなるかを評価します。

具体的には、2-optで選んだ2つの辺 \( (i, i+1) \) と \( (j, j+1) \) を切断し、経路の部分区間を逆順に入れ替えます。これにより新たな巡回路 \( \pi’ \) が得られます。もし \( f(\pi’) < f(\pi) \) なら解を更新します。

以下はPythonで簡単な2-opt局所探索の例です。

def calc_total_distance(route, distance_matrix):
    total = 0
    n = len(route)
    for i in range(n - 1):
        total += distance_matrix[route[i]][route[i+1]]
    total += distance_matrix[route[-1]][route[0]]
    return total

def two_opt(route, distance_matrix):
    n = len(route)
    best_route = route[:]
    best_distance = calc_total_distance(route, distance_matrix)
    improved = True
    while improved:
        improved = False
        for i in range(1, n - 2):
            for j in range(i + 1, n):
                if j - i == 1:
                    continue
                new_route = best_route[:]
                new_route[i:j] = reversed(best_route[i:j])
                new_distance = calc_total_distance(new_route, distance_matrix)
                if new_distance < best_distance:
                    best_route = new_route
                    best_distance = new_distance
                    improved = True
                    break
            if improved:
                break
    return best_route, best_distance

このコードでは、距離行列と初期ルートを基に2-optで局所的に改善を試みています。局所探索法は必ずしも最適解を保証しませんが、計算量を抑えつつ良好な解を効率的に得ることができます。初心者でも理解しやすいアルゴリズムなので、ぜひ実際に試してみてください。

Pythonコード解説：初期解の生成

局所探索法は、問題空間の中から「良い解」を探していくアルゴリズムです。まずは探索のスタート地点となる「初期解」を生成することが重要です。初期解の質によって、その後の探索効率や最終的な解の良さが大きく左右されるため、慎重に扱います。

初期解は一般的に問題の制約を満たすランダムな解として設定されます。たとえば、整数値の組み合わせ問題なら、各変数にランダムな値を割り当てます。数学的には、初期解 \( \mathbf{x}^{(0)} \) は探索空間 \( S \) の中の任意の点として表せます。

つまり、

\[ \mathbf{x}^{(0)} \in S \]

ここで、\( S \) は制約条件を満たす解の集合です。Pythonで初期解を生成する際は、制約条件を考慮しつつ乱数を利用することが多いです。以下は、整数の配列を初期解としてランダム生成する例です。

import random

def generate_initial_solution(size, lower_bound, upper_bound):
    # サイズと範囲を指定して初期解を生成
    solution = [random.randint(lower_bound, upper_bound) for _ in range(size)]
    return solution

# 例: 長さ10、値は0から100の範囲
initial_solution = generate_initial_solution(10, 0, 100)
print(initial_solution)

このコードは、探索空間の一部である整数の配列をランダムに作成します。ここでのポイントは、初期解があくまで「探索の出発点」であり、局所探索の中で徐々に改善されることです。初期解の生成方法を工夫すると、より効率的に良い解に辿り着けやすくなります。

まとめると、初期解生成は以下のステップで行います：

• 問題の探索空間 \( S \) と制約条件を明確にする
• ランダムまたはヒューリスティックに初期解 \( \mathbf{x}^{(0)} \) を作成
• 生成した解が有効かどうか（制約を満たしているか）をチェック

この段階をしっかり押さえることで、局所探索法の効果を最大限に引き出せます。

Pythonコード解説：隣接解の探索

局所探索法において「隣接解の探索」は、現在の解の近くにある候補解（隣接解）を見つけるプロセスです。これにより、より良い解を探索空間の中から段階的に探し出すことができます。数学的には、ある解 \( x \) に対して、その「隣接解」は以下のように定義されることが多いです。

例えば、解がベクトル \( x = (x_1, x_2, \ldots, x_n) \) で表される場合、隣接解 \( x’ \) は一部の要素が微小に変化したもので、一般的に次のように表せます。

\[ x’ = (x_1, \ldots, x_i + \delta, \ldots, x_n) \quad \text{ただし} \quad \delta \in \{-1, 1\} \]

ここで、\(\delta\) は解空間内で「一歩」隣接する方向を示しています。局所探索法では、現在の解 \( x \) からこのような隣接解を生成し、評価関数で良さを判定します。

以下は、Pythonで隣接解の探索を実装したシンプルな例です。ここでは整数ベクトルの各要素に対して、プラス1またはマイナス1の変更を加えた全ての隣接解をリストアップしています。

def generate_neighbors(current_solution):
    neighbors = []
    for i in range(len(current_solution)):
        for delta in [-1, 1]:
            neighbor = current_solution.copy()
            neighbor[i] += delta
            neighbors.append(neighbor)
    return neighbors

# 例: 現在の解
current = [3, 5, 2]
# 隣接解を生成
neighbors = generate_neighbors(current)
print(neighbors)

このコードのポイントは以下の通りです。

• 解の構造を保つ：元の解をコピーして変更を加えることで、元の解を壊さずに隣接解を作成しています。
• 全ての要素に対して隣接解を生成：各要素を±1ずつ変化させた解を網羅的に生成し、探索の幅を確保します。
• 簡単な変更で局所探索法を実現：この方法は非常に直感的で、初心者にも理解しやすい局所探索の基礎となります。

このように、隣接解の探索は現在の解の「小さな変化」を体系的に探すことです。実際の問題では、隣接解の定義や生成方法は問題特性に応じて工夫されますが、基本は「近い解を探索する」という考え方に変わりありません。

Pythonコード解説：評価関数の実装

局所探索法では、現在の解の良さを数値で表す「評価関数」が非常に重要です。評価関数は、解の「質」を計算し、探索の方向性を決定します。ここでは、評価関数の基本的な構造とPythonによる実装例を紹介します。

まず、評価関数は一般的に以下のように定義されます。

解をベクトル \(\mathbf{x} = (x_1, x_2, \dots, x_n)\) とし、評価関数 \(f(\mathbf{x})\) はその解の良さを示すスカラー値を返します。例えば、最小化問題の場合は、

\[
f(\mathbf{x}) = \sum_{i=1}^n w_i \cdot g_i(x_i)
\]

ここで、\(w_i\) は重み、\(g_i(x_i)\) は各変数に対する評価項目です。この式は、複数の要素を加重平均的に評価する場合に使われます。

次に、この数式を基にしたPythonコード例を見てみましょう。以下は、簡単な評価関数の実装例です。

def evaluate_solution(x, weights):
    """
    評価関数：解 x と重み weights を受け取り、
    加重和を計算して返す。

    Parameters:
    x (list of float): 解の各要素
    weights (list of float): 各要素の重み

    Returns:
    float: 評価値
    """
    total = 0
    for xi, wi in zip(x, weights):
        total += wi * xi**2  # xiの2乗を評価項目とする例
    return total

この例では、評価関数として単に各要素の2乗に重みをかけて合計しています。実際の問題に応じて、関数 \(g_i(x_i)\) の部分を変えることで多様な評価基準を設計できます。

局所探索法では、評価関数の値が「小さいほど良い」または「大きいほど良い」とすることで、隣接解への移動判断に使われます。初心者の方は、まずはシンプルな評価関数を実装し、動作を確認しながら徐々に複雑な評価基準へと発展させるのがおすすめです。

局所最適解とグローバル最適解の違い

局所探索法を理解する上で重要なのが、「局所最適解」と「グローバル最適解」の違いです。最適化問題において、解の良さを評価する関数（目的関数）が存在し、これを最大化または最小化することが目標となります。

局所最適解とは、ある解の周辺だけを見たときに最も良い解のことを指します。つまり、その近傍の解と比べて目的関数の値が改善できない状態です。一方、グローバル最適解は問題全体の中で最も良い解であり、全ての可能な解の中で目的関数の値が最大または最小となる点です。

数学的には、目的関数を \( f(x) \) とし、探索空間を \( X \) としたとき、ある点 \( x^* \in X \) が局所最適解であるとは、ある半径 \( r > 0 \) に対して次が成り立つ場合を言います。

（ここでは最小化問題の例）

\[
f(x^*) \leq f(x), \quad \forall x \in X \text{ かつ } \|x – x^*\| < r \]

一方、グローバル最適解は探索空間全体で成り立ちます。

\[
f(x^*) \leq f(x), \quad \forall x \in X
\]

局所探索法は、現在の解から近い解を順に探索し、改善が見られなくなるまで繰り返す方法であるため、局所最適解に陥りやすい特徴があります。以下は簡単なPythonの例です。隣接する解の中で最も目的関数値が小さい解に移動し続けるシンプルな局所探索のコード例です。

def objective(x):
    return (x - 3)**2 + 5

def local_search(start, step=0.1, max_iter=100):
    current = start
    for _ in range(max_iter):
        neighbors = [current - step, current + step]
        next_point = min(neighbors, key=objective)
        if objective(next_point) >= objective(current):
            break
        current = next_point
    return current

result = local_search(start=0.0)
print(f"局所探索法による解: {result}, 目的関数値: {objective(result)}")

この例では、目的関数は \( f(x) = (x-3)^2 + 5 \) で、グローバル最適解は \( x = 3 \) です。スタート地点が遠い場合でも、局所探索法は近くの「山（谷）」を探しに行きますが、複雑な関数形では局所最適解にとどまってしまうことがあります。

局所探索法の性能を高めるためには、初期解の選び方や探索範囲の広げ方、場合によっては確率的な手法を組み合わせて局所最適解から脱出する工夫が必要です。

局所探索法の改良手法

局所探索法はシンプルで実装も容易な反面、解が局所最適に陥りやすいという課題があります。そこで、より良い解を見つけるためにいくつかの改良手法が提案されています。ここでは初心者にも理解しやすい代表的な改良手法を紹介します。

1. 焼きなまし法（Simulated Annealing）

焼きなまし法は、温度パラメータを使って探索の自由度を制御し、局所最適から脱出しやすくする手法です。基本的な考え方は、現在の解より悪い解も一定確率で受け入れることで、探索の幅を広げることにあります。

受け入れ確率は次の式で表されます：

\[
P = \exp \left( -\frac{\Delta E}{T} \right)
\]

ここで、\(\Delta E\) は新しい解のコストと現在の解のコストの差、\(T\) は温度です。温度が高いほど悪い解も受け入れやすく、温度が下がるにつれて探索は収束していきます。

この考え方をPythonで実装すると以下のようになります：

import math
import random

def acceptance_probability(old_cost, new_cost, temperature):
    if new_cost < old_cost:
        return 1.0
    else:
        return math.exp(-(new_cost - old_cost) / temperature)

# 例: 現在のコスト100、新しいコスト110、温度50のとき
prob = acceptance_probability(100, 110, 50)
print(prob)  # 0.8187... のような値が出力されます

2. タブー探索（Tabu Search）

タブー探索は、過去に訪れた解の履歴（タブーリスト）を管理することで、同じ解に戻るのを防ぎ、多様な探索経路を確保する方法です。これにより、単純な局所探索法よりも広い範囲を探索できます。

タブーリストは最近の解を一定数記憶し、それらの解への遷移を禁止します。これにより、探索が局所的なループに陥るのを防ぎます。

まとめ

局所探索法の改良手法は、探索の自由度を高めて局所最適からの脱出を助けます。焼きなまし法は確率的な受け入れルールで探索範囲を広げ、タブー探索は探索履歴を利用して新しい経路を模索します。これらを組み合わせたり、問題に応じてパラメータを調整することで、より良い結果が期待できます。

焼きなまし法（シミュレーテッドアニーリング）

局所探索法の一つである焼きなまし法（シミュレーテッドアニーリング）は、物理学の「アニーリング（焼きなまし）」の過程を模倣した最適化手法です。局所最適解に陥りやすい単純な探索法と異なり、時には悪化する方向の解も受け入れることで、グローバル最適解に近づきやすい特徴があります。

焼きなまし法の基本的な考え方は、探索空間を「温度」というパラメータで制御しながら、解の良し悪しに応じて遷移確率を調整することです。温度が高い初期段階では解の質が悪くても移動を許容し、徐々に温度を下げることでより良い解への改善を促します。

確率的遷移の数式

新しい解 \(x’\) が現在の解 \(x\) よりも良い場合（評価関数 \(f(x’) < f(x)\)）は必ず受け入れます。しかし、悪い場合でも次の確率で受け入れることがあります：

\[
P = \exp\left(-\frac{f(x’) – f(x)}{T}\right)
\]

ここで、\(T\) は温度パラメータで、反復のたびに少しずつ減少させます。この式は「悪化度合い」と「温度」に応じて受け入れ確率を決定し、温度が高いほど悪い解も受け入れやすく、温度が低くなると悪い解がほとんど受け入れられなくなります。

Pythonによる簡単な実装例

以下は焼きなまし法の基本的な流れを示したPythonコードです。評価関数は単純な1変数の関数として定義し、最小化を目指します。

import math
import random

def objective(x):
    return x**2 + 10 * math.sin(x)

def simulated_annealing():
    current_x = random.uniform(-10, 10)
    current_f = objective(current_x)
    T = 10.0  # 初期温度
    cooling_rate = 0.95
    min_T = 1e-3
    
    while T > min_T:
        candidate_x = current_x + random.uniform(-1, 1)
        candidate_f = objective(candidate_x)
        delta = candidate_f - current_f
        
        if delta < 0 or random.random() < math.exp(-delta / T):
            current_x, current_f = candidate_x, candidate_f
        
        T *= cooling_rate  # 温度を下げる
    
    return current_x, current_f

best_x, best_f = simulated_annealing()
print(f"最適解 x = {best_x:.4f}, 目的関数値 = {best_f:.4f}")

このコードでは、初期温度から徐々に温度を下げつつランダムに解を生成し、改善または一定確率で悪化を受け入れています。これにより単純な局所探索法よりも広い範囲を探索でき、局所解からの脱出が期待できます。

焼きなまし法は、組合せ最適化問題や関数最小化など幅広い応用先があり、局所探索法の中でも特に汎用性が高い手法として知られています。初心者でも理解しやすく、試行錯誤しながらパラメータ調整を行うことで実務的な問題に適用可能です。

タブーサーチ

タブーサーチは、局所探索法の一種で、単純な局所探索が陥りやすい「局所最適解」にとどまらず、より良い解を探すための工夫が加えられています。基本的な局所探索法では、現在の解の近傍の中で最も良い解に移動しますが、これが繰り返されると同じ箇所をぐるぐる回ってしまうことが多くあります。タブーサーチは、過去に訪れた解やその特徴を記録し、すぐに戻らないようにすることで探索の多様性を確保し、より広い範囲を探索します。

具体的には、「タブーリスト」と呼ばれる一定期間解の履歴を保存するリストを用います。これにより、最近訪れた解は「禁じ手（タブー）」とされ、同じ解にすぐ戻ることを防ぎます。これが局所最適解の脱出に効果的です。

例えば、近傍解の評価値を \( f(x) \) とし、現在の解を \( x_t \)、次の解を \( x_{t+1} \) とします。通常の局所探索では

\[
x_{t+1} = \arg\min_{x \in N(x_t)} f(x)
\]

となりますが、タブーサーチではタブーリストに含まれる解は探索対象から除外します。

Pythonでの簡単なイメージコードは以下の通りです。ここでは、解を整数値とし、近傍を「現在の解の前後の整数」としています。

def tabu_search(f, start, iterations, tabu_size):
    current = start
    best = current
    tabu_list = []
    
    for _ in range(iterations):
        # 近傍生成（現在の前後の整数）
        neighbors = [current - 1, current + 1]
        # タブーリストに含まれる解を除外
        candidates = [x for x in neighbors if x not in tabu_list]
        if not candidates:
            break
        # 最良の候補を選択
        next_sol = min(candidates, key=f)
        # タブーリストの更新
        tabu_list.append(current)
        if len(tabu_list) > tabu_size:
            tabu_list.pop(0)
        current = next_sol
        # 最良解の更新
        if f(current) < f(best):
            best = current
    return best

このように、タブーリストを用いることで単純な局所探索よりも探索範囲を広げ、より良い解を見つけやすくなります。初心者の方でも、局所探索法の欠点を補う強力な手法として理解しておくと良いでしょう。

局所探索法の収束条件と停止基準

局所探索法は、初期解から少しずつ改善を重ねて最適解を目指すアルゴリズムです。しかし、無限に探索を続けるわけにはいかないため、収束条件や停止基準を適切に設定することが重要です。ここでは、局所探索法が「収束した」と判断するための基準と、その実装方法を初心者向けに解説します。

1. 収束条件の考え方

局所探索法では、改善が見られなくなったときに「収束」とみなすことが多いです。具体的には、探索のステップごとに評価関数（目的関数）の値が良くならなくなった場合に停止します。評価関数を \( f(x) \) とし、現在の解を \( x_t \)、次の解を \( x_{t+1} \) とすると、収束条件は以下のように表せます。

\[
f(x_{t+1}) \geq f(x_t)
\]

この条件は「改善がない」または「悪化した」場合を意味します。ここで評価関数は最大化問題を想定していますが、最小化問題であれば不等号の向きが逆になります。

2. 停止基準の例

収束条件だけでなく、以下のような停止基準も併せて設定することが一般的です。

• 一定の改善が見られないステップ数（例：10回連続で改善なし）
• 探索の最大繰り返し回数（例：1000ステップ）
• 評価関数の変化が閾値以下（例：\(\left|f(x_{t+1}) – f(x_t)\right| < \epsilon\)）

これらの基準を組み合わせることで、過度な計算を防ぎつつ十分な探索が行えます。

3. Pythonでの簡単な実装例

以下は、改善が見られなくなった場合に探索を停止するシンプルなコード例です。ここでは最大化問題を仮定し、改善がなければ停止します。

def local_search(initial_solution, evaluate, get_neighbors, max_no_improvement=10):
    current_solution = initial_solution
    current_value = evaluate(current_solution)
    no_improve_count = 0

    while no_improve_count < max_no_improvement:
        neighbors = get_neighbors(current_solution)
        next_solution = max(neighbors, key=evaluate)
        next_value = evaluate(next_solution)

        if next_value > current_value:
            current_solution = next_solution
            current_value = next_value
            no_improve_count = 0
        else:
            no_improve_count += 1

    return current_solution, current_value

このコードのポイントは、改善が10回連続で見られなければループを抜ける点です。これにより、無駄な計算を減らし、効率的に収束を判定できます。

実践での局所探索法の使いどころ

局所探索法は、最適化問題を解く際に「現在の解の近くを探索し、より良い解を見つける」手法です。実務では、膨大な解空間を効率的に探索したい場合や、厳密解法が計算困難な問題に対して特に有効です。例えば、配送経路の最適化や機械学習のハイパーパラメータ調整、スケジューリング問題など、多様な分野で活用されています。

基本的な数式として、現在の解を \(x\)、近傍解の集合を \(N(x)\) とすると、局所探索法は以下のように動作します。

現在の解 \(x\) の近傍解 \(x’ \in N(x)\) を評価し、目的関数 \(f(x)\) の値が改善される解を見つけます。

これをPythonでシンプルに表現すると以下のようになります。

def local_search(current_solution, neighborhood, objective_function):
    best_solution = current_solution
    for candidate in neighborhood(current_solution):
        if objective_function(candidate) < objective_function(best_solution):
            best_solution = candidate
    return best_solution

このコードは、与えられた近傍解をすべて評価し、目的関数の値がより良い解を見つけて返すものです。実務では、近傍の定義や探索戦略を工夫することで、より効率的かつ効果的な解探索が可能になります。

局所探索法は単純ながらも、問題の規模や複雑度によってはグローバルな最適解にたどり着かないこともありますが、短時間で良好な解を得たい場合には非常に有用な手法です。初心者の方はまずは小規模な問題で局所探索法を動かしてみて、その挙動を理解することから始めるのが良いでしょう。

局所探索法の性能評価方法

局所探索法は、最適解に近い解を見つけるためのヒューリスティックな手法ですが、その性能を評価するにはいくつかのポイントを押さえる必要があります。初心者の方でも理解しやすいように、基本的な評価指標と具体的な実装例を交えて解説します。

1. 目的関数値の推移を観察する

局所探索法の性能を評価する最も基本的な方法は、探索の途中で得られた解の目的関数値（評価値）を追うことです。例えば、ある問題の目的関数を \( f(x) \) とすると、各ステップ \( t \) における解 \( x_t \) の値は次のように表せます。

式：

\[
f(x_t)
\]

この値が反復を重ねるごとに改善（最小化問題なら減少）しているかをグラフで見ることで、探索の進み具合や収束状況を把握できます。

2. 実装例：目的関数値の推移を記録するPythonコード

以下は、単純な局所探索法の実装例で、目的関数値の推移をリストに記録するコードです。

def objective(x):
    return x**2 + 4*x + 4  # 例：二次関数

def local_search(start, iterations):
    current = start
    history = [objective(current)]
    for _ in range(iterations):
        neighbors = [current - 1, current + 1]
        next_candidate = min(neighbors, key=objective)
        if objective(next_candidate) < objective(current):
            current = next_candidate
        history.append(objective(current))
    return current, history

best_solution, history = local_search(start=10, iterations=20)
print("Best solution:", best_solution)
print("Objective history:", history)

このコードでは、現在の解の近傍（neighbors）を探索し、目的関数値が改善する解に移動します。各ステップの目的関数値を history に保存することで、後で性能の推移を確認できます。

3. 複数回の実行による統計的評価

局所探索法は初期解に依存するため、単一の実行結果だけで性能を判断するのは危険です。複数回ランダムな初期解から探索を行い、得られた解の平均値や分散を計算することで、より安定した評価が可能になります。

例えば、複数回の実験で得られた最良解の平均を

\[
\bar{f} = \frac{1}{N} \sum_{i=1}^N f(x_i^*)
\]

とし、ばらつきは分散や標準偏差で表します。これにより、局所探索法の安定性や再現性も評価できます。

まとめ：局所探索法を使いこなすために

局所探索法は、最適化問題を解く強力な手法の一つです。特に大規模な問題や複雑な探索空間では、全探索が困難なため、近傍解を辿りながら解を改善していくこの方法が有効です。ただし、局所最適解に陥るリスクもあるため、その性質を理解し上手に使いこなすことが重要です。

局所探索法の基本的な考え方は、現在の解を \( x \) としたとき、近傍解 \( N(x) \) の中から評価関数 \( f \) がより良い解を選択し、反復的に更新していくことです。数学的には以下のように表せます。

評価関数 \( f \) を最大化問題とした場合：

\[
x^{(t+1)} = \arg\max_{x’ \in N(x^{(t)})} f(x’)
\]

ここで、\( x^{(t)} \) は時刻 \( t \) の解を表し、\( N(x^{(t)}) \) はその近傍解集合を意味します。この操作を繰り返すことで、徐々に良い解へと収束していきます。

Pythonでの簡単な局所探索法の実装例を示します。ここでは単純に1次元の整数問題で、評価関数 \( f(x) = -(x-3)^2 + 10 \) を最大化します。

def f(x):
    return -(x - 3) ** 2 + 10

def get_neighbors(x):
    return [x - 1, x + 1]

def local_search(start):
    current = start
    while True:
        neighbors = get_neighbors(current)
        next_candidate = max(neighbors, key=f)
        if f(next_candidate) <= f(current):
            break
        current = next_candidate
    return current

result = local_search(0)
print(f"局所探索法の結果: x = {result}, f(x) = {f(result)}")

このコードでは、スタート地点から近隣の解を評価し、より良い解がなければ探索を終了します。結果として、この例では最大値の近くで探索が止まります。

局所探索法を効果的に使うためには以下のポイントが役立ちます：

• 評価関数の設計：問題の目的を正確に反映する関数を作ることが重要です。
• 近傍の定義：探索空間の構造に合った近傍を設定し、多様な解を探索できるようにすること。
• 局所最適解の脱出策：単純な局所探索は局所最適に陥りやすいので、ランダムな初期解や擬似乱数的なステップを取り入れる方法も検討しましょう。

これらを踏まえ、局所探索法は実践的な問題解決において非常に有用です。まずは簡単な問題から実装し、数式とコードの両面から理解を深めることで、より高度な応用へと進んでいくことをおすすめします。

参考文献とさらなる学習リソース

局所探索法は多くの問題に適用できる強力な最適化手法ですが、その理論と実装を深く理解するためには信頼できる参考文献や学習リソースを活用することが重要です。ここでは、初心者の方でも取り組みやすい書籍やウェブサイト、そして局所探索法をPythonで実装する際に役立つ簡単な数式とコード例を紹介します。

おすすめの参考書籍とオンラインリソース

• 「最適化入門」（著：〇〇）：最適化の基本概念から局所探索法のアルゴリズムまで幅広く解説。
• CourseraやUdemyの最適化・探索アルゴリズムコース：動画で手を動かしながら理解でき、Python実装も学べる。
• QiitaやZennの記事：実践的な局所探索法の解説やPythonコード例が豊富。

局所探索法の基本数式とPythonコード例

局所探索法では、現在の解 \( x \) の近傍解 \( x’ \) を探索し、目的関数 \( f(x) \) を改善します。改善条件は通常、次のように表されます。

式：

\[
f(x’) < f(x) \]

この条件を満たす \( x’ \) が見つかれば、解を \( x’ \) に更新します。Pythonでの簡単な実装は以下の通りです。

def local_search(f, x_init, neighbors, max_iter=100):
    x = x_init
    for _ in range(max_iter):
        improved = False
        for x_prime in neighbors(x):
            if f(x_prime) < f(x):
                x = x_prime
                improved = True
                break
        if not improved:
            break
    return x

このコードでは、関数 f が評価関数、x_init が初期解、neighbors は現在の解の近傍を生成する関数です。局所探索法の基本的な流れを理解し、実際に手を動かしてみることで理解が深まります。

これらのリソースや例を活用しながら、ぜひ局所探索法の理論と実装の両面から学習を進めてください。