1.2 差分进化算法研究现状

1.2.1 差分进化算法研究数据统计

DE算法最初是由Rainer Storn和Kenneth Price为求解切比雪夫多项式而于1995年共同提出的一种采用浮点矢量编码在连续空间中进行随机搜索的群智能优化算法。该算法的原理简单，受控参数少，实施随机、并行、直接的全局搜索，易于理解和实现，是进化算法产生以来在算法方面取得的巨大进展[1,2]。在1996年日本召开的第一届国际进化优化计算竞赛（International Competitionon Evolutionary Optimization，ICEO）中，DE算法表现突出并取得了进化类算法的第一名，从而引起了广泛关注[9]。由于初期基础理论不成熟，直至2004年之后DE算法才开始得到广泛研究与应用，现已在数字信号处理、神经网络优化、模式识别、机器人路径规划、化工、医学等诸多工程领域取得了良好的应用效果[3-8]。2004年12月，DE 算法的创始人Rainer Storn、Kenneth Price 和 Jouni Lampinen 共同编写并出版了专著Differential Evolution:A Practical Approach to Global Optimization，该书深入阐述了DE算法的基本原理和实际应用领域，成为 DE 算法的经典之作并将 DE 算法的影响进一步扩大，随后相关研究报告和研究成果大量涌现，继而掀起了国内外研究热潮。

图1-1是截至2016年上半年国内外DE算法相关研究文献的统计结果，其中浅灰色柱状数据代表SCI检索的外文文献数量，深灰色柱状数据代表国内中文文献数量。从该结果中可以看出，2004年之前国外的DE算法研究文献数量一直较少，而国内几乎尚未开始研究。2004年后国内外文献数量一直保持逐年上升趋势，到2013年达到峰值。目前DE算法已成功应用于复杂网络挖掘、人工神经网络、化工、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业等诸多领域，成为国内外进化计算、智能优化技术领域的重要分支。

目前，在美国、印度和欧洲都有大学和专门研究机构进行DE算法的相关研究，如美国的伯克利大学、印度的希格瑞嘉工程大学等。国内从事DE算法研究的相关机构及知名学者主要包括：西安电子科技大学的公茂果、焦李成、尚荣华教授，湘潭大学的郑金华教授，中国地质大学的曾三友、蔡之华、龚文引教授等。

在国内，国家自然科学基金对DE算法理论及应用研究的资助力度逐年上升。近3年资助研究课题包括：2013年资助项目“基于多元统计分析的群智能优化算法相关问题研究”（61375066）、“基于混合差分进化的多目标工艺规划和调度研究”（U1304609）、“基于差分进化的流程工业生产过程操作优化”（61374203）、“面向大规模优化问题的基于云计算模型的协同差分进化方法研究”；2014年资助项目“基于云计算的自适应分布式差分进化算法研究”（61402545）、“大规模全局优化问题的高效协同演化算法研究”（U1404622）、“基于多目标差分进化算法的节能分批优化调度研究”（61403163）；2015年资助项目“资源和目标双重约束下的复杂联盟机制研究”（61573125）和“混合智能算法的融合机制设计及在铁路客流大数据中的应用”（61563028）。以上数据反映出现阶段DE算法研究倾向于解决大规模、分布式、多目标优化问题及在实际工程领域中的高效应用。本书中重点介绍了DE算法在高维复杂单目标优化、多目标优化及高维多目标优化等方向上的理论创新，以及DE算法在医学图像处理、电子商务、智能交通等实际工程领域中的应用案例，为DE算法研究者及相关技术人员提供了一定的参考依据。

1.2.2 差分进化算法理论及应用研究概况

经过十多年的发展，国内外学者对DE算法进行了深入系统的研究工作，并取得了令人瞩目的研究成果。涉及的主要研究方向包括DE算法的基础理论研究、DE算法的性能改进研究以及DE算法的应用研究三大部分。下面就各方向上所取得的代表性研究成果进行简要总结。

1.DE算法的基础理论研究

在基础理论研究方面，尽管 DE 算法在实际应用中被证明有效，但和其他众多进化算法一样，其数学基础理论研究还相对薄弱，算法的全局收敛性尚未得到完全证明。现有DE算法的数学基础理论分析研究成果有，Xue F等人在假设DE算法无选择算子的前提下，证明了初始种群服从高斯分布的依概率收敛性，并在此基础上提出了有利于实际应用的关于参数设置的结论[10]。但由于该证明是在假设的前提下进行的，因此理论分析模型与实践执行模型之间有较大的误差，从而降低了其理论说服力。Zaharie对DE算法的收敛性给出了部分证明，在DE算法变异因子F满足正态分布的条件下，证明算法是以概率1收敛的[11]。Zaharie通过研究DE算法的种群多样性变化过程指出，如果变异因子F取值过小，将使种群的多样性迅速变差而早熟收敛，并据此给出了变异因子下限值的计算表达式。通过该表达式，只要已知种群规模和交叉因子就可以计算出变异因子的下限值[11]。Price在文献[12]中分析指出在只包含变异算子的DE算法中，变异因子F与种群规模NP之间的关系，若F减小就需要通过增加种群规模NP来避免算法早熟收敛，但该结论也只是通过实验证明其有效性，没有相关理论证明。国内在 DE 算法的数学基础理论分析研究方面目前仍处于初始阶段。

2.DE算法的性能改进研究

