基于改进的蜂群遗传算法求解多选择背包问题-论文.pdf

《基于改进的蜂群遗传算法求解多选择背包问题-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第6期计算机应用研究V01．31No．62014年6月ApplicationResearchofComputersJun．2014基于改进的蜂群遗传算法求解多选择背包问题吴迪，杨欣字，王崇，李卫平(1．齐齐哈尔大学计算机与控制工程学院，黑龙江齐齐哈尔161006；2．武汉理2r．大学信息工程学院，武汉430070)摘要：多选择背包问题是组合优化中的典型NP难题之一。针对传统蜂群算法存在的收敛速度慢、易陷入局部最优的缺点，提出改进策略。改进的算法通过设置两个自适应变化的种群雄蜂群和雌蜂群，雄蜂群负责与蜂后交叉操作以保持种群的选择压力，雌蜂群负责自适应变异操作以保持种群多样性，

2、蜂后则根据启发式规则主动进化以局部寻优。根据算法实现的核心思想，仿真实验结果表明，提出的改进算法可以有效避免陷入局部最优，同时通过实例也验证了算法的可行性和有效性。关键词：多选择背包问题；蜂群遗传算法；双种群；主动进化中图分类号：TP181文献标志码：A文章编号：1001—3695(2014)06—1632—03doi：10．3969／j．issn．1001—3695．2014．06．006Bee-—swarmgeneticalgorithmformultiple-choiceknapsackproblemWUDi，YANGXin．yu，WANGChong‘LIWei—ping。，

3、(1．SchoolofComputer＆ControlEngineering，QiqihaerUniversity，QiqihaerHeilongfiang161006，China；2．CollegeofInformationEngineering，WuhanUniversityofTechnology，Wuhan430070，China)Abstract：Multiple—choiceknapsackproblem(MCKP)isNPhardasoneofcombinatorialoptimization．Thispaperproposedabee．swarmgeneticalg

4、orithm(BSGA)tosolveMCKP．ThereweretwoadaptivepopulationsinBSGA．malebeeswarmcrossoveredwithqueentokeeppressureofselection，femaleswarnlmutatedtokeeppopulationdiversity。thequeenevolvedundertheinstructionofheuristicrules．ItpresentedthemainideaofBSGAandimplementedbvMATLAB．Throughakindofin—stances．BS

5、GAcomparedwithotheralgorithms。itshowsthefeasibilityandeffectivenessoftheproposedalgorithm．Keywords：multiple—choiceknapsackproblem；bee—swarmgeneticalgorithm；twopopulations；activeevolution背包问题是属于组合优化中的典型NP难问题⋯，对该况下，实现总价值最大的目标。问题的研究具有很强的理论价值和实践意义。根据现实情多选择背包问题的数学描述如下：况的不同，典型的背包问题包括有界和无界背包问题及多维nima

6、x_厂()=c()多选择背包问题等。其中多选择背包问题相比其他几种背约束条件如下：包问题约束条件较多，也更加复杂，因此，对多选择背包问题li的研究相对较少。由于传统确定性寻优算法(如动态规划、≤()，分支定界法等)难以处理大规模背包问题，目前比较常用，l，：1i=1，2，⋯，m(3)的方法是运用各种智能优化算法，如粒子群算法、遗传算，法。]、知识进化算法]、差异演化算法，和人工蜂群遗传∈{0，1}，Vi√式(1)中：c代表第i类第个物品的价值；n是第i类中物品算法及其他算法等来求解该问题。本文在前面工作的数量；代表第i类第个物品是否放人背包，取值1或0。的基础上，采用蜂群遗传算法对

7、多选择背包问题进行求解，式(2)中：为第i类物品中的第个物品的重量，是背包的仿真实验表明蜂群遗传算法在求解多选择背包问题上具有承重。式(3)表示强制每个类中只能有一个物品被选中。较高的可行性。2蜂群遗传算法描述1多选择背包问题数学描述多选择背包问题的一般性描述如下：有一个载重有限的背2．1蜂群个体编码包(承重为)和一批价值、重量均不同的物品，首先要把所有本文选择实数编码表示蜂群个体。每个个体均由m个基的物品分为m类，然后从每类中选择且仅选择一个物品放进因组成，对应m类