改进膜蜂群算法求解0-1背包问题.pdf

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

1、JournalofComputerApplicationsISSN10o1．90812015．07．10计算机应用，2015，35(7)：2088—2092C0DENJYIIDUhttp：／／www．joca．cn文章编号：1001．9081(2015)07．2088—05doi：10．11772／j．issn．1001—9081．2015．07．2088改进膜蜂群算法求解0-1背包问题宋潇潇。，王军(西华大学电气与电子信息学院，成都610039)(通信作者电子邮箱sxx—pippen@163．com)摘要：针对现有算法在求解大规模0．

2、1背包问题时存在的不足，提出一种改进膜蜂群算法(IABCPS)。IABCPS将膜计算(MC)的思想引入人工蜂群(ABC)算法，基于极坐标编码的方式，采用细胞型单层膜结构(OLMS)，利用各基本膜中改进人工蜂群算子进行迭代，并结合表层膜实现数据交流；算法通过调整内部参数，实现寻优过程中开发和探索的有效配合。实验结果表明IABCPS在求解小规模背包问题时能准确找到最优解。在求解200个物品的背包问题时，IABCPS相对克隆选择免疫遗传算法(CSIGA)平均结果提高了0．15％，方差降低了97．53％；相对于ABC算法平均结果提高了4．15％

3、，方差降低了99．69％，表现出了良好的寻优能力和稳定性。在与ABCPS求解物品数量为300，500，700，1000的大规模背包问题的比较实验中，IABCPS的平均结果比ABCPS分别高1．25％、3．93％、6．75％和11．21％，且方差与实验次数的商始终维持在个位数，表现出了良好的鲁棒性。关键词：人工蜂群算法；膜计算；0．1背包问题；极坐标编码；细胞型P系统中图分类号：TP301．6；TP18文献标志码：AImprovedartificialbeecolonyalgorithmbasedonPsystemfor0-1knapsa

4、ckproblemSONGXiaoxiao。．WANGJun(SchoolofElectricalEngineeringandElectronicInformation，XihuaUniversity，ChengduSichuan610039，China)Abstract：Aimingatthedefectsofresolvinglargescale0-1knapsackproblemwithexistedalgorithm，anImprovedArtificialBeeColonyalgorithmbasedonPSystems(IA

5、BCPS)wasintroducedinthispaper．TheideaofMembraneComputing(MC)，polarcoordinatecodingandOneLevelMembraneStructure(OLMS)wasusedbyIABCPS．EvolutionaryrulesofimprovedArtificialBeeColony(ABC)algorithmandtransformationorcommunicationrulesinPsystemswereadoptedtodesignitsalgorithm．

6、Thelimitofnumberoftrials“limit”wasadjustedtokeepthebalanceofexploitationandexploration．TheexperimentalresultsshowthatIABCPScanfindtheoptimumsolutionsinsolvingsmallscaleknapsackproblems．Insolvingaknapsackproblemwith200items，comparedwithClonalSelectionImmuneGeneticAlgorith

7、m(CSIGA)，IABCPSincreasestheaverageresultsby0．15％anddecreasesvarianceby97．53％；comparedwithABCalgorithm，IABCPSincreasestheaverageresultsby4．15％anddecreasesvarianceby99．69％．TheresultsdemonstratethatIABCPShasgoodabilityofoptimizationandstability．ComparedwithArtificialBeeColo

8、nyalgorithmbasedonPSystems(ABCPS)insolvinglargescaleknapsackproblemwith300，500，700and1000itemsrespectiv