启发式算法-禁忌搜索算法

禁忌搜索是一种可以用于解决组合优化问题的启发式算法，通过引入记忆机制跳出局部最优，避免重复搜索。该算法从一个初始解开始，通过邻域搜索策略来寻找当前解的邻域解，并在邻域解中选择一个最优解作为下一次迭代的当前解，为了避免算法陷入局部最优，引入禁忌表来记录已经访问过的操作，禁止算法在一定迭代次数内再次选择这些被禁忌的操作，另外算法可以设置一些特赦条件，使得被禁忌的操作可以解除禁忌，从而探索更优的解空间。

算法流程

旅行商问题
假设有 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;}
}