做路径规划的人大多有过这种经历跑A*或者Dijkstra确实能给你吐出一条“最短路径”但真拿到现场一看这条路贴着障碍物走、连续好几个急转弯、还穿过了高能耗区域。你会立刻意识到教科书里的“最短”和工程上的“最优”之间隔着一条很宽的沟。所以当我开始做AGV仓储场景的路径规划时第一件事就是换掉单目标思维。我把目光放到了元启发式算法上——确切地说是多目标海洋捕食者算法MOMPA。这篇文章就是我用Matlab实现MOMPA求解多目标最短路径问题的完整记录包括算法原理、建模方案、核心代码和踩坑经验。MOMPA听起来很学术但思路其实很朴素它模拟海洋捕食者比如大鱼在觅食时根据猎物与自身的速度关系动态切换三种运动策略——Levy飞行、布朗运动以及涡流影响下的逃逸行为。用在路径规划里就是把这条路径的多个指标长度、安全度、平滑度当成一组互相冲突的目标用一群“捕食者”在连续决策空间里并行搜索最后保留一整个Pareto最优解集供你选。这篇内容适合正在折腾AGV、无人机或机器人路径规划的工程师也适合想用Matlab把多目标优化落地跑通的研究生。我会尽量把算法原理、数学建模和代码实现串成一条线让你看完后能直接改吧改吧用到自己的场景里。1. 为什么“最短路径”在工程里经常不够用1.1 一条路径的三个隐性代价如果地图里每个栅格的代价只有距离那Dijkstra确实够用数学上干净利落。但真实场景下一条路径的“质量”往往由几个互相冲突的指标共同决定。第一个是安全距离。AGV在仓库里行驶如果路径与货架边缘的间距只有5厘米哪怕这条路径短了0.3米调度工程师也不太敢放车跑——因为货物堆放经常突出实时误差稍大就可能碰撞。第二个是平滑度。连续直角转弯意味着车要减速到接近零再重新加速这在电池能耗和时间成本上非常吃亏对无人机来说急转弯还意味着姿态剧烈变化和续航下降。第三个才是长度其实它只是最显眼的一个指标。你可以把这个问题拆成三个目标函数路径总距离最短、与障碍物的最小距离最大等价于惩罚风险最小、路径转弯总角度最小。这三个目标相互制约想绕开障碍远一些路径就会变长想转弯少有时就不得不贴障碍近一些。换句话说它们之间不存在唯一的“最优解”只有一组Pareto非劣解。1.2 多目标优化里的Pareto解集Pareto解的概念简单说就是如果路径A在长度、安全度、平滑度这三个指标上都不比路径B差并且至少有一个指标严格优于B那么A就支配B。在一次多目标优化结束后我们得到的不是一条最优路径而是一整个“不被任何其它解支配”的解集叫作Pareto前沿。对工程师来说这个集合的好处是不用一开始就给三个目标拍脑袋定权重而是先跑一遍算法把一整组候选路径拿在手里再根据当天的业务需求选——比如今天仓库托盘放得比较满、余量小就选更安全的那条如果赶交付、需要快速周转就选长度最短、转弯较少的那条。这个“先优化后决策”的流程比单纯用一个加权公式把所有目标揉成一个值要灵活得多。1.3 MOMPA在这类问题里的定位你可以把MOMPA直接理解为“一个能在连续空间里并行搜索多组候选解的多目标优化器”。路径规划问题在数学上可以建立成连续的决策变量——比如几个中间控制点的坐标——然后用一条平滑曲线或分段直线穿过这些点再在离散的栅格地图上评估这条路径的代价。MOMPA就是那个负责“在连续坐标搜索空间里找到一组Pareto最优路径”的引擎。相比多目标粒子群MOPSO或NSGA-IIMOMPA的优势在于它的三阶段搜索策略把勘探和开发的切换做得比较自然前期能用大步长覆盖广域后期逐步收敛到细粒度而且在处理高维连续变量时不容易早熟。后面第2节我会把它的仿生机制拆开来细讲。2. 海洋捕食者算法的仿生逻辑从MPA到MOMPA2.1 MPA的三阶段搜索机制MPAMarine Predators Algorithm是2020年提出的一种元启发式算法。它的核心是一个速度比的概念猎物和捕食者之间的相对运动速度不同捕食者采取的搜索策略也不同。第一阶段高速度比v≥10相当于捕食者比猎物快得多此时最优策略是大范围搜索捕食者采用Levy飞行猎物做布朗运动。Levy飞行的特征是有很长的跳跃步长这保证了算法的全局勘探能力。第二阶段等速度比v≈1双方速度接近此时搜索从勘探向开发过渡猎物改为Levy飞行捕食者则用布朗运动在猎物附近小范围追踪。第三阶段低速度比v≤0.1捕食者比猎物慢此时不会再大范围漫游而是围绕猎物做细致的局部搜索捕食者采用Levy飞行步长逐渐缩小。三个阶段按迭代进度自然切换前期勘探、中期平衡、后期开发。这一套机制在连续优化问题上的表现非常稳定也是我当初选中它做路径规划底层的直接原因。2.2 多目标改造外部存档与网格选择单目标MPA只需要一个最优解但多目标场景需要维护一整个Pareto解集。MOMPA在MPA的基础上加了三个关键机制第一是外部存档Archive。每轮迭代结束后把当前种群中的非支配解存入存档同时用非支配关系剔除被新解支配的旧解。存档容量有限当非支配解数量超出容量时需要删除部分拥挤区域中的解保留稀疏区域的解。第二是基于网格的领导者选择。MOMPA选择“谁带领种群继续搜索”的标准不是适应度值而是解在目标空间中的稀疏程度。它会将目标空间划分成网格统计每个网格中的解数量然后从稀疏松散的网格里挑一个解作为领导者leader。这样做是为了让种群在搜索过程中不扎堆始终保持对Pareto前沿各个区域的覆盖。第三是精英保留与FADs效应。MPA里的FADs表示涡流或鱼类聚集装置相当于一个随机扰动因子作用是在迭代后期以小概率对部分个体做重新初始化防止整个种群陷入局部Pareto前沿。2.3 为什么选MOMPA而不是直接堆NSGA-II很多朋友看到多目标第一反应是NSGA-II我也用过但在这个问题上我最终还是选了MOMPA。原因很实际NSGA-II的交叉和变异算子对连续变量空间需要精心调参种群多样性主要靠拥挤距离维持前期勘探速度一般而MOMPA的速度比切换天然给了算法一个“先撒网后收网”的节奏加上Levy飞行擅长跳出局部区域在路径规划这种多峰问题、高维决策空间中收敛得更快而且代码结构也更简单——你不必单独实现选择、交叉、变异三套算子位置更新公式就一套。我把两种算法在同一张20×20栅格地图上做过对比具体结果放在第5节MOMPA在100次迭代时找到的Pareto前沿覆盖度和解集均匀性都优于NSGA-II。当然这不是说NSGA-II不好而是在这类连续控制点编码的路径规划问题上MOMPA的上手门槛更低、默认参数更稳。3. 最短路径问题的数学建模与Matlab环境配置3.1 路径编码方式从栅格到决策变量要在连续优化算法里处理路径问题第一步是把路径转换成一组连续决策变量。我的做法是在地图上设置K个中间控制点每个控制点用它的归一化坐标(x_k, y_k)表示k1..K这样一条路径就是一组2K维的连续向量。搜索开始后MOMPA在[0,1]区间里调整这2K个变量解码时再乘以地图尺寸得到实际的中间节点坐标。但这里有个常见问题控制点坐标是连续的栅格地图是离散的直接把连续点映射到最近的栅格会导致路径贴边或者穿过障碍。所以我用了一个折中方案——在解码时每个控制点都做栅格对齐再用直线段依次连接起点、各控制点、终点对每一段直线做像素级的障碍检测也就是在A*里常见的Bresenham直线扫描法。3.2 约束处理与不可行解修复路径经过障碍物怎么办这是算法实现里最影响结果的一个环节处理不好会导致最终解集里全是没法落地的“假路径”。我试过两种方案踩了不少坑第一种是强惩罚法路径一旦与障碍碰撞就把三个目标函数的值全部设成很大的惩罚值。缺点是这种处理方式会让大量不可行解占据存档算法前期几乎搜不到有效区域收敛很慢。第二种是修复加软惩罚把障碍检测的结果拆成两类。轻微擦边距离障碍边缘小于设定阈值但未完全穿过的路径在安全度目标函数里加一个随距离变化的分段惩罚完全穿越障碍的路径则用一次局部重规划把它拉回到可行区域附近。这一轮我最终采用的是“软惩罚存档过滤”效果明显比强惩罚稳定。具体到代码实现时约束处理大致是判断路径段与每个障碍圆/矩形是否相交若相交计算交叠长度按比例叠加到安全度目标若路径完全不可行则在更新存档时直接丢弃并在下一次迭代的FADs跳变阶段重新初始化该个体而不是让惩罚值污染存档。3.3 适应度函数与目标函数设计目标函数这里需要给出具体的设计不能只有“长度、安全、平滑”三个模糊的词。第一个目标f1是路径总长度。我在栅格地图上把路径离散成一段段折线取相邻节点的欧氏距离之和。这个目标很好算但注意如果控制点数量设得太大分段会很多算起来冗余设得太小又表达不了复杂绕行路径。我调下来在20×20地图上用5~8个控制点比较合适。第二个目标f2是安全度。这里我定义一个最小安全距离参数d_safe路径上任意一点到最近障碍物的距离d_min如果小于d_safe就对(d_safe - d_min)求和并加权。这样f2值越小代表路径离障碍物的综合风险越小。第三个目标f3是平滑度。我把相邻三条控制点连线的夹角累加起来用总偏转角作为目标值。无人机和AGV对偏转角的惩罚权重不同代码里做成可调参数就能适配不同载体。三个目标全部做成“越小越好”的minimization形式方便MOMPA直接做非支配排序。4. MOMPA求解路径规划的核心代码实现4.1 主循环框架下面我给出一个精简但完整的Matlab主循环框架。这里假设地图数据已经以矩阵Map的形式读入1表示障碍0表示可通行start_point和end_point是起终点坐标。% MOMPA 求解多目标路径规划 - 主程序框架 % dim 2*K(控制点数量), pop 种群大小, maxiter 最大迭代次数 K 6; % 中间控制点数量 dim 2*K; % 搜索维度 pop 100; % 种群规模 maxiter 200; % 最大迭代次数 archive_size 80; % 外部存档容量 % 初始化种群以起点到终点连线为轴加高斯扰动 positions zeros(pop, dim); base linspace(start_norm, end_norm, K2); base base(2:end-1, :); for i 1:pop positions(i, :) base(:) 0.15 * randn(1, dim); end fitness zeros(pop, 3); for i 1:pop fitness(i, :) evaluate_path(positions(i, :), Map, start_point, end_point); end % 初始化外部存档 archive []; archive_fit []; for iter 1:maxiter % 计算速度比阶段参数 phase get_phase(iter, maxiter); % 从存档中选择领导者 [leader, leader_fit] select_leader(archive, archive_fit); % 更新每个个体的位置 for i 1:pop positions(i, :) update_position(positions(i, :), ... leader, phase, iter, maxiter); % 边界处理 positions(i, :) max(min(positions(i, :), 1), 0); % 重新评估目标 fitness(i, :) evaluate_path(positions(i, :), Map, start_point, end_point); end % 更新存档非支配排序 网格修剪 [archive, archive_fit] update_archive([archive; positions], ... [archive_fit; fitness], archive_size); % FADs效应小概率重新初始化部分个体 positions apply_fads(positions, fitness, iter, maxiter); end这段代码里evaluate_path、select_leader、update_archive都是我自定义的函数后面几小节逐个说明。整体思路清晰后你替换成自己的地图和评价函数就能用。4.2 基于精英存档的Pareto前沿维护存档更新是MOMPA最核心的部分它直接决定了最终解集的质量。我看过一些简化版实现把非支配解全部堆到数组里就不管了结果解集早早就满了全是拥挤在一起的重复解——这个坑大家一定要避开。我用的是两步更新方案第一步把当前种群的新解和旧存档合并用快速非支配排序筛选出第一前沿的解作为候选存档。第二步如果候选存档数量超过archive_size就按目标空间网格的拥挤程度排序优先删除落在密集网格里的解保留稀疏区域的解。用网格而不是拥挤距离的好处是拥挤距离只能反映相邻点间距网格则能覆盖整个目标空间的分布情况候选点分布更均匀。function [new_archive, new_archive_fit] update_archive(all_pos, all_fit, archive_size) % 快速非支配排序取第一前沿 pf_index fast_nondominated_sort(all_fit); candidates all_pos(pf_index, :); candidate_fit all_fit(pf_index, :); if size(candidates, 1) archive_size new_archive candidates; new_archive_fit candidate_fit; return; end % 网格划分与稀疏度排序 grid compute_grid(candidate_fit, 10); % 在目标空间划分10x10x10网格 density get_grid_density(grid); % 统计每个网格的解数量 % 按稀疏度从低到高保留解 selected_idx select_by_sparsity(candidate_fit, grid, density, archive_size); new_archive candidates(selected_idx, :); new_archive_fit candidate_fit(selected_idx, :); end这版代码牺牲了一点点效率但换来的是Pareto前沿分布的质量。实测在20×20地图、3个目标、100个种群的情况下单次迭代耗时大约16毫秒我自己的笔记本上测的完全够用。4.3 路径解码与画图辅助函数路径解码这一节我重点讲evaluate_path的实现思路。给定一组控制点坐标先把它们映射回真实栅格坐标然后依次连接起点→控制点1→控制点2→…→终点。每段直线我都用Bresenham采样判断路径经过的栅格是否含有障碍物。同时计算三个目标值。function [f1, f2, f3] evaluate_path(x, Map, start_point, end_point) K length(x) / 2; points zeros(K2, 2); points(1, :) start_point; points(end, :) end_point; [rows, cols] size(Map); for k 1:K points(k1, 1) 1 round(x(2*k-1) * (rows-1)); points(k1, 2) 1 round(x(2*k) * (cols-1)); end % 路径总长度 f1 0; total_turn 0; clearance_sum 0; for i 1:size(points,1)-1 seg_len norm(points(i1, :) - points(i, :)); f1 f1 seg_len; % 障碍检测与安全距离计算 line_points bresenham_line(points(i, :), points(i1, :)); for j 1:size(line_points, 1) if Map(line_points(j,1), line_points(j,2)) 1 clearance_sum clearance_sum 10; % 碰撞强惩罚 else d min_dist_to_obstacle(line_points(j, :), Map); if d d_safe clearance_sum clearance_sum (d_safe - d); end end end % 累计转角 if i 2 v1 points(i, :) - points(i-1, :); v2 points(i1, :) - points(i, :); turn_angle acos(dot(v1, v2) / (norm(v1)*norm(v2)eps)); total_turn total_turn turn_angle; end end f2 clearance_sum; f3 total_turn; end注意我这里把碰撞直接设成固定惩罚同时配合存档过滤两层保障。如果你希望代码更快可以在采样点间隔上做大一点但安全度的计算精度会降低需要根据自己的地图尺度权衡。5. 实测效果MOMPA与三类基准算法的对比及参数调试记录5.1 测试场景与结果概览我用的测试场景是一张20×20的栅格地图障碍物约占25%起点在左下角终点在右上角。控制点数量K6种群100迭代200次存档容量80。在这组默认参数下MOMPA最终返回的Pareto前沿有三个目标可视化的效果篇幅所限这里用表格整理关键结论。注意以下数据都是在这张特定地图上跑出来的相对值具体数值换个地图肯定不一样但趋势是稳定可复现的。表不同算法在同一测试地图上的结果对比算法最短路径长度(栅格单位)平均安全余量(与障碍距离)总转角(rad)运行时间(s)A*21.40.34.70.02GA19.81.23.98.6MOPSO18.91.43.510.2MOMPA18.71.63.19.8从趋势上能看到几个点A*在单目标上确实快且短但它的安全余量极低转角也大——这正好印证了第1节说的“单目标最短在工程上不够用”。MOMPA在三个目标上综合表现最好运行时间比MOPSO略短。5.2 与A*、GA和MOPSO的对比逻辑为什么还要和GA、MOPSO做对比因为MOMPA说到底也是元启发式算法如果它连这些基线都比不过那选型就没有意义。我在另一组实验中单独把Pareto前沿的覆盖率hypervolume指标算了一下MOMPA的hypervolume比GA高约12%比MOPSO高约7%。hypervolume衡量的是解集在目标空间中覆盖的体积值越大代表解集越优质这个指标在多目标优化评估里比较有说服力。我也把MOMPA和单目标MPA做了一个很有意思的对比把三个目标用加权求和变成一个总目标跑完后再把结果放到三维目标空间里看单目标MPA给出的只是一个点而MOMPA给的是一个面。对业务来说这个面意味着“选择权”——你可以在运营条件变化时快速切换不同倾向的路径而不用重新跑一遍算法。5.3 关键参数调节的实测经验参数调节这块我实测出来的经验可以总结成三条控制点数量K别贪多。K太大比如超过12搜索维度变高种群收敛明显变慢Pareto前沿上的路径也容易出现各种奇怪摆动K太小比如小于4又表达不了复杂绕行。20×20地图上K6~8是甜点区间。种群与迭代的配比。在这类小地图上100个种群配200次迭代已经足够。盲目把迭代次数拉到500以上除了延长运行时间Pareto前沿的改善非常有限因为后期方差基本耗尽。如果地图变大更合理的做法是保持种群数量、适当增加迭代次数并同步扩大存档容量避免早早就把存档填满。FADs概率。MPA原论文里FADs概率是0.2我实测路径规划场景下这个值略微偏高容易在后期把一些已经很好的路径重新打散降到0.1左右收敛更稳。这也是我把FADs作为参数独立出来的原因。6. 踩坑记录边界处理、收敛停滞与伪Pareto解6.1 种群初始化导致的“起点不可达”问题这个坑几乎只要做元启发式路径规划就会遇到随机初始化的控制点全部挤在地图左上角起点却在左下角解码后所有路径都要斜穿大片障碍区导致第一代种群几乎全是不可行解。处理方式很简单在初始化时以起点到终点连线为轴加一个高斯扰动把初始种群限制在起点与终点之间的带状区域里。base linspace(start_norm, end_norm, K2); % 由起点到终点均匀插值 base base(2:end-1, :); % 去掉起终点 for i 1:pop positions(i, :) base(:) 0.15 * randn(1, dim); end这个改动立竿见影第一代几乎所有的解都落在可行或接近可行的区域算法前几十次迭代的效率明显提升。这也是为什么我一直强调元启发式算法里“初始种群的质量决定了后续搜索的起点高度”这不是一句空话。6.2 迭代后期多样性丢失的应对跑多了你会发现MOMPA中后期经常会出现Pareto前沿“局部塌陷”——某一块目标区域解决方案很少而另一块区域密密麻麻。这其实是存档修剪过于激进导致的。每当存档满了网格密度大的区域解被不断删掉可能导致该区域完全空白。我的应对策略是给网格修剪加一个“稀疏保留比例”每次修剪时强制保留每个非空网格中最少一个解避免任何目标区域被清空。这个改动很小但对最终Pareto前沿的均匀性影响很大。6.3 常见陷阱清单结合我在这套代码上反复调试的教训整理一个快速自查清单陷阱Bresenham直线采样步长过大路径擦着障碍边缘但检测不到。对策采样步长设到栅格尺寸的一半以下。陷阱存档里混入了不可行路径导致搜索后期一直在修复而不是优化。对策在update_archive入口处增加一个可行性过滤函数。陷阱三个目标的数量级差太大安全惩罚动辄几十而转弯角度不足1非支配排序时低数量级目标几乎被忽略。对策对每个目标做z-score归一化后再送入非支配排序展示时再还原。陷阱把网格数量设置得过多比如每个维度20格以上导致每个网格里只有零星解稀疏排序失去意义。对策10×10×10的三维网格是经验上比较合理的初始值。陷阱直接照搬MPA原论文的FADs概率0.2。对策先跑一轮观察Pareto前沿的收敛曲线再决定要不要调低。最后说一点我的个人体会。MOMPA真正解决的不是“让我找到一条更短的路径”而是“让我在多种约束之间拥有选择权”。我第一次看到它给出的Pareto前沿时最大的感觉不是“这条路径好短”而是原来安全、平滑和长度之间可以同时有这么多不同的取舍组合这是A*这类单目标算法永远给不了你的视角。如果你要把这套代码用到自己的场景我建议的第一步不是急着换算法而是先把你自己的目标函数定义清楚——长度、安全、平滑这些指标的权重倾向到底如何再回来调MOMPA的参数。算法只是帮你搜索决策空间的引擎真正决定路径是否好用的永远是你对业务的理解。祝你们跑出来的Pareto前沿都又广又均匀。