大规模黑盒全局优化中基于种群的元启发式算法研究进展（第一部分）——IEEE Transactions on Evolutionary Computation综述报告

作者与机构
本文由Mohammad Nabi Omidvar（英国利兹大学）、Xiaodong Li（澳大利亚皇家墨尔本理工大学）和Xin Yao（中国南方科技大学/英国伯明翰大学）合作完成，发表于2022年10月的《IEEE Transactions on Evolutionary Computation》（第26卷第5期）。研究得到澳大利亚研究理事会、深圳市科技计划等多项基金支持。

研究背景与目标
随着机器学习、工程优化等领域问题规模指数级增长，传统优化算法面临“维度灾难”（curse of dimensionality）的严峻挑战。本文作为两篇系列综述的第一部分，聚焦大规模黑盒全局优化（large-scale black-box global optimization）领域，重点分析两类核心算法：1) 问题分解（problem decomposition）；2) 模因算法（memetic algorithms）。其目标是为研究者提供领域全景视图，梳理算法发展趋势及最新技术。

核心内容与观点

1. 问题分解：从隐式到显式的方法

隐式方法通过概率模型间接捕捉问题结构，例如：
- 分布估计算法（EDA）：通过高斯分布建模变量相关性，但高维场景下参数估计复杂度呈立方级增长。改进策略包括空间划分（如随机投影降维）和重尾分布采样（如Cauchy分布）。
- CMA-ES算法：通过协方差矩阵自适应实现旋转不变性，但计算成本高达O(n³)。研究通过低秩近似（如LM-CMA）和矩阵简化（如SEP-CMA-ES）将复杂度降至线性。

显式方法则直接识别变量交互结构，核心技术包括：
- 随机分组（random grouping）：简单但交互变量同组概率随维度升高骤降（公式4）。
- 差分分组（DG）：基于有限差分定理（定理1）检测变量交互，精度高但计算复杂度为O(n²)。其改进版DG2通过误差分析实现无参数阈值设定，在CEC2013基准测试中表现优异。
- 递归分组（RDG）：利用同时扰动多变量技术（定理2），将复杂度降至O(n log n)，但无法处理重叠组件问题。

实验支持：DG2在CEC2013基准测试中准确分解18/20函数，而RDG3（CEC2019竞赛冠军）进一步解决了组件重叠问题。

2. 模因算法：全局与局部搜索的协同

模因算法通过结合进化算法的全局搜索与局部搜索的精细调优，平衡探索-开发（exploration-exploitation）矛盾。关键设计维度包括：
- 搜索频率控制：固定间隔（如MA-SW-Chains）、自适应比率（如Zhao等基于成功率的动态调整）。
- 个体选择策略：精英个体优先（如top 25%）、多样性保障（如niching算法clearing）。
- 局部搜索算子：MTS-LS1（坐标下降）、Solis & Wets（随机搜索）和Rosnbrock/Powell（线搜索）最常用。

典型框架：
- MA-SW-Chains：将Solis & Wets局部搜索链式调用，以历史最优点为起点持续优化，获CEC2010竞赛第一名。
- MOS多子代框架：集成多种变异算子（如DE/PSO），根据实时性能动态选择，在CEC2013/2015竞赛中夺冠。

混合协同进化：如MLSHADE-SPA算法先对分解后的子问题并行优化，再通过局部搜索精调，获CEC2018亚军。

3. 方法对比与挑战

• 隐式 vs 显式：显式方法（如DG）在可分离函数中效率更高（O(n log n)），而隐式方法（如CMA-ES）对重叠结构更灵活但需要更大样本量。
  
• 未解决问题：重叠组件处理、阈值敏感性（如ε的选择）、高维约束优化等仍是开放课题。

研究价值与亮点

1. 系统性分类：首次将大规模优化算法按“隐式-显式”和“分解-模因”双维度细分，提出图4的完整分类框架。
   
2. 技术突破：DG2的误差边界理论、RDG的递归分组机制、MA-SW-Chains的链式搜索均为领域标志性进展。
   
3. 应用导向：算法已在超高层建筑优化（千米级）、十亿参数神经网络训练等场景验证实效。
   

数据佐证：据Scopus统计（图1），2011-2021年大规模优化论文年增长率达25%，计算机科学与数学贡献占比超60%，凸显领域热度。

未来方向

第二部分将涵盖代理模型、并行化等主题，并探讨多目标优化、动态优化等新兴领域的挑战。本文为算法设计者提供了结构化的方法论工具，尤其强调变量交互分析对算法效率的核心影响（如协方差矩阵与问题非线性度的关联）。