求解0-1背包問題的混合貪婪遺傳算法

陳 楨，鐘一文，林 娟

（1.福建農(nóng)林大學(xué)計(jì)算機(jī)與信息學(xué)院，福州 350002；2.智慧農(nóng)林福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室（福建農(nóng)林大學(xué)），福州 350002）

0 引言

背包問題（Knapsack Problem，KP）［1］屬于經(jīng)典的組合優(yōu)化問題，屬于NP 難問題［2］，該類問題包括許多變種：0-1KP［3］、有界KP、無界KP、多重約束的KP、多維KP、集合并集的KP、多KP、多重選擇的KP、二次KP、動(dòng)態(tài)KP、折扣KP［4］以及其他類型的KP。在眾多變體KP中，最基本的就是0-1KP。在理論上，許多整數(shù)規(guī)劃問題的求解都依賴于一個(gè)高效的求解KP的算法，因此在實(shí)際應(yīng)用中常常被用于工業(yè)、金融等領(lǐng)域，比如投資決策、貨物裝載等。

傳統(tǒng)求解0-1KP 的辦法是精確算法，譬如窮舉法、動(dòng)態(tài)規(guī)劃法、遞歸法、回溯法和分支定界法等［4］。精確算法可以得到問題的精確解，但是隨著物品數(shù)量和背包容量的增加，算法時(shí)間的復(fù)雜性呈現(xiàn)出指數(shù)級(jí)的增長(zhǎng)趨勢(shì)，計(jì)算效率比較低，因此只適合小規(guī)模問題的求解。而元啟發(fā)式算法作為近似搜索算法，可在較短時(shí)間找到問題的近似有效解，逐漸成為解決大規(guī)模0-1KP 的主流方法。該類算法大致可分為兩類：以局部搜索為特征的單個(gè)體迭代算法，包括經(jīng)典的模擬退火（Simulate Annealing，SA）算法［5］、混合貪婪修復(fù)算子的噪聲檢測(cè)算法（Noising Methods with hybrid greedy repair operator，NM）［6］等；以協(xié)同搜索為特征的基于種群的智能優(yōu)化算法，包括常見的蟻群優(yōu)化（Ant Colony Optimization，ACO）［7］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）［8］、遺傳算法（Genetic Algorithm，GA）［9］，新興的布谷鳥搜索［10］、帝王蝶優(yōu)化算法［11］，以及和聲搜索算法（Harmony Search Algorithm，HSA）［12］等，均可見在0-1KP上的應(yīng)用。

GA作為一種典型的進(jìn)化型算法，其獨(dú)特的選擇、交叉、變異算子以及概率化的尋優(yōu)方式，使得算法自動(dòng)獲取解空間的布局，自適應(yīng)地調(diào)整搜索狀態(tài)，因此算法具有較好的全局協(xié)同搜索能力。但由于GA 缺乏有效的小范圍搜索策略，導(dǎo)致其局部搜索能力較差，在實(shí)際應(yīng)用中，容易產(chǎn)生早熟收斂的問題。為了有效提高GA 在全局大范圍搜索中跳出局部極值解的能力，同時(shí)結(jié)合0-1KP 的問題特征，本文提出混合貪婪遺傳算法（Hybrid Greedy Genetic Algorithm，HGGA）：在GA 的并行解空間中，增加提高個(gè)體的局部求精能力的搜索模塊；并針對(duì)常用的基于物品價(jià)值密度的修復(fù)優(yōu)化算子僅強(qiáng)調(diào)物品的性價(jià)比，使得總體價(jià)值高但相對(duì)性價(jià)比低的物品難以被選入，從而導(dǎo)致搜索范圍縮減及收斂速度降緩的問題，提出同時(shí)選擇物品價(jià)值密度以及物品價(jià)值為標(biāo)準(zhǔn)的混合貪婪操作算子，在局部解空間中展開彈性的動(dòng)態(tài)搜索。算法在并行迭代的算法框架中，通過增強(qiáng)GA 的精細(xì)搜索能力得到算法求精能力和求泛能力的良好平衡。算法在不同問題性質(zhì)及大規(guī)模的測(cè)試集上進(jìn)行了測(cè)試，并通過與同類算法的對(duì)比，顯示出較好的性能。

1 相關(guān)工作

1.1 0-1背包問題

0-1KP 可以簡(jiǎn)單描述為：給定n種物品集合N=｛1，2，…，n｝和一個(gè)背包容量為C的背包。每一種物品i都有它的重量wi（＞0）和價(jià)值vi（＞0）（i=1，2，…，n）。求最優(yōu)裝包方案（x1，x2，…，xn），xi∈｛0，1｝（xi=0 表示不把第i個(gè)物品放入背包，xi=1 表示把第i個(gè)物品放入背包），使得背包的總重量W不超過C的同時(shí)獲得的價(jià)值V達(dá)到最大。在選擇物品裝入背包時(shí)，物品只有兩種狀態(tài)：整體裝入或不裝入。其數(shù)學(xué)表達(dá)式為：

