作者及机构
本文由Xiaofen Lu（南方科技大学计算机科学与工程系）、Ke Tang（南方科技大学计算机科学与工程系、可信自主系统研究院）、Stefan Menzel（本田欧洲研究院）和Xin Yao（南方科技大学及英国伯明翰大学）共同撰写，发表于IEEE Transactions on Evolutionary Computation（2022年6月，第26卷第3期）。研究得到了中国国家自然科学基金、深圳市孔雀计划等多个项目的资助。
动态优化问题（Dynamic Optimization Problems, DOPs）广泛存在于物流、高频交易、实时调度等实际场景中，其目标函数、约束条件或决策变量会随时间变化，要求算法能够快速响应环境变化并输出高质量解。传统基于进化算法（Evolutionary Algorithms, EAs）的动态优化方法（如多样性驱动、记忆方法和预测方法）在应对快速变化环境时表现不佳，因为EA通常需要大量计算资源才能收敛到近似最优解。
针对这一挑战，本研究提出了一种新框架Set-based Dynamic Optimization (SDO)，其核心思想是通过离线进化搜索预先生成一个解集（archive），在线阶段则基于该解集通过局部搜索快速适应新环境。这一方法将动态优化转化为静态的集合导向优化问题（set-oriented optimization），显著提升了算法在快速变化环境中的响应速度。
动态优化问题被定义为最大化目标函数
[ \max_x f(x, \alpha(t)) \quad \forall t ]
其中环境变量(\alpha(t))的取值空间已知但实时值未知。为实现高效优化，研究将问题转化为静态集合优化：
[ \maxX \sum{i=1}^{env_size} \max_{x \in X} f(x, \alpha_i) ]
其中(X)为待优化的解集，(\alpha_i)为通过均匀采样生成的环境变量样本。
采用NCS-C算法（一种基于负相关搜索的进化算法）生成解集：
1. 初始化：随机生成环境样本和解集初始种群。
2. 进化操作：通过高斯变异生成子代，计算个体对解集性能的贡献度（目标函数提升与约束违反降低的加权和）。
3. 选择与更新：保留贡献度高的个体，动态调整变异步长（1/5成功规则）。
4. 输出：最终得到一个覆盖多环境的高质量解集(X)。
在线阶段的核心流程如下：
1. 初始化：将离线解集(X)作为初始种群。
2. 局部搜索：对解集中每个个体施加高斯变异，生成新解并评估其在当前环境下的性能（采用可行性规则处理约束）。
3. 环境变化检测：通过哨兵解（sentinel solutions）的重新评估检测环境变化。
4. 动态更新：若环境变化，保留当前最优解并重新启动局部搜索。
在MPB-2基准测试（36个函数）上，SDO框架的实例化算法SDCO相比现有方法（如SELS、LTFR-DSPSO、DyCODE）表现出显著优势：
- 快速适应性：在环境变化频率为500次函数评估（FEs）时，SDCO仍能快速收敛，而其他方法因计算资源不足失效（图3）。
- 解质量提升：离线生成的解集显著减少了在线阶段找到可行解所需的评估次数（表III-IV）。
在需求动态变化的F-n45-k4实例中，SDCO的改进版本SDCO-DVR优于传统重启策略（restart-EA）和记忆方法（memory-EA），其关键优势在于：
- 并行化潜力：解集中的个体可并行优化，进一步加速实时响应。
- 鲁棒性：即便在需求变化剧烈时，仍能保持较低路径成本（表VIII）。
本研究通过离线进化搜索+在线局部搜索的框架，为解决快速变化环境下的动态优化问题提供了新思路。其科学价值和应用价值包括：
1. 理论贡献：首次将动态优化问题转化为静态集合优化问题，并提出可操作的求解框架。
2. 算法创新：结合NCS-C算法与局部搜索，平衡了多样性与收敛速度。
3. 应用潜力：在物流调度、实时交易系统等需快速响应的场景中具有直接应用价值。
（报告字数：约1600字）