差分进化算法

智能优化算法之三:差分进化算法(或差异演化算法)太原科技大学张学良在科学和工程领域中，经常会遇到连续空间中的数值优化问题，它们的目标函数通常是非线性甚至是不可微的，这时传统的优化方法便很难获得成功。20世纪50年代中期创立了仿生学，自然界的生物体通过自然选择和自然遗传机制就能自组织、自适应地使问题得到完满的解决，这种能力启发人们通过模拟自然演化过程来解决某些复杂问题。演化计算正是在这种指导思想下发展起来的计算机科学领域内的一个崭新分支。近50年的研究表明，模拟自然进化的搜索过程可产生非常鲁棒的计算方法，即使这些模型只是自然界生物体演化过程的粗糙简化。§3.1概述在演化算法家族中，相对发展较早的有进化规划(EvolutionaryProgramming)、遗传算法(GeneticAlgorithm)等，它们都是基于这种思想而发展起来的问题求解方法。这些算法在赋予演化算法自组织、自适应、自学习等特征的同时，不受搜索空间限制性条件(如是否可微、是否连续等)的约束，也不需要其他辅助信息(如梯度)，不仅能获得较高的效率，而且具有易于操作和通用的特点。近些年来，随着人们对生命本质的不断了解，使人工智能的研究开始摆脱经典逻辑计算的束缚，大胆探索新的非经典计算途径。在这种背景下，社会性动物(如蚁群、蜂群、鸟群等)的自组织行为引起了人们的广泛关注，许多学者对这种行为进行数学建模并用计算机对其仿真，这就产生了所谓的“群智能”(SwarmIntelligence，SI)，或称为“群集智能”。群智能中的群体指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体(Agent)，这组主体通过合作进行分布式的问题求解”，而群智能则是指“无智能的主体通过合作表现出智能行为的特性”。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点。目前，群智能演化算法研究的主要算法有：粒子群算法(ParticleSwarmOptimization，PSO)、蚁群算法(AntColonyAlgorithm)、差异演化算法(DifferentialEvolution，DE)等。差异演化(DifferentialEvolution，DE)是一种基于群体差异的演化算法，该算法是RainerStorn和KennethPrice[3]在1996年为求解切比雪夫多项式而提出的。差异演化算法在当年首届IEEE演化计算大赛中表现超群，随后在各个领域得到了广泛的应用。其基本思想在于应用当前种群个体的差异来重组得到中间种群，然后应用子代个体与父代个体竞争来获得新一代种群。差异演化算法最新颖的特征是它的变异操作，当选定一个个体后，算法通过在该个体上加上两个个体带权的差来完成变异。在算法迭代的初期，因为种群中个体的差异较大，从而这样的变异操作会使算法本身具有较强的全局搜索能力，而到迭代的后期，当趋于收敛的时候，种群中个体的差异较小了，这也使得算法具有较强的局部搜索能力。这种新颖的变异操作也使得该算法在求解函数优化等问题上有着其它同类方法不可比拟的优点。主要优点有：待定参数少；不易陷入局部最优；收敛速度快。§3.2差异演化算法的基本原理差异演化算法是基于实数编码的进化算法，最初的群体是随机均匀产生的，每个个体为搜索空间中的一个实向量。令是第g个代的第i个个体，，则()igx)(gXi)()()(gXgXgXUiiLimax21,,2,1;,,2,1)),(,),(),(()(TgNPigxgxgxgXiniii为最大进化代数。为种群规模，为个体的上、下界，、max)()(TNPgXgXUiLi差异演化算法的实施过程如下：(1)生成初始种群在维空间随机产生个NP个体，实施措施如下：))(1,0()0(LijUijLijijxxrandxx数。上服从均匀分布的随机是]1,0[)1,0(rand(2)变异操作变异操作是差异演化的关键步骤，是从种群中随机选择3个个体：ipppXXXppp321,,,321且则)()(321jpjppijxxFxghF为缩放因子。变异操作过程如图所示(3)交叉操作交叉操作可以增加种群的多样性，操作如下：(),(0,1)(1,)(1)(),(0,1)(1,)ijijijgrandCRjrandnggrandCRjrandnhvx或者或者式中，CR为交叉概率，这种交叉策略可以确保中至少有一个分量由贡献。交叉过程如图2.2所示。0,1CR数。上服从均匀分布的随机是]1,0[)1,0(rand(1)ijgv()ijgh图2.2DE交叉操作(4)选择操作由评价函数对向量和向量进行比较。(1)igv()igx(1),((1))(())(1)(),((1)(())iiiiiiigfgfgggfgfgvvxxxvx反复执行2)到4)，直到达到最大进化代数，或达到所要求的收敛精度。§3.3差异演化算法的扩展模式除了上述的演化模式外，RainerStorn和KennethPrice还提出了其他的模式，算法的通式表示为///DExyz式中，DE是指差异演化算法；x代表被加噪声的个体向量；y代表差异向量的个数；z代表交叉模式，分为指数模式(exp：exponential)和二项式模式(bin：binomial)。假设,1,2,(,,,)iiiinXxxx是微粒的当前位置，是微粒i的当前飞行速度，那么，基本粒子群算法的进化方程如下:,,11,,22,(1)()()(()())()(()())ijijijijgijvtvtcrandptxtcrandPtxt,,,(1)()(1)ijijijxtxtvt(1)(2)t表示迭代代数;表示微粒i迄今为止经过的历史最好位置；是当前粒子群搜索到的最好位置，也称为全局最好位置；,()ijpt()gPt为学习因子，通常在0～2间取值。主要是为了调节微粒向自身的最好位置飞行的步长，是为了调节微粒向全局最好位置飞行的步长。具体的参数取值分析在后面会有详细的介绍。，是在上的两个相互独立的随机数。12,cc1c2c1()rand2()rand0,1在上述的基本粒子群算法的进化方程中，第一部分为微粒先前的速度，第二部分为“认知”部分，表示微粒本身的思考，第三部分为“社会”部分，表示微粒间的信息共享。如果进化方程只有“认知”部分，即只考虑粒子自身的飞行经验，那么不同的微粒间就缺少了信息的交流，得到最优解的概率就非常小；如果进化方程中只有“社会”部分，那么微粒就失去了自身的认知能力，虽然收敛速度比较快，但是对于复杂问题，却容易陷入局部最优点。所以,基本微粒群算法的速度进化方程可以看成是由认知和社会两部分组成的。,()ijvt11,,()(()())ijijcrandptxt22,()(()())gijcrandPtxtPSO算法有几个重要的控制参数：微粒群规模、认知学习系数、社会学习系数、控制微粒飞行速度的速度上限、惯性权重系数。1c2cmaxVw间接地影响算法的全局搜索能力。当时，的取值最好选择接近1；当时，是最佳的选择。当时，一般可达到比较理想的效果。认知学习系数和社会学习系数之和最好接近4.0，通常取max2Vmax3V0.8w(0.9,1.2)w1c2c122.05ccmaxVw测试函数1：测试函数1是由K.A.DeJong提出的，被称为Rosenbrock函数，非凸、病态函数，在时达到极小值。测试函数2：测试函数2是著名的Schaffer函数，由Schaffer提出，全局极大点是(0，0)，在距离全局极大点大约3.14的范围内存在无限多的次全局极大点，函数强烈震荡的性态使其难于全局最优化，它的全局最小值为§2.3利用PSO求解优化问题222112112,()100()(1),2.0482.048Ffxxxxxx1ix1(1,1)0F22212222212sin0.5()1,100100[10.001()]iixxFfxxxx2(0,0)0.5F测试函数标准粒子群算法的最优解F1（0.995443，0.991405）4.5576ｅ-5F2（-66.001343，91.955075）0.500044614谢谢大家！