0-1KP 問題屬于帶有約束條件的最大值優(yōu)化問題，對(duì)違反約束條件的處理通常有兩種方法。第一種是罰函數(shù)方法，通過對(duì)不可行解增加一個(gè)負(fù)值罰分從而排查此類解進(jìn)入下一輪迭代的可能性。另外一種更常見的方法是引入修復(fù)優(yōu)化操作，該操作分為兩個(gè)步驟：首先是修復(fù)操作，即對(duì)不可行解按照一定的準(zhǔn)則移除物品，直到該不可行解變?yōu)榭尚薪鉃橹?；接下來是?yōu)化操作，即選擇合適的物品加入，在出現(xiàn)不可行解之前停止。其中，對(duì)于物品的選擇標(biāo)準(zhǔn)，通常采用的是基于價(jià)值密度的貪婪選擇方法，即優(yōu)先選擇單位價(jià)值（vi/wi）密度大的物品。具體算法描述如算法1和算法2。在兩個(gè)算法中，均引入了一個(gè)基于價(jià)值密度降序排列的物品列表HD，當(dāng)不可行解出現(xiàn)時(shí)，首先采用貪婪修復(fù)算子（OPerator-Repair，OP-R）進(jìn)行修復(fù)，根據(jù)物品在HD中的排序依次對(duì)物品進(jìn)行考察，如果當(dāng)前物品在背包中，將其移除，直至背包內(nèi)物品總量量滿足約束條件為止；隨后采用貪婪優(yōu)化算子（OPerator-Optimization，OP-O）對(duì)該解進(jìn)行優(yōu)化，同樣根據(jù)HD中物品的順序，優(yōu)先選擇價(jià)值密度大的物品進(jìn)行加入。

算法1 貪婪修復(fù)算子（OP-R）。

1.2 求解0-1背包問題的啟發(fā)式算法

GA作為一個(gè)經(jīng)典的啟發(fā)式搜索算法，通過對(duì)生物遺傳和進(jìn)化過程中選擇、交叉、變異機(jī)制的模仿，來完成對(duì)問題最優(yōu)解的自適應(yīng)搜索過程，在解決大規(guī)模組合問題方面具有較好的表現(xiàn)。其中在解決0-1KP 方面，一般是通過兩種方法進(jìn)行求解：一種是基于罰函數(shù)的基本遺傳算法（Simple GA，SGA）［13］；一種是基于處理約束條件的修復(fù)或修復(fù)優(yōu)化的貪婪算子的改進(jìn)遺傳算法，其中改進(jìn)遺傳算法較SGA 優(yōu)越。Michalewicz［14］首先研究了利用GA 求解0-1KP 時(shí)個(gè)體編碼方法的優(yōu)劣以及處理0-1KP 不可行解的罰函數(shù)法與修復(fù)法，指出：GA的個(gè)體采用0-1向量編碼比自然數(shù)編碼的效果更佳，而且利用修復(fù)法處理0-1KP 不可行解比罰函數(shù)法的結(jié)果更好。從此，人們?cè)诶肎A 求解0-1KP 時(shí)一般均采用0-1 向量的編碼方式。

GA 的搜索能力由選擇算子、雜交算子決定，變異算子保證算法能搜索到問題空間的盡可能多的點(diǎn)，從而使其具有搜索全局最優(yōu)的能力，所以一般求解0-1KP的改進(jìn)GA 也是從這3 個(gè)算子上做調(diào)整和改進(jìn)，結(jié)合基于修復(fù)或修復(fù)優(yōu)化的貪婪算子求得最優(yōu)解。文獻(xiàn)［15］將貪婪算子與GA 結(jié)合起來得到混合遺傳算法（Hybrid Genetic Algorithm，HGA）。在HGA 中首先采用二進(jìn)制編碼的GA 產(chǎn)生新解，然后通過價(jià)值密度引導(dǎo)的貪婪算子對(duì)不滿足約束條件的解進(jìn)行修復(fù)。文獻(xiàn)［16］針對(duì)HGA 中提出的貪婪算子的缺陷提出新的貪婪算子，不僅僅修復(fù)不滿足約束條件的種群，也優(yōu)化滿足條件的種群，并將此方法與GA 相結(jié)合構(gòu)成一種新的算法GGA。文獻(xiàn)［17］將基于價(jià)值密度的貪婪算法與GA 相結(jié)合提出一種改進(jìn)的混合GA來求解0-1 背包問題，改進(jìn)的混合GA 通過GA 的擇優(yōu)，重復(fù)執(zhí)行選擇、交叉和變異以及基于價(jià)值密度的貪婪算法的修復(fù)優(yōu)化這樣一個(gè)過程，使得解無限接近最優(yōu)解，同時(shí)采用精英保留機(jī)制來提高算法的收斂速度。文獻(xiàn)［18］用GGA 改進(jìn)的貪婪算子提出一種改進(jìn)混合遺傳算法（Improved Hybrid Genetic Algorithm，IHGA），對(duì)染色體進(jìn)行修復(fù)和優(yōu)化，并基于穩(wěn)態(tài)復(fù)制的策略，對(duì)GA 的選擇操作進(jìn)行改進(jìn)，給出了隨機(jī)選擇操作。

