蝙蝠算法背包问题求解

《蝙蝠算法背包问题求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第32卷第11期计算机应用研究Vol．32No．112015年11月ApplicationＲesearchofComputersNov．2015*基于改进蝙蝠算法的背包问题求解李佩泽，王姗姗，樊岩(天津工业大学理学院，天津300387)摘要:为了提高蝙蝠算法求解背包问题的性能，受病毒进化机制启发，提出了一种求解背包问题的改进蝙蝠算法。构建背包问题的数学模型，然后采用改进蝙蝠算法进行求解，采用病毒群体感染主群体，主群体在历代个体间纵向传递信息，病毒群体通过感染操作在同代个体间横向传递信息。最后采用三个背包问题对算法性能进行仿真实验

2、，结果表明，相对于对比算法，改进蝙蝠算法的寻优精度和求解稳定性更优。关键词:背包问题;蝙蝠算法;病毒进化;多目标优化中图分类号:TP301．6文献标志码:A文章编号:1001-3695(2015)11-3226-04doi:10．3969/j．issn．1001-3695．2015．11．005SolutionofknapsackproblembasedonimprovedbatalgorithmLiPeize，WangShanshan，FanYan(CollegeofScience，TianjinPolytechnicUniv

3、ersity，Tianjin300387，China)Abstract:Inordertoimprovetheperformanceofbatalgorithmtosolveknapsackproblems，thispaperproposedanimprovedbatalgorithmforsolvingknapsackproblems．Firstly，itestablishedthemathematicmodelofknapsackproblems，andthensolvedthemodelbytheimprovedbatal

4、gorithmwhichthemaingroupsconsistedofbatstransmitinformationcrossedtheverti-calgenerationsandthevirusgroupstransferedevolutionaryinformationcrossedthesamegenerationthroughvirusinfection．Fi-nally，thesimulationexperimentswerecarriedwiththreeknapsackproblems．Theresultssh

5、owthattheproposedalgorithmcanobtainbetteraccuracyandrobustnesscomparedwithotheralgorithms．Keywords:knapsackproblem;batalgorithm;virusevolution;multi-objectiveoptimization体是蝙蝠算法的基本单元，整个群体的运动在问题求解空间中0引言产生从无序到有序的演化过程，从而获取最优解，具有模型简单、收敛速度快、具有潜在并行等优点，已有学者将其应用于连背包问题(knapsac

6、kproblem，KP)作为运筹学中一个典型［9～12］续函数优化问题，并取得了不错的效果。然而，与其他基的组合优化问题，它是一个NP完全难题，最早由Dantzing于［1］于种群迭代搜索的群智能优化算法一样，基本蝙蝠算法同样存20世纪50年代提出并研究。背包问题不但具有重要的理在后期收敛速度慢、局部搜索能力弱和易早熟收敛等缺点，产论意义，而且具有十分重要的实际应用价值，如可以应用于预生早熟收敛等缺陷的根本原因是随着迭代次数的增加而种群算控制、项目选择、货物装载、下料问题、投资决策等，因此背包［10］［2］多样性快速下降。病毒系

7、统是免疫系统的一个主要组成部问题一直是优化领域研究中的一个热点。分，其具有信息处理机制和功能特点，如病毒不同个体的不同背包问题可以分为两类:物体可以分割的背包问题和物体［3］行为、病毒个体和宿主个体的自然划分、病毒与宿主基于感染不可分割的背包问题，后者称为典型的0-1背包问题。在实操作的协同等，这些机制可增加群智能算法的局部搜索能力，际问题当中，决策项目常常要求物体不可分割，因此越来越多［13］增强算法种群的多样性。的国内外研究学者将目光投向0-1背包问题的求解与优化［4］针对基本蝙蝠算法的缺点，提出一种改进的蝙蝠算法VE-上。

8、针对0-1背包问题，国内外学者进行了大量深入的研BA(virusevolutionarybatalgorithm)，通过引入了生物病毒机制究，提出许多背包问题求解算法，求解背包问题的精确算法主和宿主与病毒基于感染操作等思想，利用病毒的水平感染和垂要有枚举法、分支