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

タブー探索（Tabu Search）とは？

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

タブー探索（Tabu Search）の概要​

タブー探索（Tabu Search：TS） は、組み合わせ最適化問題において、局所的最適解に陥るのを防ぎながら効率的に「良い解」を探索するための強力なメタヒューリスティクス（近似解法）の一つです。

これまでの記事で解説したように、局所探索（山登り法）は常に評価が改善する方向へしか進まないため、小さな山の頂上である局所的最適解（Local Optimum）に到達すると探索が止まってしまうという決定的な弱点がありました。 この罠を抜け出すため、焼きなまし法では「確率的に一時的な改悪を許容する」というアプローチをとりました。

タブー探索は、これらとは全く異なるアプローチで局所解の罠を克服します。最大の特徴は、探索の過程に 「記憶（Memory）」 を持たせる点です。

人間の行動に例えてみましょう。迷路で行き止まり（局所解）にぶつかったとき、人は「さっき通った道には戻らないようにしよう」と記憶を頼りに別のルートを探します。タブー探索も同様に、直近に訪問した解や実行した操作を 「タブーリスト（Tabu List）」 と呼ばれるメモリに一定期間記録し、その状態への逆戻り（ループ）を 「タブー（禁じ手）」 として禁止します。

  • タブーリスト（Tabu List）: 最近訪れた解を一定数記憶しておくリスト。
  • タブー期間（Tabu Tenure）: リストに記憶しておく期間（長さ）。この期間が過ぎるとタブーは解除され、再びその解に移動できるようになります。

これにより、「今よりスコアが悪化しても、タブーリストに載っていない新しい場所なら移動する」というルールを適用でき、来た道を戻る無限ループを防ぎながら局所解の谷を乗り越えることができるのです。

山登り法・焼きなまし法との違い（探索のルール）​

各アルゴリズムが、現在の解 xx から近傍の解 x′x' へどのように移動するかを比較してみましょう。近傍の集合を N(x)N(x) とします。

山登り法 (Hill Climbing)​

常に良くなる方向へ進み、改善できなくなれば終了します。

  • 探索範囲: N(x)N(x) のすべて
  • 移動条件: Δf>0\Delta f > 0 となる最大の x′x' を選ぶ。なければ終了。

焼きなまし法 (Simulated Annealing)​

温度 TT に基づく確率（メトロポリス基準）によって、悪化する方向への移動も許容します。

  • 探索範囲: N(x)N(x) からランダムに選んだ x′x'
  • 移動条件: Δf>0\Delta f > 0 なら移動、Δf≤0\Delta f \le 0 でも確率 exp⁡(Δf/T)\exp(\Delta f / T) で移動。

タブーリスト TlistT_{list} に含まれない近傍の中で、最も良い解（たとえ現在より悪化しても） へ確実に移動します。

  • 探索範囲: N(x)∖TlistN(x) \setminus T_{list} （近傍からタブーリストにある解を除外したもの）
  • 移動条件: 探索範囲の中で最もスコアが良い x′x' を選び、無条件で移動する。

※実際には、タブーリストに含まれていても、これまでの最高スコアを更新するような非常に良い解であれば特別に移動を許可する「アスピレーション条件（Aspiration Criterion）」という例外ルールを設けるのが一般的です。

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

それでは、Pythonコードを使ってタブー探索の挙動を確認してみましょう。これまでの記事と同じく、評価関数 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  # グラフ日本語表示用

# 評価関数（目的関数）
def f(x):
    return math.sin(x) + math.cos(0.5 * x)

# 探索空間の設定
x_min, x_max = 0.0, 10.0
step_size = 0.1  # 近傍への移動距離

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

# --- 可視化のためのデータ生成 ---
# 探索範囲内のx値のリストを作成
x_vals = [i * step_size for i in range(int(x_max / step_size) + 1)]

# 各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()

実行結果​

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

評価関数

このプロットからわかるように、評価関数 f(x)f(x) には複数の山が存在します。 具体的には、x≈1.7x \approx 1.7 付近に最も高い大域的最適解があり、x≈8.3x \approx 8.3 付近にそれよりは低い局所的最適解が存在します。 ここからは、山登り法と焼きなまし法が、この関数をどのように探索していくかを見ていきましょう。

山登り法による探索（失敗例）​

最初に、山登り法で探索します。意図的に局所解に陥りやすいよう、初期値を 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("❌ 課題: スタート地点によっては小さな山の頂上で止まってしまう。")

このコードは、current_x_hc を初期位置 8.0 としてスタートし、while True ループの中で現在位置の左右の点（neighbors）を評価します。そして、最もスコアが高い点を best_neighbor として見つけ、そこに移動します。もし、どの近傍点も現在のスコアを上回らなければ、それ以上改善できないため break してループを終了します。

実行結果​

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

この結果が示すように、探索は x≈8.3x \approx 8.3 の地点で終了しました。これはグラフ上の小さな山（局所的最適解）の頂上であり、より高い山（大域的最適解, x≈1.7x \approx 1.7）には到達できていません。このように、スタート地点によっては最良の解を見つけられないのが山登り法の課題です。

