关于差分进化算法(Differential Evolution)

关于差分进化算法(Differential Evolution)

觉得有用的话,欢迎一起讨论相互学习~

• 最近因为论文和审稿等综合因素的影响，决定对DE进行多一些研究，发现原先自己的了解太肤浅了_{发现了不少非常经典和实用的参考文献以及论述}

• 包括但不限于以下专家和教授的文章
  [I] 差分演化算法的理论与应用 [M] 熊盛武，胡中波，苏清华
  [II] S. Das and P. N. Suganthan, “Differential Evolution: A Survey of the State-of-the-Art,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 1, pp. 4–31, Feb. 2011, doi: 10.1109/TEVC.2010.2059031.
  [III] A. K. Qin, V. L. Huang, and P. N. Suganthan, “Differential Evolution Algorithm With Strategy Adaptation for Global Numerical Optimization,” IEEE Trans. Evol. Computat., vol. 13, no. 2, pp. 398–417, Apr. 2009, doi: 10.1109/TEVC.2008.927706.

• 差分进化算法最具有特色的是它的自适应变异操作，在演化的初期阶段，因为种群中个体的差异较大，因此用来作为变异扰动的差向量也较大，个体的扰动就较大，有利于算法的全局搜索；随着演化的进行，当算法趋于收敛的时候，种群中个体的差异随之较小，因此用来变异扰动的差向量也随之自适应地变小，较小的扰动有利于局部搜索。正是由于这种简单又独具特色的变异操作有效地平衡了差分演化算法的全局搜索能力和局部搜索能力。值得注意的是，差分进化算法的变异操作对于搜索空间是不封闭的，即变异后得到的捐助向量有可能溢出搜索空间。

• 差分演化算法仅有三个经验控制参数，即种群规模N，变异因子F和交叉概率CR，算法的表现对于参数的设置是敏感的，针对其中两个关键控制参数F和CR，已经研究出了较多简单有效的自适应控制方法。

• 算子的搜素能力可以分为全局搜索和局部搜索能力，全局搜索能力可由种群的多样性反映，种群的多样性又可由种群的方差反映，沿着这一研究思路，Zaharie应用基于统计量的方法从理论上研究了差分演化算法的算子搜索机理。

Mutation with Difference Vectors

• 生物学上，“突变(mutation)”是指染色体基因特征的突变。然而，在进化计算范式的背景下，突变也被视为随机元素的变化或扰动。在DE文献中，来自当前世代的亲本载体称为目标载体 (target vector)，通过差分突变操作获得的突变载体称为供体载体（donor vector），最后通过将供体与目标载体重组形成的后代称为试验载体（trial vector）。在一种最简单的DE突变形式中，为了从当前种群中为每个第i个目标向量创建供体向量，还需要另外三个不同的参数向量，比如${\vec{X}}_{r_1^i},{\vec{X}}_{r_2^i},{\vec{X}}_{r_3^i}$是从当前种群中随机采样的。索引$r_1^i,r_2^i,r_3^i$是从范围[1，NP]中随机选择的互斥整数，它们也不同于基向量索引i。这些索引对于每个突变向量随机生成一次。现在，这三个向量中任意两个向量的差按标量F（通常位于区间[0.4，1]）缩放，并将缩放后的差加到第三个向量上，我们从那里获得供体向量${\vec{V}}_{i,G}$。我们可以将过程表示为
  $${\vec{V}}_{i,G}={\vec{X}}_{r_1^i,G}+F\cdot \left({\vec{X}}_{r_2^i,G}-{\vec{X}}_{r_3^i,G}\right)（3）$$

• 决策空间示意图
  

DE Family of Storn and Price

• DE中的突变是最重要的组成部分，上一节的公式使用随机选择的向量${\vec{X}}_{r_1^i}$和带权值的差向量F*(${\vec{X}}_{r_2^i}-{\vec{X}}_{r_3^i}$)来扰动基向量。因此，在文献中，上节中使用的特定突变方案成为DE/rand/1,当其与二项式交叉结合使用时，其过程成为DE/rand/1/bin.我们现在可以知道不同的DE方案是如何命名的。上面使用的一般约定是DE/x/y/z，其中DE代表“微分进化”，x代表表示要被扰动的基向量的字符串，y是考虑扰动x的差向量的数量，z代表所使用的交叉类型（exp:指数；bin:二项式） Storn和Price[74]、[75]提出的其他四种不同突变方案总结如下
  
• 索引ri1、ri2、ri3、ri4和ri5是从范围[1，NP]中随机选择的整数，并且都不同于基本索引i。这些索引对于每个供体向量随机生成一次。缩放因子F是用于缩放差向量的正参数。${\vec{X}}_{best,G}$ 是种群中G代具有最佳适应度值（如果是最小化问题就是具有最低目标函数值）的最佳个体。注意，创建供体向量的一些策略可能是突变的重组个体。例如，（8）中供体向量即是一个两向量重组个体 ${\vec{X}}_{i,G}+F\cdot \left({\vec{X}}_{\text{best },G}-{\vec{X}}_{i,G}\right)$