還有一類改進(jìn)GA，通過加入模擬退火算法（SA）或改進(jìn)的SA 來增加局部搜索能力，使得通過GA 的全局搜索方式下求得的解能夠跳出局部極值，并最終趨于全局優(yōu)化。文獻(xiàn)［19-20］分別運(yùn)用模擬退火和遺傳算法相結(jié)合的方法求解0-1KP，克服了各自的弱點(diǎn)，提高算法的優(yōu)化性能、優(yōu)化效率和可靠性。文獻(xiàn)［21］借鑒二重結(jié)構(gòu)編碼的解碼處理方法設(shè)計(jì)了一種新解碼方法，在保證解可行性的同時(shí)修正種群中無對(duì)應(yīng)可行解的個(gè)體；采用模擬退火算法和改進(jìn)的精英選擇算子改進(jìn)SGA。

上述算法在進(jìn)化效率或最優(yōu)解搜索能力上都存在一些不足，因此，受SA具有較強(qiáng)局部搜索能力可以彌補(bǔ)GA的局部求精能力不足的啟發(fā)，同時(shí)借鑒文獻(xiàn)［6］中貪婪算子的改進(jìn)方法，本文提出了一種新的混合貪婪遺傳算法，使得局部搜索和全局搜索相互結(jié)合，取長(zhǎng)補(bǔ)短。

2 改進(jìn)的混合貪婪遺傳算法

本文提出的改進(jìn)算法主要針對(duì)以下問題：混合GA 的局部求解能力不足、算法傾向早熟收斂；基于價(jià)值密度的修復(fù)優(yōu)化方法過分強(qiáng)調(diào)價(jià)值與重量的比率、無法全面覆蓋優(yōu)質(zhì)解且降低搜索速度。本文提出結(jié)合局部搜索和混合修復(fù)優(yōu)化算子的混合貪婪遺傳算法，首先在標(biāo)準(zhǔn)的GA 框架下增加局部搜索模塊，并采用基于貪婪思想的混合修復(fù)優(yōu)化算子，對(duì)個(gè)體展開解空間中的精細(xì)更新，有機(jī)結(jié)合協(xié)同搜索和局部搜索的優(yōu)勢(shì)，從而提高算法的整體性能。

2.1 解的表示及初始化

0-1KP 屬于組合優(yōu)化問題，對(duì)于此類問題的解，在GA 中采用二進(jìn)制編碼方式，即種群中的每一個(gè)個(gè)體為一個(gè)n元0-1向量x，該向量中的每一位隨機(jī)取值為0或1，分別表示把此物品放入或不放入背包中。

2.2 全局搜索模塊

本文提出的算法依托標(biāo)準(zhǔn)GA 的全局開拓能力，執(zhí)行標(biāo)準(zhǔn)GA 的進(jìn)化框架，在種群隨機(jī)初始化產(chǎn)生之后，通過交叉、變異和選擇操作產(chǎn)生新的種群。

1）交叉操作：對(duì)初始化種群中的解隨機(jī)取兩個(gè)染色體作為父母?jìng)€(gè)體，依照交叉概率選擇個(gè)體進(jìn)行均勻交叉操作，生成與父代個(gè)體數(shù)目一致的子代個(gè)體。

2）變異操作：對(duì)子個(gè)體按照變異概率進(jìn)行基位變異，對(duì)選中的位置上的0/1 編碼進(jìn)行逆向轉(zhuǎn)化，即0 變異位1，1 變異為0。

3）選擇操作：采用擇優(yōu)選擇法，將父代和子代的個(gè)體統(tǒng)一按照適應(yīng)值的降序排序，根據(jù)該排序選擇滿足種群數(shù)的個(gè)體組成新一代的種群。

2.3 局部搜索模塊

