调参数时,把一个数加上0.1就能得到新方案。规划路线时,把城市编号加上0.1却失去了意义。MMAO怎样处理这两种结构差异很大的任务?
其跨域设计把候选解的表示、修改动作和评价方式交给领域适配器,再通过资源、角色与种群状态组织搜索。用一条四城市路线走一遍,会比只看接口名称更容易理解。
假设城市A、B、C、D依次位于单位正方形的四个顶点,要求从A出发,访问每个城市一次,最后返回A,目标为路程最短。
候选路线A—C—B—D—A有两条对角线,总长约4.8284。把中间一段访问顺序反转,得到A—B—C—D—A,总长降到4,改进约0.8284。下面用标准Python复核。
from math import dist
cities = {"A": (0, 0), "B": (1, 0), "C": (1, 1), "D": (0, 1)}
def route_length(route):
closed = route[1:] + route[:1]
return sum(dist(cities[a], cities[b]) for a, b in zip(route, closed))
before = ["A", "C", "B", "D"]
after = before[:1] + list(reversed(before[1:3])) + before[3:]
print(round(route_length(before), 4), round(route_length(after), 4))输出为4.8284 4.0。这个例子演示了路线编码、一次2-opt式片段反转和评价方式,便于理解路线适配器需要提供的内容。公开包的完整求解还包括种群与资源控制。
计算路线长度时,最后一个城市还要连接回起点。若只把访问顺序中相邻城市的距离相加,就会漏掉闭环的一条边。这个错误在小例子里很容易发现,在较大数据集上则可能让结果看起来异常好。
城市编号也只是索引。编号相近通常无法说明地理位置相近,因此路线动作应针对顺序与连接结构。片段反转之所以有意义,是因为它能够改变边的连接,同时保留城市集合。生成新路线之后,仍要检查每个城市是否恰好出现一次。
前面的四城市问题允许手算最优值,可以同时检查距离函数、闭环处理和一次局部修改。扩大到标准实例后,还需要确认距离定义,例如是否按数据集规则取整。两个实现采用不同距离口径时,即使访问顺序相同,报告长度也可能不同。
还可以比较同一条闭环的不同写法。从不同城市开始列出顺序,可能表示相同回路。对称距离下,逆向访问也可能具有相同长度。若使用缓存或结构记忆,可以考虑这些等价关系,明确什么算作一个新方案。
这些细节会影响后续资源反馈。距离函数漏算一条边,会产生错误改进。重复城市若未被发现,候选可能获得不合理的低成本。先把合法性与评价写清楚,才能让控制器接收到可靠信号。
一个路线个体保存当前访问顺序、路线长度、能量、角色和相关记忆。它产生新路线后,先检查城市是否完整且没有重复,再计算长度变化,将缩短量转换成资源反馈。
获得改进的个体可能继续围绕较好路线细化,公共资源也可能支持生成新路线个体。更大的结构扰动则帮助搜索不同的路线区域。具体使用哪些动作、何时使用,取决于对应实现。

