📝
巡回セールスマン問題をいろいろな手法で解いてみる③：タブーサーチ
はじめに
第三弾です。
引き続き、巡回セールスマン問題を題材にし、最適化を行います。
巡回セールスマン問題をいろいろな手法で解いてみる①
巡回セールスマン問題をいろいろな手法で解いてみる②
初回ではpulpを用いて厳密解を確認しました。
前回では最もシンプルな局所最適化である山登り法を紹介しました。
今回は前回の山登り法をタブーサーチに発展させます。
タブーサーチ
山登り法とタブーサーチ
山登り法は、前回まとめたように、
- 暫定解から近傍を生成
- 近傍の中から最も評価値の高いものに遷移
を繰り返す手法です。
前回の記事の解の更新過程からも少しずつ解が良くなっていき、近似解が生成されることを確認できたかと思います。
一方で、生成された近似解はpulpで生成された厳密解よりも悪い結果であることも確認できました。
では、なぜ厳密解にならなかったのでしょうか？
これを解析するために、繰り返し数と暫定解の目的関数値を示すグラフを見てみましょう。
青線が交換近傍、オレンジ戦が2-opt近傍の探索結果です。
序盤で勢いよく解が更新されていることが確認できます。
ただ、イテレーション数が50あたりから解の更新が止まってしまっています。
これは、暫定解が局所解にとらわれてしまっているためです。
暫定解から生成されうる近傍解がすべて暫定解よりも悪ければ、解の遷移は生じません。
したがって、厳密解に遷移するためには、時には解の改悪を許さなければならない場合もあるということです。
所謂ところの局所最適解にとらわれている状況です。
タブーサーチでは解の改悪を許すことで局所最適解から脱出する手法の一つです。
タブーサーチ
タブーサーチと山登り法の主な違いはタブーリストの有無です。
一定数の解をプールしておくタブーリストを使い、一定期間そこへの立ち入りを禁じることで、ループを回避しつつ未知の領域を探索させます。
- ランダムに初期解を生成
- 終了条件（繰り返し数が上限になる）を満たすまで3～5から
- 現在の解をもとに近傍解を生成する
- 近傍解を評価する
- 現在の解を近傍解の中で最もよい解に更新する
実装コード（抜粋）
メインの探索処理です。現在の解より悪くなる移動も許容する点が山登り法との大きな違いです。
tabu_search.py
def tabu_search(self, ini_route, iteration, instance, tabu_length, neighbor_ope, change_route, word):
best_cost = float('inf')
current_cost = self.cal_cost(ini_route, instance)
route = ini_route.copy()
best_route = ini_route.copy()
tabu_list = self.Tabu_list(tabu_length)
tabu_list.add(route)
for k in range(iteration):
neighbors = []
# 近傍解を100個サンプリング
for _ in range(100):
index_i, index_j = random.sample(range(instance.n), 2)
# 変化量（delta）を計算
delta = neighbor_ope(index_i, index_j, route, instance)
neighbors.append([delta, index_i, index_j])
# サンプルの中で最も良い（マシな）移動を選択
neighbors.sort(key=lambda x: x[0])
for delta, index_i, index_j in neighbors:
tmp_route = change_route(route.copy(), index_i, index_j)
# タブーリストにない移動なら確定
if not tabu_list.check(tmp_route):
tabu_list.add(tmp_route)
current_cost += delta
route = tmp_route.copy()
# 全期間通しての最良解を更新
if current_cost < best_cost:
best_cost = current_cost
best_route = route.copy()
break # 移動が決定したのでループを抜ける
return {'tour': best_route, 'cost': best_cost}
実行結果
都市数40、イテレーション数300、タブー期間1という設定で、「交換近傍」と「2-opt近傍」の2パターンを比較しました。
最終的な目的関数値（移動距離）
交換近傍を用いたタブー探索：627
2-opt近傍を用いたタブー探索：534
やはり、近傍操作そのものが強力な 2-opt を組み込んだほうが、より短い経路を見つけることができました。
考察
タブー探索の挙動を追うと、山登り法では停止してしまうような場面でも、一時的にコストを悪化させながら探索を継続している様子が見て取れます。
今回はタブー期間を 10 としましたが、この値を調整したり、タブーリストに「解そのもの」ではなく「入れ替えた枝のペア」などを保存するように工夫することで、さらに性能を向上させることが可能です。
まとめ
単純な山登り法に「記憶」の概念を追加するだけで、探索能力を大幅に強化できるのがタブー探索の面白いところです。
今回のコードでは、neighbor_ope（コスト変化の計算）と change_route（ルートの更新）を引数として渡すことで、近傍操作を自由に入れ替えられるように設計しました。TSP以外の組み合わせ最適化問題にも応用しやすい形になっています。
次回は、また別のメタヒューリスティクス（焼きなまし法など）についても触れていきたいと思います！
参考コード全体：
tabu_search.py
import math
import random
import time
import os
import networkx as nx
from matplotlib import pyplot as plt
from collections import deque
# --- 問題の設定を管理するクラス ---
class Instance:
"""都市の数、座標、および距離行列を保持する"""
def __init__(self, n):
random.seed(111) # 再現性のためにシードを固定
self.n = n
# 0-100の範囲でランダムな座標を生成
self.points = [[random.randint(0, 100), random.randint(0, 100)] for _ in range(n)]
# 距離行列（i番目とj番目の都市間の距離）を計算
self.cost = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
# ユークリッド距離の計算
dist = int(math.sqrt((self.points[i][0] - self.points[j][0])**2 +
(self.points[i][1] - self.points[j][1])**2))
self.cost[i][j] = dist
self.cost[j][i] = dist
# --- タブー探索のアルゴリズムを管理するクラス ---
class Solve:
def initial_route(self, instance):
"""初期解として都市番号順のルートを作成"""
return list(range(instance.n))
def cal_cost(self, route, instance):
"""現在の経路の総距離を計算"""
sum_cost = 0
n = instance.n
for i in range(n - 1):
sum_cost += instance.cost[route[i]][route[i + 1]]
sum_cost += instance.cost[route[n - 1]][route[0]] # 始点に戻る
return sum_cost
def get_cost(self, index_i, index_j, route, instance):
"""インデックスが端に来た際の処理を含めて距離を返す"""
if index_i == instance.n: index_i = 0
if index_j == instance.n: index_j = 0
return instance.cost[route[index_i]][route[index_j]]
# --- 近傍操作1：交換 (Exchange) ---
def exchange_neighbor(self, index_i, index_j, route, instance):
"""2つの要素を入れ替えた時のコスト変化量(delta)を計算"""
n = instance.n
delta = 0
# 隣接判定と変化する枝の計算
if(index_i == index_j - 1 or index_i == index_j + n - 1):
delta -= (self.get_cost(index_i - 1, index_i, route, instance) + self.get_cost(index_j, index_j + 1, route, instance))
delta += (self.get_cost(index_i - 1, index_j, route, instance) + self.get_cost(index_i, index_j + 1, route, instance))
elif(index_i == index_j + 1 or index_j == index_i + n - 1):
delta -= (self.get_cost(index_j - 1, index_j, route, instance) + self.get_cost(index_i, index_i + 1, route, instance))
delta += (self.get_cost(index_j - 1, index_i, route, instance) + self.get_cost(index_j, index_i + 1, route, instance))
else:
delta -= (self.get_cost(index_i - 1, index_i, route, instance) + self.get_cost(index_i, index_i + 1, route, instance))
delta += (self.get_cost(index_j - 1, index_i, route, instance) + self.get_cost(index_i, index_j + 1, route, instance))
delta -= (self.get_cost(index_j - 1, index_j, route, instance) + self.get_cost(index_j, index_j + 1, route, instance))
delta += (self.get_cost(index_i - 1, index_j, route, instance) + self.get_cost(index_j, index_i + 1, route, instance))
return delta
def exchange_route(self, route, index_i, index_j):
"""要素を入れ替えた新しい経路リストを返す"""
new_route = route.copy()
new_route[index_i], new_route[index_j] = new_route[index_j], new_route[index_i]
return new_route
# --- 近傍操作2：2-opt ---
def two_opt_neighbor(self, index_i, index_j, route, instance):
"""2本の枝を繋ぎ替えた時のコスト変化量を計算"""
if index_i > index_j: index_i, index_j = index_j, index_i
delta = 0
if not (index_i == 0 and index_j == instance.n-1):
delta -= (self.get_cost(index_i - 1, index_i, route, instance) + self.get_cost(index_j, index_j + 1, route, instance))
delta += (self.get_cost(index_i - 1, index_j, route, instance) + self.get_cost(index_i, index_j + 1, route, instance))
return delta
def two_opt_route(self, route, index_i, index_j):
"""指定区間を反転させた新しい経路リストを返す"""
if index_i > index_j: index_i, index_j = index_j, index_i
new_route = route.copy()
new_route[index_i:index_j+1] = reversed(new_route[index_i:index_j+1])
return new_route
# --- タブー探索本体 ---
def tabu_search(self, ini_route, iteration, instance, tabu_length, neighbor_ope, change_route, word):
"""
タブー探索の実装
- neighbor_ope: 近傍評価関数
- change_route: ルート更新関数
"""
# 保存用フォルダの作成
dir_name = 'Tabu' + word + '_fig'
if not os.path.exists(dir_name): os.makedirs(dir_name)
# 初期値の設定
current_route = ini_route.copy()
current_cost = self.cal_cost(current_route, instance)
best_route = current_route.copy()
best_cost = current_cost
# タブーリストの初期化（操作のペアを保存）
tabu_list = deque(maxlen=tabu_length)
iteration_values = []
fig_index = 0
gen_fig(instance, best_route, f"{dir_name}/{fig_index:04}.png")
for k in range(iteration):
neighbors = []
# 1. 近傍候補をランダムにサンプリング
for _ in range(100):
i, j = random.sample(range(instance.n), 2)
delta = neighbor_ope(i, j, current_route, instance)
neighbors.append((delta, i, j))
# 2. 改善量の大きい順（deltaが小さい順）にソート
neighbors.sort(key=lambda x: x[0])
# 3. 非タブー解の中から最良の移動を選択
for delta, i, j in neighbors:
# 操作を特定するためのペア（ソートして一意にする）
op = tuple(sorted((i, j)))
# タブーリストにない、または最高値を更新する場合（吸引基準）
if op not in tabu_list or (current_cost + delta < best_cost):
# 移動実行
current_route = change_route(current_route, i, j)
current_cost += delta
tabu_list.append(op) # 新しい操作をタブーに追加
# 全体最良解の更新
if current_cost < best_cost:
best_cost = current_cost
best_route = current_route.copy()
fig_index += 1
gen_fig(instance, best_route, f"{dir_name}/{fig_index:04}.png")
break # 今回のステップの移動を決定
iteration_values.append(best_cost)
return {'tour': best_route, 'cost': best_cost, 'iteration_values': iteration_values}
def plot(self, results, iteration):
"""コストの収束グラフを表示・保存"""
plt.figure(figsize=(10, 6))
for i, res in enumerate(results):
label_name = "Exchange" if i == 0 else "2-opt"
plt.plot(range(iteration), res['iteration_values'], label=label_name)
plt.xlabel('Iteration')
plt.ylabel('Best Cost (Total Distance)')
plt.title('Optimization Process (Tabu Search)')
plt.legend()
plt.grid(True)
plt.savefig("result.png")
plt.close()
# --- 経路の可視化関数 ---
def gen_fig(instance, path, fig_name):
plt.figure(figsize=(8, 8))
G = nx.Graph()
G.add_nodes_from(range(instance.n))
for i in range(instance.n):
G.add_edge(path[i-1], path[i])
nx.draw_networkx(G, pos=instance.points, node_color="cyan", node_size=200, with_labels=False)
plt.title(f"Route Visualization: {fig_name}")
plt.savefig(fig_name)
plt.close()
# --- メイン処理 ---
def main():
# パラメータ設定
problem_size = 40 # 都市数
iteration = 300 # 試行回数
tabu_length = 10 # タブー期間（重要！）
instance = Instance(problem_size)
solve = Solve()
ini_route = solve.initial_route(instance)
print(f"--- 探索開始 (都市数: {problem_size}, イテレーション: {iteration}) ---")
# 1. 交換近傍を用いたタブー探索
start_time = time.time()
res_ex = solve.tabu_search(ini_route, iteration, instance, tabu_length, solve.exchange_neighbor, solve.exchange_route, 'Exchange')
print(f"【交換近傍】コスト: {res_ex['cost']}, 時間: {time.time()-start_time:.2f}s")
# 2. 2-opt近傍を用いたタブー探索
start_time = time.time()
res_2opt = solve.tabu_search(ini_route, iteration, instance, tabu_length, solve.two_opt_neighbor, solve.two_opt_route, 'TwoOpt')
print(f"【2-opt近傍】コスト: {res_2opt['cost']}, 時間: {time.time()-start_time:.2f}s")
# グラフの出力
solve.plot([res_ex, res_2opt], iteration)
print("--- 探索完了 (result.png を確認してください) ---")
if __name__ == '__main__':
main()
Discussion