0引言
高维复杂函数的求解会随着维数的增加，解空间急剧膨胀，问题求解难度大幅增加。对于大规模高维(维数超过100维)优化问题，必须能够在每一维都能获得最优解才可保证全局最优，采用传统的优化算法往往很少能够在短时内在所有决策变量上获得最优解。如果优化问题是多模问题，存在多个局部最优点，问题会更为复杂。高维函数优化问题可用如下数学模型描述：min
1
=
拓守恒，周涛：基于维度分组交叉的自适应差分进化算法
100以下进行测试，对于500、1000维或者更高维时，求解速度难以保证。
Storn和Price[9]提出的差分进化算法(differentialevolution，DE)是一种新兴的进化计算技术，该算法通过群体内个体间的合作与竞争产生的群体智能指导优化搜索[10]。DE算法具有通用性强、算法原理简单容易实现、具有利用个体局部信息和群体全局信息指导算法进行协同搜索的能力，并且易于和其它算法混合等特性[11-12]，文献[13]一种基于多进化模式协作的差分演化算法，在高维优化问题取得了较好效果。
本文提出一种改进的自适应多模式差分变异算法，并针对高维复杂问题，提出了一种基于维度分组交叉的自适应差分进化算法。算法首先利用种群中各维变量间的相关性进行维度划分，从而实现降维，然后通过一个种群在一个维度划分上进行自适应差分进化，最后在种群间按组进行交叉，从而较好实现了多种群的并行差分进化从而有效提高了高维复杂问题的求解速度，通过4个高维多模Benchmark函数实验测试表明，该方法有收敛速度快，求解精度高和稳定性好等优异性能。
维度划分参数设置
2011,Vol.32,No.93175
种群初始化P1
i=1
各维之间相关性计算和分析
i Y 对种群Pi在第i个 维度划分上进行自适应差分变异(具体见算法1) ＝…=Pk=P1 1基础知识 设S=( 1 i++ , 1 , N 1 1 2 , ，＝１，２，…k,那么 , ，那么 2 2 ∪…∪,…, 1 1 2 ,…, (xi,xj)，将相关性 较高的决策变量(相互关联紧密的变量)分在同一组[14-15]。如 1221 2 1+ 1+ 1 121 2+…+1+ 1 2,, 1, 2,, 1,2 1+,2 果决策变量之间没有相关性，各自完全独立，或者变量之间全部紧密相关，也可以在初始参数中设置分组长度 +1+1 1, 1 +1 1+ 1 +1,2+…+ ，2,…,——各维度划分的长度，K—— 维度划分的个数，m——优化问题的维数(决策变量的个数)，——种群中个体i在第j维的取值。定义3， 定义4 第i个属性取值(决策分量)的平均值，。 第i个属性取值(决策分量)的均方差，２， 定义5 。 １ ＝［ 相关系数，属性ai和aj的相关系数， =1,2,…, 31762011,Vol.32,No.9计算机工程与设计ComputerEngineeringandDesign Forj=1:N Y1(t)=Yj(t);%Yj(t)为P(t)中的第j个个体Y2(t)=randselectfromPi'(t);Y(t)=Cross(Y1(t),Y2(t)); %(用Y2(t)中的第i组决策变量值替换Y1(t)第i组决策 变量值，替换后结果赋给Y(t))； IFf(Y(t)) Pj(t+1)=Yj(t+1) %更新P(t)中的第j个个体Pj(t+1)进入下一代。EndFor P1(t+1)=P2(t+1)=…=Pk(t+1)=P(t+1) =0=1 %利用组合优化后的种群P(t+1)更新子种群，准备下一代群内自适应差分进化。 当每个种群在各自维度划分内进行一代差分进化后，可能在各自维度划分的决策变量上取得优化，但此优化结果并不能保证在全局所有维上是较优解，算法2通过在种群间按维度划分进行交叉组合操作，从而促进种群向全局最优方向优化。 高而提高，而对于高维优化问题(维度在100以上)，DE变异算子对函数的评价次数也大幅提高，从而导致算法的收敛速度和性能急剧降低，往往很难在短时内获得高维优化问题的最优解。本文对DE变异算法进行改进，提出一种自适应多模式并行差分变异算法[13]。 算法1：自适应并行差分变异算法Fori=1tosize(Pop) 随机从种群选择个体Xr1,Xr2 r={s1s2,…,sD}==round(rand(1,D)*ex;(其中ex= 2 , max ∈[0.7,2]) = ｛++ .×+ =2=3 式中：m——[0,2]内的随机整数，Xbest(t)——当前种群Pop中最优解，Xrnd(t)——在可行解空间中随机产生的一个新个体。 IFf(Vi(t+1)) 算法1采用多模式随机变异，m=0时，应用传统DE变异；m=1和2时，通过向当前最优个体学习，有助于加快算法的收敛速度，提升搜索精度；m=3时，采用和随机个体做差分，能够保持种群的多样性，避免种群进入局部搜索。当问题的维数很高时，函数评价的用时较长，算法通过产生二进制串ri={s1s2,…,sD}=round(rand(1,D)*ex)和Xr(t)做点乘进行自适应变异操作，变异频率随着进化代数的增加逐步减小。算法1时间复杂度为O(N)，N是种群大小。函数评价次数为N次，显然，算法通过对个体的各维变量同时并行变异，不会随着函数维数的增加而提高算法的时间复杂度和函数评价次数。 2.2.3拥挤裁剪策略 算法如果仅仅采用群内自适应差分进化和群间分组交叉 操作，对于一个高维多峰值的优化问题，很容易陷入一个局部最优点，为了保持种群的多样性，采用拥挤裁剪策略，计算种群P中每个个体的拥挤距离，剔除拥挤距离最小的个体。然后随机产生新个体进行补充，从而保持种群的多样性。 3仿真实验 本文选取了4个benchmark函数作为测试集，仿真实验使 用微机硬件环境为：华硕笔记本电脑IntelCorei32.27GHzCPU,2GB内存，软件采用Matlab2009(a)进行编程实现。在所有测试函数中，算法1参数u=1.2, 2.2.2 群间分组交叉算法(算法2) 在种群P1(t),P2(t),…,Pk(t)经过一代群内自适应差分进化后 变为P1'(t),P2'(t),…,Pk'(t)，但P1'(t),P2'(t),…,Pk'(t)分别仅仅是在第i(i=2,3,…,k)个维度划分上进行了优化，为了能够让种群在所有维上整体优化，让P1'(t)分别在第i(i=2,3,…,k)维度划分上依次和种群P2'(t),…,Pk'(t)进行交叉操作。 例如：P1'(t)和P2'(t)做交叉时，首先，分别从P1'(t)和P2'(t)中随机选择一个个体Y(t)=Y1(t)=(Y2(t)=(Z(t)=( … 1 1 1 0.2 2 exp( 1 … 12 …)， 1 …… …)i=1…N，用Y2(t)中的第二组 2 决策变量替换Y1(t)中的第二组决策分量，交叉后的结果记为 1 = 11 [100(=1 4 (cos())+11)2] …)，如果Z(t)的适应度优于Y1(t) 3 和Y2(t)，则让Y1(t+1)=Z(t)，否则Y1(t+1)=min(f(Y1(t)),f(Y1(t)))。继续在P1'(t)和P2'(t)中选取个体交叉，经过一轮交叉后，种群P1'(t)在第二组决策变量中获得了优化，然后P1'(t)再和P3'(t),…, Pk'(t)进行交叉。具体维度分组组合交叉算法如下： 算法2：维度分组组合交叉算法P(t)=P1'(t)；%P1'(t)=(A1',A2,…,Ak)；Fori=2:k = 4 16+55≤≤5 从表1中可以看出，本文算法能在500次以内进化后获得全局近似最优解。算法在20次独立运行中最优值、平均值和标准差在函数f1和f2上与MEDE算法接近，对函数f3,f4结 果明显优于MEDE算法(而MEDE进化代数是50000代)。从 拓守恒，周涛：基于维度分组交叉的自适应差分进化算法 表1 函数(最小值)f1(0.0)f2(0.0)f3(0.0)f4( 78.29906 78.29905 78.33233 维数 2011,Vol.32,No.93177 本文算法与MEDE算法在函数f1-f4上的测试结果比较 MEDE 本文算法 平均值 标准差 进化代数 种群大小 最小值 平均值 标准差 进化代数种群大小最小值 78.332328 表2 函数(最小值) f3(0.0)f4( 维数D5001000 种群大小 3030 本文算法对500和1000维函数的测试结果 最小值0.0063493240.6128676878.332321267 78.332267平均值1.21287186.4330241878.332288 标准差1.57869615.12341671.1749e-0053.578227e-0068.43069e-006 MFEs11349102359880233220763470314370 M-time126s253s43s247s113s 进化代数15003000 图2和图3可以发现，本文算法对函数f2和f3在200维时的收敛速度明显优于MEDE算法。 500400适应值3002001000 适应多模式差分变异算法和维度分组交叉的差分进化的应用对于DE算法性能改进有较大的作用。 4结束语 本文在传统的差分进化算法基础上提出了一种改进自适 应多模式差分变异算子，通过自适应多模式并行变异策略提高算法的运行速率，利用种群中各维变量间的相关性进行维度划分，从而实现降维，每个种群只在一组决策变量上进行差分进化，种群间按组进行交叉，实现了多种群协同进化。通过 0 100 200300 进化代数 400 500 仿真实例比较可以看出，在提高算法的寻优速度的同时，还有效地克服了早熟收敛等问题。由于在仿真实验时，文中测试全部是在单机上运行，部分函数在1000维时用时较多(超过300s)，如果在实际应用时，本文算法完全可以在多机中协同进化，将会大幅提高运行速度。 本文算法；MEDE 图2函数f2在200维时的进化收敛曲线 500400适应值30020010000 100 200300 进化代数 本文算法 400 500 参考文献: [1] TsengLin-Yu,ChenChun.Multipletrajectorysearchforlargescaleglobaloptimization[C].IEEECongressonEvolutionaryComputation,2009:3052-3059.[2][3][4][5] 关晓颖,胡晓敏,张军.降维式自主迁移伪并行遗传算法[J].计算机工程与设计,2009,30(1):158-163. 朱咸坤,万剑怡.并行遗传算法骨架的研究和实现[J].计算机工程与设计,2009,30(20):4588-4591. 刘胜,李高云,孙天英.一种基于种群多样度的实数编码并行遗传算法[J].智能系统学报,2008(5):423-428. 江中央,蔡自兴,王勇.求解全局优化问题的混合自适应正交遗传算法[J].软件学报,2010,21(6):1296-1307.[6] YUWanxia,ZHANGWeiCun,Zhenghongxing.Geneticandparticleswarmalgorithm—basedoptimizationsolutionforhigh-dimensioncomplexfunctions[J].ComputerEngineeringandAp-plications,2007,43(36):31-33. MEDE; 图3函数f3在200维时的进化收敛曲线 从表2中测试数据可以看出，本文算法在500和1000维时，进化代数没有明显的增加，除了函数f3以外，都能够在500次以内进化后获得全局近似最优解。根据平均运行时间M-time可以看出，在单个计算机中本文算法也能够快速获得最优解，如果多机并行运行速度会更快。综合仿真实验结果，自 [11][10周靖，刘晋胜：采用特征相关性差异优化距离的改进 因篇幅问题不能全部显示，请点此查看更多更全内容