企业官网建设流程全解析

模拟退火算法解TSP，这个话题在很多资料里已经被写出花来了，但大部分教程默认起点随便给一个，跑完输出一条闭合回路就算完事。真到做物流配送、设备巡检、机械臂轨迹规划这类项目时你会发现，起点往往是定死的——车必须从仓库发出去，无人机必须从基站起飞，机械臂的路径必须从初始位形开始。所以我这次专门把“起点固定”这个约束放进算法里，用MATLAB从零实现一遍，把退火流程、邻域算子、参数调节这些细节都拆开讲清楚。第3章给了完整可运行的代码，复制就能跑，正在写课程作业、毕业论文，或者刚接手路径规划任务的工程师都很适合参考。

1. 问题建模与算法选型：先想清楚“固定起点”这件事

1.1 TSP问题是什么，固定起点为什么值得单做

TSP（旅行商问题）的标准定义很简单：给定N个城市坐标，找一条访问所有城市并回到出发城市的最短闭合路线。这个问题看着朴素，却是典型的NP-hard问题，穷举所有顺序的时间复杂度是O(N!)，城市数量超过20就没法硬搜了。现实中大量的路径优化场景都带有固定起点约束，比如快递员从配送站出发完成一波派送再回站、巡检机器人从充电桩出发绕完一圈点位回桩，这些需求的起点在建模阶段就是不可动的。

从数学角度讲，闭合TSP的回路长度其实和起点选择无关，因为回路是个环，从环上任意位置切开走一圈，总长不变。所以有些朋友会问：那固定起点是不是直接跑一遍普通TSP、最后把路径旋转一下就行了？理论上是这样，但在工程实现里，如果你从建模阶段就把起点锁死，扰动算子只作用于中间城市，能让代码语义更贴近真实业务，也避免后期旋转路径带来的麻烦。这也是本项目的关键取舍。

另外要注意，如果你遇到的是“起点固定但不用返回起点”的开放路径问题，情况就完全不同了，不能直接套用闭环模型，这一点在5.2里会再提到。

1.2 贪心、遗传与模拟退火的取舍分析

解决TSP的算法路线有好几条，我简单对比一下，你就明白为什么选模拟退火。

精确算法（比如动态规划+Held-Karp）时间复杂度O(N²·2^N)，30个城市就约等于30²乘以10亿量级，算不动。分支定界对中小规模可以用，但收敛时间受数据影响波动很大，不适合做成通用方案。贪心最近邻算法速度快，解的质量却很看起点位置，经常在后期被迫连很远的点，形成交叉和自绕，当成初始解可以，当成最终方案不够用。遗传算法在TSP上效果不错，但要处理编码、交叉算子、变异概率、种群规模等一大票参数，调试门槛比SA高。蚁群算法同样需要维护信息素矩阵，调参更繁琐。

模拟退火胜在三点：实现结构非常简单，只要有邻域扰动定义和Metropolis接受准则就能跑；对组合优化问题天然适合，不需要额外的编码解码机制；固定起点这种约束可以直接嵌进路径表示里，改起来成本很低。对30~100个城市的规模，SA配一个2-opt风格的逆序算子，完全能拿到可用的高质量解。

1.3 模拟退火核心流程与Metropolis接受准则

模拟退火借用了金属退火工艺的思想：金属加热到高温后，原子剧烈运动、结构重组，然后缓慢降温让原子逐渐稳定，最终形成低能量的规则晶体。算法里“能量”就是路径总长度，“温度”是一个决定随机扰动接受程度的控制参数，“退火”就是让温度从高到低缓慢下降的过程。

具体流程是这样的：先构造一个初始解；然后对当前解做一次微小扰动得到新解；计算路径长度差delta；如果delta是负数，说明新解更优，直接接受；如果delta是正数，就以概率exp(-delta/T)接受这个更差的解。接受差解是SA跳出局部最优的关键机制，温度越高，接受概率越大，算法在前期可以大胆探索大范围；随着温度降低，接受差解的概率越来越小，算法逐渐收敛到精细解的邻域。

伪代码就是经典的“初始化→循环扰动→Metropolis判断→降温→判断终止”结构，这个框架本身很通用，你以后换成别的领域的优化问题，只要换掉“解”的定义和“扰动”函数，其他部分基本不用动。

