基于禁忌搜索算法的TSP路径规划matlab仿真

1.程序功能描述

基于禁忌搜索算法的TSP路径规划,输出优化收敛曲线以及路线规划图。

2.测试软件版本以及运行结果展示

MATLAB2022a版本运行

3.核心程序

for it = 1:Iteration
    it
    % 初始化本次迭代的最佳新解代价为正无穷  
bestnewsol.Cost = inf;

    % 遍历所有动作并尝试应用它们  
    for i = 1:Nact
        if TC(i) == 0% 如果这个动作不在Tabu列表中  
newsol.Position = func_Action(sol.Position, ActionList{i});
newsol.Cost = Js(newsol.Position);% 计算新解的代价  
newsol.ActionIndex = i;% 记录应用的动作索引 
            % 如果新解的代价更好，则更新本次迭代的最佳新解  
            if newsol.Cost<= bestnewsol.Cost
bestnewsol = newsol;
            end
        end
    end

    % 用最佳新解更新当前解  
    sol = bestnewsol;

    % 更新Tabu列表  
    for i = 1:Nact
        if i == bestnewsol.ActionIndex% 如果这个动作是最佳新解的动作  
            TC(i) = TL;       % 将其添加到Tabu列表中  
        else
            TC(i) = max(TC(i)-1, 0);% 否则减少Tabu计数器  
        end
    end

    % 如果找到了更好的解，则更新最佳解  
    if sol.Cost<= BestSol.Cost
BestSol = sol;
    end

    % 保存最佳代价 
BestCost(it) = BestSol.Cost;


    % 绘制最佳解  
figure(1);
func_plot(BestSol);
pause(0.01);

end
% 只保留实际迭代次数的最佳代价  
BestCost = BestCost(1:it);

%% Results

figure;
plot(BestCost, 'LineWidth', 2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;
23

4.本算法原理

        基于禁忌搜索算法的TSP（旅行商问题）路径规划是一种求解TSP问题的优化算法。禁忌搜索算法是一种启发式搜索方法，它通过避免重复搜索和陷入局部最优解来提高搜索效率。在TSP问题中，禁忌搜索算法通过不断地调整路径中的城市顺序来寻找最优路径。

4.1 TSP问题描述

       TSP问题是一个经典的组合优化问题，其目标是找到访问一系列城市并返回起点的最短可能路径。给定一个城市列表和每对城市之间的距离，TSP问题的解是一个排列，它表示访问每个城市一次并返回起点的顺序。

4.2 禁忌搜索算法原理

       禁忌搜索算法是一种基于局部搜索的元启发式算法，它通过引入禁忌列表来避免重复搜索和陷入局部最优解。禁忌搜索算法从一个初始解开始，然后在其邻域内搜索更好的解。搜索过程中，算法会记住已经访问过的解，并将它们加入到禁忌列表中，以避免在近期内重复访问。当搜索到一定程度后，禁忌列表中的解会逐渐被释放，从而允许算法在更大的范围内搜索。

4.3 算法步骤

禁忌搜索算法求解TSP问题的步骤大致如下：

初始化：选择一个初始路径作为当前解，并初始化禁忌列表为空。

邻域搜索：定义当前解的邻域。在TSP问题中，邻域通常通过交换、插入或逆序等操作来生成新的路径。

评估：计算邻域内所有解的目标函数值（路径总长度）。

选择：从邻域中选择一个非禁忌的最优解作为新的当前解。如果邻域中的所有解都被禁忌，则选择其中最好的解，并更新禁忌列表。

更新禁忌列表：将新选择的解加入到禁忌列表中，并移除最早加入的解（如果禁忌列表已满）。

终止条件：如果达到预设的最大迭代次数或满足其他终止条件，则停止搜索；否则，返回步骤2。