在DE算法的性能改进研究方面，国内外大量研究实验证明DE算法偶尔会出现种群停止向全局最优方向进化的现象，尽管此时算法没有陷入局部最优解或其他点[13]。在某些情况下，即使有新的个体加入种群，算法本身也不再进化继续寻找更优解，这种情况称为停滞（Stagnation）。除此之外，DE算法与其他进化算法一样，其收敛性能会随着搜索空间维数的增加而退化，因此在求解高维复杂优化问题上仍存在早熟收敛现象[13]。为了克服这些缺陷并提高DE算法的收敛速度和稳定性，国内外学者进行了大量的研究工作，主要改进措施集中于以下4个方面：①对DE算法中的 3 个进化算子进行改进；② DE算法与其他最优化方法进行混合；③改善DE算法结构和工作机理；④ DE算法控制参数设置原则改进。以下针对上述4个方面改进措施对典型的代表性算法进行简要综述。

对DE算法进化算子的改进研究主要包括：文献[14]中Hui-Yuan和Jouni Lampinen提出了一种基于三角变异操作的改进DE（Trigonometric Differential Evolution，TDE）算法，使新产生的试验个体被限定在一个三角区域内，三角变异操作在寻优方面比DE算法的变异操作更有效率，TDE算法在神经网络学习中取得了较好的结果。文献[15]中Swagatam Das等人提出一种基于邻域拓扑思想的DE算法变异算子，通过局部邻域模型与全局变异模型的有机组合平衡算法的“开采”与“勘探”能力，避免了现有基于最优解个体的变异策略不利于“勘探”能力提升的缺点。Pavlidis将遗传程序设计GP引入DE算法，利用其自动生成变异算子，新算法在测试函数上表现出优良的性能[16]。

将DE算法与其他最优化方法混合的研究主要包括：文献[17]将DE算法与分布式评估算法（Estimation Distribution Algorithm，EDA）相混合解决连续空间的全局最优问题；Zhang等人在文献[18]中提出了DE算法与PSO算法相结合的混合差分进化算法——DEPSO算法，实验显示混合算法对Rosenbrok和Rastrigrin函数优化结果优于DE算法和PSO算法；Das S将模拟退火算法与DE算法混合，提出了新的个体接受准则和变异策略，结果显示An DE混合算法的性能传统优于DE算法[19]；范瑜等人结合DE算法和遗传算法构建了一种新的混合优化方法，通过融合两种优化方法各自的优点，显著改善多参数、高度非线性问题的优化结果并提高了计算效率[20]。

改善DE算法结构和工作机理的研究主要包括：Anyong Qing提出了动态微分进化算法[21]，其基本思想是使种群中每个个体的更新结果都及时地得到利用，而不是等种群中所有个体都更新完毕后再一起替代旧种群，这样既利用了进化过程中的有用信息，又节省了算法运行所需的存储空间；Bergey提出了改进算法MDE，将种群中所有个体按照适应度值高低进行排序，适应度高的个体以较大的概率被选中作为变异操作的父体[22]；Noman通过将局部搜索技术引入DE，改善了算法对高维函数优化问题的求解性能[23]；Hossein等人通过整合决策空间和目标空间信息，智能化选择变异操作中的差分向量，提高变异操作质量[24]；Rahnamayan等人提出一种基于反向机制的改进（Opposition-Based Differential Evolution，ODE）算法，将基于反向学习（Opposition-Based Learning，OBL）的概念引入DE算法中以加快算法收敛速度，改进后算法尤其适用于求解含噪优化问题[25]。

DE算法相比其他进化算法控制参数较少，只包括种群规模NP、缩放因子F、交叉概率因子CR。在最初的DE算法中，这3个参数在进化过程中是固定不变的，但随后人们意识到固定不变的参数设置方式影响算法达到最优的收敛性能，因此控制参数的设置方式成为 DE 算法的一个研究热点，许多参数自适应调整方法相继被提出[26-35]。DE算法控制参数改进的典型代表算法包括：Liu和Lampinen提出了一种模糊逻辑自适应差分进化（Fuzzy Adaptive Differential Evolution,FADE）算法，利用模糊逻辑控制器，通过输入连续数代种群个体和相应函数值调整变异和交叉因子[26];Brest和Greiner将参数F和CR编码进个体中，并通过两个新引进的概率因子τ1和τ2控制其取值，由此为每个个体设定独立的控制参数，并在进化过程中以一定的规则自动调整[27]；文献[28]中Qin和Suganthan提出一种自适应差分进化（Self-adaptive Differential Evolution,SaDE）算法，算法中子代个体的生成策略以及相应的参数设置均通过学习历代优秀解个体及参数值而自适应生成。

3.DE算法的应用研究

随着DE算法的理论完善及性能提升，DE算法已经越来越多地被应用于求解实际工程领域中的最优化问题[36-50]。Rainer Storn将DE算法应用于非标准数字滤波器优化设计问题[36, 37]。Ilonen J等人将DE算法用于前馈神经网络的训练[38]。Silvio等人将DE算法用于解决广播网络基站的优化设计问题[39]。此外DE算法已经成功应用于信号处理[40]、电磁场反散射设计优化问题[21]、机器智能[41]、模式识别[42]、空气动力学优化[43]、多模态优化控制[44]和地震源定位[45]等工程优化领域。

在国内，越来越多的研究者认识到DE算法的优越性并利用其解决实际工程问题。例如，杨坤德等人利用DE算法进行海洋环境参数反演[46]，史彦君等人将DE算法用于航天器复杂布局优化[47]，范瑜等人将基于DE算法应用在阵列天线方向图综合中[20]，姜爽将DE算法用于工业机器人的运动轨迹规划[48]，孔晓红等人将DE算法用于多处理机任务调度[49]，张越将DE算法用于气动优化设计[50]等。