基于禁忌搜索算法的TSP问题最优路径搜索matlab仿真

clc; clear; close all;

%% 参数设置
numCities = 20;          % 城市数量
maxIter = 500;           % 最大迭代次数
tabuLen = 10;            % 禁忌表长度

%% 随机生成城市坐标
city = rand(numCities,2)*100;

%% 计算距离矩阵
distMat = squareform(pdist(city));

%% 初始解（随机路径）
curSolution = randperm(numCities);
curCost = calcCost(curSolution, distMat);

bestSolution = curSolution;
bestCost = curCost;

%% 禁忌表初始化
tabuList = [];

%% Tabu Search 主循环
for iter = 1:maxIter
    % 生成邻域解（两城市交换）
    neighbors = [];
    neighborCosts = [];
    moves = [];
    for i = 1:numCities-1
        for j = i+1:numCities
            tmp = curSolution;
            tmp([i j]) = tmp([j i]);  % 交换城市
            move = [i j];
            
            % 检查是否在禁忌表中
            if ~ismember(move, tabuList, 'rows')
                neighbors = [neighbors; tmp];
                neighborCosts = [neighborCosts; calcCost(tmp, distMat)];
                moves = [moves; move];
            end
        end
    end
    
    % 选择邻域中最优解
    [minCost, idx] = min(neighborCosts);
    curSolution = neighbors(idx,:);
    curCost = minCost;
    
    % 更新最优解
    if curCost < bestCost
        bestSolution = curSolution;
        bestCost = curCost;
    end
    
    % 更新禁忌表
    tabuList = [tabuList; moves(idx,:)];
    if size(tabuList,1) > tabuLen
        tabuList(1,:) = [];
    end
end

%% 输出结果
fprintf('最优路径长度: %.4f\n', bestCost);
disp('最优路径:');
disp(bestSolution);

%% 绘制最优路径
figure;
plot(city(bestSolution,1), city(bestSolution,2), 'o-', 'LineWidth',2);
hold on;
plot([city(bestSolution(end),1) city(bestSolution(1),1)], ...
     [city(bestSolution(end),2) city(bestSolution(1),2)], 'o-', 'LineWidth',2);
title('TSP 最优路径（禁忌搜索）');
xlabel('X'); ylabel('Y'); grid on;

function cost = calcCost(path, distMat)
    n = length(path);
    cost = 0;
    for i = 1:n-1
        cost = cost + distMat(path(i), path(i+1));
    end
    % 回到起点
    cost = cost + distMat(path(end), path(1));
end