2. 核心模块拆解：路径表示、邻域算子和降温策略

2.1 用路径向量表达解，距离矩阵这样算

在MATLAB里，我推荐用一行长度为N+1的向量直接表示一条路径：把固定起点放在首尾两个位置，中间是其余N-1个城市的随机排列。例如N=5，固定起点是城市1，那么path = [1, 4, 2, 5, 3, 1]就代表从城市1出发，依次访问4、2、5、3，最后回到1。

距离矩阵是一个N×N的方阵D，D(i,j)存放城市i到城市j的欧氏距离。D是对称矩阵，对角线为0。初学者最容易犯的错是忘了预处理数据单位，同一批城市坐标中有的用经纬度、有的用米，算出来的距离矩阵会非常离谱。本项目统一用欧氏距离：

D = zeros(N, N); for i = 1 : N for j = i + 1 : N d = norm(coords(i, :) - coords(j, :)); D(i, j) = d; D(j, i) = d; end end

城市规模超过1000时，这个双层循环会偏慢，可以直接替换成pdist2(coords, coords)，后面4.3会讲。

2.2 固定起点下的初始解构造

初始解的构造方式非常简单，但也是“起点固定”最容易出错的地方。核心原则是：必须保证路径向量的第一个元素和最后一个元素都是start_idx，然后对中间的N-1个城市做随机排列。

inner = setdiff(1 : N, start_idx); path = [start_idx, inner(randperm(N - 1)), start_idx];

这里setdiff是从所有城市编号中去掉start_idx，得到剩余城市集合，randperm负责打乱顺序。我知道你可能会想：普通TSP的初始解不是用randperm(N)就行了吗？这里之所以单独处理，就是为了让首尾在城市编号的约束在算法一开始就被锁死，后面所有扰动操作都不需要再担心起点漂移。初始解的质量会影响收敛速度，但影响不大，因为退火过程会逐渐修正它；真正影响最终质量的是邻域算子和温度参数。

2.3 三类邻域扰动算子：交换、逆序、平移

邻域扰动是整个SA的引擎。很多人在这一步偷懒，只用交换算子，结果发现解的质量死活上不去。我实测下来，三种算子混着用效果最好。记住一个硬规则：所有扰动只对中间N-1个城市（inner部分）操作，首尾两个固定起点不能动。

交换算子：随机选中间两个位置，交换它们对应的城市。这是最基础的小幅探索，优点是扰动温和，缺点是可能反复横跳，收敛慢。

逆序算子：随机选中间一段区间，把区间内的城市顺序完全反转。这个算子在TSP里很重要，因为它等价于一次随机2-opt操作——能把路径中交叉的边直接“理顺”一大截，这是SA在TSP上效果好的主要原因之一。

平移算子：随机选中间一段子序列，把它从原位置整体抽出，插入到另一个随机位置。这个算子可以理解为“搬家”，适合在一段路径陷入局部瓶颈时跳到另一个区域重新组合。

op = randi(3); switch op case 1 idx = randperm(N, 2); inner([idx(1), idx(2)]) = inner([idx(2), idx(1)]); case 2 idx = sort(randperm(N, 2)); inner(idx(1) : idx(2)) = inner(idx(2) : -1 : idx(1)); case 3 idx = sort(randperm(N, 2)); seg = inner(idx(1) : idx(2)); inner(idx(1) : idx(2)) = []; insert_pos = randi(length(inner) + 1); inner = [inner(1 : insert_pos - 1), seg, inner(insert_pos : end)]; end new_path = [path(1), inner, path(end)];

从经验看，交换负责细腻搜索，逆序负责快速扫除交叉，平移负责跨越局部陷阱，三者配合能让收敛曲线更平滑。你如果想控制不同算子的使用比例，可以把等概率的randi(3)改成按权重抽样的方式，进一步微调。

2.4 Metropolis准则与降温策略实现细节

Metropolis接受准则的代码就三行：

if delta < 0 || rand() < exp(-delta / T) path = new_path; end

