导读
元启发式算法设计正经历从人工经验驱动向计算智能驱动的深刻转型,其核心在于利用自动化手段替代人类专家在算法构思、构建与验证中的角色。早期研究局限于固定原型内的超参数优化,受限于单一算法族,难以发现跨家族的新颖结构。随着计算资源提升,研究重心转向通用原型与自动化算法设计,旨在通过计算能力探索更广阔的算法设计空间。大语言模型的引入进一步带来了范式革新,从离线静态设计转向在线零样本控制,结合探索性景观分析实现动态超参数演化。各路线在计算成本、泛化能力与可解释性之间做出了不同取舍,由此形成当前多元并存的方法格局。本综述梳理这条从参数配置到结构生成的因果演进链条,为读者提供一张领域认知地图。全文按问题演化与路线取舍组织,覆盖该领域从奠基到当前的主要工作。
1. 研究背景、问题结构与演进脉络
元启发式算法设计领域的兴起源于解决离散、多模态及黑盒优化问题的迫切需求。传统手动调参因高自由度、耗时且易过拟合而受限,且固定原型(如遗传算法或粒子群优化)难以发现跨家族的新颖结构。这一矛盾催生了自动化算法设计(Automated Algorithm Design, AAD)的概念,旨在利用计算资源自动构思、构建和验证元启发式算法,替代人工试错以发现超越人类经验的新颖结构。AAD 的核心在于定义一个由算法原型和表示法构成的设计空间,该空间的丰富度直接决定了算法创新的潜力。算法原型作为调节算法形成的连贯模板,避免了生成不可行算法,而通用原型则旨在覆盖更广泛的元启发式家族以发现多样性。
问题形式化可表述为:给定一个目标问题分布 $D$ 和计算预算 $B$,在算法设计空间 $\mathcal{A}$ 中搜索一个算法 $a^ \in \mathcal{A}$,使得其在 $D$ 上的期望性能 $E[f(a^, D)]$ 最大化,且满足 $Cost(a^*) \le B$。这一形式化揭示了子问题间的强依赖关系:首先需解决“设计空间表示”问题(通用原型),才能进行有效的“结构搜索”(自动化设计);进而需解决“计算成本”问题(在线自适应或大语言模型加速),才能实现“实时部署”;最后需通过“组件级分析”来验证“泛化能力”与“可解释性”。算法选择(Algorithm Selection, AS)与算法配置(Algorithm Configuration, AC)是 AAD 的前置或子集,AS 从现有算法库中选择,AC 调整参数,而 AAD 旨在生成新结构,三者边界清晰但目标一致。
2019 至 2022 年间,领域处于工具化配置阶段。irace 和 ParamILS 确立了参数优化的基线,但受限于固定原型,难以突破单一算法族的限制。这一时期的核心假设是“算法结构固定,参数可调”,研究重心在于在有限设计空间内寻找最优超参数。2023 年,AutoOpt 提出通用原型,通过选择、搜索、更新及归档算子的组合覆盖广泛的算法结构,实现了从参数配置向结构生成的转变。这一转折标志着设计空间从局部参数空间扩展至全局结构空间,计算成本随之增加,但创新潜力显著提升。
2024 年,ALDes 引入自回归生成模型,将算法设计重新定义为序列生成任务,打破了固定结构的限制。这一范式转移使得算法生成不再受限于单一算法范式的约束,推动了该领域从基于搜索的自动设计向基于生成模型的自动设计转变。2025 年,AutoEP 结合探索性景观分析(Exploratory Landscape Analysis, ELA)与大语言模型(LLM),实现了零样本超参数控制,克服了传统强化学习样本复杂度高的问题。METAFOR 则提供了模块化混合元启发式软件框架,支持不同算法组件的灵活组合,揭示了混合策略在复杂连续问题上的优势。
当前,研究处于从“离线静态设计”向“在线自适应与终身学习”过渡的阶段。核心挑战在于如何在无免费午餐定理约束下,通过自动化手段在巨大的算法设计空间中高效搜索出针对特定问题分布具有最优探索-利用平衡且具备泛化能力的算法结构。这一挑战不仅涉及计算效率,还涉及算法设计的可解释性与泛化能力,是领域未来发展的关键方向。
如果用一个核心问题概括该领域,那便是:如何在无免费午餐定理约束下,通过自动化手段在巨大的算法设计空间中高效搜索出针对特定问题分布具有最优探索-利用平衡且具备泛化能力的算法结构。
2. 方法体系
2019:irace——基于估计分布算法(EDA)的自动配置工具,通过迭代采样与概率模型更新来优化算法参数,是早期自动化设计领域的标准基线工具
2020:ParamILS——结合迭代局部搜索与参数优化的框架,通过局部改进与全局扰动在算法设计空间中搜索,为后续基于局部搜索的自动设计提供了基础范式
2023:AutoOpt——提出了一种通用的元启发式算法原型,通过选择、搜索、更新及归档算子的组合覆盖广泛的算法结构,突破了以往固定模板的限制
2024:ALDes——将元启发式算法设计形式化为序列生成任务,利用自回归生成网络生成不同长度和结构的算法,实现了从固定结构到开放结构设计的跨越
2025:AutoEP——结合探索性景观分析(ELA)与大型语言模型(LLM)的零样本超参数控制框架,利用LLM的推理能力动态调整元启发式算法的超参数
2025:METAFOR——一个模块化混合元启发式软件框架,专门用于混合PSO、DE和CMA-ES,并支持局部搜索模块的交错执行
这条时间线勾勒了该领域方法演进的代表性节点:从 2019 年的 irace 奠定该领域方法基线,经 2020 年 ParamILS 的推进,到 2025 年的 METAFOR 代表当前前沿。各节点对应的技术路线、取舍与关联,详见后续小节。
2.1 自动化算法设计
自动化算法设计(AAD)的核心在于利用计算资源自动构思、构建和验证元启发式算法。早期工作如 irace 和 ParamILS 聚焦于固定原型内的超参数优化,受限于单一算法族,难以发现跨家族的新颖结构。AutoOpt(Zhao et al., 2022, P4)针对这一局限,提出了一种通用的元启发式算法原型,通过定义选择、搜索、更新和归档四个核心算子,构建了一个能够实例化多种算法结构的通用模板。其关键技术在于利用条件变量控制搜索路径的切换与终止,从而在统一的框架下表达从局部搜索到进化算法的广泛变体。这种方法允许设计空间覆盖整个元启发式家族,使得自动设计过程能够发现超越人类专家经验的新颖算法结构。其代价是原型设计的复杂性增加,需要更精细的算子接口定义以确保不同算子间的兼容性。AutoOpt 为元启发式算法的自动化设计提供了基础架构,使得算法生成不再受限于单一算法范式的约束,推动了该领域从参数配置向结构生成的转变。
ALDes(Zhao et al., 2024, P9)进一步将元启发式算法设计重新定义为序列生成任务,利用自回归学习模型(如 Transformer)来生成算法组件序列。该方法的核心创新在于打破了传统自动设计中固定算法结构的限制,通过自回归推理生成具有不同长度和结构的算法,从而能够探索更广阔的算法设计空间。模型在神经元中积累的设计知识可以被检索用于未来问题的设计,支持持续学习和开放式的算法演化。与基于固定模板或图表示的方法不同,ALDes 直接生成算法的逻辑序列,使得生成的算法具有更高的结构多样性。其局限性在于序列生成的长度可能影响计算效率,且需要大量的训练数据来学习算法组件间的依赖关系。ALDes 代表了从基于搜索的自动设计向基于生成模型的自动设计的范式转移,为元启发式算法的智能化设计提供了新的技术路径。
AutoOptLib(Zhao et al., 2023, P7)构建了一个用于元启发式优化器自动设计的综合平台,提供了丰富的组件库、灵活的算法表示以及多种设计目标和技术。该平台的核心是支持连续、离散和排列问题的组件库,以及用于演化多样化算法结构的图表示方法。它集成了迭代局部搜索用于操纵算法组件组合,以及 CMA-ES 用于优化超参数,实现了结构与参数的联合优化。AutoOptLib 提供了图形用户界面,降低了自动设计的技术门槛,使非专家用户也能利用计算资源定制优化器。其设计目标是民主化高性能元启发式优化器的获取,减少对人力的依赖。该平台通过提供标准化的接口和工具,促进了自动设计领域的可复现性和比较研究,是该领域基础设施的重要组成部分。
Automated Design Survey(Zhao et al., 2023, P6)系统综述了元启发式算法自动设计领域的现状,区分了自动算法选择、自动算法配置和自动算法设计三个相关但不同的概念。综述详细分析了设计空间(计算原语与算法算子)、算法表示(树、线性数组、图)以及设计策略(模型无关的局部/进化搜索与模型基于学习的方法)。它指出,基于计算原语的设计空间具有更高的创新潜力但计算成本高昂,而基于算法算子的空间则更适合资源受限场景。综述还强调了混合条件设计空间的处理策略,如离散化连续参数或投影到统一原型。该综述为研究者提供了清晰的概念框架和技术选型指南,明确了自动设计在超越人工设计极限方面的潜力与挑战,是该领域的重要参考文献。
| 方法 | 核心机制 | 设计空间表示 | 计算复杂度 | 可解释性 | 适用场景 |
|---|---|---|---|---|---|
| AutoOpt | 通用原型 + 局部/进化搜索 | 算子组合 | 中等 | 高 | 资源受限,需可解释性 |
| ALDes | 自回归生成模型 | 序列生成 | 高 | 低 | 探索未知设计空间,需多样性 |
| AutoOptLib | 组件库 + 图表示 + 联合优化 | 图表示 | 中等 | 高 | 非专家用户,需标准化接口 |
| AutoEP | LLM + ELA 零样本控制 | 超参数空间 | 低 | 中 | 缺乏训练数据的新问题场景 |
2.2 超参数自动配置
超参数自动配置旨在对算法内部参数(如变异率、种群大小)进行静态或动态调整,以平衡探索与利用。AutoEP(Xu et al., 2025, P14)提出了一种基于大型语言模型(LLM)的零样本超参数进化框架,用于动态控制元启发式算法的超参数。该方法结合了探索性景观分析(ELA)的定量特征与 LLM 的定性推理能力,通过构建包含当前状态和历史经验的提示词,引导 LLM 生成新的超参数配置。与传统的深度强化学习方法不同,AutoEP 无需昂贵的实例特定训练,利用 LLM 预训练知识实现零样本适应。其核心模块包括状态感知与上下文构建、基于链式推理(CoR)的决策引擎以及经验池反馈机制。这种方法解决了传统数据驱动方法样本复杂度高和泛化能力差的问题,特别适用于缺乏大量训练数据的新问题场景。AutoEP 展示了 LLM 在算法控制中的潜力,为元启发式算法的自适应配置提供了一种新颖且高效的范式。
Greedy Restart Schedules(Schäpermeier, 2025, P13)提出了一种简单的动态算法选择基线方法,通过迭代选择在当前未解决训练问题分布上表现最佳的算法来构建求解器调度表。该方法针对数值黑盒优化问题,利用 CMA-ES 的不同配置和局部优化器组成算法池。其核心思想是贪心地根据当前剩余问题的特征选择最合适的算法,从而在问题无关的调度中最大化整体性能。与传统的基于实例特征的静态选择不同,该方法考虑了优化过程中的动态变化,通过重启机制适应不同阶段的问题特性。其优势在于实现简单且计算开销低,能够显著缩小单一算法与虚拟最佳求解器之间的性能差距。该方法为更复杂的动态算法选择模型提供了一个强有力的基准,揭示了重启调度在元启发式算法组合中的重要性。
2.3 混合策略与组件分析
混合策略与组件分析探讨多算法混合机制及组件对性能的影响。METAFOR(Camacho-Villalón et al., 2025, P12)开发了一个模块化混合元启发式软件框架,专门用于单目标连续优化问题,支持粒子群优化(PSO)、差分进化(DE)和协方差矩阵自适应进化策略(CMA-ES)的混合。该框架的核心创新在于允许这些全局搜索算法与局部搜索模块交错执行,通过自动配置工具 irace 生成多种混合实现。METAFOR 提供了标准化的接口,使得不同算法组件可以灵活组合,从而探索混合策略的空间。其设计目标是利用不同优化技术的优势,通过混合机制提升在复杂连续问题上的性能。框架支持分层训练集和留一法交叉验证等实例分离策略,以评估混合算法的泛化能力。METAFOR 为混合元启发式算法的研究提供了可复现的实验平台,揭示了特定问题类别下最有效的混合模式。
Component-wise Analysis(Lavinas et al., 2022, P3)提出了一种新的方法论,用于分析自动设计的多目标算法中各组件对性能的具体影响,特别是在约束多目标优化问题中。该方法利用 irace 生成高性能的 MOEA/D 实例,然后通过消融实验对比不同组件(如重启策略和更新策略)对搜索轨迹网络(STN)、种群多样性和超体积的影响。研究发现,重启策略和更新策略是最具影响力的组件,且其相对重要性取决于问题的难度:在 MOEA/D 表现较好的问题上,不使用重启策略影响更大;而在表现较差的问题上,更新策略影响更大。这种组件级分析超越了以往仅关注整体性能提升的研究,深入揭示了算法内部机制与问题特性之间的交互作用。该方法为理解自动设计算法的有效性提供了微观视角,有助于指导新组件的开发和优化。
Hybrid HGSO(Zamli et al., 2021, P1)提出了一种混合亨利气体溶解度优化算法(HGSO),通过动态集群到算法映射机制解决基于搜索的软件工程问题。该方法将种群划分为多个集群,每个集群对应不同的气体类型和亨利常数,并通过动态映射将不同集群分配给不同的元启发式算法或搜索策略。其核心思想是利用不同算法在探索和利用方面的互补性,通过集群间的动态交互提升整体搜索效率。与传统的静态混合不同,该方法根据搜索过程中的状态动态调整算法分配,增强了算法的适应性。这种混合策略旨在克服单一算法在复杂问题上的局限性,通过多算法协同工作提高找到全局最优解的概率。该工作展示了混合元启发式算法在特定应用领域(如软件工程)中的有效性和灵活性。
2.4 算法评估与基准综述
算法评估与基准综述对大量元启发式算法进行系统性评估、分类与综述。Metaheuristic Tutorial(Osaba et al., 2024, P10)提供了一套针对真实世界优化问题的元启发式算法设计、实验与应用的综合指南,强调了从理论到实践部署的完整流程。该教程详细阐述了问题描述、功能与非功能需求分析、算法设计、性能评估及最终部署的关键步骤,特别强调了非功能需求(如可移植性、可靠性)在算法选型中的重要性。它指出,许多文献研究忽略了非功能需求,导致算法难以在实际环境中部署,因此提出了包含实验室环境和应用环境的双阶段工作流。该指南旨在纠正领域内常见的不良方法论习惯,促进可复现和具有实用价值的研究。通过提供具体的建议和最佳实践,该教程为研究人员提供了从理论模型到实际系统部署的路线图,提升了元启发式算法研究的工程化水平。
500+ Metaheuristics Assessment(Ma et al., 2022, P5)对 500 多种基于自然启发的元启发式算法进行了系统性评估和列表,基于引用频率、问题类型多样性、代码可用性和参数调优难度等标准筛选出代表性算法。该研究通过大规模文献计量分析,揭示了元启发式算法领域的研究热点和趋势,指出尽管新算法层出不穷,但许多算法在性能上并未显著超越经典算法。它强调了算法评估的标准化和可复现性的重要性,提供了公开的代码库和基准测试数据,便于研究者进行公平比较。该工作为算法选型提供了科学依据,帮助研究者避免盲目追求新算法而忽视经典算法的有效性。通过全面梳理算法家族,该综述为元启发式算法的分类和评估建立了更清晰的框架。
Pioneering Metaheuristics Survey(Dokeroglu et al., 2024, P11)对 2019 年至 2024 年间提出的元启发式算法进行了深入综述,重点评估了算法的影响力、有效性和创新性。该研究从 158 种新算法中筛选出 23 种具有独特贡献的算法,分析了它们在解决长期优化挑战方面的优势,如克服停滞和早期收敛问题。综述比较了这些算法的强度、局限性、相似性和应用,突出了它们在多样化问题类型中的表现。该工作旨在帮助研究者和实践者区分最具影响力的算法,避免在大量新算法中迷失方向。通过强调代码可用性和参数调优的便利性,该综述促进了算法的实际应用和复现。它为元启发式算法的未来发展方向提供了洞察,指出了需要进一步改进的领域和潜在的研究路径。
2.5 新算法机制设计
新算法机制设计提出具有创新搜索机制或理论基础的元启发式算法。Space Net Optimization (SNO)(Tsai et al., 2023, P8)提出了一种具有解空间视觉的元启发式算法,通过构建空间网络来描绘解空间的地形,以增强搜索性能。该方法初始化一组弹性点形成空间网络,将解空间划分为多个区域,并为每个区域关联期望值以描述其潜力。算法通过区域搜索、点搜索、空间网络调整和种群调整四个算子迭代运行,利用空间网络信息引导全局和局部搜索。其核心创新在于利用已搜索解的信息构建解空间的“地图”,从而更智能地选择搜索方向,类似于在未知区域制作地图以寻找宝藏。这种方法旨在克服传统元启发式算法缺乏全局信息利用的局限,通过空间结构感知提升收敛速度和全局搜索能力。SNO 为元启发式算法引入了空间感知机制,提供了一种新的视角来理解和优化解空间。
Complexity-Theoretic Algorithm Selection(Wang et al., 2021, P2)利用复杂性理论中的黑盒复杂度概念,为随机搜索启发式算法的选择提供理论指导。该研究分析了不同算法(如精英进化算法和非精英 Metropolis 算法)在特定基准问题(如 DLB 问题)上的运行时复杂度,证明了非精英算法在某些问题上可以显著优于精英算法。通过建立算法类与问题复杂度之间的理论联系,该方法为算法选型提供了基于理论的下界和上界分析,而非仅依赖实验结果。其核心贡献在于揭示了算法内部机制(如精英主义与否)对特定问题结构适应性的影响,为设计新算法或选择现有算法提供了理论依据。这种方法将算法设计与复杂性理论紧密结合,提升了元启发式算法研究的理论深度,指导了更高效的算法开发。
3. 关键共识、分歧与开放问题
3.1 领域共识
领域共识认为,手动设计元启发式算法劳动密集、易出错且不可追溯,自动化设计是提升效率与性能的必要途径。这一共识在多个基准上被反复验证:AutoEP 在 TSP 基准上的 0.00% Opt.gap 与 ALDes 在 Power System Restoration 基准上的 3016.52 分钟恢复时间均大幅超越传统方法。元启发式算法的性能取决于探索与利用的平衡,超参数配置是控制这一平衡的核心手段。无免费午餐定理表明不存在通用最优算法,因此需要针对特定问题或问题分布进行算法定制或动态选择。设计空间中的算法表示决定了搜索策略的可行性,通用原型应尽可能覆盖广泛的算法结构。自动化设计应区分离线(针对问题分布)和在线(针对搜索轨迹)两种模式,离线设计适用于可预知计算资源的场景。混合元启发式算法通常优于单一算法,但最佳混合策略依赖于问题类型,需通过自动配置工具进行实证评估。大语言模型提供了零样本算法控制的新范式,其优势在于利用预训练知识进行推理,而非从头学习策略。组件级分析有助于理解自动化设计算法的性能来源,重启和更新策略通常对多目标优化性能影响显著。
3.2 观点分歧
搜索型设计与生成型设计的优劣是领域内的主要分歧。搜索型方法(如 AutoOpt)强调计算可控性与可解释性,通过通用原型和局部/进化搜索在结构化空间内优化,适合资源受限场景。生成型方法(如 ALDes)强调结构多样性与开放式创新,利用 Transformer 生成非模板化算法,适合探索未知设计空间。现有证据偏向搜索型在计算效率和可复现性上占优,生成型在结构新颖性上占优。但缺乏在相同计算预算下的公平对比,且生成型方法的可解释性验证不足。这一分歧的背后,是另一个更根本的争论:LLM 在算法控制中的实际贡献度。AutoEP 认为 LLM 提供零样本推理能力,利用预训练知识动态调整超参数,克服 DRL 样本复杂度高问题,适合缺乏训练数据的新问题。传统 DRL/RL 方法认为数据驱动方法在大规模数据下能学习更精细的策略,LLM 的推理能力可能受限于预训练数据的分布,存在幻觉风险。AutoEP 在 TSP 等组合优化问题上展示了零样本适应的优势,但缺乏与 DRL 在相同数据量下的公平对比。证据强度中等,主要基于小样本实验。场景依赖:LLM 的优势可能在数据稀缺场景下更明显,而在数据丰富场景下 DRL 可能更优。测量工具盲区:缺乏评估 LLM“推理质量”与“算法性能提升”之间因果关系的指标。
3.3 其他开放问题
当前研究面临“计算成本”与“泛化能力”的双重瓶颈。工程问题在于如何降低评估开销和实现分布式计算。研究问题在于如何建立算法结构与问题特征的映射关系,以及开发大规模预训练通用设计器。认知边界包括理论指导缺乏(黑盒复杂度应用不足)、实时部署挑战(非功能性需求忽视)和可解释性缺失(高维设计空间因果归因困难)。已知:自动化设计是必然趋势,探索-利用平衡是关键机制。争议:搜索型与生成型方法的优劣,LLM 在算法控制中的实际贡献度。未知:算法结构与问题特征的映射关系,大规模预训练通用设计器的可行性,MetaBBO 专用基准的构建。发展趋势:从离线静态设计向在线自适应与终身学习过渡,结合 LLM 的推理能力与生成模型的创造力,有望突破无免费午餐定理的限制,实现真正的自动化算法设计。
4. 总结与展望
元启发式算法设计已从“调参”走向“造法”,核心挑战在于如何在计算资源约束下实现高效、泛化且可解释的算法结构生成。这一挑战源于无免费午餐定理导致的通用性缺失与自动化设计带来的计算成本高昂之间的矛盾。早期研究聚焦于固定原型内的超参数优化,受限于单一算法族,难以发现跨家族的新颖结构。随着计算资源提升,研究重心转向通用原型与自动化算法设计,旨在通过计算能力探索更广阔的算法设计空间。大语言模型的引入进一步带来了范式革新,从离线静态设计转向在线零样本控制,结合探索性景观分析实现动态超参数演化。当前研究处于从“离线静态设计”向“在线自适应与终身学习”过渡的阶段,核心问题是如何在计算资源约束下,利用 LLM 等新兴技术实现高效、泛化且可解释的算法结构生成与动态配置。
未来可能突破的方向包括:降低自动化算法设计的计算开销,探索算法结构与问题特征的映射关系,开发大规模预训练通用设计器。这些方向需 ≥2 篇论文共同指向,如 AutoEP 和 ALDes 均强调了计算效率与泛化能力的重要性。对进入者最值得做的一件事是:在统一骨干与统一预训练条件下重评测代表性方法,以 Meta-Dataset 多域协议为主基准,建立针对元黑盒优化(MetaBBO)的专用基准与评估协议。这将有助于准确衡量元学习策略在算法选择、配置和生成任务上的有效性,推动领域向更科学、更实用的方向发展。
以上为节选,完整内容见ArxivReview