禁忌搜索是一種可以用于解決組合優化問題的啟發式算法，通過引入記憶機制跳出局部最優，避免重復搜索。該算法從一個初始解開始，通過鄰域搜索策略來尋找當前解的鄰域解，并在鄰域解中選擇一個最優解作為下一次迭代的當前解，為了避免算法陷入局部最優，引入禁忌表來記錄已經訪問過的操作，禁止算法在一定迭代次數內再次選擇這些被禁忌的操作，另外算法可以設置一些特赦條件，使得被禁忌的操作可以解除禁忌，從而探索更優的解空間。

算法流程

旅行商問題
假設有 4 個城市A、B、C、D，旅行商需要從一個城市出發，遍歷所有城市且每個城市只經過一次，最后回到起始城市，要求找到最短的旅行路線，城市距離矩陣如下，最短的旅行路線為 A → B → D → C → A

禁忌搜索代碼

public class TabuSearchTSP {// 城市距離矩陣private static final int[][] DISTANCE_MATRIX = {{0, 2, 9, 10},{2, 0, 6, 4},{9, 6, 0, 8},{10, 4, 8, 0}};private static final int NUM_CITIES = 4;      // 城市數量private static final int TABU_TENURE = 2;     // 禁忌表長度private static final int MAX_ITERATIONS = 100; // 最大迭代次數public static void main(String[] args) {int[] bestSolution = tabuSearch();System.out.println("最優路徑: " + formatPath(bestSolution));System.out.println("最短距離: " + calculateDistance(bestSolution));}private static String formatPath(int[] path) {String[] cities = {"A", "B", "C", "D"};StringBuilder sb = new StringBuilder();for (int idx : path) {sb.append(cities[idx]).append(" → ");}sb.append(cities[0]);return sb.toString();}// 禁忌搜索核心算法private static int[] tabuSearch() {// 初始化解int[] currentSolution = generateInitialSolution();int[] bestSolution = currentSolution.clone();int bestDistance = calculateDistance(bestSolution);// 禁忌表Queue<String> tabuList = new LinkedList<>();// 迭代搜索for (int iter = 0; iter < MAX_ITERATIONS; iter++) {int[] bestCandidate = null;int bestCandidateDist = Integer.MAX_VALUE;String move = null;// 生成鄰域解for (int i = 1; i < NUM_CITIES; i++) {for (int j = i+1; j < NUM_CITIES; j++) {// 避免重復交換String swapKey = i + "-" + j;// 生成候選解int[] candidate = currentSolution.clone();swap(candidate, i, j);int candidateDist = calculateDistance(candidate);// 檢查是否滿足特赦的條件boolean isAspiration = candidateDist < bestDistance;// 選擇最優候選解或者滿足特赦條件的候選解if (!tabuList.contains(swapKey) || isAspiration) {if (candidateDist < bestCandidateDist) {bestCandidate = candidate.clone();bestCandidateDist = candidateDist;move = swapKey;}}}}// 更新當前解if (bestCandidate != null) {currentSolution = bestCandidate.clone();// 更新禁忌表tabuList.add(move);if (tabuList.size() > TABU_TENURE) {tabuList.poll();}// 更新全局最優解if (bestCandidateDist < bestDistance) {bestSolution = bestCandidate.clone();bestDistance = bestCandidateDist;}}}return bestSolution;}private static int[] generateInitialSolution() {int[] solution = new int[NUM_CITIES];for (int i = 0; i < NUM_CITIES; i++) {solution[i] = i;}return solution;}private static void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;}// 計算路徑總距離private static int calculateDistance(int[] path) {int distance = 0;for (int i = 0; i < NUM_CITIES; i++) {int from = path[i];int to = path[(i+1)%NUM_CITIES];distance += DISTANCE_MATRIX[from][to];}return distance;}
}