资源描述：
《基于多交换邻域搜索的多维0_1背包问题竞争决策算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第30卷第8期系统工程理论与实践认21.30No.82010年8月SystemsEnginering一Thory&PractieeAug2010文章编号:1000-6788(2010)05-1445一09中图分类号:文献标志码:A基于多交换邻域搜索的多维背包问题竞争决策算法熊小华l,2,宁爱兵-,马良-(1.上海理工大学管理学院,上海200093;2.上海第二工业大学计算机与信息学院,上海201209)摘要提出了一种求解多维0/1背包问题的竞争决策算法,算法采用一种新的资源交换规则)多交换的资源交换规则,使问题具有更大的
2、邻域搜索空间,从而避免问题陷入局部最优解,同时通过对可行解的随机部分扰动进一步扩大问题的搜索空间.经过测试表明:算法具有计算时间短,求解效果好的特点.关键词多维0/1背包问题;竞争决策算法;竞争力函数;决策函数;资源交换规则;多交换ComPetitivedeeisionalgorithmformultidimensionalo/1knaPsackProblembasedonmulti一exehangeneighborhoodsearehxIONGXiao-hual,2,NINGAi-bingl,MALiangl(1.Se
3、hoolofManagement,UniversityofShanghaiforSeienceandTeChnolo瓢Shanghai200093,China:2.CollegeofComputerandInformation,ShanghaiSecondPolytechnieUniversity,Shang喊201209,China)Abstractproposedanewcompetitivedecisionalgorithm(CDA)tosolvemultidimensionalo/1knapsaCkproblem
4、,AnditadoPtsmuiti一exehan罗neighborhoodsearehasresoureeexehangerule.ThenewresoureeexehangerulePreventtheproblemfrombecomingtr即pedinloealoPtimalsolutionandimprovetheefeetandefielencyofthealgorithm.ThealgorithmProPosedhereincorporatesanovelapPro朗hthatconsistsofrandom
5、lyPerturbingtheeurrentsolutioninordertomovesomeitemsfromknaPsack,whichmakesroomfornewitemstobeinsertedthroughmuiti一exehange刀"ovementsandallowsforimprovedsolutions.w七usethisalgnrithmtosolvema叮testinstaneesofMKPandeomputationalresuitsresultingoodperformances.Keywor
6、dsmulti-dimensionalo/1kn即sackproblem;eompetitivedecisfonalgorithm;competitiveforeefunetion:deeisionfunetion;resoureesexchangerule;muiti-exehange1引言背包问题(KnapsackProblem)是一个典型的组合优化难题,属于经典的NP难题,有着广泛的实际应用背景.如可应用于投资决策!资源分配!项目选择!货物装载等,并且还常常作为其他间题的子间题而加以研究=,一2}.该问题有多种形式
7、,其中一般的整数背包间题都可以转化为等价的"/1背包问题.传统的"/1背包间题是把具有一定重量(或体积)和价值的"件物品放在一个重量(或容量)有限的背包中,最后使得背包中物品的总价值最大.记p->0,二->0分别表示物品乞的价值!重量,x-表示物品乞的标志变量(x-=1表示将物品装入到背包中,x-二0表示不装入),V表示背包的重量(或体积)限制,则"八背包间题的数学模型可描述如下:(1)max:一艺几二收稿B期:200,o孚25资助项目:国家自然科学基金(70871081);上海市高校选拔培养优秀青年教师科研专项基金(2
8、1012);上海市重点学科建设项目(s3050,);上海市教育委员会知识创新工程智能信息月赂与支持工程项目作者简介:熊小华(1978-),女,博士研究生,主要研究方向为系统工程!算法设计;宁爱兵(1972一),男,博士,副教授,主要研究方向为系统工程!算法;马良(l964-),男,博士,教授,博士生导师,主要研究方向
