企业官网建设流程全解析

我最早把模拟退火算法（SA）用在TSP上，是因为一个配送路径优化的小项目：30个城市，如果直接穷举，所有路径数量是天文数字，MATLAB的perms函数跑到10个城市就内存爆炸。后来换成SA-TSP方案，几秒钟就能给出一个相当不错的近优解，而且每次迭代都能看到最优路径在动态调整，那种"盯着曲线一点点压下去"的过程非常直观。这篇文章就把我从建模、写代码到调参数完整踩过的坑都记下来。内容围绕MATLAB环境和模拟退火算法，手写一套不依赖额外工具箱的SA-TSP，适合正在做路径规划、组合优化问题，或者需要学习启发式算法的朋友参考。

1. 为什么用模拟退火算法解TSP：核心思路拆解

1.1 TSP问题本质与暴力求解的困境

TSP的完整表述其实很简单：给定N个城市的坐标，找一条从起点出发、经过所有城市恰好一次再回到起点的最短闭合回路。数学上这是一个组合优化问题，可行解的数量是阶乘级别。严格讲，如果有N个城市，固定起点后还有(N-1)!种排列，再考虑方向重复，实际不重复路径是(N-1)!/2。这个数增长有多快？N=10的时候是181440条，暴搜还能勉强跑；N=20的时候就已经接近6×10^16，MATLAB就算每秒计算1万条路径，也要跑上千年。

我当时遇到的真实场景是30个城市，用暴力搜索连边都摸不着。这时候最直接的教训就是：面对TSP这类NP-hard问题，追求理论最优解在工程上是不现实的，我们需要一个能在合理时间内给出高质量可行解的近似算法。模拟退火的价值就在这里：它不保证100%找到全局最优，但能以很大的概率找到接近全局最优的解，而且实现成本低，换一组城市规模只需要改参数。

1.2 模拟退火凭什么跳出"局部最优"这个坑

贪心算法和局部搜索算法的通病是"走一步看一步"：只要新解比当前解差，就直接拒绝，于是很容卡在某个山谷里出不来。真实世界里的物理退火给出一个启发：金属在高温时原子运动剧烈，能量状态可以上下波动；随着温度缓慢降低，原子逐渐稳定在低能量位置。模拟退火把这种机制搬到了算法里，核心是"接受坏解"。

具体到TSP，当前最优路径就好比一个金属块的能量状态。算法每次对当前路径做一次扰动，得到一个新路径。如果新路径距离更短，那自然接受它；如果新路径距离更长，也不是一票否决，而是给一个概率，按Metropolis准则计算：概率 = exp(-ΔE / T)，其中ΔE是新解与当前解的差值，T是当前温度。温度高的时候，exp函数的值接近1，差解很容易被接受；温度慢慢降低，接受差解的概率越来越小，最终变成一个只接受好解的局部搜索。

我用一个生活化的类比来记这个概念：手里握着一把弹珠在漏斗里筛，一开始使劲摇晃，让弹珠有机会跳出浅坑；晃动的幅度逐渐变小，弹珠最后落到底部深坑。模拟退火的"摇晃幅度"就是温度，"跳出浅坑"就是接受差解跳出局部最优。设计得好的SA，能让弹珠在"找到全局深坑"和"最终稳定下来"之间取得平衡。

1.3 为什么选MATLAB做SA-TSP而不是C++或Python

选择MATLAB不是因为它速度最快，而是因为在这类教学、验证、原型开发场景里，它的开发效率和可视化能力太占优势。距离矩阵用pdist2一行就能算出来，二维平面上的路径曲线用plot可以实时更新，不需要自己写矩阵运算和绘图库。Python当然也行，numpy加matplotlib也不差，但MATLAB的调试体验和矩阵语法更适合快速验证算法思想。

另外还有一点很关键：MATLAB自带的优化工具箱里有simulannealbnd，但那是一个连续参数优化函数，直接套TSP这种离散组合优化问题并不方便。手写SA-TSP反而是最常用的做法：解用整数排列表示，邻域扰动用逆序或交换，完全自己控制。这样写出来的代码不依赖特定工具箱，换到别人电脑上也能跑，后续要加限制条件（比如带时间窗的TSP）也更容易改。

