求解随机时变背包问题的精确算法与进化算法

软件学报ISSN1000-9825,CODENRUXUEWE-mail:[e-mail],[doi:10.13328/j.cnki.jos.004937]©中国科学院软件研究所版权所有.Tel:[phone]求解随机时变背包问题的精确算法与进化算法∗贺毅朝1,5+,王熙照2,李文斌3,赵书良4,51(石家庄经济学院信息工程学院,河北石家庄050031)2(深圳大学计算机与软件学院,广东深圳518060)3(石家庄经济学院网络与信息安全实验室,河北石家庄050031)4(河北师范大学数学与信息科学学院,河北石家庄050024)5(河北师范大学软件学院,河北石家庄050024)通讯作者:贺毅朝,E-mail:[e-mail],摘要:随机时变背包问题(RTVKP)是一种新的动态背包问题,也是一种新的动态组合优化问题,目前它的求解算法主要是动态规划的精确算法、近似算法和遗传算法.本文首先利用动态规划提出了一个求解RTVKP问题的新精确算法,对算法时间复杂度的比较结果表明:它比已有的精确算法更适于求解背包载重较大的一类RTVKP实例.然后,分别基于差分演化和粒子群优化与贪心修正策略相结合,提出了求解RTVKP问题的两个进化算法.对5个RTVKP实例的数值计算结果比较表明:精确算法一般不宜求解大规模的RTVKP实例,而基于差分演化、粒子群优化和遗传算法与贪心修正策略相结合的进化算法却不受实例规模与数据大小的影响，对于振荡频率大且具有较大数据的大规模RTVKP实例均能求得的一个极好的近似解.关键词:动态规划;时间复杂度;差分演化;粒子群优化;修复方法中图法分类号:TP18中文引用格式:贺毅朝,王熙照,李文斌,赵书良.求解随机时变背包问题的精确算法与进化算法.软件学报.英文引用格式:HeYC,WangXZ,LiWB,ZhaoSL.ExactAlgorithmsandEvolutionaryAlgorithmsforRandomizedTime-VaryingKnapsackProblem.RuanJianXueBao/JournalofSoftware,2016(inChinese).(CollegeofInformationEngineering,ShijiazhuangUniversityofEconomics，Shijiazhuang050031,China)2(CollegeofComputerScienceandSoftwareEngineering,ShenzhenUniversity,Shenzhen518060,China)3(LaboratoryofNetworkandInformationSecurity,ShijiazhuangUniversityofEconomics,Shijiazhuang050031,China)4(CollegeofMathematicsandInformationScience,HebeiNormalUniversity,Shijiazhuang050024,China)5(SoftwareCollege,HebeiNormalUniversity,Shijiazhuang050024,China)Abstract:Therandomizedtime-varyingknapsackproblem(RTVKP)isbothanewkindofdynamicknapsackproblemandanewkindofdynamiccombinationaloptimizationproblem.Nowtheexactalgorithmbaseondynamicprogramming,approximationalgorithmsbaseongreedy-choicestrategyandevolutionaryalgorithmbaseongeneticalgorithmarethemainalgorithmstosolveit.Inthispaper,wefirstgiveanovelexactalgorithmbaseondynamicprogrammingtosolvetheRTVKP,andcomparethetimecomplexitytotheexistedexact∗基金项目:国家自然科学基金(71371063,61170040)Foundationitem:NationalNaturalScienceFoundationofChina(71371063,61170040)收稿时间:2014-08-04;修改时间:2015-01-21;采用时间:2015-10-30;jos在线出版时间:2015-11-18CNKI网络优先出版:2015-11-1814:58:47,软件学报algorithms.ResultsshowthatthealgorithmweproposedismoresuitabletosolvetheRTVKPwhoseprofitislarger.ThenwecombinetheGreedycorrectionandoptimizationstrategywithdifferentialevolutionandparticleswarmoptimizationrespectivelytosolveRTVKP.Thenumericalresultsofthe5instancesofRTVKPshowthattheevolutionaryalgorithmswhichcombinethedifferentialevolution,particleswarmoptimizationandgeneticalgorithmwithGreedycorrectionandoptimizationstrategyrespectivelyaremoresuitabletosolvethehardRTVKPwhosescaleandoscillationfrequencyarelargerandowningbiggerdata.Keywords:dynamicprogramming;timecomplexity;differentialevolution;particleswarmoptimization;repairapproach背包问题(Knapsackproblem,KP)[1]是计算机科学中的一类重要的NPC问题,也是一类经典的组合优化问题,在投资决策与资源分配等方面具有重要的应用背景[2,3].0-1背包问题(0-1knapsackproblem,0-1KP)[2]是最典型的KP问题,其一般描述为:从n个具有价值与重量的物品中,选择若干个装入一个具有载重限制的背包,如何选择物品使得装入物品的重量之和在不超过背包载重前提下价值之和达到最大.设第i(1≤i≤n)个物品的价值与重量分别为vi与wi，背包载重为C,其中vi,wi与C均为正整数;令Y=(y1,y2,..,yn)∈{0,1}n表示0-1KP的一个可行解,当第i个物品被装入背包时yi=1,否则yi=0,则0-1KP的数学模型为:∑==niiiyvYf1max)(max(1)∑=≤niiiCywts1..(2)动态背包问题(Dynamicknapsackproblem,DKP)[4,5]是0-1KP的一种动态扩展形式.在DKP中,物品的价值、重量或背包载重不再固定不变,而是随着时间的推移可能变大或缩小,因此DKP是一种比0-1KP更不易求解的动态组合优化问题.Goldberg和Smith[4]首先提出了背包载重在两个固定值之间振荡变化的DKP:时变背包问题(Time-varyingknapsackproblems,TVKP),并且他们利用二倍体遗传算法(Geneticalgorithm,GA)求解TVKP问题.随后,Hadad和Eick[6]改进了Goldberg和Smith的方法,提出了求解TVKP的多倍体GA,并指出对于变化频率较大的TVKP多倍体方法更具有优势.YangS[7]利用原对偶遗传算法(Primal-dualgeneticalgorithm,PDGA)求解TVKP问题,计算结果表明其求解效果优于基本GA.Lewis[8]等人比较了几种多倍体方法在求解TVKP时的优劣,指出当背包载重在k(k≥3)个固定值之间振荡变化时多倍体方法的优势并不非常明显.周传华和谢安世[9]提出了一种带动态小生境的自组织学习算法(DNSLA),并将DNSLA用于求解多个规模为100的TVKP实例.贺毅朝[10,11]等人利用动态规划(Dynamicprogramming,DP)求解背包载重在给定区间内随机振荡变化的TVKP问题,提出了求解它的两个精确算法.李宁[12]等人则利用具有混合编码的和声搜索算法求解背包载重在给定区间内随机振荡变化的TVKP问题.最近,YichaoHe[13]等人将TVKP推广为随机时变背包问题(Randomizedtime-varyingknapsackproblems,RTVKP),并分别利用DP、贪心算法和GA给出了求解RTVKP问题的精确算法、近似算法和进化算法,初步讨论了求解动态组合优化问题的近似算法优劣的评价标准.由于0-1KP是RTVKP的特例,因此RTVKP也是一个NPC问题;此外,随着时间的推移,RTVKP中物品的价值、重量以及背包载重均可能变大或减小,故而RTVKP是比TVKP的求解难度更大的DKP.在本文中,首先利用DP提出一个求解RTVKP的新精确算法,然后分别基于差分演化和粒子群优化给出求解RTVKP的两个有效进化算法.本文其余内容组织如下:在第1节中给出RTVKP的定义与数学模型,并简要分析了它的特性;在第2节中,介绍了利用第二动态规划法求解0-1KP的基本算法,利用它们提出了一个求解RTVKP的新精确算法,并比较了它与已有精确算法的时间复杂度;在第3节中,首先给出了基于进化算法求解RTVKP时处理不可行解的有效算法GOA[13],然后分别基于差分演化和粒子群优化与GOA相结合提出了求解RTVKP问题的两个进化算法;在第4节中,通过对5个较大规模RTVKP实例的仿真计算,验证了进化算法求解RTVKP问题的高效性与实用性;最后,总结全文提出今后进一步的研究思路.贺毅朝等:求解随机时变背包问题的精确算法与进化算法31RTVKP问题及其数学模型所谓随机时变背包问题(RTVKP)[13],即给定n个物品和一个背包,每个物品均具有价值与重量两种属性,背包具有载重限制,并且物品的价值和重量以及背包载重均可以随着时间的推移而动态随机振荡变化.如何在每一变化间隔周期内选择物品装入背包,使得在不超过背包当前载重的前提下装入物品的价值之和达到最大.设RTVKP中n个物品的初始价值集与初始重量集分别为V0={v01,v02,…,v0n}和W0={w01,w02,…,w0n},v0jא[Av,Bv],w0jא[Aw,Bw](1≤j≤n),背包初始载重为C0א[Ac,Bc],其中Av,Bv,Aw,Bw,Ac和Bc均为正整数,且AvBv,