通過第一階段的種群進(jìn)化過程，種群中的個(gè)體已覆蓋了較廣的搜索區(qū)域，但對(duì)于現(xiàn)有范圍的精細(xì)搜索，在GA 的算法框架內(nèi)沒有較好的辦法。因此，在種群總體得到一次進(jìn)化操作后，對(duì)于種群中的每一個(gè)個(gè)體，增加一個(gè)局部搜索模塊，使得每一個(gè)個(gè)體以自身為搜索起點(diǎn)，在其周圍展開局部范圍內(nèi)的搜索。具體操作步驟為：對(duì)于種群中的每一個(gè)個(gè)體，隨機(jī)對(duì)一個(gè)位進(jìn)行翻轉(zhuǎn)，采用貪婪的方式接受修改，即如果該操作使得對(duì)應(yīng)的適應(yīng)值得到提高，就接受新解以代替舊解；否則沿用舊解，進(jìn)行下一輪的局部擾動(dòng)，直到達(dá)到預(yù)先設(shè)置的局部搜索次數(shù)。在后續(xù)的操作中，經(jīng)過新一輪的全局搜索過程，采用GA三個(gè)基本操作將優(yōu)質(zhì)的局部解信息迅速擴(kuò)散，同時(shí)在局部搜索中出現(xiàn)的極易陷入局部最小值，而貪婪接收方式無法輕易跳出極值的問題，通過全局的進(jìn)化過程，陷入極值的解得以相應(yīng)調(diào)整并往正確的方向進(jìn)化。進(jìn)一步地，在總體迭代條件不變的情況下，通過合理平衡全局迭代次數(shù)以及局部搜索次數(shù)，在種群中的優(yōu)良信息得以均勻快速地推廣同時(shí)，在較理想的解空間周邊的細(xì)致搜索也使得算法找到全局最優(yōu)解的可能性大大提高。通過這樣全局搜索和局部搜索有機(jī)結(jié)合的方式，算法在全局求泛和局部求精的性能上得到了良好的平衡。具體算法描述如算法3。在算法3 中，對(duì)于種群的每一個(gè)個(gè)體，隨機(jī)選擇一維進(jìn)行擾動(dòng)，同時(shí)進(jìn)行修復(fù)和優(yōu)化，如果之后的結(jié)果好于原先的解，就替代原先的解，繼續(xù)進(jìn)行下一輪搜索，直到達(dá)到局部搜索次數(shù)為止。

算法3 局部搜索算法。

2.4 混合貪婪算子

對(duì)于在迭代過程中不可行解的處理，通常采用基于價(jià)值密度的貪婪修復(fù)和優(yōu)化操作。雖然這種操作方式使得性價(jià)比高的物品優(yōu)先進(jìn)入背包，但是這種單一的選取方法將導(dǎo)致具有較大價(jià)值但相對(duì)性價(jià)比低的物品無法被選入，而這部分物品的加入可大幅提高算法的全局尋優(yōu)速度。但是單純選擇價(jià)值大的物品同樣也會(huì)增加算法陷入局部最優(yōu)解的概率。因此在HGGA 中采用基于混合策略貪婪修復(fù)算子（Operator-Hybrid，OP-H）。該算子借鑒了文獻(xiàn)［6］的混合貪婪修復(fù)算子策略，在不可行解時(shí)，算法首先采用采用基于價(jià)值密度的準(zhǔn)則移除性價(jià)比最低的物品，在盡量保持現(xiàn)有優(yōu)質(zhì)解信息的同時(shí)進(jìn)行有效率的修復(fù)；在優(yōu)化過程中，采用隨機(jī)的方式，概率性地選擇基于價(jià)值密度或價(jià)值的策略，彈性地對(duì)解進(jìn)行優(yōu)化，在提高算法的收斂速度的同時(shí)有效避免陷入極值點(diǎn)。與文獻(xiàn)［6］不同的地方在于：NM算法在不可行解出現(xiàn)時(shí)，直接采用概率方法選擇不同的策略同時(shí)進(jìn)行修復(fù)和優(yōu)化，這樣會(huì)造成價(jià)值大的物品有較大概率被移除出背包，從而降低算法收斂速度。具體算法描述如算法4。

算法4 混合貪婪算子（OP-H）。

輸入 按照價(jià)值密度降序排列的物品列表HD，按照價(jià)值降序排序的物品列表HV，選擇概率p和不可行解個(gè)體x。

輸出 滿足約束條件的優(yōu)化解x′。

在算法4中，首先基于價(jià)值密度的選擇方式調(diào)用算法1修復(fù)初始解x中的不可行解，接著隨機(jī)生成概率r，對(duì)于修復(fù)過的可行解來說，如果r小于p，采用基于價(jià)值密度的選擇方法對(duì)個(gè)體x進(jìn)行優(yōu)化；反之則優(yōu)選選擇價(jià)值大的物品加入x中。

在算法運(yùn)行過程中，一旦產(chǎn)生新解，上述兩個(gè)算子OP-R及OP-O就對(duì)該新解分別進(jìn)行修復(fù)和優(yōu)化的工作。其中，貪心修復(fù)算子負(fù)責(zé)將價(jià)值密度最低的物品盡快移除，在對(duì)違反約束條件的解進(jìn)行修復(fù)的同時(shí)提供進(jìn)一步優(yōu)化的空間，貪心優(yōu)化算子負(fù)責(zé)對(duì)修復(fù)后的解進(jìn)行局部?jī)?yōu)化。兩個(gè)算子協(xié)同工作，在解空間中展開合法、有效的搜索。

2.5 HGGA框架

HGGA 主要有3 個(gè)重要的組成部分：在初始解隨機(jī)生成之后，首先依靠GA 的全局搜索流程，通過經(jīng)典的交叉、變異、選擇操作進(jìn)化出新一代種群；然后對(duì)種群中的每一個(gè)個(gè)體展開局部范圍內(nèi)的更新；對(duì)于不可行解的修復(fù)過程采用混合貪婪修復(fù)算子進(jìn)行操作。3 個(gè)組成部分協(xié)同搜索，構(gòu)造有效解空間，引導(dǎo)整個(gè)種群進(jìn)化，最終找到最優(yōu)解。具體算法描述如算法5。

