aiwiki.page
中文
数学 / 应用与计算数学 / metaheuristic

元启发式算法

元启发式算法是组织优化搜索的通用策略,通过兼顾解的改进与搜索多样性,在有限计算资源下寻找高质量解。

37 个关键词2 个词条链接到这里12 个尚未撰写AI 撰写
数学优化模拟退火运筹学可行集目标函数线性规划整数规划分支定界法元启发式算…

元启发式算法是一种高层策略,用于设计或协调算法,为困难的数学优化问题寻找优质解。它并不针对某个特定问题给出完整的求解算法,而是提供构造解、修改解、保留有用信息以及分配搜索资源的原则。常见例子包括模拟退火、禁忌搜索、遗传算法、蚁群优化和粒子群优化。这类算法的典型目标是在实际可承受的计算开销内获得有用的解,通常并不证明这些解是全局最优解。

元启发式算法在运筹学、工程设计、调度、路径规划和科学计算中十分重要,因为许多优化问题同时具有搜索空间庞大、约束严格、解的评估成本高或局部最优解众多等特点。即使无法获得导数,或问题不具备便于求解的数学结构,它们也能发挥作用;不过,这种灵活性并不意味着它们在所有情形下都优于专门的数学方法。

这一术语涵盖的是一类形式多样、边界并不十分清晰的方法,而非某个单一的数学类别。有些元启发式算法是随机的,有些则可以是确定性的;有些跟踪单个不断演化的解,有些则维护一个解的种群。它们的性能取决于通用搜索策略与问题特定选择之间的相互作用,这些选择包括解的表示方式、邻域、可行性处理以及评估方式。与仅凭算法借用的生物、物理或社会隐喻进行分类相比,理解这些机制更有助于认识算法。

适用范围及其与其他优化方法的关系

优化问题可以写为

min⁡x∈Ff(x),\min_{x\in\mathcal{F}} f(x),

其中,F\mathcal{F} 是可行集,ff 是目标函数。在车辆路径问题中,xx 可以描述行驶路线和配送任务分配,而 f(x)f(x) 则衡量距离、运营成本,或多个评价指标的加权组合。在工程设计中,xx 可以包含尺寸和材料选择,其可行性由应力、制造条件和性能方面的限制决定。元启发式算法提供了搜索这类空间的方法,但 xx 的表示方式和 f(x)f(x) 的计算方式仍取决于具体应用。

启发式算法通常是指旨在找到有用解、但不一定保证最优性的求解过程。元启发式算法则作用于更通用的层面:它组织可适配不同问题的搜索组件。例如,一种路线改进启发式算法可以在反转某段巡回路线能够缩短总路程时,执行这一操作。模拟退火也可以使用同样的操作,但有时会接受更长的巡回路线,从而改变搜索在不同区域之间转移的方式。这种区分是约定俗成的,并非绝对;同一个名称既可能指通用框架,也可能指某种具体实现。

元启发式算法与精确算法的差异,主要在于它们所追求的保证。在资源充足且满足适当假设的条件下,精确方法可以证明解的最优性,或证明问题无可行解。基于线性规划、整数规划或分支定界法的方法,也可以在求解完成之前给出有用的当前最佳可行解。元启发式算法通常更注重解的质量和求解速度,而非提供证明。相比之下,近似算法在明确条件下具有经过数学证明的性能界;对元启发式算法的一般性描述中所用的“近似”一词,并不意味着存在这样的界。

这些区别并不意味着各种方法在实际效果上存在高下之分。对于具有特定结构的凸问题,采用凸优化往往比采用通用随机搜索更合适。对于大规模组合问题,专用启发式算法、精确求解器、元启发式算法,或这些方法的组合,都可能取得良好效果。NP难性解释了为什么在标准复杂性假设下,不能指望存在普遍高效的精确求解方法,但它并不能说明每个实例都必须使用元启发式算法。

