資源描述：
《基于人類進(jìn)化算法的背包問題求解方法-論文.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、第26卷第3期湖南理工學(xué)院學(xué)報(bào)(自然科學(xué)版)V01．26No．32013年9月JournalofHunanInstituteofScienceandTechnology(NaturalSciences)Sep．2013———基于人類進(jìn)化算法的背包問題求解方法嚴(yán)太山1,2郭觀七1,2，李武，一，李文彬，2(1．湖南理工學(xué)院信息與通信工程學(xué)院，湖南岳陽414006；2．湖南理工學(xué)院復(fù)雜系統(tǒng)優(yōu)化與控制湖南省普通高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，湖南岳陽414006)摘要：背包問題是計(jì)算機(jī)算法中的一個(gè)ⅣP完備類困難問題，使
2、用傳統(tǒng)的優(yōu)化方法在求解較大規(guī)模的背包問題時(shí)，都存在計(jì)算量大、迭代時(shí)間長(zhǎng)的缺陷．人類進(jìn)化算法是模擬人類進(jìn)化機(jī)理而建立的一種智能優(yōu)化算法，本文闡述了人類進(jìn)化算法的基本原理和實(shí)現(xiàn)方法．為提高背包問題的求解速度和精度，將人類進(jìn)化算法應(yīng)用于背包問題的求解，演示了算法的工作過程．試驗(yàn)結(jié)果表明，使用該方法求解背包問題是完全可行的和有效的，與眾多優(yōu)化算法相比，人類進(jìn)化算法具有更高的求解效率．關(guān)鍵詞：人類進(jìn)化算法；生物進(jìn)化；知識(shí)進(jìn)化；背包問題；優(yōu)化求解中圖分類號(hào)：TP183文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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引言背包問題是著名的Ⅳ尸完備類困難問題，這類問題的一般提法是：已知Ⅳ個(gè)物品的體積及其價(jià)值分別為(>0)和vi(>O)(1，2，?，N)，背包的容量假設(shè)為c(>0)，如何選擇哪些物品裝入背包以使在背包的容積限制之內(nèi)所裝物品的總價(jià)值最大?其數(shù)學(xué)描述為：maxf(xI，x2，?，xn)=，i=1—．
8、t≤c，∈{0，1)，i=l，2，一Ⅳ．i=1其中xi為0／1決策變量，一=1時(shí)表示將物品i放人背包中，誓：0則表示不將物品i放人背包中．求解背包問題的算法通常有動(dòng)態(tài)規(guī)劃法、貪心算法等經(jīng)典算法，以及遺傳算法、蟻群算法、免疫算法等生物進(jìn)化算法[]．經(jīng)典算法的時(shí)間復(fù)雜性是指數(shù)階的，計(jì)算量大，對(duì)于大規(guī)模背包問題的求解效率極低，不能保證求得最優(yōu)解．生物進(jìn)化算法是對(duì)簡(jiǎn)單生物進(jìn)化過程的模擬，在求解大規(guī)模背包問題方面，具有速度更快、求解結(jié)果更優(yōu)的優(yōu)點(diǎn)，但同樣也不一定能