算法5 HGGA流程。

輸入 函數(shù)評(píng)價(jià)次數(shù)MET，popSize，localTimes，HD，HV。

輸出 最優(yōu)解Xbest。

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 測(cè)試數(shù)據(jù)集

為了驗(yàn)證HGGA 的性能，引入在各文獻(xiàn)中出現(xiàn)的3 個(gè)數(shù)據(jù)測(cè)試集分別進(jìn)行測(cè)試。

第1 個(gè)測(cè)試數(shù)據(jù)集來自文獻(xiàn)［22］，根據(jù)問題特征按照物品質(zhì)量、價(jià)值呈無相關(guān)、弱相關(guān)和強(qiáng)相關(guān)分為3 類，分類特征如表1所示。每類中包含5個(gè)測(cè)試實(shí)例，分別包含物品數(shù)量為800、1 000、1 200、1 500 和2 000。在表2 中分別給出這3 類測(cè)試?yán)拥木唧w名稱、物品數(shù)目及理論最優(yōu)解。

第2 個(gè)測(cè)試數(shù)據(jù)集的兩個(gè)實(shí)例（實(shí)例1、2）是0-1KP 的經(jīng)典實(shí)例，實(shí)例來自文獻(xiàn)［18］，兩個(gè)實(shí)例的實(shí)驗(yàn)次數(shù)均為50 次。n為物品數(shù)量，C為背包容量，V為物品價(jià)值，W為物品重量。

第3 個(gè)測(cè)試數(shù)據(jù)集來自文獻(xiàn)［23］，數(shù)據(jù)集是大規(guī)模的0-1KP 產(chǎn)生的。每個(gè)物品的價(jià)值是從0.5到1之間隨機(jī)生成的，相應(yīng)的物品重量也是在0.5到2之間隨機(jī)生成的。

背包的最大容量被設(shè)置為上述物品重量之和的0.75 倍。這些數(shù)據(jù)都是隨機(jī)生成器一次生成的，并且用于所有的實(shí)驗(yàn)。放入背包的物品數(shù)量從100 到6 400，包括100、200、300、500、700、1 000、1 200、1 500、1 800、2 000、2 600、3 000、3 500、4 900、5 800、6 400。這些實(shí)例被標(biāo)記為L(zhǎng)KP1～LKP16。

表1 第1個(gè)大樣本數(shù)據(jù)的分類特征Tab.1 Classification characteristics of first dataset of large sample data

表2 第1組15個(gè)測(cè)試?yán)拥膮?shù)值Tab.2 Parameter values of 15 test cases in first dataset

3.2 參數(shù)設(shè)置及運(yùn)行環(huán)境

在HGGA 中，采用函數(shù)評(píng)價(jià)次數(shù)MET作為迭代結(jié)束條件，取值為40 000；在GA框架下的參數(shù)沿用經(jīng)典的GA參數(shù)［24］設(shè)置：交叉概率cp取值為0.1，變異概率mp取值為0.01；對(duì)于平衡算法全局與局部搜索性能的種群數(shù)popSize和局部搜索次數(shù)localTimes，在固定的MET條件下，采用實(shí)驗(yàn)的方式?jīng)Q定。混合貪婪算子的選擇概率dp設(shè)為0.5。每個(gè)測(cè)試用例上的實(shí)驗(yàn)獨(dú)立運(yùn)行次數(shù)設(shè)為100。

實(shí)驗(yàn)的硬件環(huán)境為小米筆記本，CPU 型號(hào)為Intel Core i5-8250U，內(nèi)存8 GB，軟件環(huán)境為64 位Windows 10 操作系統(tǒng)，算法使用Java語言在Eclipse IDE中編寫。

3.3 參數(shù)分析

在相同的函數(shù)評(píng)價(jià)次數(shù)下，如何設(shè)置種群數(shù)和局部搜索次數(shù)決定了HGGA 搜索的深度和廣度。如果種群數(shù)太大，而局部搜索次數(shù)太小，會(huì)導(dǎo)致種群在局部范圍內(nèi)搜索精度不足，從而影響算法整體尋優(yōu)能力；反之如果局部搜索次數(shù)太大，而種群數(shù)設(shè)置太小，會(huì)因算法的多樣性不足而容易出現(xiàn)早熟收斂的現(xiàn)象。選用3.1 節(jié)中的第1 組數(shù)據(jù)集中的重量?jī)r(jià)值呈強(qiáng)相關(guān)的5 個(gè)數(shù)據(jù)集，對(duì)于popSize和localTimes分別設(shè)置（100，10）、（50，20）、（20、50）、（10、100）進(jìn)行測(cè)試，并觀察100 次重復(fù)實(shí)驗(yàn)中Xbest最后一次得到改善時(shí)的平均迭代次數(shù)。從圖1可以看出，當(dāng)種群數(shù)和搜索次數(shù)取（10、100）時(shí)，最優(yōu)解得到最后一次改進(jìn)所需要的迭代次數(shù)最少，所以這種搭配可以對(duì)算法在多樣性和收斂性上達(dá)到一個(gè)比較均衡的平衡。因此，算法最終的popSize設(shè)置為10，localTimes設(shè)置為100。