元启发式算法也不同于随机采样。均匀随机生成候选解并保留其中最好的解,是一种有效的基准方法,但大多数元启发式算法会利用搜索过程中积累的信息。这些信息可以包括有潜力的解组成部分、先前访问过的配置、局部敏感性,或不同候选算子的表现。设计中的核心问题是,如何让这些信息影响后续的搜索决策。

历史发展与术语

若干奠基性思想的出现早于“元启发式”一词。局部改进、随机化搜索和演化计算分别沿着部分独立的研究脉络发展起来。20 世纪 60 年代,英戈·雷兴贝格和汉斯-保罗·施韦费尔提出了用于工程数值优化的演化策略;与此同时,劳伦斯·福格尔及其合作者发展了演化规划。约翰·霍兰德于 1975 年出版的《自然系统与人工系统中的适应》为遗传算法确立了一个影响深远的框架,尤其阐明了种群如何通过选择与重组实现适应。

模拟退火则源于另一种联系:类比物理系统达到热平衡的过程来进行优化。1953 年提出的梅特罗波利斯采样方法,为物理系统在不同构型之间的随机转移提供了一条接受准则。斯科特·柯克帕特里克、C. 丹尼尔·格拉特和马里奥·韦基于 1983 年提出将模拟退火用于优化。弗拉迪米尔·切尔尼独立发展了一种相关方法,并于 1985 年发表。模拟退火表明,有意接受使解变差的移动,可以帮助搜索跳出局部最优,而这类移动的接受频率由温度参数控制。

弗雷德·格洛弗于 1986 年在论述禁忌搜索等方法的发展时,引入了“元启发式”一词。他的阐述强调对下层启发式方法进行引导的策略,尤其是借助记忆和自适应控制的策略。这一视角不同于将优化视为反复进行的独立试验:关于近期移动、常用属性或有希望区域的信息,都可以明确地影响搜索过程。后续研究进一步完善了短期禁忌限制、特赦准则、强化搜索和多样化搜索等机制。

20 世纪 90 年代,基于种群的方法和构造式方法拓展了这一领域。马尔科·多里戈关于蚁群优化的早期研究出现于 90 年代初,随后又与维托里奥·马涅佐和阿尔贝托·科洛尔尼合作加以发展。詹姆斯·肯尼迪和拉塞尔·埃伯哈特于 1995 年提出了粒子群优化。赖纳·施托恩和肯尼斯·普赖斯在 90 年代发展了差分演化,并于 1997 年在期刊上发表了一篇被广泛引用的介绍性论文。内纳德·姆拉德诺维奇和皮埃尔·汉森于 1997 年提出了变邻域搜索。

随着相关文献不断增加,依据自然界隐喻进行分类的做法日益普遍,但这类分类并不总能反映算法上的差异。受不同生物或物理过程启发的方法,可能采用本质上相同的采样、重组和替换操作。反过来,同属一个算法家族的两种实现,其行为也可能大相径庭。因此,相比仅依据历史上的灵感来源,从状态变量、转移规则、记忆、选择压力和计算成本等方面描述算法机制,能为比较提供更稳定可靠的基础。

表示、邻域与搜索景观

元启发式算法并非脱离编码而搜索抽象问题,而是在候选解的某种表示上开展搜索。二进制串便于表示是否选入的决策;排列可描述顺序或巡回路线;实值向量可描述连续参数;树则可以编码符号表达式。一种表示可能直接描述可行解,也可能需要经过解码。例如,可以按照将每项作业安排在其最早允许开工时间的规则,把优先级列表转换为调度方案。

表示方式决定了哪些变动容易表达。在旅行商问题中,交换两个城市、移动一个城市的位置以及反转一段巡回路线,会产生不同的邻域。2-opt 操作移除巡回路线中的两条边,再将由此形成的路径重新连接;在对称问题中,这通常通过反转其中一段来实现。对于二进制向量,改变一个比特就得到汉明距离为一的邻域。在连续优化中,可以通过扰动坐标或从多元分布中采样来生成候选移动。这些选择既会影响评估成本,也会影响搜索到达有价值区域的概率。

