基于人类进化算法的背包问题求解方法-论文.pdf

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

1、第26卷第3期湖南理工学院学报(自然科学版)V01．26No．32013年9月JournalofHunanInstituteofScienceandTechnology(NaturalSciences)Sep．2013———基于人类进化算法的背包问题求解方法严太山1,2郭观七1,2，李武，一，李文彬，2(1．湖南理工学院信息与通信工程学院，湖南岳阳414006；2．湖南理工学院复杂系统优化与控制湖南省普通高等学校重点实验室，湖南岳阳414006)摘要：背包问题是计算机算法中的一个ⅣP完备类困难问题，使

2、用传统的优化方法在求解较大规模的背包问题时，都存在计算量大、迭代时间长的缺陷．人类进化算法是模拟人类进化机理而建立的一种智能优化算法，本文阐述了人类进化算法的基本原理和实现方法．为提高背包问题的求解速度和精度，将人类进化算法应用于背包问题的求解，演示了算法的工作过程．试验结果表明，使用该方法求解背包问题是完全可行的和有效的，与众多优化算法相比，人类进化算法具有更高的求解效率．关键词：人类进化算法；生物进化；知识进化；背包问题；优化求解中图分类号：TP183文献标识码：A文章编号：1672—5298(2

3、013)03．0035．05SolvingKnapsackProblemsbyHumanEvolutionaryAlgorithmYANTai—shanl’，GU0Guan—qi，LIWuz．LIWen．binl，z(1．CollegeofInformationandCommunicationEngineering，HunanInstituteofScienceandTechnology,Yueyang，414006，China2．KeyLaboratoryofOptimizafionandContr

4、olofComplexSystems，HunanInstituteofScienceandTechnology，Yueyang，414006，China)Abstract：KnapsackproblemisregardedasadificultⅣ_尸completenessproblemincomputeralgorithms．Whentheknapsackproblemswithlargescalearesolvedbytraditionaloptimizationmethods．thecomput

5、ationiSlargeandtheiterationtimeislong．HumanEvolutionaryAlgorithm(HEA1isanintelligentoptimizationalgorithmsimulatinghumanevolutionarymechanism．Thebasicprincipleandrealizationmethodofthisalgorithmisdiscussed．Inordertoimprovethespeedandprecisionofthesoluti

6、on．HumanevolutionaryalgorithmisusedtosolveKnapsackproblems．TheworkprocessofalgorithmiSanalyzed．Theexperimenta1resultsproveitsfeasibilityandvalidityinsolvingKnapsackproblems．HumanevolutionaryalgorithmiSmoreeficientcomparedwithmanyotheroptimizationalgorit

7、hms．Keywords：humanevolutionaryalgorithm；creatureevolution；knowledgeevolution；knapsackproblems；optimization引言背包问题是著名的Ⅳ尸完备类困难问题，这类问题的一般提法是：已知Ⅳ个物品的体积及其价值分别为(>0)和vi(>O)(1，2，⋯，N)，背包的容量假设为c(>0)，如何选择哪些物品装入背包以使在背包的容积限制之内所装物品的总价值最大?其数学描述为：maxf(xI，x2，⋯，xn)=，i=1—．

8、t≤c，∈{0，1)，i=l，2，一Ⅳ．i=1其中xi为0／1决策变量，一=1时表示将物品i放人背包中，誓：0则表示不将物品i放人背包中．求解背包问题的算法通常有动态规划法、贪心算法等经典算法，以及遗传算法、蚁群算法、免疫算法等生物进化算法[]．经典算法的时间复杂性是指数阶的，计算量大，对于大规模背包问题的求解效率极低，不能保证求得最优解．生物进化算法是对简单生物进化过程的模拟，在求解大规模背包问题方面，具有速度更快、求解结果更优的优点，但同样也不一定能