タブー探索による探索​

山登り法が局所解（x≈8.3x \approx 8.3）で止まってしまった初期値 8.0 からスタートし、タブーリストを使って大域的最適解へたどり着けるか試します。

# --- タブー探索（TS）のパラメータ設定 ---
tabu_tenure = 15      # タブーの期間（この手数だけ過去の解を記憶する）
max_iterations = 100  # 探索の最大繰り返し回数

# 初期解（山登り法が失敗した「8.0」をスタート地点とする）
current_x = 8.0
current_score = f(current_x)

# 探索全体を通しての最良解を記録する変数
best_x = current_x
best_score = current_score

# タブーリスト（最近訪れた解の記録）を初期化
tabu_list = []

print("--- タブー探索開始 ---")

for i in range(max_iterations):
    # 近傍の生成（今回は左右の点だけでなく、少し広めの範囲を近傍とします）
    neighbors = [current_x + step_size * d for d in [-3, -2, -1, 1, 2, 3]]
    valid_neighbors = [nx for nx in neighbors if x_min <= nx <= x_max]
    
    best_candidate = None
    best_candidate_score = -float('inf')
    
    for nx in valid_neighbors:
        score = f(nx)
        
        # 丸め誤差を防ぐため、小数点以下1桁でタブー判定
        nx_rounded = round(nx, 1)
        
        # タブーリストに含まれていない、またはアスピレーション条件（過去の全体ベストを更新）を満たすか
        is_tabu = nx_rounded in tabu_list
        aspiration = score > best_score
        
        if (not is_tabu) or aspiration:
            if score > best_candidate_score:
                best_candidate_score = score
                best_candidate = nx
                
    # 移動先がない場合（すべてタブーなど）は終了
    if best_candidate is None:
        break
        
    # 現在地を更新
    current_x = best_candidate
    current_score = best_candidate_score
    
    # タブーリストに現在の位置を追加
    tabu_list.append(round(current_x, 1))
    # リストが上限を超えたら、一番古い記憶を消す
    if len(tabu_list) > tabu_tenure:
        tabu_list.pop(0)
        
    # 全体のベストスコアを更新
    if current_score > best_score:
        best_score = current_score
        best_x = current_x

print(f"タブー探索の最適解: x = {best_x:.2f}, スコア = {best_score:.4f}")
print("⭕ 利点: 過去の軌跡を記憶することで、来た道を戻らずに局所解の谷を下ることができる。")

まず、タブー探索の挙動を制御する2つの主要なパラメータ、tabu_tenure（タブーリストの長さ）とmax_iterations（最大繰り返し回数）を設定します。探索は山登り法が局所解に陥ったcurrent_x = 8.0から開始し、探索全体で見つかった最も良い解をbest_xとbest_scoreに記録します。

forループの中で、探索が実行されます。

  1. 近傍の生成: 現在位置current_xの周辺から、複数の候補点（neighbors）を生成します。山登り法と異なり、少し離れた点も探索対象に含めています。
  2. 候補の評価: 各候補点nxについて、そのスコアを計算します。
  3. タブー判定とアスピレーション条件:
    • nx_rounded in tabu_listにより、その候補がタブーリスト（過去に訪問した点の記録）に含まれているか（is_tabu）を判定します。浮動小数点数の比較誤差を避けるため、round()で丸めてから判定しています。
    • score > best_scoreにより、その候補がこれまでの探索全体で見つかった最高スコアを更新するか（aspiration）を判定します。
  4. 最良候補の選択: (not is_tabu) or aspirationという条件で、候補点が「タブーではない」または「タブーであっても最高スコアを更新する（アスピレーション条件を満たす）」場合に、移動先の候補とします。その中で最もスコアが高いものをbest_candidateとして選びます。このルールにより、たとえ現在のスコアより悪化しても、タブーでなければ移動が許可されます。
  5. 状態の更新: current_xをbest_candidateに更新し、新しい位置をtabu_listに追加します。リストの長さがtabu_tenureを超えた場合は、tabu_list.pop(0)で最も古い記憶を削除します。
  6. 全体最適解の更新: もし新しいスコアがbest_scoreを上回れば、最適解を更新します。

このプロセスを繰り返すことで、短期的なループを防ぎながら、局所解の谷を越えて広範囲な探索を実現します。

この実装では、tabu_list に訪問済みの座標を記録し、そのリストの長さが tabu_tenure を超えたら古いものから削除（pop(0)）しています。近傍を評価する際、nx_rounded in tabu_list でタブー判定を行い、リストにない（または過去の最高スコアを更新する）候補の中で最も良いものを選んで移動し続けます。

実行結果​

--- タブー探索開始 ---
タブー探索の最適解: x = 1.30, スコア = 1.7596
⭕ 利点: 過去の軌跡を記憶することで、来た道を戻らずに局所解の谷を下ることができる。

