SaDE

全局数值优化适应策略差分进化算法（SaDE）张玉龙差分进化算法概述•在科学和工程领域中，经常会遇到连续空间中的数值优化问题，它们的目标函数通常是非线性甚至是不可微的，这时传统的优化方法便很难获得成功。•20世纪50年代中期创立了仿生学，自然界的生物体通过自然选择和自然遗传机制就能自组织、自适应地使问题得到完满的解决，这种能力启发人们通过模拟进化过程来解决某些复杂问题。进化计算正是在这种指导思想下发展起来的计算机科学领域内的一个崭新分支。近50年的研究表明，模拟自然进化过程可产生非常鲁棒的计算方法，即使这些模拟只是自然界生物体进化过程的粗糙简化。差分进化算法（DifferentialEvolution,DE）•DE是一种基于群体差异的进化算法，该算法是RainerStorn和KennethPrice在1996年为求解切比雪夫多项式而提出的。差分进化算法在当年首届IEEE进化计算大赛中表现超群，随后在各个领域得到了广泛的应用。其基本思想在于应用当前种群个体的差异来重组的到中间种群，然后应用子代个体与父代个体竞争来获得新一代种群。•差分进化算法最新颖的特征是它的变异操作，当选定一个个体后，算法通过在该个体上加上两个个体带权的差异来完成变异。在算法迭代初期，因为种群中个体的差异较大，从而这样的变异操作会使算法本身具有较强的全局搜索能力，而到迭代的后期，当趋于收敛的时候，种群中个体的差异较小，这也使得算法具有较强的局部搜索能力。这种新颖的变异操作也使得该算法在求解函数优化等问题上有着其它同类方法不可比拟的优点：待定参数少，不易陷入局部最优，收敛速度快。差分进化算法的基本原理•差分进化算法是基于实数编码的进化算法，最初的群体是随机均匀产生的，每个个体为搜索空间中的一个实向量。令是第g代的第i个个体，，则)(gXi)()()(gXgXgXUiiLimax21...,2,1;,...,2,1)),(),...,(),(()(TgNPigxgxgxgXiniii为最大进化代数为种群规模，为个体的上、下界，、max)()(TNPgXgXUiLi差分进化算法的实施过程如下：（1）生成初始种群在D维空间随机产生NP个个体，生成方法如下：rand（0,1）是[0,1]上服从均匀分布的随机数))(1,0()0(LijUijLijijxxrandxx（2）变异操作变异操作是差分进化算法的关键步骤，是从种群中随机选择3个个体：则F为缩放因子ipppXXXppp321,,,321且)()(321jpjppijxxFxgh变异操作过程如图所示（3）交叉操作交叉操作可以增加种群的多样性，操作如下：式中，CR为交叉概率，CR∈[0,1]这种交叉策略可以确保中至少有一个分量贡献。交叉过程如图所示：),1()1,0(),(),1()1,0(),()1(nrandjCRrandgxnrandjCRrandghgvijijij或或)1(gvij)(ghijDE交叉操作（4）选择操作有评价函数对向量和进行比较。反复执行2）到4），直到达到最大进化代数，或达到所要求的收敛精度。)1(gvi)(gxi))(())1((),())(())1((),1()1(gxfgvfgxgxfgvfgvgxiiiiiii全局数值优化适应策略差分进化算法（SaDE）（1）适应的试验向量生成策略解决不同的问题时，不同的试验向量生成策略效果不同。例如：DE/rand-to-best/1/bin、DE/best/1/bin和DE/best/2/bin对于单峰问题有较快的收敛速度DE/rand/1/bin收敛速度慢，但有很好的探索能力DE/current-to-rand/1对于多目标问题效果明显构成候选策略池：SaDE算法的试验向量生成过程中，每个个体以一定概率在候选策略中选择一种完成变异过程)()(:1//,)1,0[rand),()(:/2//,)1,0[)()()(:/2//,)10[),(:/1//321543214321321GrGriGGriGiGijrandjrjrjrjxrjrijijrandjrjrjrjrijbestjijijijrandjrjrjrijXXFXXKXurandtocurrentDExjjCRxxFxFxubinrandDExjjCRrandxxFxxFxxFxubinbesttorandDExjjCRrandxxFxubinrandDE其它或如果其它或如果其它或，如果每代中，每个变异策略生成的个体，能够通过选择过程成功进入下一代的个数将被记录在成功记忆，失败的个体数目将记录在失败记忆其中，计算每个策略的成功率pkG,该成功率将直接影响下一代选择相应策略的概率。KkGkGkGkSSp1,,,);,...,2,1(,11,,1,,LPGKknfnsnsSGLPGgGLPGggkgkGLPGggkGk成功记忆更新过程当记忆代数达到LP时，每当有新的记忆产生，变删除最早的一代记忆。关于LP设置的讨论参数的设置：缩放因子F，根据正态分布N（0.5,0.3）随机生成。交叉率CR，根据正态分布N（CRk，memory,0.1）随机生成。LP代后每代都会记录每个策略成功个体的交叉率CRk值。其中，CRk,memory在代数小于LP时为0.5，LP代以后根据上一代每个策略的成功个体CRk的平均值作为CRk,memory。SaDE与其它DE算法的性能比较