如果你做过组合优化尤其是路径规划类的题目对麻雀搜索算法SSA肯定不会觉得陌生。它属于群体智能算法思路来自麻雀觅食和反捕食行为优点是代码简单、参数不多在连续优化问题上收敛速度很不错。但一旦把它扔到旅行商问题TSP这种离散组合优化场景你就会发现原生SSA的很多机制并不匹配位置更新公式是连续值而TSP需要的是排列编码前期的搜索能力虽强后期却很容易在原地打转跑几个测试集就能看到差距。这个项目做的就是一件事把麻雀搜索算法改造成能用在TSP上的版本并用多种策略来补齐原生算法的短板。“多混合策略”这个词听起来比较唬人但落到实现层面并不高深就是混沌初始化、自适应权重、2-opt局部搜索、精英保留这几类做法组合在一起最后用Matlab实现并逐一验证。适合谁看如果你正准备写智能算法类的课程设计、论文仿真或者想用群体智能算法处理TSP以及类似的排序组合问题这篇文章里从原理设计到代码结构再到调参避坑基本都能找到可以直接参考的部分。1. 项目概述与核心思路拆解1.1 麻雀搜索算法的基本原理要把改进方案讲清楚得先把原生麻雀搜索算法的逻辑捋一遍。麻雀搜索算法把种群分成三类角色发现者负责带路能量储备较高对应适应度比较好的个体加入者跟着发现者的方向走同时有机会竞争更好的觅食位置侦察者数量不大但任务很重发现危险时会第一时间发出警报带动整个群体散开。原生算法里的位置更新公式是在连续空间设计的发现者会根据预警值R2和安全阈值ST决定是否扩大搜索范围加入者则向当前最优位置或全局最优位置靠拢侦察者会随机接受一个扰动从而维持整个种群的多样性。优点很明显结构简单、容易理解和实现连续优化时收敛速度确实快。但缺点也同样突出。第一种群的更新严重依赖连续数值运算而TSP的解空间是离散的排列不能直接套用第二麻雀搜索算法没有有效的记忆机制一旦某种模式占据了主导地位后续很难跳出来结果就是提前收敛到局部最优第三对路径这类强约束的解直接交换或随机扰动的破坏性太强可能会导致结构被反复冲散。这几个缺点也正是“多混合策略改进”想解决的三个方向。1.2 为什么拿TSP做验证场景TSP是一个经典的NP难问题描述起来一句话就能说清楚给定若干城市和两两之间的距离找一条经过所有城市且只经过一次的路径使总里程最短。但“一句话能说清楚”不代表“一行代码能解决”。城市数量增加到三五十个解空间就会膨胀到天文数字如果城市上百靠穷举和简单贪心根本不可能保证最优。正因为它足够难又有公认的测试集和已知最优解所以特别适合用来验证一个智能算法的改进是否有效。你说算法好那就拿TSPLIBTSP标准测试库里的berlin52、eil51、st70跑一跑收敛曲线、平均解、最优解全部对照一遍好坏一目了然。另外TSP本身在物流配送、航班调度、电路钻孔等场景中也有大量真实需求把改进算法跑通TSP后后续要套到工程问题上思路也顺理成章。1.3 “多混合策略”整体设计思路我在这个项目里的设计思路本质上是在补SSA在离散优化上的三块短板初始解质量、后期逃逸能力、精细局部寻优。单独拿任何一个策略出来都不是很新鲜的东西但组合起来能解决实际问题。初始质量初始化时引入Logistic混沌映射在排列空间上生成分布更均匀的初始路径集合避免一开始就挤在一起搜索节奏用非线性自适应权重和动态发现者比例让迭代前期多探索、后期多开发避免后期完全停滞局部寻优在每轮更新后对精英个体做2-opt局部搜索相当于给全局搜索加了一把精细的旋钮全局记忆采用精英保留策略每一代的最优解不会被后续操作破坏并且通过停滞判断触发部分个体重新初始化。四个策略各管一个阶段组合起来就是我标题里说的“多混合策略”。下面把每个策略的设计原因和实现细节展开讲。2. 多混合策略改进的详细设计2.1 混沌映射初始化让初始种群先“铺开”原生SSA大多用纯随机方式生成初始种群在连续空间下问题不大因为连续空间的随机分布还算均匀。但用到TSP的排列编码后纯随机初始化的结果往往有两类问题一是很多初始路径的结构高度相似比如都保留了“先按序号排序再局部微调”的趋向导致种群的探索范围非常窄二是个体间差异过大被随机冲散后续收敛需要花掉大量迭代次数。我的做法是先用Logistic混沌序列来生成初始路径。Logistic映射是一个很常见的一维混沌系统公式是x_{n1} μ * x_n * (1 - x_n)当μ取3.99到4之间时序列会进入混沌状态遍历性比普通随机数好得多。实现时先给每个个体生成一列长度为城市数量的混沌值再把这列值按从小到大排序用排序后的索引当作路径编码。这样既保持了随机性又让路径在排列空间里更分散初始种群的多样性会有可感知的提升。这里有一个细节需要特别注意μ的取值范围不能太随意。取3.8以下时混沌性会明显减弱序列可能落入周期轨道我一般固定在3.99到4之间既保证混沌性也避免数值溢出。这个小细节在低维度不敏感但城市数量过百后差异会放大。2.2 自适应权重与发现者比例调整原生SSA把发现者的比例固定为一个常数通常是20%左右。但在实际迭代中这个比例不应该一成不变前期种群需要更多“探索者”去发现新的区域后期则只需要少部分个体做局部开发其他个体应该围绕已发现的好区域做更精细的搜索。我在这版实现里加了两个调整。一个是惯性权重w按照w w_max - (w_max - w_min) * iter / maxIter线性递减用来控制位置更新的幅度另一个是发现者比例初始值设成0.35然后逐步降到0.15左右。这两个参数都在迭代过程中动态变化目的都是为了在不同阶段控制算法的“探索”和“开发”倾向。有人可能会问就一个比例参数值得专门写吗值得。如果你跑过原生SSA求解TSP你会发现后期几乎每轮产生的都是非常相似的路径这说明群体已经严重同质化。动态比例配合后面的重启机制能明显把这个同质化趋势往后推给算法争取更多的有效迭代空间。2.3 2-opt局部搜索给全局搜索装上“精修扳手”TSP里最经典的局部搜索就是2-opt。它的思路特别朴素在一条路径里任选两条边把这两条边之间的路径段反转一下如果翻转后的总距离更短就接受这个翻转否则不保留。我现在电脑上跑TSP的时候2-opt几乎是我必加的一个后处理算子因为它专门处理路径里的“交叉边”。为什么它能有效因为对欧氏距离下的TSP来说一条没有交叉的路径是局部最优的必要条件。路径一旦存在交叉边2-opt一定能找到更短的结构。对TSP来说交叉边几乎等价于“坏解”所以2-opt可以快速清理全局搜索产生的低质量结构把解拉到更合理的邻域里。实现时要注意我并不是对每个个体都做完整2-opt那样时间复杂度会非常高。一个比较务实的做法是只对当代种群中适应度最好的前3到5个个体执行2-opt其余个体保持原来的全局搜索节奏。这样既能保证最优个体不断被精修又不会让运行时间失控。2.4 精英保留与停滞重启群体智能算法有一个通病经过若干代迭代后如果某个个体偶然占据优势整个种群会迅速向它靠拢。这时候如果该个体只是一个局部最优解算法就会卡住再迭代多少代都不会有本质改善。针对这个问题我加了一个比较简单的精英保留机制每轮迭代结束后如果发现新的最优解就覆盖记录如果连续很多代都没有提升就触发停滞重启。重启方式不是全部推倒而是随机抽掉一部分个体用混沌初始化重新生成同时保留精英个体继续参与竞争。相当于在老的格局里放一批“新血液”再让自然选择去重新洗牌。这个策略唯一的代价是多了一个动态阈值参数我习惯设成最大迭代次数的10%也就是连续10%的迭代都没有更新最优解就触发一次重启。在后面的Matlab代码里这个逻辑可以看得很清楚。3. Matlab实现与核心代码3.1 数据预处理距离矩阵与路径长度计算Matlab里做TSP第一步通常是加载城市坐标然后算出两两距离矩阵。以TSPLIB的berlin52为例数据文件里给的是x、y坐标直接用欧氏距离计算即可。下面是通用的距离矩阵计算函数function distMat calcDistance(cityXY) % CALCDISTANCE 计算城市间欧氏距离矩阵 % cityXY : N x 2矩阵第1列是x坐标第2列是y坐标 % distMat: N x N矩阵distMat(i,j)为城市i到j的直线距离 N size(cityXY, 1); distMat zeros(N, N); for i 1:N for j i1:N d sqrt((cityXY(i,1) - cityXY(j,1))^2 ... (cityXY(i,2) - cityXY(j,2))^2); distMat(i, j) d; distMat(j, i) d; end end end路径长度函数更简单就是把相邻城市间的距离累加最后再加回起点的距离。注意在TSP里路径可以看成一个闭合回路所以计算时要多算一次“最后回到起点”的边。很多新手在这里漏掉闭合回路导致最后结果比实际要小这个问题在结果对比时会直接影响排名。3.2 混沌映射初始化函数混沌初始化函数的核心就是用Logistic序列生成排列。代码量不大但要注意先把随机序列迭代一段预热消除初始随机数的影响function pop chaosInit(popSize, Ncity, mu) % CHAOSINIT 基于Logistic混沌序列生成初始路径种群 % popSize : 种群规模 % Ncity : 城市数量 % mu : Logistic参数通常取3.99~4 % pop : popSize x Ncity矩阵每行是一条路径的序号序列 pop zeros(popSize, Ncity