山登り法では x≈8.3x \approx 8.3 で停止してしまいましたが、タブー探索は見事に谷を乗り越え、x≈1.7x \approx 1.7 付近の最も高い山（大域的最適解）を発見することができました。

探索軌跡の可視化​

タブー探索が局所解の罠をどのように回避したのか、グラフで軌跡を確認しましょう。

import math
import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib  # グラフ日本語表示用

# 評価関数（目的関数）
def f(x):
    return math.sin(x) + math.cos(0.5 * x)

# NumPy用の評価関数の定義（背景のグラフ描画用）
def f_np(x):
    return np.sin(x) + np.cos(0.5 * x)

# --- パラメータ設定 ---
x_min, x_max = 0.0, 10.0
step_size = 0.1
tabu_tenure = 15      # タブーリストの長さ
max_iterations = 100  # 最大探索回数

# --- タブー探索の軌跡シミュレーション ---
current_x = 8.0  # 山登り法が失敗した初期解
best_score = f(current_x)
tabu_list = []

# 軌跡を保存するリスト（スタート地点を初期登録）
path_x = [current_x]

for i in range(max_iterations):
    # 近傍の生成
    neighbors = [current_x + step_size * d for d in [-3, -2, -1, 1, 2, 3]]
    valid_neighbors = [nx for nx in neighbors if x_min <= nx <= x_max]
    
    best_candidate = None
    best_candidate_score = -float('inf')
    
    for nx in valid_neighbors:
        score = f(nx)
        nx_rounded = round(nx, 1)
        
        is_tabu = nx_rounded in tabu_list
        aspiration = score > best_score
        
        # タブーリストにない、または全体ベスト更新（アスピレーション）なら許可
        if (not is_tabu) or aspiration:
            if score > best_candidate_score:
                best_candidate_score = score
                best_candidate = nx
                
    if best_candidate is None:
        break
        
    current_x = best_candidate
    current_score = best_candidate_score
    
    # タブーリストの更新
    tabu_list.append(round(current_x, 1))
    if len(tabu_list) > tabu_tenure:
        tabu_list.pop(0)
        
    if current_score > best_score:
        best_score = current_score

    # 現在位置を軌跡リストに記録
    path_x.append(current_x)

# 軌跡のy座標を計算
path_y = [f(x) for x in path_x]

# --- グラフの描画 ---
# 背景となる目的関数のデータ生成
x_vals_np = np.linspace(0, 10, 200)
y_vals_np = f_np(x_vals_np)

plt.figure(figsize=(10, 6))
plt.plot(x_vals_np, y_vals_np, color='#1f77b4', linewidth=2, label='目的関数 f(x)')

# 軌跡を緑色でプロット
plt.plot(path_x, path_y, marker='o', color='green', markersize=4, linestyle='-', alpha=0.6, label='タブー探索の軌跡')

# スタート地点と最終到達地点を強調してプロット
plt.plot(path_x[0], path_y[0], marker='s', color='black', markersize=8, label='スタート地点')
plt.plot(path_x[-1], path_y[-1], marker='*', color='red', markersize=12, label='最終到達地点')

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()

このコードは、前のセクションで実行したタブー探索のアルゴリズムと基本的に同じですが、探索の各ステップで現在位置current_xをpath_xというリストに逐一記録する点が異なります。

探索ループが終了した後、path_xに記録された各x座標に対応するy座標をpath_yに計算します。 最後に、matplotlibライブラリを使い、背景に目的関数を描画した上で、plt.plot(path_x, path_y, ...)で探索の軌跡を緑色の線でプロットしています。スタート地点は四角（marker='s'）、最終到達地点は星印（marker='*）で強調表示することで、探索がどのように進んだかを視覚的に追跡できるようにしています。
実行結果軌跡を見ると、スタート地点から右側の小さな山の頂上に到達した後、山登り法のように停止せず、スコアが悪化するにもかかわらず谷を下って左へ移動していることがわかります。これは、「右側（来た道）に戻るのはタブー」として禁止されているため、消去法でスコアが下がる左側へ進むしかなかったからです。結果として谷を越え、より高い大域的最適解の山へと辿り着きました。 探索軌跡

まとめ​

本記事では、「記憶」を活用して局所的最適解を回避するメタヒューリスティクス「タブー探索（Tabu Search）」について解説しました。

  • タブーリストによる逆戻り防止: 過去に訪問した状態への遷移を一定期間禁止することで、探索が同じ場所をループするのを防ぎ、強制的に未探索の領域へ押し出します。
  • 改悪の許容とアスピレーション: タブーでない範囲で最良の選択肢を選び続けるため、結果的に谷を下る（改悪する）ことができます。また、圧倒的に良い解を見つけた場合は例外を認める柔軟性も持っています。

焼きなまし法が「確率と温度」を利用するのに対し、タブー探索は「リストによる決定的な制限」を利用します。問題の性質に応じて、これらのメタヒューリスティクスを使い分けたり、組み合わせたりすることが、実用的な最適化システムを構築する上での鍵となります。

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