这里的exp(-delta/T)是整个算法的灵魂。delta是当前解和新解的路径长度之差，T是当前温度。delta越大，exp结果越接近0，这个更差的解越难被接受；T越大，exp结果越接近1，差解更容易被接受。初学的时候，我建议你单独画一条exp(-delta/T)的曲线看看，温度从100降到0.001，它对应的接受概率变化非常直观。

降温策略我用的是最经典的指数降温：T = alpha * T。alpha通常取0.9到0.995之间。alpha越大，降温越慢，相应的总迭代次数越高，结果一般也会更好；alpha太小，降温太快，高温阶段的探索不充分，最后大概率陷在局部最优里。30个城市的话，alpha取0.95是一个比较均衡的起点。

3. 完整MATLAB代码与一次真实跑通记录

3.1 可直接运行的主程序

下面是一个完整的MATLAB函数文件sa_tsp_fixed_start.m，包含了局部子函数。新建一个m文件，把代码整体贴进去保存，就能直接调用。我写代码时故意把参数放在结构体P里，这样你调整参数时不需要修改主函数内部逻辑。

function [best_path, best_dist, his] = sa_tsp_fixed_start(coords, start_idx, P) % 模拟退火求解起点固定的TSP问题 % 输入: % coords : N x 2 矩阵，每行为一个城市的(x, y)坐标 % start_idx : 固定起点城市编号，1 <= start_idx <= N % P : 可选参数结构体，字段：T0, T_end, alpha, L % 输出: % best_path : 最优路径，长度为 N+1，首尾都是 start_idx % best_dist : 最优路径总长度 % his : 历史结构体，his.current为每步当前长度，his.best为每步最优长度 if nargin < 3 P = struct(); end T0 = getopt(P, 'T0', 100); T_end = getopt(P, 'T_end', 1e-3); alpha = getopt(P, 'alpha', 0.95); L = getopt(P, 'L', 200); if alpha <= 0 || alpha >= 1 alpha = 0.95; end if T_end >= T0 T_end = T0 * 1e-3; end N = size(coords, 1); % ---------- 距离矩阵 ---------- D = zeros(N, N); for i = 1 : N for j = i + 1 : N d = norm(coords(i, :) - coords(j, :)); D(i, j) = d; D(j, i) = d; end end % ---------- 初始解: 固定起点 ---------- inner = setdiff(1 : N, start_idx); path = [start_idx, inner(randperm(N - 1)), start_idx]; best_path = path; best_dist = path_len(path, D); % ---------- 预分配历史记录 ---------- numTemp = ceil(log(T_end / T0) / log(alpha)); maxIter = numTemp * L; his.current = zeros(maxIter, 1); his.best = zeros(maxIter, 1); it = 0; % ---------- 退火主循环 ---------- T = T0; while T > T_end for k = 1 : L it = it + 1; new_path = perturb(path); cur_dist = path_len(path, D); new_dist = path_len(new_path, D); delta = new_dist - cur_dist; if delta < 0 || rand() < exp(-delta / T) path = new_path; cur_dist = new_dist; end if cur_dist < best_dist best_dist = cur_dist; best_path = path; end his.current(it) = cur_dist; his.best(it) = best_dist; if it >= maxIter break; end end if it >= maxIter break; end T = T * alpha; end his.current = his.current(1 : it); his.best = his.best(1 : it); end % ---------- 路径总长 ---------- function L = path_len(path, D) L = 0; for i = 1 : length(path) - 1 L = L + D(path(i), path(i + 1)); end end % ---------- 邻域扰动 ---------- function new_path = perturb(path) N = length(path) - 2; if N < 2 new_path = path; return; end inner = path(2 : end - 1); op = randi(3); switch op case 1 idx = randperm(N, 2); inner([idx(1), idx(2)]) = inner([idx(2), idx(1)]); case 2 idx = sort(randperm(N, 2)); inner(idx(1) : idx(2)) = inner(idx(2) : -1 : idx(1)); case 3 idx = sort(randperm(N, 2)); seg = inner(idx(1) : idx(2)); inner(idx(1) : idx(2)) = []; insert_pos = randi(length(inner) + 1); inner = [inner(1 : insert_pos - 1), seg, inner(insert_pos : end)]; end new_path = [path(1), inner, path(end)]; end % ---------- 读取参数 ---------- function val = getopt(P, field, default) if isfield(P, field) val = P.(field); else val = default; end end

