禁忌搜索（Tabu Search）是由Fred Glover提出的元启发式算法，通过引入”禁忌表”记录近期访问过的解，避免搜索陷入局部最优的循环。与模拟退火依赖概率接受劣解不同，禁忌搜索主动禁止回退到近期访问过的状态，强制探索新的搜索区域。本文用Java实现完整的禁忌搜索框架，并以旅行商问题（TSP）和”游戏地图资源布局优化”两个案例展示其在组合优化中的强大能力。
一、算法核心思想
禁忌搜索包含三个关键机制：
- 邻域结构：定义从当前解如何生成邻近解（如TSP中的2-opt交换）
- 禁忌表：记录近期执行过的移动或访问过的解，禁止回退
- ** aspiration准则**：当某个被禁忌的移动能产生优于历史最优的解时，破例允许
二、通用禁忌搜索框架
package com.algorithm.tabu;
import java.util.*;
/**
* 禁忌搜索通用框架
* 通过泛型支持各类组合优化问题
*/
public class TabuSearch<S, M> {
private final Neighborhood<S, M> neighborhood; // 邻域生成器
private final ObjectiveFunction<S> objective; // 目标函数
private final TabuList<M> tabuList; // 禁忌表
private final int maxIterations; // 最大迭代次数
public TabuSearch(Neighborhood<S, M> neighborhood,
ObjectiveFunction<S> objective,
TabuList<M> tabuList,
int maxIterations) {
this.neighborhood = neighborhood;
this.objective = objective;
this.tabuList = tabuList;
this.maxIterations = maxIterations;
}
/**
* 执行禁忌搜索
* @param initialSolution 初始解
* @return 搜索过程中的最优解
*/
public SearchResult<S> search(S initialSolution) {
S currentSolution = initialSolution;
S bestSolution = initialSolution;
double bestObjective = objective.evaluate(initialSolution);
List<Double> history = new ArrayList<>();
history.add(bestObjective);
for (int iteration = 0; iteration < maxIterations; iteration++) {
// 生成所有邻域解
List<Neighbor<S, M>> neighbors = neighborhood.getNeighbors(currentSolution);
Neighbor<S, M> bestNeighbor = null;
double bestNeighborValue = Double.POSITIVE_INFINITY;
boolean isMinimization = objective.isMinimization();
for (Neighbor<S, M> neighbor : neighbors) {
double value = objective.evaluate(neighbor.solution);
boolean isTabu = tabuList.isTabu(neighbor.move);
// Aspiration准则：如果被禁忌的移动能产生全局最优，则破例允许
boolean aspiration = (isMinimization && value < bestObjective) ||
(!isMinimization && value > bestObjective);
if (isTabu && !aspiration) {
continue; // 禁忌且不满足aspiration，跳过
}
// 选择最优的邻域解
if (bestNeighbor == null ||
(isMinimization && value < bestNeighborValue) ||
(!isMinimization && value > bestNeighborValue)) {
bestNeighbor = neighbor;
bestNeighborValue = value;
}
}
if (bestNeighbor == null) {
// 所有邻域解都被禁忌且不满足aspiration，提前终止
System.out.println("迭代 " + iteration + ": 所有移动被禁忌，搜索终止");
break;
}
// 执行移动
currentSolution = bestNeighbor.solution;
tabuList.add(bestNeighbor.move);
// 更新历史最优
if ((isMinimization && bestNeighborValue < bestObjective) ||
(!isMinimization && bestNeighborValue > bestObjective)) {
bestSolution = bestNeighbor.solution;
bestObjective = bestNeighborValue;
}
history.add(bestObjective);
if (iteration % 100 == 0) {
System.out.printf("迭代 %d: 当前最优 = %.2f, 禁忌表大小 = %d%n",
iteration, bestObjective, tabuList.size());
}
}
return new SearchResult<>(bestSolution, bestObjective, history);
}
// 接口定义
public interface Neighborhood<S, M> {
List<Neighbor<S, M>> getNeighbors(S solution);
}
public interface ObjectiveFunction<S> {
double evaluate(S solution);
boolean isMinimization();
}
public interface TabuList<M> {
void add(M move);
boolean isTabu(M move);
int size();
}
public static class Neighbor<S, M> {
public final S solution;
public final M move;
public Neighbor(S solution, M move) {
this.solution = solution;
this.move = move;
}
}
public static class SearchResult<S> {
public final S bestSolution;
public final double bestObjective;
public final List<Double> history;
public SearchResult(S bestSolution, double bestObjective, List<Double> history) {
this.bestSolution = bestSolution;
this.bestObjective = bestObjective;
this.history = history;
}
}
}
三、禁忌表实现
package com.algorithm.tabu;
import java.util.*;
/**
* 基于固定长度的循环队列禁忌表
* 记录最近执行过的移动，防止回退
*/
public class FixedSizeTabuList<M> implements TabuSearch.TabuList<M> {
private final Deque<M> tabuQueue;
private final Set<M> tabuSet;
private final int maxSize;
public FixedSizeTabuList(int maxSize) {
this.maxSize = maxSize;
this.tabuQueue = new LinkedList<>();
this.tabuSet = new HashSet<>();
}
@Override
public void add(M move) {
if (tabuQueue.size() >= maxSize) {
M removed = tabuQueue.pollFirst();
tabuSet.remove(removed);
}
tabuQueue.addLast(move);
tabuSet.add(move);
}
@Override
public boolean isTabu(M move) {
return tabuSet.contains(move);
}
@Override
public int size() {
return tabuQueue.size();
}
}
/**
* 基于移动属性的禁忌表（更灵活，可禁忌相似移动）
*/
public class AttributeTabuList implements TabuSearch.TabuList<int[]> {
private final Deque<int[]> tabuQueue;
private final int maxSize;
private final int tabuTenure; // 禁忌任期（移动涉及的属性被禁忌的迭代次数）
public AttributeTabuList(int maxSize, int tabuTenure) {
this.maxSize = maxSize;
this.tabuTenure = tabuTenure;
this.tabuQueue = new LinkedList<>();
}
@Override
public void add(int[] move) {
tabuQueue.addLast(move.clone());
if (tabuQueue.size() > maxSize) {
tabuQueue.pollFirst();
}
}
@Override
public boolean isTabu(int[] move) {
// 如果移动中涉及的任何元素在禁忌表中，则视为禁忌
for (int[] tabuMove : tabuQueue) {
if (sharesAttribute(move, tabuMove)) {
return true;
}
}
return false;
}
private boolean sharesAttribute(int[] move1, int[] move2) {
// 两个移动共享至少一个元素位置则认为相关
for (int m1 : move1) {
for (int m2 : move2) {
if (m1 == m2) return true;
}
}
return false;
}
@Override
public int size() {
return tabuQueue.size();
}
}
四、旅行商问题（TSP）求解
package com.algorithm.tabu;
import java.util.*;
/**
* TSP问题的禁忌搜索实现
* 邻域结构：2-opt交换（反转路径中的一段子序列）
*/
public class TSPTabuSearch {
private final double[][] distanceMatrix;
private final int numCities;
public TSPTabuSearch(double[][] distanceMatrix) {
this.distanceMatrix = distanceMatrix;
this.numCities = distanceMatrix.length;
}
/**
* 2-opt交换：反转路径中from到to之间的子序列
*/
public static class TwoOptMove {
final int from;
final int to;
TwoOptMove(int from, int to) {
this.from = from;
this.to = to;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof TwoOptMove)) return false;
TwoOptMove that = (TwoOptMove) o;
return from == that.from && to == that.to;
}
@Override
public int hashCode() {
return Objects.hash(from, to);
}
}
/**
* 2-opt邻域生成器
*/
public class TwoOptNeighborhood implements TabuSearch.Neighborhood<int[], TwoOptMove> {
@Override
public List<TabuSearch.Neighbor<int[], TwoOptMove>> getNeighbors(int[] tour) {
List<TabuSearch.Neighbor<int[], TwoOptMove>> neighbors = new ArrayList<>();
// 随机采样部分2-opt移动，避免邻域过大
Random rand = new Random();
int sampleSize = Math.min(numCities * (numCities - 1) / 2, 500);
for (int s = 0; s < sampleSize; s++) {
int i = rand.nextInt(numCities);
int j = rand.nextInt(numCities);
if (i == j || Math.abs(i - j) == 1 ||
(i == 0 && j == numCities - 1) ||
(j == 0 && i == numCities - 1)) {
continue;
}
if (i > j) {
int tmp = i; i = j; j = tmp;
}
int[] newTour = apply2Opt(tour, i, j);
neighbors.add(new TabuSearch.Neighbor<>(newTour, new TwoOptMove(i, j)));
}
return neighbors;
}
}
/**
* 执行2-opt交换
*/
private int[] apply2Opt(int[] tour, int from, int to) {
int[] newTour = tour.clone();
// 反转from+1到to之间的路径段
int left = from + 1;
int right = to;
while (left < right) {
int tmp = newTour[left];
newTour[left] = newTour[right];
newTour[right] = tmp;
left++;
right--;
}
return newTour;
}
/**
* TSP目标函数
*/
public class TSPObjective implements TabuSearch.ObjectiveFunction<int[]> {
@Override
public double evaluate(int[] tour) {
double total = 0;
for (int i = 0; i < numCities; i++) {
int from = tour[i];
int to = tour[(i + 1) % numCities];
total += distanceMatrix[from][to];
}
return total;
}
@Override
public boolean isMinimization() {
return true;
}
}
/**
* 生成随机初始解
*/
public int[] generateInitialSolution() {
int[] tour = new int[numCities];
for (int i = 0; i < numCities; i++) tour[i] = i;
Random rand = new Random();
for (int i = numCities - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int tmp = tour[i]; tour[i] = tour[j]; tour[j] = tmp;
}
return tour;
}
/**
* 主求解方法
*/
public TabuSearch.SearchResult<int[]> solve(int maxIterations, int tabuSize) {
int[] initial = generateInitialSolution();
TabuSearch<int[], TwoOptMove> ts = new TabuSearch<>(
new TwoOptNeighborhood(),
new TSPObjective(),
new FixedSizeTabuList<>(tabuSize),
maxIterations
);
return ts.search(initial);
}
public static void main(String[] args) {
// 创建20个城市的随机TSP实例
int n = 20;
Random rand = new Random(123);
double[][] dist = new double[n][n];
// 随机生成城市坐标
double[][] coords = new double[n][2];
for (int i = 0; i < n; i++) {
coords[i][0] = rand.nextDouble() * 100;
coords[i][1] = rand.nextDouble() * 100;
}
// 计算欧几里得距离矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double dx = coords[i][0] - coords[j][0];
double dy = coords[i][1] - coords[j][1];
dist[i][j] = Math.sqrt(dx * dx + dy * dy);
}
}
System.out.println("=== TSP禁忌搜索求解 ===\n");
System.out.println("城市数量: " + n);
TSPTabuSearch tsp = new TSPTabuSearch(dist);
TabuSearch.SearchResult<int[]> result = tsp.solve(2000, 50);
System.out.printf("\n最优路径长度: %.2f%n", result.bestObjective);
System.out.print("最优路径: ");
for (int city : result.bestSolution) {
System.out.print(city + " -> ");
}
System.out.println(result.bestSolution[0]);
}
}
五、游戏地图资源布局优化
package com.algorithm.tabu;
import java.util.*;
/**
* 游戏地图资源布局优化：禁忌搜索求解
* 目标：在地图上放置N个资源点（如宝箱、怪物营地），使得玩家访问路径最短，
* 同时满足资源点之间的最小距离约束
*/
public class MapResourcePlacement {
private final int mapWidth;
private final int mapHeight;
private final int numResources;
private final double minDistance; // 资源点之间的最小距离
private final Random rand = new Random(42);
public MapResourcePlacement(int mapWidth, int mapHeight,
int numResources, double minDistance) {
this.mapWidth = mapWidth;
this.mapHeight = mapHeight;
this.numResources = numResources;
this.minDistance = minDistance;
}
/**
* 解的表示：每个资源点的(x,y)坐标数组
*/
public static class Placement {
final int[][] positions; // positions[i] = {x, y}
Placement(int[][] positions) {
this.positions = new int[positions.length][];
for (int i = 0; i < positions.length; i++) {
this.positions[i] = positions[i].clone();
}
}
Placement clonePlacement() {
return new Placement(this.positions);
}
}
/**
* 移动：将一个资源点移动到新位置
*/
public static class Move {
final int resourceIndex;
final int oldX, oldY;
final int newX, newY;
Move(int resourceIndex, int oldX, int oldY, int newX, int newY) {
this.resourceIndex = resourceIndex;
this.oldX = oldX;
this.oldY = oldY;
this.newX = newX;
this.newY = newY;
}
}
/**
* 邻域生成器：随机移动一个资源点到附近位置
*/
public class PlacementNeighborhood implements TabuSearch.Neighborhood<Placement, Move> {
@Override
public List<TabuSearch.Neighbor<Placement, Move>> getNeighbors(Placement solution) {
List<TabuSearch.Neighbor<Placement, Move>> neighbors = new ArrayList<>();
for (int attempt = 0; attempt < 100; attempt++) {
int idx = rand.nextInt(numResources);
int oldX = solution.positions[idx][0];
int oldY = solution.positions[idx][1];
// 在周围5格范围内随机移动
int newX = Math.max(0, Math.min(mapWidth - 1,
oldX + rand.nextInt(11) - 5));
int newY = Math.max(0, Math.min(mapHeight - 1,
oldY + rand.nextInt(11) - 5));
if (newX == oldX && newY == oldY) continue;
int[][] newPositions = new int[numResources][];
for (int i = 0; i < numResources; i++) {
newPositions[i] = solution.positions[i].clone();
}
newPositions[idx][0] = newX;
newPositions[idx][1] = newY;
neighbors.add(new TabuSearch.Neighbor<>(
new Placement(newPositions),
new Move(idx, oldX, oldY, newX, newY)
));
}
return neighbors;
}
}
/**
* 目标函数：最小化玩家从起点访问所有资源的总路径长度
* 同时惩罚违反最小距离约束的布局
*/
public class PlacementObjective implements TabuSearch.ObjectiveFunction<Placement> {
@Override
public double evaluate(Placement placement) {
// 计算近似TSP路径长度（最近邻启发式）
double pathLength = computeNearestNeighborPath(placement);
// 惩罚项：距离过近的资源对
double penalty = 0;
for (int i = 0; i < numResources; i++) {
for (int j = i + 1; j < numResources; j++) {
double dist = distance(placement.positions[i], placement.positions[j]);
if (dist < minDistance) {
penalty += (minDistance - dist) * (minDistance - dist) * 100;
}
}
}
return pathLength + penalty;
}
private double computeNearestNeighborPath(Placement placement) {
boolean[] visited = new boolean[numResources];
int current = 0; // 从第一个资源开始
visited[current] = true;
double total = 0;
int visitedCount = 1;
while (visitedCount < numResources) {
double minDist = Double.MAX_VALUE;
int next = -1;
for (int i = 0; i < numResources; i++) {
if (!visited[i]) {
double d = distance(placement.positions[current],
placement.positions[i]);
if (d < minDist) {
minDist = d;
next = i;
}
}
}
total += minDist;
visited[next] = true;
current = next;
visitedCount++;
}
return total;
}
@Override
public boolean isMinimization() {
return true;
}
}
private double distance(int[] a, int[] b) {
double dx = a[0] - b[0];
double dy = a[1] - b[1];
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 生成随机初始布局
*/
public Placement generateInitialPlacement() {
int[][] positions = new int[numResources][2];
for (int i = 0; i < numResources; i++) {
positions[i][0] = rand.nextInt(mapWidth);
positions[i][1] = rand.nextInt(mapHeight);
}
return new Placement(positions);
}
/**
* 自定义禁忌表：禁忌最近移动过的资源索引
*/
public class ResourceTabuList implements TabuSearch.TabuList<Move> {
private final Deque<Integer> tabuQueue = new LinkedList<>();
private final int maxSize;
ResourceTabuList(int maxSize) {
this.maxSize = maxSize;
}
@Override
public void add(Move move) {
tabuQueue.addLast(move.resourceIndex);
if (tabuQueue.size() > maxSize) {
tabuQueue.pollFirst();
}
}
@Override
public boolean isTabu(Move move) {
return tabuQueue.contains(move.resourceIndex);
}
@Override
public int size() {
return tabuQueue.size();
}
}
public TabuSearch.SearchResult<Placement> solve(int maxIterations, int tabuSize) {
Placement initial = generateInitialPlacement();
TabuSearch<Placement, Move> ts = new TabuSearch<>(
new PlacementNeighborhood(),
new PlacementObjective(),
new ResourceTabuList(tabuSize),
maxIterations
);
return ts.search(initial);
}
public static void main(String[] args) {
System.out.println("=== 游戏地图资源布局优化 ===\n");
// 100x100地图上放置15个资源点
MapResourcePlacement problem = new MapResourcePlacement(100, 100, 15, 15.0);
TabuSearch.SearchResult<Placement> result = problem.solve(1000, 10);
System.out.printf("最优布局得分: %.2f%n", result.bestObjective);
System.out.println("资源点坐标:");
for (int i = 0; i < result.bestSolution.positions.length; i++) {
int[] pos = result.bestSolution.positions[i];
System.out.printf(" 资源%d: (%d, %d)%n", i, pos[0], pos[1]);
}
}
}
六、复杂度与参数调优
| 参数 | 作用 | 典型取值 |
|---|---|---|
| 禁忌表长度 | 控制记忆深度 | 7-20或问题规模的1/4 |
| 邻域大小 | 每轮评估的候选解数 | 50-500 |
| 最大迭代次数 | 终止条件 | 1000-10000 |
| Aspiration阈值 | 破例条件 | 优于历史最优即可 |
复杂度分析：
– 每轮迭代：O(N_neighbors × Evaluate)
– 总时间：O(Iterations × N_neighbors × Evaluate)
– 禁忌表查询：O(1)（哈希实现）
七、与其他元启发式的对比
| 算法 | 核心机制 | 优点 | 缺点 |
|---|---|---|---|
| 禁忌搜索 | 记忆禁忌+局部探索 | 收敛快，参数少 | 依赖邻域设计 |
| 模拟退火 | 概率接受劣解 | 跳出局部最优能力强 | 降温参数敏感 |
| 遗传算法 | 种群进化 | 全局搜索能力强 | 编码设计复杂 |
| 蚁群算法 | 信息素正反馈 | 适合图/路径问题 | 收敛慢 |
禁忌搜索最适合邻域结构明确、需要精细局部探索的组合优化问题，如调度、路由、布局等。在游戏开发中，可用于：地图生成优化、AI策略参数调优、资源分配、关卡难度平衡等场景。