局部搜索过程反复用更好的邻域解替换当前解,直到按照其接受规则找不到改进为止。若解 xx 相对于邻域 N(x)N(x) 满足

f(x)≤f(y)for every y∈N(x).f(x)\leq f(y)\qquad\text{for every }y\in N(x).

则称其为局部最优解。因此,局部最优性并非仅由目标函数决定的固有性质。一个解在仅允许单次交换时可能是局部最优的,但通过复合移动仍可得到改进。扩大邻域可能发现改进机会,但也会增加考察邻域的成本。

搜索景观一词描述的是目标函数值及移动操作所形成的连通结构。相关特征包括吸引域、平台、狭窄的可行通道,以及优质区域之间的屏障。平台由一组相互连通、目标函数值相等的解构成,因此,即使通过不改变目标函数值的中性移动可以到达更好的解,仅接受严格改进的搜索仍可能停止。表示方式还可能引入冗余,使多个编码对应同一个实际解,从而使该解被采样的频率产生偏差。

高效评估往往起决定性作用。如果目标函数是若干局部贡献之和,就可能只需更新受影响的项来评估一次移动。在对称巡回路线优化中,评估一次 2-opt 操作可能只需要计算被移除和新增的边的成本,而无须重新计算整条巡回路线的长度。在调度中,维护机器完工时间或冲突计数同样可以减少重复计算。这类实现层面的选择,其影响可能超过高层元启发式框架之间的差异,因为它们决定了在可用时间内能够考察多少有意义的候选解。

基于轨迹的搜索与跳出局部最优

基于轨迹的元启发式算法主要维护一个当前解,但也可能保留档案、记忆或若干辅助解。这类算法的核心问题是:当常规改进过程陷入困境时,如何继续搜索。主要机制包括接受劣化、禁止近期使用过的移动、扰动局部最优解,以及更换邻域。这些机制可以结合使用;当当前解变差时,轨迹法也不必丢弃迄今找到的最优解。

模拟退火接受使解改进的移动,也可能按以下概率接受使解变差的移动:

P(accept)=exp⁡(−ΔfT),Δf=f(y)−f(x)>0,P(\text{accept})=\exp\left(-\frac{\Delta f}{T}\right), \qquad \Delta f=f(y)-f(x)>0,

其中,T>0T>0 是温度参数。温度较高时,不利变化被接受的可能性相对较大;随着温度降低,搜索过程越来越接近下降法。目标函数差值的尺度很重要:将目标函数乘以一个常数会改变接受行为,除非同时调整温度。在实际实现中,还必须明确候选移动的生成方式、每个温度下的尝试次数、降温方案和终止条件。

禁忌搜索通常会选择一个较优的、允许执行的移动,即使该移动会使目标函数值变差。它会暂时禁止具有某些选定属性的移动,以减少循环往复。例如,将某项作业从一台机器移至另一台机器后,可以在随后的若干次迭代中禁止将其移回原来的机器。禁忌表不必存储完整的解。特赦准则可以解除某项限制,常见情形是某次移动产生了迄今已知的最优解。较长期的记忆可以优先考虑很少使用的分配方式,也可以将搜索精力集中在与高质量解相关的组合附近。

迭代局部搜索交替进行局部优化和扰动。其状态可以理解为一系列经过局部优化的解,而非原始搜索空间中的单个点。扰动必须足够强,才能离开当前吸引域,但又不能过度破坏,以免丢失所有有用的结构。随后,接受规则决定是否用新的局部最优解替换当前保留的解。在变邻域搜索中,系统地切换邻域提供了另一种跳出局部最优的途径:在一个邻域中未能取得改进,就转而探索另一个邻域或更大的邻域。

重启策略提供了一种更简单的替代方案。相互独立的随机重启可以减少对单一初始吸引域的依赖,而带有偏向的重启则可以保留选定的优良组成部分。比较时,关键不只是复杂的跳出机制最终能否找到更好的解,而是在固定计算预算下,它能否改善结果的分布。精心实现的多起点局部搜索将成本低廉的改进过程与广泛的搜索覆盖相结合,因此可以成为一个很难超越的比较基准。

