多选择背包问题离散狼群算法研究.pdf

《多选择背包问题离散狼群算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2015年第34卷第6期传感器与微系统(TransducerandMicrosystemTechnologies)21DOI：10．13873／J．1000-9787(2015)06-0021-03多选择背包问题离散狼群算法研究董亚科，杜军，李博，丁超(空军工程大学航空航天工程学院，陕西西安710038)摘要：狼群算法是一种通过模拟狼群的捕食行为和猎物分配方式提出的群体智能算法，为求解复杂组合优化问题提供了一种新的思路。目前狼群算法不能解决离散问题，以NP难中的经典问题——多选择背包问题的求解为研究对象，设计了

2、基于离散空间的狼群算法。对于离散空间的狼群算法，通过将人工狼编码，重新设计了狼群的游走、奔袭和围捕过程，并设计了三个过程中的步长。把学习机制引入离散狼群算法，实现了人工狼之间的交流，且确立了自适应步长公式。结果表明：离散狼群算法成功实现了对离散问题的求解，为组合优化问题的求解提供了新方法。关键词：离散狼群算法；组合优化；自适应；学习中图分类号：TP18文献标识码：A文章编号：1000-9787(2015)06-0021-03Researchondiscretewolfpackalgorithmofmutiple

3、chqoi"ceknapsackproblemDONGYa—ke，DUJun，LIBo，DINGChao(SchoolofAeronauticsandAstronauticsEngineering，AirForceEngineeringUniversity，Xi’al710038，China)Abstract：Wolfpackalgorithmisanswarmintelligencealgorithmwhichsimulatespredationbehaviorandpreyallocationmodeofw

4、olfpack，whichprovidesanewmethodtosolvecomplexcombinatorialoptimizationproblems．Wolfpackalgorithmcan’tsolvediscreteproblems，solvingofclassicalNP—hardproblem，multiplechoiceknapsackproblemisresearchgoal，designawolfpackalgorithmbasedondiscretespace．Throughartifi

5、cialwolfcoding，redesignwolves，migration，long—rangeraid，androundupprocess，andstepsizeofthreeprocessisdesigned．Thelearningmechanismisintroducedintodiscretewolfpackalgorithm(DWPA)，whichrealizescommunicationbetweenartificialwolvesandestablishtheadaptivesteplengt

6、hformula．TheresultsshowthatDWPAnotonlyimplementsdiscreteproblemsolving，butalsoprovidenewmethodforsolvingcombinatorialoptimizationproblem．Keywords：discretewolfpackalgorithm(DWPA)；combinatorialoptimization；selfadaptive；learning0引言码规则，把人工狼引入到了离散领域。利用学习机制，使得多选择背

7、包问题是经典的NP难问题，现实中的很多人工狼优秀基因得到继承，实现了人工狼之间的交流，保证问题都是以多选择背包问题为背景而建模的。因此，对该了离散狼群算法的收敛性，通过人工狼的“强者生存”群体类的研究具有重大理论意义和应用价值。目前对NP难问更新策略，保留了最优个体，增加了搜索的多样性，猛狼奔题已经提出如人工鱼群算法、启发式算法、粒子群算法、遗袭采用了自适应步长，加快了算法收敛速度。传算法等诸多方法，但在大规模约束条件下这些算法1多选择背包模型很难获得最优解。狼群算法在多维多峰值连续函数寻优方多选择背包问题有如

8、下定义：有一个载重重量一定的面取得了很好效果，如何将狼群算法扩展到离散领域，背包和一批要放进该背包具有一定价值和重量的物品，这准确地找到最优解，在研究狼群算法和多选择背包问题两些物品首先被分为相互排斥的若干类，每一类中有若干个方面都具有重要意义。不同物品。从每一类物品中取一个物品放入背包中，在背本文提出的一种求解多选择背包问题离散狼群算法包内的物品重量在不超过背包载重前提下，使背包内物