具有自加速与变邻域搜索的差分演化算法

摘要:在分析差分演化（DE）进化方式基础上，首先利用自加速性改进差异算子与选择算子，然后结合变邻域搜索改善算法的局部搜索能力，提出了一种具有自加速特性与变邻域搜索能力的差分演化算法(SAVNDE)；基于DE的三种进化模式，利用5个Benchmark测试函数进行对比计算,实验结果表明：SAVNDE在保持了DE原有特性基础上，以较快的速度获得更好的结果。

关键词:差分演化；进化模式；自加速特性；变邻域搜索；Benchmark函数

中图分类号: TP18;TP301.6文献标志码:A

引言1996年，Storn和Kenneth Price提出了差分演化(Differential Evolution, DE)［1］算法，也称微分进化算法，由于具有较快的收敛性能，已成为智能计算领域的一个研究热点。当前，有关DE的研究主要集中在算法分析、改进与应用方面。其中在算法分析方面，Dasgupta等［2］分析了具有动态群体DE的稳定性；贺毅朝等［3］证明了DE的渐进收敛性。在算法改进与应用方面，DE的研究成果非常丰富，其中Fan等［4］将三角变异嵌入到差分演化，提出了一种具有三角变异的差分演化算法；Rahnamayan［5］基于逆向优化的思想，提出了逆向差分演化算法(Oppositionbased Differential Evolution,ODE)；张利彪等［6］将极大极小距离密度引入差分演化，提出了求解多目标优化问题的微分进化算法；贺毅朝等［7］提出了一种具有混合编码的二进制差分演化算法，将差分演化用于求解组合优化问题；赵光权等［8］基于局部优化观点，提出了一种带增强算子的微分进化算法；Rahnamayan等［9］改进了ODE，提出了一种具有可变跳跃速率(Variable Jumping Rate)的ODE；张晓伟等［10］为避免设定比例因子的麻烦，提出了免比例因子的差分进化算法。虽然以上改进都使算法的性能得到了相应的改善，但却无一例外地引入了新的计算，不仅加大了算法的时间复杂度，而且还增加了空间复杂度。为了挖掘DE自身的隐含特性，提高其收敛速度，本文基于自加速特性和变邻域搜索提出了一种新的DE算法。全文组织如下：在第2节中，介绍了DE算法与变邻域搜索原理；第3节在分析DE进化方式基础上揭示了DE所隐含的自加速特性，并结合变邻域搜索提出了一种具有自加速与变邻域搜索的差分演化算法