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。