图1 框架论文中的eil51代表性轨迹,记录路线长度与资源、种群和角色状态。
看图1时,可以先找到路线长度下降的区间,再对照种群与资源池。同样是一次目标改善,路线实现必须先产生合法排列,才能进入后续反馈环节。图中的曲线可以帮助定位何时发生了改进,具体采用了哪种路线操作还要查日志。
一个可检查的路线适配器至少需要完成初始化、产生修改、检查合法性和计算长度。初始化可以从随机排列或构造方法开始,修改可以采用片段反转、交换或较大扰动,合法性检查则确认城市集合与访问次数。
假设一个个体在路线中找到可缩短的连接,改进量先按既定目标计算,再进入收益转换。资源控制决定后续投入倾向,具体怎样反转片段仍由路线操作实现。研究某种反馈是否有效时,应该尽量固定这些领域动作,避免把动作本身的改善与控制变化混在一起。
局部搜索还涉及搜索深度。尝试一次边交换,与扫描大量边组合寻找最好交换,成本可能相差很大。即使两者都被称为一次局部改进,内部检查数量也可能不同。实验中可以记录候选路线评价数、局部交换检查数和总时间,解释计算花在何处。
如果预先计算城市距离矩阵,某次路线变化的增量也可以通过少量边计算获得。采用增量计算后,还应定期与完整路线长度核对,防止更新误差累积。这样的工程细节会影响速度,也影响结果是否可靠。
连续任务可以沿方向试探、加入小幅扰动,再处理上下界。旅行商任务更适合片段反转、交换和路线重构。多维背包则用选或不选表示物品,一次位翻转之后还要检查所有容量限制。
任务 | 候选方案 | 一次修改 | 修改后必须检查 |
|---|---|---|---|
连续参数 |
| 调整数值 | 边界与目标返回值 |
城市路线 |
| 反转访问片段 | 城市完整性与闭环长度 |
物品选择 |
| 加入或移除物品 | 各维容量约束 |
分类配置 | 特征掩码和模型参数 | 修改特征与参数 | 合法配置、训练与验证流程 |
接入业务问题时,可以先写出“构造一个合法解”“修改一个解”“评价一个解”三个最小函数。随机生成一批候选,检查这些函数在极端输入下是否仍能工作,再接入完整优化循环。
例如,背包方案超载时,需要明确修复规则以及修复后的收益计算。如果修复过程进行了多次评价,这些调用也应进入成本记录,否则比较时容易低估实际开销。
连续任务看起来只需处理实数,变量尺度仍会影响搜索。假设一个参数在0到1之间,另一个在0到一万之间,对两者使用相同绝对扰动,就可能让前者变化过大、后者几乎不动。可以根据各自边界定义相对变化,再检查实际动作是否符合业务含义。
边界处理也会改变候选分布。直接截取到上下界,可能让一些候选集中在边界。反射或重新采样则有不同的行为。使用公开实现时,应先阅读它采用的方式,再判断是否适合自己的变量范围。
若变量必须为整数,生成连续值后如何取整,也需要确定。某些整数变量只允许若干离散档位,简单四舍五入可能产生无效值。混合变量任务还可能包含条件参数,例如选择某类模型后,只有部分参数生效。编码与解码应明确这些关系。
可以先生成十几个候选,把解码后的业务配置打印出来。检查数值范围、整数规则和条件参数,再运行完整优化。这个小步骤能够提前发现大量输入问题,减少把编码错误误判为算法表现不佳的情况。
用一个教学函数可以说明这个问题,令f(x) = (x*x - 1)**2 + 0.2*x,以目标越小越好。右侧低谷在0.97附近,那里目标约为0.1975。向0.9移动时目标约为0.2161,走到0则为1;左侧位置-1的目标为-0.2,更加有利。
如果一个实现只接受改善当前目标的候选,那么逐步经过这些较差位置会受到接受规则限制。它的跨区域机会主要来自一次足够大的候选跳跃,直接到达更好位置,或者来自在其他区域初始化的新个体。角色变得更偏探索时,还需要候选尺度与采样支持覆盖到这些位置。
路线任务也有类似问题。一条路线可能在规定的2-opt邻域内已经找不到改善,但经过更大结构重组后,仍可能获得更短路线。此时,可以由路线扰动产生新的结构,再进行局部改进。资源反馈能够安排何时投入这些动作,具体跨越能力则由扰动、修复与接受方式共同决定。
因此,应用MMAO时可以检查停滞后实际生成了什么。连续候选是否跨出当前盆地,路线是否改变了关键连接,修复是否又把候选带回原有结构。这些领域记录能够解释角色调整与个体更新为何有效,以及它们在哪些条件下作用有限。
假设有A、B、C三件物品,收益分别为4、5、6。每件物品消耗两类容量,A为[2, 1],B为[3, 2],C为[2, 3],两类容量上限都是4。候选[1, 0, 1]选择A与C,总消耗为[4, 4],收益为10,满足容量限制。
若候选变成[1, 1, 1],收益虽然升到15,总消耗却为[7, 6]。程序需要按定义处理超载,例如通过修复规则移除物品,或在评价中明确约束代价。采用修复时,必须使用修复后的方案与收益继续搜索。
在这个例子里,移除B会回到A与C的可行组合。其他实例可能存在多种修复顺序,它们会影响最终得到的候选。对比两种资源控制配置时,修复规则应记录一致,才能解释质量差异来自哪里。
修复也可能重复产生相同解。多个超载向量经过同一规则后都回到一个可行组合,表面候选数量很多,实际覆盖却有限。可以记录修复前后表示、修复次数和重复率,观察搜索是否把大量投入花在相同方案上。
适配器环节 | 连续任务可以核对什么 | 路线或背包可以核对什么 |
|---|---|---|
初始化 | 各维范围与尺度 | 合法排列或可行选择 |
候选生成 | 扰动幅度与变量类型 | 结构修改与容量变化 |
修复和解码 | 边界、整数、条件参数 | 城市完整性与多维约束 |
评价 | 目标方向与有限返回值 | 距离口径、收益及约束 |
成本记录 | 函数调用和耗时 | 局部检查、修复与调用 |
IEEE Access论文给出了如下十种子结果,指标为相对已知最优路线的平均差距,越低越好。
实例 | MMAO | CI+2opt | 校正后的比较 |
|---|---|---|---|
Berlin52 | 6.610% | 15.360% | 差异显著 |
eil51 | 10.070% | 10.260% | 差异未达显著水平 |
Berlin52上的差距相差8.750个百分点,eil51上相差0.190个百分点。两行结果共同说明,同一类路线配置在不同实例上的收益幅度会变化。论文中的Elkai-LKH专门方法在两者上均达到已知最优值,为路线求解质量提供了进一步参照。
引用这些数值时,要保留期刊论文的配置。早期框架论文也评估过这两个实例,其迭代、种群和实现设置不同,对应结果应分别阅读。

