大规模优化问题的差分进化策略对比实验研究?

杨茂保

【摘要】差分进化算法（Differential Evolution，DE）有多种进化策略，并在求解各种优化问题时存在较大性能差异，求解大规模优化问题时不同策略间差异尤其明显。利用标准测试函数集对常用5种差分进化策略进行对比实验研究，分析这些策略的求解效果，总结求解大规模优化问题的不同差分进化策略适用性，为大规模优化问题的差分进化求解的策略选择提供帮助。

【关键词】大规模；优化问题；差分进化；进化策略；对比实验

中图分类号：TP391 文献标识码：A

A comparative experimental study on the differential evolution strategy for large scale optimization problems

YANG Maobao

（Jiujiang University， Jiujiang Jiangxi 332005， China）

[Abstract] Differential evolution algorithm（Differential Evolution，DE） has a variety of evolutionary strategies.And there exists a large performance differences between different strategies while solving multiple optimization problems. Especially，in view of large-scale optimization problem， this difference is particularly obvious. By using the standard test functions， 5 kinds of commonly used differential evolution strategy are compared.Based on the above，by analyzing the effect of these strategies， the paper summarizes the applicability of the differential evolution strategy of this research， which could provide the efficient help for the differential evolution strategy selection in sovling large scale optimization problems.

[Key words] large scale； optimization problem； differential evolution； evolutionary strategy；comparative experiment

0 引言

大数据时代，大规模优化问题在科学研究和工程实践中不断涌现，比如网络大数据挖掘、过程系统的大规模优化等，这些优化问题一般具有非线性、多峰、不可微、复杂度高等特性，依赖硬件和传统优化方法往往难以求解。近年来由于进化算法在求解复杂优化问题上的优越性能，使其广泛应用于约束优化问题求解、自适应控制、经济分配等领域[1]。

在进化算法中，差分进化算法吸引了众多关注，自差分算法正式形成定义以来，已对其展开了深入的分析及研究[2]，并提出了各种改进DE算法的差分进化策略，现有的差分进化策略适用于低维中小规模优化问题，在面向高维大规模优化问题时，差分进化计算虽然可以不受规模条件限制，但与低维优化问题相比在求解高维优化问题时出现收敛速度慢、局部优化等问题[5]。近期文献中也相继涌现了在求解大规模优化问题的改进差分策略。毕晓君等[1]设计开发了一种高维多目标多方向协同进化算法（HMMCA），在HMMCA中应用一种混合变异策略加强算法在每个方向上的收敛能力。孔祥勇等[2]在求解大规模问题的改进算法中采用两区间选择策略，提高解决大规模系统可靠性问题时的寻优效果。

本文围绕文献[6]中的5个差分策略和10个优化问题利用标准DE算法对500维的高维化问题进行测试，对每个问题分别设计30次独立实验，记录最好解和平均值以及标准方差，通过对比测试结果来分析评价各种差分策略在面向大规模优化问题时的搜索性能、收敛速度、稳定性和适用情况。

1 标准差分进化算法

差分进化（DE）算法由Storn等人于1995年提出，是一种新兴的进化计算技术。DE算法是一种模拟生物进化规律的智能算法，基本思想是通过种群内个体的交流、通过反复迭代，使得那些适应环境的个体获得了保存，从而逼近问题最优解。标准DE的算法流程如图1所示。

在标准DE算法中，问题的解被抽象成D维空间中的个体，每粒个体均存在一个由优化函数决定的适应度（fitness），首先初始种群，然后经过个体变异、交叉以及选择这3种基本操作，种群逐代进化直至达到终止条件，从而繁衍出具有更高适应度的个体。描述如下：

1）初始种群。DE算法中，问题的解首先被抽象成一个D维空间，并在这个D维空间上随机产生NP个有上下界约束条件的个体 ， 。

2）变异算子。DE算法的变异算子是利用当前种群中2个或多个随机选择的个体之间的差向量产生新的中间个体（记为 ）。DE算法的变异算子衍变有多种形式，Price和Storn等人先后提出了近10种不同策略的差分进化算法[7]，当前最多使用的变异算子是DE/rand/1/bin，如公式（1）所示：

由前述10个函数的收敛曲线图对比分析可得，混合策略ES6在10个问题上的进化基本上趋向于ES1，进而得出如下结论：如果改变混合策略对某一策略的选择概率，则趋向某一策略的程度也相应变化，混合策略在问题上的进化仅仅是受选策略的中和，因而并非有效方法。

5 结束语

针对大规模的高维优化问题难以解决并且优化耗费时间长的不足，实验证明，仅是通过更新差分进化策略对于高维优化问题却仍未得到满意的结果。而利用本次研究实验及相关文献分析可知，若将协同进化思想引入到差分进化领域是当前能够有效避免早熟收敛等现象的全局优化理想算法，同时由此提取得到的关联规则更显显示功用，并在应用于高维优化问题时获得了突出卓越的研究表现。

参考文献

[1]孔祥勇，高立群，欧阳海滨，等.求解大规模可靠性问题的改进差分进化算法[J].东北大学学报（自然科学版）， 2014，35（3）：328-332.

[2]毕晓君，张永建，沈继红.高维多目标多方向协同进化算法[J].控制与决策， 2014，29（10）：1737-1743.

[3]王元卓，靳小龙，程学旗.网络大数据：现状与展望[J].计算机学报， 2013，36（6）：1125-1138.

[4]STORN R， PRICE K. Differential evolution——a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization， 1997， 11（4）：341-359.

[5]邓长寿，赵秉岩，梁昌勇.改进的差异演化算法[J].计算机工程， 2009，35（24）：194-195，198.

[6]刘琛，林盈，胡晓敏.差分演化算法各种更新策略的对比分析[J].计算机科学与探索， 2013，7（11）：983-993.

[7]PRICE K， STORN R， LAMPINEN J. Differential evolution—apractical approach to global optimization[M]. Berlin：Springer， 2005.

[8]YUAN Jungang， SUN Zhiguo， QU Guangji. Study about problems in application of differential evolution[J]. Computer Engineering and Applications， 2007， 43（7）： 75-77.

[9] MEZURA-MONTES E， VELAZQUEZ-REYES J， COELLO C A. A com-parative study of differential evolution variants for global optimization[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation （GECCO 06）. New York， NY， USA： ACM， 2006： 485-492.

[10] WANG Yong，CAI Zixing，ZHANG Qingfu. Enhancing the search ability of differential evolution through orthogonal crossover [J]. Information Sciences， 2006，185： 153-177.

[11]王旭，赵曙光.解决高维优化问题的差分进化算法[J].计算机应用， 2014，34（1）：179-181.

[12]林志毅，王玲玲.求解高维函数优化问题的混合蜂群算法[J].计算机科学， 2013，40（3）：279-282.

[13] STORN R. On the usage of differential evolution for function optimization[C]//Proceedings of the 1996 Conference of the North American Fuzzy Information Processing Society（NAFIPS 1996）. Berkeley， USA：IEEE， 1996： 519-523.