2. 模拟退火算法的核心原理与关键参数设计

2.1 从金属退火到算法迭代：Metropolis准则全解析

标准的模拟退火流程可以压缩成五步：初始化温度和解、生成新解、计算能量差、按接受准则决定是否接受、降温。伪代码写过很多次，但这里还是贴一段最清晰的流程，方便后面讲参数：

1. 随机生成一个初始路径S，计算路径总距离E(S)
2. 对S做邻域扰动，得到新路径S'
3. 计算ΔE = E(S') - E(S)
4. 如果ΔE < 0，直接接受S' 作为当前解
5. 如果ΔE >= 0，则以P = exp(-ΔE / T)的概率接受S'
6. 按照降温函数更新温度T = α * T
7. 重复步骤2到6，直到满足终止条件

这里最容易忽略的是步骤5中的exp计算。当ΔE远大于T的时候，exp结果趋近于0，差解几乎不会被接受；当ΔE和T在同一量级时，差解有相当的几率被接受。所以初始温度T0必须设置得足够高，否则第一步就丧失了跳出局部最优的能力。很多人第一次跑SA发现结果很差，多半就是T0设得跟ΔE一个量级，导致算法实际变成了一个随机局部搜索。

2.2 初始温度、降温系数与终止温度的确定方法

这三个参数直接决定了SA的探索能力和收敛速度。我给出一个比较实用的调参思路，而不是直接扔一个公式。

初始温度T0：理论上要高于最大的ΔE，这样任意差解的接受概率都不低于0.3到0.5。实际操作中，可以先随机生成几百个初始路径，统计相邻路径之间距离差值的分布，取出最大ΔE或者95%分位数，然后乘以2到3倍作为T0。比如30个城市，坐标在0到100的区域内，ΔE的典型值可能在几十到几百之间，我一般取T0=500到1000，都能得到不错的结果。

降温系数α：这是SA里最敏感的参数。α取0.8，温度很快就降到接近0，算法很快退化成贪心搜索；α取0.99，温度下降非常慢，搜索充分但耗时也成倍增加。我的经验是，30城市以内α取0.95到0.98比较好，100城市以上至少要0.98以上。如果非要给一个"能跑出漂亮结果"的默认值，我推荐T0=1000，α=0.99，终止温度T_end=1e-3，迭代次数上限设为2000到5000次。这个组合不一定最快，但结果通常很稳。

终止条件：可以用固定迭代次数，也可以用温度阈值，也可以两者结合。我更倾向用温度阈值加最大迭代次数的双保险，避免温度降到很小时循环还在空转。还有一个容易被忽略的点：当连续很多代最优解都没有任何改进时，可以直接终止，节省运行时间。

2.3 新解生成策略：2-opt逆序还是两点交换

TSP的邻域结构决定了搜索路径能不能有效覆盖解空间。最简单的是随机交换两个城市的位置，叫swap；另一种是随机选取一段子路径整体逆序，叫2-opt；还有一种是把一段子路径移动到另一个位置，叫insert或shift。实测下来，2-opt在TSP上的效果最好，因为它能把路径中的交叉直接消除。

实现2-opt的MATLAB代码非常短：随机生成两个索引i和j，用S(i:j) = S(j:-1:i)就能完成逆序。为什么这个操作对TSP这么有效？因为TSP的最优解在二维平面上通常是一条无交叉的闭合曲线，任何交叉都会导致距离变长。2-opt一次操作可以消除一个交叉，相当于在局部进行了一次"拉直"。

我在实际代码里做了混合扰动：大约20%的概率执行swap，80%的概率执行2-opt。这样既能通过2-opt快速优化路径形状，又能保留swap带来的随机性，防止搜索空间过度受限。混着用比单纯用一种效果好很多，尤其是城市坐标分布比较均匀的情况。

3. MATLAB项目实现：从0到1手写SA-TSP

3.1 数据准备与距离矩阵计算

先写数据这一层。无论城市坐标来自何处，第一步都是把所有点放到一个N×2的矩阵里，每一行是一个城市的(x,y)坐标。演示代码就用rand生成30个城市，在[0,100]的方形区域里随机分布：

rng(2025); % 固定随机种子，保证实验可复现 N = 30; coords = rand(N, 2) * 100;

然后计算距离矩阵。最省事的方法是用MATLAB的pdist2：

distMat = pdist2(coords, coords); distMat(1:N+1:end) = 0; % 对角线置零

这里要注意，pdist2默认计算的是欧几里得距离，也就是直线距离。如果城市坐标是经纬度，就需要用球面距离公式，否则距离矩阵会有明显误差。还有一个坑：如果直接拿pdist2的结果当权重矩阵，对角线是0，这没问题，但如果你在计算路径总距离时会把城市本身重复计算，务必要小心索引。

计算一条路径总距离的函数，我习惯写成独立m文件，方便复用：

function totalDist = pathLength(path, distMat) totalDist = 0; for k = 1:length(path)-1 totalDist = totalDist + distMat(path(k), path(k+1)); end totalDist = totalDist + distMat(path(end), path(1)); % 回到起点 end

这个循环速度够用，但如果你追求极致性能，完全可以用sum(distMat(sub2ind(...)))向量化，下面讲优化时会提到。

3.2 主循环代码实现与动态寻优

核心代码不依赖任何工具箱，直接把Section 2.1的伪代码翻译成MATLAB。我把整个主循环封装成一个函数，输入城市坐标和参数，输出最优路径、最优距离和收敛曲线：

function [bestPath, bestDist, record] = sa_tsp(coords, T0, T_end, alpha, maxIter) N = size(coords, 1); distMat = pdist2(coords, coords); distMat(1:N+1:end) = 0; currentPath = randperm(N); % 随机初始路径 currentDist = pathLength(currentPath, distMat); bestPath = currentPath; bestDist = currentDist; record = zeros(maxIter, 1); T = T0; for iter = 1:maxIter newPath = currentPath; % 混合扰动：20% 概率 swap，80% 概率 2-opt if rand < 0.2 pos = randperm(N, 2); newPath(pos(1)) = currentPath(pos(2)); newPath(pos(2)) = currentPath(pos(1)); else pos = sort(randperm(N, 2)); newPath(pos(1):pos(2)) = newPath(pos(2):-1:pos(1)); end newDist = pathLength(newPath, distMat); deltaE = newDist - currentDist; % Metropolis接受准则 if deltaE < 0 || rand < exp(-deltaE / T) currentPath = newPath; currentDist = newDist; if currentDist < bestDist bestDist = currentDist; bestPath = currentPath; end end T = alpha * T; if T < T_end break; end record(iter) = bestDist; end record = record(1:iter); end

这段代码看起来不长，但已经把SA的核心全部包括了。动态寻优体现在哪里？如果你在循环体内每50代画一次路径，就能看到路径从一团乱麻逐渐变得规则，最终收拢成一条近似短文环。后面我会写一个可视化小节。

3.3 最优路径可视化与结果输出

运行函数后，我们需要把结果展示出来。最短路径值和路径序列直接输出到命令行：

[bestPath, bestDist, record] = sa_tsp(coords, 1000, 1e-3, 0.99, 3000); fprintf('最优路径距离 = %.2f\n', bestDist); disp('最优路径序列：'); disp(bestPath);

路径可视化首先是平面路径图，把城市坐标画出来，再用plot把bestPath连成一条闭合线：

figure; plot(coords(bestPath, 1), coords(bestPath, 2), 'o-', 'LineWidth', 1.5); hold on; plot([coords(bestPath(end), 1), coords(bestPath(1), 1)], ... [coords(bestPath(end), 2), coords(bestPath(1), 2)], 'r-', 'LineWidth', 1.5); xlabel('X'); ylabel('Y'); title('SA-TSP最优路径');

动态寻优图就是记录数组的收敛曲线，用plot(record)画出来，能看到最优距离随着迭代代数的下降趋势。如果我还做了动画，通常在循环内用drawnow limitrate控制刷新频率，但要注意绘图会拖慢计算速度，我建议每50代或100代更新一次视图。

在实际项目中，这个结果可以导出为.gpx或Excel表格，也可以接入GIS系统做进一步分析。MATLAB的优势就在于从算法到可视化一条龙，不用额外折腾前端。

4. 参数调优与实验结果分析

4.1 不同参数组合对收敛效果的影响

我特意用同一份30城市坐标数据，跑了几组不同参数，结果整理成表格供参考。每组参数独立运行10次，取最优值和平均运行时间（我机器上大概是几十毫秒到几秒）。

这个实验告诉我们：alpha的作用远大于T0。alpha=0.8的时候，即使初始温度很高，温度也会迅速跌到零点附近，算法后半程基本在做一个局部搜索。alpha=0.99时，搜索过程更长，更容易找到好的路径。注意这里的"最优距离"只是30城市随机坐标下的一个示例值，具体数值取决于坐标分布，但趋势是一致的。

我再补充一个很容易踩的坑：不要为了追求快，把alpha设成0.7以下。那样的SA其实变成了一个带随机扰动的爬山算法，和纯贪心差别不大，很多小规模TSP问题都能跑出明显不合理的交叉路径。

4.2 动态寻优曲线里藏着哪些信息

把record数组画出来看，收敛曲线大致分成三个阶段。第一阶段是温度还很高的时候，最优值曲线会有一个明显的快速下降，因为算法刚开始接受大量随机差解，探索范围大，能很快碰到此前没发现的好区域；第二阶段是温度降到中等水平，接受差解概率下降，曲线下降变慢，呈现阶梯状；第三阶段是低温阶段，路径基本定型，曲线趋于水平，偶尔还有小幅下降。

如果曲线在第一阶段没有明显下降，说明初始解质量还行，但探索不够；如果曲线第二阶段还在剧烈震荡，说明T0设置过高，或者扰动生成的步子太大，导致差解接受概率始终偏高。如果曲线在很长时间里完全水平，之后突然降一段，这正是SA跳出局部最优的标志，也是动态寻优最直观的价值体现。

我在调参时经常同时画两条曲线：一条是当前解的距离变化，一条是历史最优距离。当前解曲线会一直抖动，历史最优曲线单调下降。只要历史最优还在下降，就说明算法还没收敛，可以继续跑；如果连续几百代历史最优都不变，再考虑增加T0或减小alpha。

4.3 和穷举法、贪心算法的对比实验

为了验证SA-TSP的价值，我用N=10的小规模城市做了对比。N=10时，可以用perms穷举所有不重复路径，找出真正的全局最优。用同一组坐标，实验结果是：贪心算法（从1号城市出发，每次都走最近的下一个城市）得到的距离大约比全局最优高12%；SA-TSP用很适当的参数，在10次运行中有8次找到全局最优，另外两次也只差不到1%。这个对比说明SA在规模不大时已经能逼近全局最优。

到了N=30，穷举法完全不可行，SA-TSP依然能在几秒内得到高质量解。而贪心算法速度虽然快，但结果往往比SA差15%甚至更多，因为贪心只看眼前，很容易在最后被迫走一条很长的边。这个实验让我彻底明白了：在组合优化领域，启发式算法不是"凑合"，而是工程上最实用的策略。

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

5.1 结果不收敛或早熟怎么看

这是我被问得最多的问题。判断早熟的方法很简单：跑完算法输出最优路径，在二维图上如果明显出现交叉，或者路径形状很乱，那么基本可以断定算法没有充分寻优。解决办法按优先级排列：

• 把alpha调高到0.98以上，增加搜索代数。
• 提高T0，尤其是当初始温度比ΔE低很多时，算法根本没有跳出能力。
• 检查扰动策略，如果只用swap，换成2-opt为主。
• 检查终止条件是不是太苛刻，T_end设成1e-3对于大T0来说可能过早终止。

还有一个小技巧：把初始路径从randperm改成贪心算法的输出，这样SA可以从一个较好的起点开始，节省一部分搜索时间，但要注意这也会削弱探索能力，所以贪心初始化只建议在对结果稳定性要求较高时用。

5.2 计算时间过长怎么优化

SA的时间主要消耗在路径长度计算和扰动操作上。N=100时，每次计算整条路径距离要遍历100个节点，如果迭代上万次，这个开销就很可观。我的优化经验有三个：

第一，用向量化计算代替循环。pathLength函数可以通过索引距离矩阵，一次性得到每个节点到下一个节点的距离并求和：

function totalDist = pathLengthVec(path, distMat) idx = sub2ind(size(distMat), path, [path(2:end), path(1)]); totalDist = sum(distMat(idx)); end

第二，减少动态绘图的频率。实时绘图非常耗时，把所有绘图操作移到循环结束之后，或者每50代记录一次绘图数据，速度能提升好几倍。

第三，将终止条件改为"连续无改进次数上限"。如果300代内最优解都没有更新，大概率已经收敛，直接跳出循环。这个策略在α很小的早期版本里特别有效。

5.3 动态寻优曲线抖动剧烈的原因与处理

收敛曲线抖动剧烈，说明算法在高温度阶段接受了大量差解，这是设计使然，不算bug。但如果你发现抖动在整个运行过程中一直存在，甚至在低温阶段还是高幅度震荡，那就是参数出了问题。

一种常见情况是T0设得过大，比如10000以上，导致前期几百代几乎接受所有新解，完全像随机游走。这时可以缩短高温阶段，让T0落在ΔE分布的1到2倍范围内即可。另一种情况是扰动太激进，比如2-opt逆序的长度经常等于N/2以上，会让路径结构被频繁打乱，难以收敛。我一般限制逆序长度不超过N/2，用if diff > N/2, continue; end之类的方式过滤掉过大的扰动。

还有一个和动态寻优相关的技巧：始终保留历史最优解。不要只维护当前解。在高温阶段，当前解可能跑得很差，但历史最优已经被记录下来，输出时用历史最优而不是当前解。这个最简单也最容易被忽略。

6. 进阶扩展与实际工程经验

6.1 从TSP到带约束路径优化

SA-TSP的逻辑完全可以扩展到更实际的场景，比如带时间窗的车辆路径问题（VRPTW）、多旅行商问题（MTSP）。只需要修改两点：一是解的表达方式，比如MTSP需要在排列中插入分隔符；二是目标函数，把时间窗惩罚、车辆数等约束作为额外项加到总代价里。模拟退火最友好的地方就是目标函数可以写得非常灵活，不需要像线性规划那样严格构造。

我做过一个带时间窗的变种，目标函数改为总行驶距离 + 惩罚系数 × 超时总量，惩罚系数可以看成另一个"温度控制量"，一开始放大惩罚，后面逐渐调整权重，效果相当不错。

6.2 多次运行取优与随机种子管理

由于SA是随机算法，单次运行存在不确定性，工程上很容易出现两次结果差异大的情况。我习惯的做法是写一个外层脚本，连续跑10次或20次，每次都换随机种子，记录每次的最优距离，最后取最小值、均值和方差。标准差能告诉你算法的稳定性，如果标准差太大，说明参数还需要调整。

设置全局随机种子rng(固定值)可以让结果可复现，这对调试和写文档非常有用。我在项目服务器上跑批处理时，会为每次实验分配不同的种子，确保结果的独立性和可对比性。

6.3 给初学者的三个实操建议

第一，先不要急着优化性能，把算法跑通的代码控制在100行以内，所有参数都用明文常量，方便观察。第二，务必画收敛曲线和路径图，肉眼观察比任何指标都直接。第三，改参数时一次只改一个，否则出了问题根本不知道是哪个参数引起的。

我自己在调试阶段还有一个坚持很久的习惯：把每次实验的参数和结果记录到一个表格里，用日期命名。不要靠记忆，因为alpha从0.95改成0.96，效果可能差别不大，但记录多了就能看出模式。比如我记录下18组参数后，才确定30城市下alpha=0.99是最合适的设定。

最后再分享一个小技巧：在算法主循环里加一个lastImproved变量，记录历史最优解更新的迭代数。当循环结束还没有找到更好的解时，如果lastImproved距离当前迭代已经超过500代，可以直接跳出。这个小改动让我的SA-TSP在几十个测试用例上平均快了30%，同时几乎不损失解质量。模拟退火这东西，看着简单，但把细节抠到位，效果能差出好几个档次。