圖1 不同參數(shù)組合下算法最后一次得到改進(jìn)所需的平均迭代次數(shù)對(duì)比Fig.1 Comparison of mean iterations required by the algorithm to have the last improvement under different parameter combinations

對(duì)于混合貪婪算子中使用的選擇概率dp的取值，采用實(shí)驗(yàn)統(tǒng)計(jì)方式進(jìn)行。當(dāng)dp取0 和1 時(shí)，分別代表只采用基于價(jià)值和密度和只采用價(jià)值作為選擇準(zhǔn)則的操作算子。測(cè)試選用3.1 節(jié)的表2 的3 組大樣本數(shù)據(jù)的15 個(gè)測(cè)試數(shù)據(jù)集，dp分別取0、0.1、0.2 取到1，統(tǒng)計(jì)15 個(gè)測(cè)試用例在不同取值下得到最優(yōu)解的個(gè)數(shù)。結(jié)果如圖2所示。

圖2 不同dp取值在15個(gè)測(cè)試?yán)由先〉阶顑?yōu)解的個(gè)數(shù)對(duì)比Fig.2 Comparison of the number of obtained optimal solutions on 15 test cases with different dp values

當(dāng)dp=0 時(shí)，僅有3 個(gè)測(cè)試用例能夠得到最優(yōu)解，當(dāng)dp在0.4～0.6 時(shí)，能夠取到的最優(yōu)解的個(gè)數(shù)最多。因此，為了增強(qiáng)算法的普適性，在本文中dp取值為0.5。

3.4 算法性能分析

為了測(cè)試HGGA 性能，在第1 個(gè)數(shù)據(jù)集上進(jìn)行了測(cè)試。算法獨(dú)立運(yùn)行100 次，統(tǒng)計(jì)得到的最優(yōu)解與理論最優(yōu)解的實(shí)際差值、最優(yōu)解、最差解、均值解、中位數(shù)解和標(biāo)準(zhǔn)差，適應(yīng)值最后一次得到提高時(shí)的迭代次數(shù)，運(yùn)行時(shí)間以及在100 次重復(fù)中得到最優(yōu)解的成功率。表3 給出測(cè)試結(jié)果。粗體部分為獲得最好狀態(tài)的解。

從表3 中可以看出，本文提出的算法在所有15 個(gè)測(cè)試用例上均能找到最好解，對(duì)于其中的11 個(gè)測(cè)試用例可以百分百找到最優(yōu)解。雖然在KP01、KP08、KP09 上的成功率較低，但是通過觀察其找到的均值解、中位數(shù)解以及最差解可以看出，HGGA 所能找到的解與最優(yōu)解非常相近，并且所有測(cè)試均在1 s內(nèi)完成100次重復(fù)性實(shí)驗(yàn)，顯示了算法的良好性能。

表3 HGGA在15個(gè)不同類型測(cè)試?yán)由系慕Y(jié)果Tab.3 Results of HGGA on 15 test cases with different types

3.5 與同類算法的比較

為了進(jìn)一步顯示HGGA 的算法性能，引入不同的測(cè)試數(shù)據(jù)分別與其他GA 以及近年來表現(xiàn)較好的其他新型算法分別進(jìn)行縱向及橫向的比較。

3.5.1 與GA的比較

測(cè)試數(shù)據(jù)采用上述第2 個(gè)測(cè)試數(shù)據(jù)集，背包里的物品數(shù)目分別取50和100，所有結(jié)果的數(shù)據(jù)均來源于原文獻(xiàn)。其中，HGA 是使用貪心變換與GA 結(jié)合的貪心GA［15］，IHGA［18］是改進(jìn)的混合GA。n代表物品個(gè)數(shù)，算法獨(dú)立運(yùn)行50 次，J為50次實(shí)驗(yàn)中得到的最好解，JC代表最好解在50 次內(nèi)出現(xiàn)的次數(shù)，JZ代表繁殖代數(shù)的均值。cp和mp分別采用與文獻(xiàn)中相同的設(shè)置值0.5和0.01。表4給出與其他GA的比較結(jié)果。

從表4 可以看出，HGA、IHGA 和HGGA 在背包里的物品數(shù)目取50時(shí)都得到最優(yōu)的結(jié)果，HGGA 在50次實(shí)驗(yàn)中每次都能求出最優(yōu)值，而背包里的物品數(shù)目取100 時(shí)，只有HGGA 能得到最優(yōu)解，而且50 次實(shí)驗(yàn)中都能找到最優(yōu)解。從這兩個(gè)結(jié)果可得出，HGGA 與同類算法相比，在小規(guī)模的測(cè)試數(shù)據(jù)上具有較好的性能。

表4 不同改進(jìn)遺傳算法求解0-1KP的結(jié)果Tab.4 Results of different improved genetic algorithms in solving 0-1KP