基于种群的方法与构造式方法

基于种群的元启发式算法保留多个候选解或搜索智能体。这样既能在不同区域之间共享信息,也能为重组、集体学习或概率模型构建提供素材。种群并不会自然而然地具有多样性:强选择压力和反复复制可能使其成员变得几乎完全相同。因此,种群规模、替换规则和交互结构都会影响计算成本与搜索行为。

遗传算法通常将选择、交叉和变异结合起来。选择使表现相对较好的候选解对后续世代产生更大的影响。交叉利用两个或更多亲代的组成部分构造子代,而变异则引入额外的变化。重组能否保留有用的结构,取决于编码方式。对排列直接使用普通交叉操作,可能导致某些元素重复、另一些元素缺失,因此排列问题需要专用算子或修复操作。精英保留策略会保留选定的高质量解,但过度保留精英可能降低多样性。更广义的演化算法还包括演化策略、演化规划,以及其他采用不同变异与自适应机制的相关方法。

差分进化主要面向连续向量设计。一种常见变体利用种群中互不相同的成员和缩放因子 FF,构造供体向量

v=xr1+F(xr2−xr3),v=x_{r_1}+F(x_{r_2}-x_{r_3}),

。供体向量的分量与目标向量的分量相结合,形成试验向量;如果试验向量的表现至少不逊于目标向量,通常就会替换目标向量。差分向量提供了搜索方向和步长,其大小反映了当前种群的分散程度。边界约束、坐标缩放、交叉概率以及种群坍缩都会影响该算法的行为。

粒子群优化维护粒子的位置与速度。一种常见的更新方式为

vit+1=ωvit+c1r1(pi−xit)+c2r2(gi−xit),xit+1=xit+vit+1,v_i^{t+1}=\omega v_i^t +c_1r_1\bigl(p_i-x_i^t\bigr) +c_2r_2\bigl(g_i-x_i^t\bigr), \qquad x_i^{t+1}=x_i^t+v_i^{t+1},

其中,pip_i 是粒子记忆中的历史最佳位置,gig_i 表示通过其通信邻域可获得的最佳位置。随机系数可以针对每个坐标分别采样。不同的通信结构会改变优良发现的传播速度。快速共享可以加快搜索进展,但也可能使粒子群过早聚集。

蚁群优化通常采用构造式方法,而不是直接扰动完整解。人工蚂蚁根据信息素值和问题特有的启发式信息选择组成部分,逐步构造解。在路径规划中,信息素浓度较高的短边可能具有较高的被选概率。信息素挥发会减少已有信息素,而选定的解则会强化其组成部分上的信息素。这样既形成了正反馈,又不会使每次决策都变成确定性的。实际实现通常将解的构造与局部搜索相结合;最终解的质量可能在很大程度上归功于局部优化器。

探索、记忆与理论保证

元启发式算法的设计常被描述为在探索与利用之间取得平衡:探索旨在寻找新的区域,利用则着眼于充分运用已经获得的信息。这一区分虽有用,却并非普适的定量理论。在一种表示方式下,大幅变异可能具有探索作用,在另一种表示方式下却可能造成破坏;重组既可能扩大搜索覆盖范围,也可能加速收敛。因此,要开展有意义的分析,就必须明确所提议移动的实际分布、保留的信息以及产生的成本。

记忆有多种形式。禁忌限制显式记录近期出现过的属性。进化种群隐式保留一批先前取得成功的结构样本。蚁群信息素汇总有关解的组成部分的信息。档案可以保存精英解,或体现不同权衡的多样化解。自适应算子选择又增加了一层记忆:算法记录哪些移动近期带来了改进,并调整它们被选中的频率。这种自适应机制可能有益,但短期奖励可能低估某些算子的价值,因为它们创造的机会只有在后续若干步之后才会显现。