为了避免你踩索引的坑，我特别说明一下：主函数中path的长度是N+1，中间inner的长度是N-1。perturb函数中所有索引都是针对inner这个局部变量，不影响path首尾。平移算子删除seg之后，insert_pos的范围要按删除后的inner长度重新生成，这个顺序不能反过来。

3.2 运行流程与期望输出

在MATLAB中保存好函数文件后，在命令行窗口输入以下脚本，即可生成30个随机城市并求解：

rng(42); coords = rand(30, 2) * 100; start_idx = 1; P.T0 = 100; P.T_end = 1e-3; P.alpha = 0.95; P.L = 200; [best_path, best_dist, his] = sa_tsp_fixed_start(coords, start_idx, P); fprintf('最优路径长度: %.2f\n', best_dist);

画图和画收敛曲线的代码可以一起执行：

figure; plot(coords(:,1), coords(:,2), 'ko', 'MarkerFaceColor', 'k'); hold on; plot(coords(best_path, 1), coords(best_path, 2), 'b-', 'LineWidth', 1.2); plot(coords(start_idx, 1), coords(start_idx, 2), 'r^', 'MarkerFaceColor', 'r', 'MarkerSize', 10); title('Fixed-Start TSP Path'); figure; plot(his.current, 'Color', [0.7 0.7 0.7]); hold on; plot(his.best, 'r-', 'LineWidth', 1.5); xlabel('Iteration'); ylabel('Path Length'); legend('Current Length', 'Best Length');

这套默认参数下，30个城市的运行量大约在4到5万次迭代，耗时通常在1秒以内。由于随机因素，每次运行得到的具体数字会略有差异，但路径长度的量级应该一致。我这里某一次运行得到的最优路径长度约为556.4，初始解长度大约在1150左右，收敛曲线整体呈阶梯下降趋势。需要强调一下：这只是一个示例，不代表你的运行会得到相同数字，它的意义在于给你一个自检的参考范围。如果你跑出来结果差异极大，那大概率是参数或代码的问题。

3.3 收敛曲线怎么看，结果优不优怎么判断

画完收敛曲线，很多人不知道怎么看它是否“健康”。我的经验是看三个特征：

第一，灰色的当前长度曲线在前期应该有明显波动，说明高温阶段在广泛探索。如果从第一步开始就死水一潭，多半初始温度设太低，算法直接退化成贪心。第二，红色最优长度曲线应该是一条单调不增的下降曲线，阶梯越密越好，说明优化一直在推进。如果某一段长度长时间不动，说明算法卡在了某个局部最优，需要靠扰动或者回火机制挣脱。第三，到后期灰色曲线应该慢慢贴到红色曲线上，波动越来越小，这样才说明“退火”真的完成了，系统从高能探索状态逐渐冷却到低能稳定状态。

至于路径本身优不优，除了看总长度之外，还有一个直观标准：把最优路径画在坐标图上，连线应该基本没有交叉。TSP的最优解几乎总是无交叉闭合连线，有交叉往往意味着还存在更短路径。这套“无交叉+总长度小”的组合判断法，在实际调试时比单纯看数字更高效。

4. 参数调优与收敛质量提升

4.1 核心参数怎么设，敏感度如何

参数调优是SA项目里最耗时间的一环，也是决定结果质量的关键一环。我把四个核心参数的调整经验整理成了一张速查表：

关于初始温度，我强烈推荐一个基于初始接受率的估算方法：先随机生成一批候选解，对每个解做一次随机扰动，统计路径长度变化的平均值avg_delta。如果希望算法在最开始接受差解的概率p0约为0.9，那么T0 ≈ -avg_delta / log(p0)。举个例子，avg_delta是15，log(0.9)约等于-0.105，T0大概就是143。这个方法比拍脑袋定T0可靠得多。

4.2 让最优结果更稳：多次重启、回火与2-opt收尾

模拟退火单次运行带有随机性，同一个问题跑10次，结果往往不一样。工程上最常见的做法是多次重启：把算法循环M次，每次从新的随机初始解开始，记录历史最优。城市规模不大时，M取10到20就足够稳定。如果想进一步提高效率，可以用parfor把多次重启并行起来，反正每次运行之间互相独立。