[74] K. Price, R. Storn, and J. Lampinen, Differential Evolution—A Practi-cal Approach to Global Optimization. Berlin, Germany: Springer, 2005.
[75] K. V . Price, “An introduction to differential evolution,” in New Ideas in Optimization, D. Corne, M. Dorigo, and V . Glover, Eds. London,U.K.: McGraw-Hill, 1999, pp. 79–108.
[92] R. Storn and K. Price, “Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces,” J. Global Optimization, vol. 11, no. 4, pp. 341–359, 1997.

• Storn和Price[74]，[92]建议了总共十种不同的DE工作策略，以及将这些策略应用于任何给定问题的一些指南。这些策略源自上述五种不同的DE突变方案。每种突变策略都与“指数”型交叉或“二项式”型交叉相结合。这产生了总共5×2=10个DE策略。事实上，许多其他线性向量组合可以用于突变。一般来说，在（3）、（7）–（10）中所述的方法中，没有一种单一突变方法是最适合所有问题的。然而，各种突变方案需要进一步研究，以确定它们在何种情况下表现良好，以及在何种问题上产生较差的结果。MezuraMontes等人在这方面开展了一些初步工作，他在[56]中对13个基准问题的测试套件中的8个不同DE方案进行了经验比较。作者考虑了一种有趣的突变方案，称为DE/rand/2/dir[26]，该方案结合了目标函数信息，以如下方式指导供体的方向：

$${\vec{V}}_{i,G}={\vec{X}}_{r_1,G}+\frac{F}{2}\cdot \left({\vec{X}}_{r_1,G}-{\vec{X}}_{r_2,G}-{\vec{X}}_{r_3,G}\right)$$

[26] V . Feoktistov and S. Janaqi, “Generalization of the strategies in differential evolution,” in Proc. 18th IPDPS, Apr. 2004, p. 165a.
[56] E. Mezura-Montes, J. V elázquez-Reyes, and C. A. Coello Coello,“A comparative study of differential evolution variants for globaloptimization,” in Proc. Genet. Evol. Comput. Conf., 2006, pp. 485–492

• 其中${\vec{X}}_{r_1,G},{\vec{X}}_{r_2,G},{\vec{X}}_{r_3,G}$是独立的个体，并且满足${\vec{X}}_{r_1,G}\le {\vec{X}}_{r_2,G},{\vec{X}}_{r_3,G}$ Mezura Montes等人进行的实验表明，基于结果的最终准确性和鲁棒性，DE/best/1/bin（始终使用最佳解决方案来寻找搜索方向，也使用二项式交叉）仍然是最具竞争力的方案，无论要解决的问题的特征如何。[56]中的作者还提到，对于单峰和可分离函数，DE/rand/2/dir取得了相当好的结果。对于单峰和不可分离函数，DE/best/1/bin始终获得最佳性能。该变型也成功地优化了多模态和可分离基准。DE/rand/1/bin和DE/rand/2/dir在这类函数上提供了类似质量的性能。然而，在多模态和不可分离函数上，DE/rand/2/dir仍然最具竞争力，收敛到全局最优的速度稍快。

• 变异基矢量是best，即是对种群当前最优个体进行变异搜索，该变异方式具有良好局部搜索能力，而不是全局搜索能力,并且能够快速收敛；对于变异基矢量是rand的方式，其变异基底是一个随机选择的个体，该变异方式具有良好的全局搜索能力。

Trial Vector Generation Strategy

• 依赖于迄今为止发现的最佳解决方案的策略，如“DE/rand to best/1/bin”、“DE/best/1/bin，”和“DE/best/2/bin”，通常具有较快的收敛速度，在解决单峰问题时表现良好。然而，在求解多模态问题时，它们更容易陷入局部最优，从而导致过早收敛。
• “DE/rand/1/bin”策略通常表现出缓慢的收敛速度和更强的探索（exploration）能力。因此，它通常比依赖于迄今为止发现的最佳解决方案的策略更适合于解决多模态问题。
• “DE/best/1/bin”策略是“DE/rand to best/1/bin”策略的退化情况，等于1。
• 两种基于差分向量的策略可能比一种基于差分向量的策略产生更好的扰动。Storn[11]声称，根据中心极限定理，当前种群中所有目标向量对的差向量之和的随机变化略微向高斯方向偏移。在粒子群优化（PSO）环境中[35]也讨论了使用两个基于差向量的策略的优势，而所有两个差向量的总和的统计分布具有钟形，通常被认为是更好的扰动模式。
• DE/current到rand/1是一种旋转不变策略。当应用于解决多目标优化问题时，其有效性已得到验证[34]。

[11] R. Storn, “On the usage of differential evolution for function optimiza-tion,” in Proc. Biennial Conf. North Amer. Fuzzy Inf. Process. Soc.,Berkeley, CA, 1996, pp. 519–523.
[34] A. Iorio and X. Li, “Solving rotated multi-objective optimization problems using differential evolution,” in Proc. Australian Conf. Artif. Intell., Cairns, Dec. 2004, pp. 861–872
[35] W. J. Zhang and X. F. Xie, “DEPSO: Hybrid particle swarm with differ-ential evolution operator,” in Proc. IEEE Int. Conf. Syst. Man Cybern.,Washington, DC, 2003, pp. 3816–3821