将状态扩展为包含下一次转移所需的全部信息后,随机方法有时可以建模为马尔可夫链。这可能要求状态不仅包含当前候选解,还要包含种群、记忆、迄今最优解以及控制参数。随时间变化的温度或自适应机制可能产生非齐次过程。严格的收敛性分析取决于可达性、进入全局最优区域的机会是否持续存在等性质;对于表面相似的算法,不能直接套用彼此的结论。

在固定的正温度下,若提议移动满足适当的对称性条件,理想化的 Metropolis 过程在有限搜索空间上的平衡分布正比于 exp⁡(−f(x)/T)\exp(-f(x)/T)。当温度趋近于零时,该分布会集中于全局最优解。关于模拟退火的研究表明,在特定条件下,足够缓慢的降温可以实现渐近意义上的全局收敛。然而,这类定理所要求的降温进度可能远比实际计算预算所允许的缓慢。因此,渐近保证并不等于对有限时间内性能的预测。

与 David Wolpert 和 William Macready 于 1997 年的研究相关的优化没有免费午餐定理指出,在特定的平均化假设下,各算法的平均性能相同;标准情形中的关键假设是对有限定义域上的所有目标函数取均匀平均。这些定理并不意味着每种算法在工程或调度问题上都表现相同。实际应用所涉及的是具有结构、分布非均匀的问题类别。其实际启示是,优化能否成功,取决于对这些问题类别的假设与信息,无论这些假设与信息是显式编码在算子中,还是隐式体现在算法选择中。

约束、混合方法与问题特有结构

在实际应用中,约束往往比目标函数更能决定问题的难度。一个路径规划方案的总路程可能很短,却违反了车辆容量或配送时间窗约束。一个结构设计可能重量很轻,却不满足应力限值。因此,元启发式算法必须明确:是否允许生成不可行的候选解,如何评价这些候选解,以及它们能否影响后续搜索。忽略这些决策,可能使目标值之间的比较失去意义。

罚函数方法用如下增广量替代受约束的目标函数:

Fρ(x)=f(x)+ρ∑j=1mmax⁡{0,gj(x)},F_\rho(x)=f(x)+\rho\sum_{j=1}^{m}\max\{0,g_j(x)\},

其中,不等式约束为 gj(x)≤0g_j(x)\leq0。对于等式约束,则需要适当的违反程度度量或容差。罚系数过小,可能使不可行候选解更受青睐;罚系数过大,则可能使趋向可行性的移动压倒目标值优劣方面的一切差异。约束的尺度也很重要:将以不同单位度量的违反量直接相加,就会引入任意的权重,除非进行了归一化处理或给出了其他合理依据。

其他方法包括修复、可行解码和直接比较规则。修复是将不可行候选解转换为可行解,例如把超载车辆的部分配送任务转移到其他路线上。解码器可以只构造满足优先次序约束的调度方案。可行性优先规则可以优先选择可行候选解,再根据约束违反程度比较不可行候选解。这些方法没有哪一种在所有情况下都是最好的。要求每个中间状态都可行,可能会切断有用的搜索路径;而不加限制地探索不可行解,则可能将大部分计算预算耗费在无关区域。

混合方法将互补的技术结合起来,而不是完全依赖通用的搜索机制。在种群方法中融入针对个体的局部改进,通常称为模因算法。数学规划可以优化选定的变量,而由元启发式算法选择外围结构。例如,在路径规划或调度问题中,可以固定大部分决策,并用精确求解器求解剩余子问题,以此定义解的邻域。反过来,元启发式算法得到的解也可以为精确方法提供优质的当前最优可行解,帮助其对部分搜索分支进行剪枝。

对于约束严格的调度问题,约束规划与大邻域搜索的结合尤其有效。破坏步骤移除解的一部分,修复过程则在满足约束的前提下重建缺失的决策。自适应版本会根据观测到的表现,调整破坏算子和修复算子的使用。这些方法说明了为什么“元启发式算法”一词的边界具有弹性:高层搜索策略可能将最重要的工作交给高度专门化的算法、约束传播过程或数学模型。