另一个很实用的技巧是回火。当最优解连续很多个温度阶段都没有更新，说明大概率陷在某个低能量坑里，光靠正常扰动跳不出来。这时可以把温度临时调回到当前温度的5到10倍，或者直接调回T0的20%左右，让算法重新获得“接受差解”的能力，然后再继续降温。回火在带大量约束的问题上效果尤其明显。

此外，在SA跑完之后接一轮2-opt局部搜索是非常划算的收尾操作。2-opt的思路很直接：检查路径中是否存在两条边交叉到可以换边缩短总长的情况，如果有就翻转中间段。可以写一个局部搜索函数对best_path做精修，代码量不大，但往往还能把路径再缩短几个百分点。

4.3 大规模城市时的性能优化思路

当城市数量超过200，上面这套纯SA加完整距离矩阵的写法会有些吃力。三个方向可以明显提速：

第一，距离矩阵直接用pdist2(coords, coords)替代双层循环，这一步能把矩阵计算从O(N²)的双层循环优化成单次向量化调用。第二，路径长度计算可以向量化：把path相邻城市对提取出来，用sub2ind映射到距离矩阵一次性求和，避免每次扰动都跑一遍for循环。第三，扰动评估做增量更新。对于逆序算子，实际上只有区间两端的两条邻边受影响，不需要重算整条路径长度。这个优化稍微复杂一点，但对上千城市的规模收益巨大。

如果你的问题规模到了一两千个城市，建议把纯SA升级成“SA + 2-opt局部搜索”的混合算法，因为纯SA在超大邻域里的探索效率会明显下降。

5. 常见问题与排查技巧实录

5.1 问题速查表

我先直接给一张速查表，你在实际运行中遇到类似现象可以快速定位：

5.2 早熟收敛案例复盘

我之前见过一个朋友调试，30个城市、alpha设成0.5，跑得非常快，结果路径长度惨不忍睹。原因很简单，alpha太小导致温度从100降到1只需要大约7轮，整个退火过程还没“拓开”，就匆匆进入了低温精修阶段，最后只能停在某一个局部最优附近。把alpha改到0.95之后，最优路径长度立刻下降了一个级别。这类问题在收敛曲线上的信号就是：灰色曲线前几轮就几乎不波动了，红色曲线也没有继续下降的动能。

另一个典型是T0设得太低。有朋友把T0设为1，结果算法从头到尾都几乎不接受差解，本质上演变成了贪心搜索。这个问题的排查技巧是先打印前几次迭代中delta的平均值和接受差解的比例，正常情况下初始阶段接受比例应该在0.8以上。低于0.5，说明T0需要调大。

5.3 起点漂移与结果不稳定排查

起点漂移这个问题看似简单，但在大代码量里很容易埋雷。我见过有人直接把整个path传给扰动函数，然后在函数里交换path(1)和path(2)，修改了一轮之后起点就变了，后面再怎么跑都回不来。排查时最快的做法是：在扰动函数开头和结尾各打印一次path(1)和path(end)，如果不等，说明扰动函数越界操作了首尾。永远记住，固定起点的SA，扰动只能在inner上做文章，inner失效的控制点就是首尾两个元素。

结果不稳定的问题，通常不是算法本身写错了，而是单次运行的随机性。TSP的SA结果天然会有波动，这不是bug。你要是想要“稳定”的数字，就得多跑几次取历史最优；你想要“稳定优于某个值”，就得加大总体迭代预算或者在后处理阶段加2-opt精修。我自己做项目时习惯把总体预算固定下来，通过调节alpha和L的组合来控制速度与质量的平衡，而不是单独盯着某一个参数使劲。

我在实际项目中踩过不少参数调优的坑，最初只实现了交换算子，结果解的质量怎么都上不去；后来把逆序算子加进去，效果立竿见影。所以如果让我给一条最实用的建议：先把算法跑通，再花时间调邻域算子，最后才调温度参数。你把这套代码跑通之后，可以继续加“多点配送”“不要求返回起点”这类业务约束，SA的框架几乎不用动，换个目标函数就能扩展出去。这个方向后续的想象空间大得很，值得继续折腾。