Skip to content
返回搜索结果

差分进化 — 全局随机优化器

提出者
Rainer Storn & Kenneth Price
年份
1997
类型
Population-based stochastic metaheuristic

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

差分进化(DE)由Rainer Storn和Kenneth Price于1997年提出,是一种基于种群的随机优化算法,专为连续参数空间设计。它通过组合现有种群成员的向量差来生成候选解,使其成为非凸、多峰或不适合基于梯度方法的搜索地形的强大且参数精简的遗传算法和粒子群优化算法的替代方案。

方法背后的直觉

想象一群探险家散布在一个未知地形上寻找最低的山谷。在每一步,每个探险家观察三个随机选择的同事,沿着其中两个之间的差值方向移动,该差值由步长因子缩放,然后决定新的位置还是旧的位置是更好的地形。经过多轮,整个群体会逐渐聚集到他们集体找到的最深的山谷周围。差分进化正是这样工作的:种群向量之间的“差值”充当搜索方向,比例因子F控制每一步的大小。

历史学

差分进化由Rainer Storn和Kenneth Price在其1997年发表于《Journal of Global Optimization》的开创性论文中提出。该算法源于Price早期在遗传退火方面的研究以及Storn在浮点交叉实验中的经验。最初的版本,现在称为DE/best/1/bin,在标准基准测试中被证明与当时的进化策略和遗传算法相当,甚至常常优于它们。Das、Mullick和Suganthan(2016)的一篇综合综述收录了二十多年来的各种变体、自适应方案和应用,确立了DE作为元启发式算法文献中的基础方法之一的地位。

何时使用

当目标函数是连续的、可能不可微或多峰的,并且所有参数的搜索边界都已知时,差分进化是适用的。它不需要梯度信息,也没有正态性假设,因此适用于工程设计、超参数调优、仿真模型校准以及任何黑盒优化任务。通常以大约参数数量10倍的种群规模作为起点。DE不应应用于纯离散或组合问题;它还需要至少1000次迭代才能可靠收敛——如果函数评估预算非常紧张,贝叶斯优化是更具样本效率的替代方案。

局限与注意事项

  • 如果迭代次数不足,收敛可能很慢;少于1000代通常会产生次优结果。
  • 性能对F和CR的选择敏感——参数设置不当可能导致过早收敛或进展过于缓慢。
  • 不适用于纯离散或组合搜索空间;存在离散扩展版本,但不太标准化。
  • 每次迭代都需要评估NP次目标函数,当每次评估计算成本高昂时,这可能非常昂贵。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 无需梯度信息——可用于任何黑盒目标函数,包括不可微和含噪声的函数。
  • 与搜索能力相比,控制参数(F、CR、NP)非常少,配置相对容易。
  • 自然地处理多峰地形,而基于梯度的优化器可能会收敛到局部最优解。
  • 种群评估是独立的,可以轻松地并行化,从而在多核系统上减少实际运行时间。
  • 在许多基准测试中,其性能与遗传算法和粒子群优化相当,同时更新规则更简单。

应用

  • 校准目标函数为非解析的仿真和基于智能体的模型。
  • 机器学习管道的超参数优化,当搜索空间是连续且有界时。
  • 工程设计问题,如天线设计、结构优化和控制器调优。
  • 在工程和自然科学中训练神经网络和拟合非线性模型。
  • 金融时间序列模型中的投资组合权重优化和参数估计。

使用方式

使用方式

1

在预定义的搜索边界内,为每个参数随机均匀地抽取NP个候选解向量的种群。搜索边界必须由用户在算法开始前指定;DE无法从问题中推断它们。一个良好的初始种群应覆盖整个可行空间,以避免算法一开始就错过有希望的区域。

2

对于种群中的每个目标向量,随机选择三个不同的向量。通过将其中两个向量的差值乘以比例因子加到第三个向量上,形成一个变异向量:v = x_r1 + F*(x_r2 - x_r3),其中F是比例因子(通常为0.4–1.0)。这种基于差值的步骤是DE区别于其他进化算法的关键,并使其在无需梯度计算的情况下具有自适应方向信息。

3

通过逐个元素地混合变异向量和原始目标向量来构建一个试验向量。每个元素以概率CR(交叉率,通常为0.5–1.0)从变异向量中选取,否则从目标向量中选取;至少有一个元素总是从变异向量中选取。此步骤控制了探索与利用之间的平衡:较高的CR有利于变异向量,较低的CR则保留更多当前解的信息。

4

在目标函数上评估试验向量,并与目标向量进行比较。如果试验向量达到了相等或更好的目标值,它将在下一代中替换目标向量;否则,目标向量保持不变。这种贪婪的一对一选择机制可以防止种群退化,并确保找到的最佳解单调改进。

5

变异、交叉和选择过程重复进行足够多的代(通常为1000代或更多),直到满足收敛标准——例如,最佳目标值的变化低于某个容差阈值,或者达到最大迭代次数。最终种群中的最佳向量就是算法的解。

常见陷阱

  • 以过少的迭代次数(低于约1000次)运行差分进化是最常见的错误——算法没有足够的时间收敛,结果应视为初步的;如果评估预算紧张,请切换到贝叶斯优化。
  • 将比例因子F设置得太低会导致多样性过早丧失;设置得太高则会阻碍收敛。从F在[0.4, 1.0]范围内开始,并通过实验进行调整。
  • 省略或错误指定搜索边界是关键错误——DE使用边界来初始化种群,如果边界太窄或缺失,将产生无意义的结果。
  • 在多峰地形上将DE视为一次性运行是有风险的——应从不同的随机种子运行多次独立试验,并报告跨运行找到的最佳解。

常见问题

如何选择比例因子F和交叉率CR?

最广泛引用的默认值是DE/best/1/bin策略的F = 0.8和CR = 0.9。实际上,F控制步长——通常在0.4–1.0之间取值——而CR控制变异向量在多大程度上替换目标向量。如果种群收敛过快,则增加F或降低CR。自适应DE变体(jDE、JADE)会在运行过程中自动调整这些参数,当手动调优不切实际时,这是一个合理的选择。

需要多少代?

经验法则是,建议至少1000代。对于高维问题(参数多)或复杂地形,可能需要更多迭代。观察最佳解在各代中的目标值变化:如果几百代都没有变化,DE可能已经收敛——或者停滞了,在这种情况下,建议使用新的随机种子重新运行。

DE与遗传算法和粒子群优化相比如何?

这三者都是用于连续优化的基于种群的元启发式算法。与GA相比,DE通常需要更少的控制参数,并且与PSO相比,其更新规则更简单、更确定。在许多标准基准测试中,DE与两者相当或优于两者,但性能取决于具体问题。选择通常取决于熟悉程度和可用实现,而不是普遍排名。

DE能处理整数或分类参数吗?

DE是为连续空间设计的。整数参数可以通过在每次更新后将连续解四舍五入到最接近的整数来容纳,但这是一种近似。纯粹的分类或组合问题——如调度或路由——最好使用为离散空间设计的算法,如蚁群优化或禁忌搜索。

相关方法

参考文献

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    打开 DOI 文献
    已复制。
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

    打开 DOI 文献
    已复制。