多目标、不确定性与高成本评估

许多应用涉及多个目标,而不是单一且明确的评分。运输方案可能需要在运营成本、排放量和服务可靠性之间权衡;工程设计则可能需要在质量与刚度之间权衡。在多目标优化中,如果存在另一个可行解,在所有目标上都不差于某个解,且至少在一个目标上严格优于它,就称该解被帕累托支配。优化的目标通常是逼近具有帕累托效率的权衡解集,而不是找出一个在所有方面都最优的答案。

基于种群的方法可以在一次运行中保留多种权衡方案。选择过程可以采用非支配排序、多样性度量、将问题分解为标量子问题,或使用评价解集质量的指标。Kalyanmoy Deb 及其合作者于 2002 年提出的 NSGA-II,将精英保留式非支配排序与拥挤距离机制相结合。权衡曲面上的解分布是否多样十分重要,因为集中在某一区域的解集可能遗漏对决策者至关重要的备选方案。随着目标数量增加,许多候选解彼此互不支配,仅靠支配关系往往越来越难以区分解的优劣。

不确定性带来了另一类困难。如果评估结果是随机输出 Y(x,ξ)Y(x,\xi),优化目标可能是

min⁡xE[Y(x,ξ)],\min_x \mathbb{E}[Y(x,\xi)],

也可能涉及分位数、失效概率或最坏情形下的表现。如果每个候选解只进行一次含噪观测,再据此选择,就可能系统性地偏向那些恰好获得异常有利误差的候选解。重复评估、自适应采样,以及使用共同随机输入进行比较,都能提高区分能力,但也会消耗资源。观测值的方差与均值一样,都会影响候选解排序的可靠性。

高成本评估可能需要进行计算流体力学仿真、实验室实验或详细的调度仿真。在这些情况下,资源预算主要受评估次数而非算法迭代次数支配。代理模型利用已经评估过的候选解来近似目标函数或约束。模型可以筛选提出的候选解,也可以引导搜索转向看似有潜力或探索不足的区域。高斯过程是一种可选的代理模型,但其计算要求和建模假设可能不适用于某些数据规模或表示形式。

模型辅助搜索必须始终与实际问题保持联系。如果算法过于激进地优化一个不准确的代理模型,就可能只是利用了预测误差,而没有找到真正优良的解。因此,对提出的候选解另行进行实际评估、控制外推,以及明确考虑仿真噪声,都是方法设计中的重要环节。运行条件的变化又增添了一层复杂性:在动态优化中,保持多样性或检测环境变化,可能比高度收敛于一个仅在当前具有价值的解更有用。

应用与计算实现

路径规划与物流是主要应用领域,因为这类问题的决策是离散的,约束相互影响,实际运营中的问题实例规模也可能很大。车辆路径问题的各种变体可能涉及容量限制、取货与送货的先后顺序、驾驶员工时限制、异构车队以及时间窗。有效的元启发式算法通常利用针对路径设计的变换操作,例如移动某个客户的位置、在不同路径间交换客户,或重新连接路径片段。通用的搜索控制只是其中一个组成部分;可行性检验、插入成本计算和增量更新往往决定了实际运行速度。

调度是另一个广泛的应用领域。在作业车间调度中,各道工序既必须遵循所属作业规定的先后顺序,又要共享机器资源。最大完工时间,即最后一道工序的完成时间,是常见的优化目标,但拖期、准备成本和能耗也可能需要考虑。有效的邻域通常着眼于关键路径上的工序,而不是任意改变工序的位置。大学课程排课和人员排班同样需要明确处理硬约束与软偏好,前者例如避免同一时段的安排冲突,后者例如避免不受欢迎的工作模式。

