求解多背包問題的混合蛙跳算法

1、【word】求解多背包問題的混合蛙跳算法求解多背包問題的混合蛙跳算法總第263期2011年第9期計(jì)算機(jī)與數(shù)字工程Computer&DigitalEngineeringVo1.39No.913求解多背包問題的混合蛙跳算法馬竹根”舒少華.（懷化學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系”懷化418008）（中方縣職業(yè)中等專業(yè)學(xué)校懷化418000）摘要針對多背包問題,提出一種改進(jìn)的離散混合蛙跳算法.算法中對青蛙個(gè)體采用十進(jìn)制整數(shù)編碼方式,應(yīng)用遺傳算法中的交叉操作來對個(gè)體進(jìn)行更新,擴(kuò)展了傳統(tǒng)混合蛙跳算法模型.將改進(jìn)的算法用于多背包問題求解,仿真實(shí)驗(yàn)表明了所提算法的有效性.關(guān)鍵詞混合蛙跳算法;多背包問題;組

2、合優(yōu)化;交叉算子中圖分類號TP301.6ShuffledFrogLeapingAlgorithmforSolvingMultipleKnapsackProblemMaZhugenShuShaohua.,Huaihu(DepartmentofComputerScienceandTechnology,HuaihuaUniversitya418008)(SpecializedSchoolofZhongfangCountryVocationalSencondarf,Huaihua418008)AbstractADiscreteShuffledFrogLeapingAlgorithmisproposed

3、tosolvetheMultipleKnapsackProblem.ThealgorithmadoptsintegercodedschemeandanewmethodofindividualproductionbycrossoveroperationtOextendthetraditionalmodelofShuffledFrogLeapingAlgorithm.Theexperimentalresultsshowthattheproposedalgorithmiseffectiveandeffient.KeyWordsshuffledfrogleapingalgorithm(SFLA),mu

4、ltipleknapsackproblem(MKP),combinatorialoptimization,crossoveroperationClassNumberTP301.61 引言多背包問題(MultipleKnapsackProblem,MKP是一個(gè)經(jīng)典的組合優(yōu)化問題，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用,如資源分配,投資決策,貨物裝載等均可建模為多背包問題.因此,多背包問題的求解一直以來是人們關(guān)注的一個(gè)研究熱點(diǎn),目前已經(jīng)提出了如精確算法1,動(dòng)態(tài)規(guī)劃法2,啟發(fā)式算法引,遺傳算法,蟻群算法引,人工魚群算法.等多種求解方法.由于精確求解的時(shí)間復(fù)雜度大,所以精確算法僅能適用于小規(guī)模的MKP基于生物進(jìn)化

5、和仿生的遺傳算法,蟻群算法,人工魚群算法等,由于具有自組織性,魯棒性好,易于獲得全局解等特點(diǎn),在求解大規(guī)模組合優(yōu)化問題中應(yīng)用越來越廣泛.混合蛙跳算法(ShuffledFrogLeapingA1一gorithm,以下簡稱SFIA)是一種新型仿生群體智能優(yōu)化算法,它結(jié)合了基于基因進(jìn)化的模因演算法(MemeticAlgorithm,MA)和基于群體行為的粒子群算法(ParticleSwarmOptimization,PSO)兩者的優(yōu)hE,具有概念簡單，參數(shù)少,計(jì)算速度快，全局尋優(yōu)能力強(qiáng),易于實(shí)現(xiàn)的特點(diǎn),在資源分配,車間作業(yè)流程安排,旅行商問題,0-1背包問題1n等工程實(shí)際問題中得到有效的應(yīng)用.文獻(xiàn)E

6、lo和文獻(xiàn)11都是采用二進(jìn)制編碼對標(biāo)準(zhǔn)的01背包問題進(jìn)行求解.本文針對多維背包問題,采用十進(jìn)*收稿日期:2011年3月15日,修回日期:2011年4月28日作者簡介:馬竹根,男,講師,研究方向:人工智能,軟件工程.馬竹根等:求解多背包問題的混合蛙跳算法第39卷制整數(shù)編碼方式,應(yīng)用遺傳算法中的交叉操作對個(gè)體進(jìn)行更新,提出一種求解多維背包問題的離散混合蛙跳算法,在具體實(shí)例上的實(shí)驗(yàn)結(jié)果表明該算法對解決多維背包問題是行之有效的.2多背包問題數(shù)學(xué)模型多背包問題是指在一個(gè)物品集合N1,2,n中選出一個(gè)子集分別裝入m個(gè)背包中，在不超出每個(gè)包的限制容量6,的條件下,使選出的全部物品的總價(jià)值最大，其中？M,M1

7、,2,，m.背包問題可形式化地描述為6:Max?CiX(1)f2aijzbiJ1,2,m(2)滿足.?Nlz?0,1i1,2,(3)其中:C表示物品i的價(jià)值a表示物品i放人背包所占的容量.式(2)表示背包約束,由于具有m個(gè)約束,多背包問題又被稱為多維背包問題.在多背包問題中,除了確定每個(gè)物體是否裝入背包外,還需要確定它將裝入哪個(gè)背包.顯然對于多背包問題的優(yōu)化會(huì)比背包問題復(fù)雜得多，它是一個(gè)NP一完全問題.3混合蛙跳算法混合蛙跳算法是模擬青蛙覓食過程中信息共享和交流的特點(diǎn)而提出的一種仿生算法.在SFLA中，種群(解集)由一群具有相同結(jié)構(gòu)的青蛙組成,每只青蛙代表一個(gè)解.種群被分成多個(gè)族群,不同的族群

8、被認(rèn)為是具有不同思想和行為方式的青蛙的集合,不同的族群之間能夠相互影響.在每個(gè)族群內(nèi)以更新最差蛙為策略,按照預(yù)先定義的局部更新迭代次數(shù)進(jìn)行更新,當(dāng)所有族群內(nèi)最差蛙完成局部更新后,各個(gè)族群間進(jìn)行思想交流實(shí)現(xiàn)族群間的混合,重新產(chǎn)生新的族群.局部搜索和混合過程一直持續(xù)到滿足收斂條件或達(dá)到最大迭代次數(shù)為止.具體來說,SFLA可分成以下步驟：1)初始化種群：隨機(jī)生成P只青蛙組成初始種群,第i只青蛙表示問題的解為X=(,.27,),其中s為解空間的維數(shù),即變量的個(gè)數(shù).2) 劃分族群:將所有青蛙按照它們的適應(yīng)值降序排列，然后將整個(gè)種群分成m個(gè)族群，每個(gè)族群包含n只蛙,要求滿足P=mXn在迭代過程中第一只蛙分

