利用二进制差分演化算法求解动态优化问题.pdf

《利用二进制差分演化算法求解动态优化问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、研究与开发文章编号：1007-1423（2014）13-0003-06DOI：10.3969/j.issn.1007-1423.2014.13.001利用二进制差分演化算法求解动态优化问题宋建民123，贺毅朝，刘建芹（1.石家庄经济学院数理学院，石家庄050031；2.石家庄经济学院信息工程学院，石家庄050031；3.石家庄信息工程职业学院国际教育部，石家庄050035）摘要：利用进化算法求解动态优化问题是智能计算领域中的研究热点。基于HBDE求解动态位匹配问题（DBMP）和时变背包问题（TVKP），在分析DBMP和TVKP的数学模型基础上分别提出利用HBDE求

2、解它们的可行算法。与原对偶遗传算法的仿真计算结果比较表明：基于HBDE求解大规模DBMP和TVKPB问题不但是可行的，而且是高效的。关键词：差分演化算法；动态位匹配问题；时变背包问题；原对偶遗传算法基金项目：河北省高等学校科技研究项目（No.Z2013110）、石家庄经济学院预研项目（No.2012-05）设HBDE的种群规模为N，n为解空间A={0，1}n0引言与辅助搜索空间S=[-5.0,5.0]n的维数。令第t代种群中近年来，诸如移动峰函数（MovingPeaksFunction,第i个个体的混合编码为（Xi（t），Bi（t）），Xi（t）=（xi1（t），

3、[1]MPF）、动态位匹配问题（DynamicBit-MatchingProbxi2（t），…，xin（t））∈S，Bi（t）=（bi1（t），bi2（t），…，bin（t））∈A；[1~2]和时变背包问题（Time-VaryingKnapsacklems，DBMP）第t+1代中间种群中第i个中间个体的混合编码为[1~6]等动态优化问题（DynamicOptimizaProblems，TVKP）（Vi（t+1），Ei（t+1）），其中Vi（t+1）=（vi1（t+1），vi2（t+1），…，tionProblems，DOPs）的有效求解研究逐渐成为了智能vin（t

4、+1））∈B，Ei（t+1）=（ei1（t+1），ei2（t+1），…，ein（t+1））∈计算领域中一个新的研究热点。由于DOPs的动态性与A，1≤i≤N。又设（Xbest（t），Bbest（t）为第t代的最好个体，随机性，使得求解此类问题比静态优化问题更加困难，IT为HBDE的最大迭代次数，于是HBDE的算法伪代由此选择合适的进化算法对于求解是非常关键的。本码描述如下：文基于在求解SAT问题和背包问题（KnapsackProblem,算法1HBDEAlgorithm[7]求解DBMP和TVKP问题。KP）中表现较好的HBDE1GenerateInitializ

5、epopulation{（Xi（0），Bi（0））

6、1≤1HBDE算法简述i≤N}randomly；差分演化（DifferentialEvolution,DE）[7~8]是由Rainer2Compute（Xbest（0），Bbest（0））andlett←0；3While（t≤IT）DoStorn和KennethPrice于1996年为求解切比雪夫多项4Fori=1toNDo式提出的一种进化算法（EvolutionaryAlgorithms,EAs），5Forj=1tonDo在求解数值优化问题中表现突出，受到了广泛的关注。文献[7]利用混合编码方法提出了一种二进制

7、差分演化6If（r≤CR∨j=R（i））thenvij（t+1）=xp1，j+算法HBDE，使DE能够有效用于求解各种以二进制向α（xp2，j（t）-xp3，j（t））elsevij（t）=xij（t）；量为可行解的组合优化问题。下面仅给出HBDE的算7Ifsig（vij（t+1））≥0.5theneij（t+1）=1else法伪代码描述，其详细内容请参考文献[7]。eij（t+1）=0；现代计算机２０14.05上髶研究与开发8Nextj法运算，从而产生新的模板TE（i+1），即TE（i+1）=[TE9Iff（Ei（t+1））

8、1），Bi（t+（i）+RE]（mod2）。对于DBMP问题，当变化周期Ti为固1））=（Vi（t+1），Ei（t+1））；定值时，又称DBMP为固定频率的动态位匹配问题（简10Else（Xi（t+1），Bi（t+1））=（Vi（t），Ei（t））；记fDBMP）。11Nexti基于DBMP的上述模型，我们给出利用HBDE求12Compute（（Xbest（t+1），Bbest（t+1））；解DBMP的算法DEfDBMP的伪代码描述。13t←t+1；设函数GetTime（）用于获取系统的当前时间，Ran14EndWhilePeriod（）用于随机产生DBMP的变化

9、周期Ti（