图2 上排为Rastrigin-30D,下排为动态Sphere,展示不同任务中的控制状态。
图2上排可观察逐步发生的种群与资源变化,下排则可围绕环境变化时点看状态重整。同样的字段在两类任务中产生不同轨迹,这使研究者能够用共同的记录方式分析各自的搜索行为。
公共池、角色和种群为不同领域提供了相近的观察入口,但字段含义要结合动作解释。连续任务中,新增个体可能围绕一个数值位置生成。路线任务中,新个体则需要一条合法排列。背包任务还要确认生成和修复之后的容量使用。
因此,可以在共同日志之外保存少量领域信息。路线保存长度和关键扰动类型,背包保存收益、容量使用和修复情况,连续任务保存试探尺度与边界命中情况。出现停滞时,这些信息能说明控制状态变化后,实际候选是否发生了有效改变。
图2上排的角色集中和公共预算积累,可以引出一个问题,后期投入是否还在改善目标。下排在环境变化附近出现状态调整,则可以继续检查旧记忆是否重评、恢复候选是否得到评价。相同字段使这些问题便于并列观察,解释仍要回到任务过程。
如果一个应用同时包含连续与离散变量,还可以先拆分检查。分别验证数值参数和组合结构的修改,再观察联合候选如何评价。这样可以定位某一类动作是否长期占用了预算,而另一部分变量几乎没有变化。
问题 | 常见检查位置 |
|---|---|
路线出现重复城市 | 编码、扰动和修复函数 |
更短路线被判为更差 | 最小化方向与奖励符号 |
资源机制正常但效果停滞 | 领域动作的幅度、覆盖和局部改进能力 |
同样迭代数耗时相差很大 | 局部搜索、修复和评价调用总数 |
四城市例子能够先验证表示和动作,Berlin52等标准实例则能检验规模扩大后的表现。沿着这条路径,读者可以逐步判断领域适配是否可靠,以及资源控制在该任务中增加了多少价值。
先把问题写成可运行的最小实例。路线任务用少量城市,背包任务用几件可手算的物品,连续任务用已知答案的简单函数。在这个阶段,重点核对表示、合法性和目标值,让每一步修改都有可解释的结果。
接着加入资源控制,保留一组固定种子和较小预算。查看个体是否获得合理收益、公共池是否按规则变化,以及新增候选是否真实进入搜索。若状态正常但目标没有改进,应先检查领域动作能否在这个实例上产生有效变化。
然后扩大规模,并加入合适的领域参照。路线可以与构造加局部搜索方法比较,背包可以在小实例上与已知最优值或精确方法核对,连续任务则可以选择成熟优化器。参照方法能够说明当前实现距离该任务的有效求解还有多远。
比较时,把领域预处理也计入说明。读取数据、建立距离矩阵、修复候选和训练模型的成本可能不同,单纯对齐外层轮数容易漏掉这些差别。根据实际需求,可以分别报告评价次数、总时间和最终质量。
最后保存能够重建问题的材料。除了软件版本与参数,还包括数据实例、距离或收益定义、约束规则、种子列表和停止条件。对于动态或在线任务,还要保存事件序列。这样,后续看到结果变化时,才有条件追溯是哪一环发生了变化。
还可以利用小实例检查终止与返回值。三物品背包只有八种选择,可以逐项枚举,确认可行组合的最高收益为10。四城市路线也可以枚举访问顺序,确认正方形边界路线达到长度4。将这些答案与程序返回值对照,可以检查它最终交付的方案是否与报告指标一致。
如果最优值已知,还可以记录第一次达到目标的评价次数。若两组配置最终都达到最优,但一组用了更多调用,这个差别对实际成本仍有意义。扩大到最优值未知的实例后,可以改为记录达到某个质量阈值的时间,或在固定预算下报告最好已知方案。
对新领域的第一次接入,最好也保留一个人工可查的反例。例如,故意输入重复城市、超载选择或越界数值,确认程序按定义处理。输入校验、修复与评价能够相互衔接,后续较长运行才更容易解释。
跨域应用的难点通常集中在这些具体接口。用四城市路线确认结构修改,用三物品背包确认约束修复,再逐步扩大问题,可以让控制器收到的每一次反馈都有明确来源。随后讨论资源如何影响搜索,才有完整的运行过程作为依据。
资料来源
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。