9、人第一個(gè)族群,第二只蛙分人第二個(gè)族群,一直分配下去，直到第m只蛙分人第rn個(gè)族群.然后第十1只蛙分人第一個(gè)族群,第m+2只蛙分入第二個(gè)族群,依此類推,直到所有青蛙分配完畢.3) 族群進(jìn)化:在每個(gè)族群中,用和X分別表示該族群中適應(yīng)值最好和最差的青蛙,用X表示整個(gè)種群中最好的青蛙.然后對每個(gè)族群進(jìn)行局部深度搜索,即對每個(gè)族群中的最差蛙按下式進(jìn)行更新操作:D=rand()*(X一)(4)新的位置Xne-u2-X(當(dāng)前位置)+D,(DD三三二一D)(5)式中rand()是0,l之間的隨機(jī)數(shù),D表示青蛙所允許改變位置的最大值.如果這個(gè)過程能夠產(chǎn)生一個(gè)較好解,那么就用新位置青蛙取代最差蛙;如果沒有改進(jìn),則

10、用X代替X重復(fù)執(zhí)行式(4)和式(5);如果仍沒有改進(jìn),則在可行域中隨機(jī)產(chǎn)生一個(gè)新解取代原來最差青蛙X.重復(fù)這種更新操作,直到達(dá)到設(shè)定的局部搜索迭代次數(shù).4) 混合:當(dāng)所有族群的局部搜索完成后,將所有族群內(nèi)的青蛙重新混合并排序,重復(fù)執(zhí)行第2步和第3步直到滿足終止條件,輸出全局最優(yōu)解.4離散混合蛙跳算法求解多背包問題在蛙跳算法中,相關(guān)參數(shù)大部分屬于連續(xù)實(shí)數(shù)域,因此蛙跳算法主要適用于求解連續(xù)空間域的優(yōu)化問題,難于直接處理離散的組合優(yōu)化問題.在分析傳統(tǒng)蛙跳算法優(yōu)化機(jī)理的基礎(chǔ)上,本文采用了整數(shù)編碼方式和新的個(gè)體更新策略,提出一種解決多背包問題的離散蛙跳算法.4.1 蛙體結(jié)構(gòu)的編碼和解性能評價(jià)設(shè)計(jì)蛙跳算法首先要建立個(gè)體矢量與問題域之間的映射關(guān)系.在蛙跳算法中,一只青蛙對應(yīng)所求問題的一個(gè)解.設(shè)有n個(gè)物品m個(gè)背包，將n個(gè)物品按順序組成一向量X(z,35z,)表示青蛙個(gè)體，其中.?0,1,n,i1,2,n.=表示將第i個(gè)物品放人第m個(gè)背包,.270表示第i個(gè)物品不放入任何背包.例如,X=(2,3,1,0,0,0,2,3,3,2,0,1