连续变量和混合变量工程问题推动了进化算法、差分进化算法和群智能方法的应用。设计变量可以包括取实数值的尺寸、取整数值的部件数量,以及表示材料类别的选择。由于仿真逻辑、离散事件或起作用的约束发生变化,这些问题的目标函数可能不光滑。当无法获得导数时,元启发式算法很有吸引力,但问题中的光滑部分仍可能受益于梯度下降等基于梯度的优化方法,或其他局部数值方法。混合算法可以先通过广泛搜索识别有潜力的区域,再用专门的求解器对其进行精细优化。

在机器学习中,应用包括特征选择、模型架构搜索和超参数优化。特征子集可以编码为二进制向量,而模型设置可能构成一个离散与连续变量混合的空间。优化目标通常是对预测性能的估计得分,因此评估过程本身也是问题定义的一部分。反复针对同一个验证集进行优化,可能导致对该验证集的过拟合。交叉验证和独立的最终评估分别处理泛化能力的不同方面,不应将它们与优化器在其所观测评分上的成功混为一谈。

实现方式也会改变算法的实际行为。独立重启、种群评估和岛屿模型都可以利用并行计算。在岛屿模型中,各子种群以一定程度的独立性演化,并定期交换解。同步实现会等待一代或一个批次全部完成;异步实现则会立即纳入已完成的评估结果。当各次评估的耗时不同时,这一区别可能影响选择过程和信息流动。因此,要保证结果可复现,仅给出方法名称和名义种群规模还不够:执行顺序、随机数生成方式、停止规则以及受硬件影响的运行时序,都可能影响结果。

实验评估与方法论局限

评估元启发式算法通常应考察多次运行结果的分布,而不是某一次成功的运行。重要指标包括固定计算预算下获得的最佳可行解目标值、达到指定目标所需的时间、可行解获得率,以及不同运行之间的变异程度。计算预算应与实际应用相匹配。当每次目标函数调用的成本相近时,目标函数求值次数是有用的衡量标准;而当算法在内部记录维护、解的修复或局部搜索方面的开销差异显著时,实际运行时间就不可或缺。仅报告迭代次数,可能掩盖每次迭代计算工作量的巨大差异。

基准测试应能代表目标问题类别,并纳入可信的基线方法。这些方法可以包括随机搜索、多起点局部搜索、成熟的专用启发式算法,以及在相同时间限制下运行的精确求解器。对于最小化问题,所报告的相对差距

100 f(x)−L∣L∣100\,\frac{f(x)-L}{|L|}

在 L≠0L\neq0 时可以解释,但其含义取决于 LL。若采用的是已证明的最优值,所得指标就是最优性差距;若采用的是有效下界,所得指标就是基于下界的差距;若采用的是当前已知最佳可行解的目标值,则只能说明结果与该值的差距。这些证据形式不能相互替代。

参数调优又引入了一层优化。种群规模、变异强度、禁忌期限、降温速率和算子选择概率都可能显著改变算法性能。对一种方法进行大量调优,却让另一种方法使用默认参数,会造成不公平的比较。用于配置算法的训练实例,应与用于支持最终结论的测试实例分开。自动化配置与超启发式方法通过选择算法、算子或参数设置,将这一过程的部分环节形式化,但也必须将它们自身的计算成本和所用训练数据纳入考量。

统计分析应体现实验结构。在同一个实例上重复运行,估计的是以该实例为条件的随机变异性,并不能证明算法在整个应用领域中的性能。跨实例比较应考虑各实例的尺度差异及其配对结构。置信区间、效应量和适当的检验可以补充描述性结果;而在比较多个算法或多项指标时,还会出现多重检验问题。仅有统计显著性,并不能证明改进具有实际应用价值。

消融研究有助于识别哪些组件带来了观察到的性能提升。依次移除局部搜索、记忆、修复或自适应机制,可以区分真正有效的机制与仅起装饰作用的隐喻。公开代码、实例定义、参数设置、随机种子和评估规则,才能让独立审查成为可能。对于提出新型通用优化器的主张,尤其需要谨慎:在小规模基准测试集上有所改进,并不能证明其在互不相关的问题上都具有优势;给已有算子换个名字,本身也不构成新的搜索原理。