3.5.2 與其他元啟發(fā)算法的比較

為了進(jìn)一步測(cè)試算法性能，算法與其他同類型的元啟發(fā)算法在不同規(guī)模的問題上進(jìn)行了比較。進(jìn)行比較的算法為：基于全局和諧搜索的混合布谷鳥搜索算法（hybrid Cuckoo Search algorithm with Global Harmony Search，CSGHS）［10］、二元帝王蝶優(yōu)化（Binary Monarch Butterfly Optimization，BMBO）算法［11］、混沌帝王蝶優(yōu)化（Chaotic Monarch Butterfly Optimization，CMBO）算法［22］、基于對(duì)立學(xué)習(xí)的帝王蝶優(yōu)化（Opposition-based learning Monarch Butterfly Optimization，

OMBO）算法［25］和混合貪婪修復(fù)算子的噪聲檢測(cè)算法（NM）［6］。表5～7分別給出了3組數(shù)據(jù)上的表現(xiàn)。

表5 HGGA與其他元啟發(fā)算法在求解5個(gè)無相關(guān)特征0-1KP時(shí)的數(shù)據(jù)對(duì)比Tab.5 Data comparison of HGGA and other meta-heuristic algorithms in solving 5 0-1KPs without correlation characteristics

表5 的數(shù)據(jù)表明，在大樣本的物品價(jià)值和數(shù)量無相關(guān)的測(cè)試數(shù)據(jù)中，CMBO、OMBO、NM 和HGGA 比CSGHS 和BMBO在找到最優(yōu)解上表現(xiàn)得更好，NM 在KP01 的測(cè)試數(shù)據(jù)里表現(xiàn)略差，CMBO 和OMBO 在KP03 上表現(xiàn)較弱。HGGA 在這5 個(gè)例子中最差解、均值解和中位數(shù)解上的表現(xiàn)都比CMBO、OMBO 和NM 好。在方差std的測(cè)算上，HGGA 的總體表現(xiàn)也是最好的，足見該算法的穩(wěn)定性。表6 顯示了這些算法在求解5 個(gè)無相關(guān)特征的0-1KP 數(shù)據(jù)上的平均排名，對(duì)于KP05，CSGHS 和BMBO 沒有數(shù)據(jù)，取KP01～KP04 排名的平均值作為KP05 的排名取值，并對(duì)這些排名數(shù)據(jù)進(jìn)行0.05 顯著性水平條件下的Friedman 檢驗(yàn)，得到的p值等于0.003，說明這些算法在排序值上有顯著性差異。

表6 6個(gè)算法在求解5個(gè)無相關(guān)特征的0-1KP時(shí)的平均排名Tab.6 Average ranking of 6 algorithms in solving 5 0-1KPs without correlation characteristics

表7 的數(shù)據(jù)表明，在大樣本的物品價(jià)值和數(shù)量呈弱相關(guān)的測(cè)試數(shù)據(jù)中，CMBO、OMBO、NM 和HGGA 比CSGHS 和BMBO 表現(xiàn)得好。OMBO、HGGA 在5 個(gè)測(cè)試算例中都得取得最優(yōu)解，CMBO 在KP08，NM 在KP09 上沒有取得最優(yōu)解。HGGA 在最差解、均值解和中位數(shù)解上綜合表現(xiàn)是勝出的，方差也較小。表8 顯示了這些算法在求解大樣本的物品價(jià)值和數(shù)量呈弱相關(guān)的測(cè)試數(shù)據(jù)上的平均排名。對(duì)于KP10，CSGHS 和BMBO 沒有數(shù)據(jù)，取KP06～KP09 排名的平均值作為KP10 的排名取值，在0.05 顯著性水平條件下的Friedman 檢驗(yàn)得到的p值為0.004，說明這些算法在排序值上有顯著性差異。

表7 HGGA與其他元啟發(fā)算法在求解大樣本弱相關(guān)特征的0-1KP時(shí)的數(shù)據(jù)對(duì)比Tab.7 Data comparison of HGGA and other meta-heuristic algorithms in solving 0-1KPs with weak correlation characteristics of large samples

表8 6個(gè)算法在求解5個(gè)大樣本弱相關(guān)特征的0-1KP的數(shù)據(jù)的平均排名Tab.8 Average ranking of 6 algorithms in solving 5 0-1KPs with weak correlation characteristics of large samples

表9 的數(shù)據(jù)表明，在大樣本的物品價(jià)值和數(shù)量呈強(qiáng)相關(guān)的測(cè)試數(shù)據(jù)中，CMBO、OMBO、NM 和HGGA 比CSGHS 和BMBO 表現(xiàn)得好。CMBO、OMBO、NM 和HGGA 在5 個(gè)測(cè)試算例中都取得最優(yōu)解。NM 和HGGA 的方差在5 個(gè)例子里都為0，說明算法的在這個(gè)測(cè)試數(shù)據(jù)集上的表現(xiàn)非常穩(wěn)定。表10顯示了這些算法在求解大樣本的物品價(jià)值和數(shù)量呈強(qiáng)相關(guān)的測(cè)試數(shù)據(jù)上的平均排名。對(duì)于KP15，取KP11～KP14 排名的平均值作為KP15 的排名取值，在0.05 顯著性水平條件下通過Friedman 檢驗(yàn)得到的p值為0.002，說明這些算法在排序值上有顯著性差異。

