Mímisbrunnr知恵の泉

← 数理最適化 一覧

🎓 レベル：標準　|　重要度：B（標準）

📎 前提：局所探索と近傍　|　関連：焼きなまし法

要点（BLUF）

概念 ── 「来た道を禁じる」

山登り（局所探索と近傍）は局所最適で止まる。焼きなまし（焼きなまし法）は確率で抜ける。タブー探索（Glover）は第3の道 ── 常に近傍の最良へ動く（悪化も受け入れる）が、最近訪れた解を「タブーリスト」に入れて一定期間禁止する。

局所最適に来ても、そこから最良の隣（＝少し悪化する隣）へ強制的に動き、その動きをタブーにする。すると元の局所最適へ戻れず、坂を登り切って別の谷へ抜けられる。記憶（短期メモリ）が、確率の代わりに脱出を生む。

graph TD
  A["現在解"] --> B["近傍を全部評価"]
  B --> C["タブーでない最良の隣を選ぶ (悪化も可)"]
  C --> D["そこへ移動し タブーリストに追加"]
  D --> E{"タブーリスト満杯?"}
  E -->|"はい"| F["最古のタブーを解除"]
  F --> B
  E -->|"いいえ"| B

主要素

Pythonで脱出を確認

山登りが −7.05-7.05 で止まる初期点（局所探索と近傍 の x=−12x=-12）から、タブー探索を走らせる。タブー探索は乱数を使わず 決定論的（同じ初期点なら同じ結果）。

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 tabu_search(start_idx, tabu_len=20, steps=500, nbhd=4):
    i = start_idx
    best_i = i
    tabu = [i]
    for step in range(steps):
        # 近傍(前後nbhd)で、タブーでない最良の隣を選ぶ(悪化も許す)
        cands = [j for j in range(i-nbhd, i+nbhd+1)
                 if 0 <= j < len(xs) and j != i and j not in tabu]
        if not cands:
            tabu = tabu[-(tabu_len//2):]    # 行き詰まったらタブーを一部解除
            continue
        i = min(cands, key=lambda k: fvals[k])   # タブー外の最良へ移動
        tabu.append(i)
        if len(tabu) > tabu_len:
            tabu.pop(0)                     # 最古のタブーを解除
        if fvals[i] < fvals[best_i]:
            best_i = i                      # 最良解を記録
    return best_i

print(f"参照(全探索)最小: x={xs[np.argmin(fvals)]:.3f}, f={fvals.min():.4f}")
r = tabu_search(60)
print(f"タブー探索(初期x=-12): x={xs[r]:+.3f}, f={fvals[r]:.4f}")

実行結果：

参照(全探索)最小: x=-1.450, f=-1.7752
タブー探索(初期x=-12): x=-1.450, f=-1.7752

山登りなら −7.05-7.05 で止まる初期点から、タブーリストが「来た道」を塞ぐことで局所最適を抜け、大域最適 x=−1.45x=-1.45 に到達。乱数なしで脱出できるのがタブー探索の特徴で、再現性が高い。

焼きなまし vs タブー探索

焼きなまし法タブー探索
脱出の仕組み確率的に悪化を受理記憶で来た道を禁止
乱数必須（確率）基本は決定論的
主パラメータ温度・冷却スケジュールタブーリスト長・近傍
近傍の見方ランダムに1つ全近傍を評価し最良
向く問題連続・大きな探索空間組合せ（スケジューリング等）

数式の直観的意味

タブー探索の核心は「探索の軌跡そのものを状態に持つ」こと。山登りや SA が現在解だけを見る 記憶なし（マルコフ的） なのに対し、タブー探索は直近の履歴を記憶し、それを使って探索を制御する 非マルコフ的な手法。局所最適に来たとき、SA は「サイコロを振って運良く登る」が、タブー探索は「最良の隣（＝最も浅い登り）へ確実に進み、戻り道を塞ぐ」。これは盆地の縁を確実に乗り越える効率的な戦術で、特に組合せ問題（ジョブショップ・配車）で強い。タブーリスト長は「どれだけ過去を覚えるか」で、短いと堂々巡り、長いと自由度を失う ── このメモリ長の調整が、探索の粘り強さを決める。

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

関連ノート