表9 HGGA與其他元啟發(fā)算法在求解大樣本強(qiáng)相關(guān)特征的0-1KP時(shí)的數(shù)據(jù)對(duì)比Tab.9 Data comparison of HGGA and other meta-heuristic algorithms in solving 0-1KPs with strong correlation characteristics of large samples

表10 6種算法在求解5個(gè)大樣本強(qiáng)相關(guān)特征的0-1KP的數(shù)據(jù)的平均排名Tab.10 Average ranking of 6 algorithms in solving 5 0-1KPs with strong correlation characteristics of large samples

值得說明的是，HGGA 與除NM 之外的其他比較函數(shù)一樣，屬于基于種群的優(yōu)化算法，因此針對(duì)0-1KP，它們的算法時(shí)間復(fù)雜度均取決于外層迭代數(shù)目、種群數(shù)目及物品數(shù)量；而NM雖然不屬于基于種群的算法，但其迭代過程類似地取決于外層迭代數(shù)目、內(nèi)層局部搜索迭代數(shù)目及物品數(shù)量；進(jìn)一步地，雖然HGGA加入了局部搜索部分，但這個(gè)部分的時(shí)間復(fù)雜度取決于局部搜索迭代次數(shù)、種群數(shù)目及物品數(shù)量，并不影響整體算法復(fù)雜度，因此這幾個(gè)參與比較的算法均具有相同的時(shí)間復(fù)雜度，而HGGA 可以在更少的函數(shù)評(píng)價(jià)次數(shù)內(nèi)找到優(yōu)質(zhì)解。

3.5.3 在大規(guī)模數(shù)據(jù)集上的比較

為了進(jìn)一步測(cè)試算法在大規(guī)模數(shù)據(jù)集上性能，采用上述第三組測(cè)試用例，進(jìn)行比較的算法為：大型0-1 背包問題的簡(jiǎn)化二進(jìn)制和聲搜索（Simplified Binary Harmony Search，SBHS）算法［23］，表11 給出了不同的算法在16 個(gè)測(cè)試數(shù)據(jù)上的表現(xiàn)。表11 的數(shù)據(jù)表明，在這16 個(gè)大型0-1KP 的測(cè)試數(shù)據(jù)中，對(duì)于前6 個(gè)數(shù)據(jù)，SBHS 和HGGA 的最優(yōu)解相同，而HGGA 在最差值、均值解和中位數(shù)上的表現(xiàn)都均優(yōu)于SBHS。在數(shù)據(jù)LKP7-LKP14 中，HGGA 在各指標(biāo)上的表現(xiàn)都優(yōu)于SBHS；在數(shù)據(jù)LKP15中，SBHS的均值解和中位數(shù)解較優(yōu)；在數(shù)據(jù)LKP16中，SBHS解的所有表現(xiàn)都會(huì)比HGGA略好。

在標(biāo)準(zhǔn)差上，除了最后一個(gè)測(cè)試?yán)油猓琀GGA 在每一個(gè)測(cè)試用例上的表現(xiàn)均優(yōu)于SBHS，足見HGGA 在大規(guī)模的測(cè)試數(shù)據(jù)上的穩(wěn)定性。

表11 HGGA與SBHS算法在求解大樣本強(qiáng)相關(guān)特征的0-1KP時(shí)的數(shù)據(jù)對(duì)比Tab.11 Data comparison of HGGA and SBHS algorithms in solving 0-1KPs with strong correlation characteristics of large samples

4 結(jié)語

針對(duì)GA 在解決大規(guī)模離散優(yōu)化問題上全局搜索能力強(qiáng)、局部求精能力薄弱的缺點(diǎn)，本文提出混合了局部搜索算子的改進(jìn)GA。算法在不變動(dòng)GA 的基本框架下，融合具備局部精細(xì)搜索能力的局部搜索方法，使得算法得以依賴GA 的強(qiáng)大全局搜索性能將局部搜索中得到的優(yōu)質(zhì)解快速擴(kuò)散；同時(shí)設(shè)計(jì)混合貪婪修復(fù)算子，在個(gè)體保留優(yōu)良信息的同時(shí)提高算法的尋優(yōu)速度。算法應(yīng)用于0-1KP，在不同問題規(guī)模及性質(zhì)的測(cè)試集上進(jìn)行大量的仿真實(shí)驗(yàn)，通過與其他同類算法的比較顯示出算法的高效性和穩(wěn)定性，特別是在大規(guī)模數(shù)據(jù)集上的有效性。

今后的工作將進(jìn)一步挖掘局部搜索和基于種群的新型智能優(yōu)化算法的有機(jī)融合，并擴(kuò)展到更大的應(yīng)用范圍，例如多維KP、折扣KP等。