改進(jìn)二進(jìn)制和聲搜索算法求解多維背包問題

劉雅文,蔣 妍,潘大志

(西華師范大學(xué)數(shù)學(xué)與信息學(xué)院,四川 南充 637009)

0 引 言

多維背包問題是運籌學(xué)中的一個經(jīng)典的NP-hard問題，廣泛地應(yīng)用于對衛(wèi)星的日常管理[1]、資源分配[2]、庫存壓縮[3]等實際問題中。目前，求解MKP的算法主要分為確定性算法和非確定性算法。確定性算法主要包括動態(tài)規(guī)劃[4-5]、分支定界[6-8]等，該類算法可以求出問題的精確解，但隨著物品數(shù)量和約束條件的增加，問題的求解難度和事件復(fù)雜度呈指數(shù)增長，因此只適用于求解規(guī)模較小的背包問題。而對大規(guī)模問題的求解需要采用啟發(fā)式算法，目前，用來求解多維背包問題的啟發(fā)式算法主要有遺傳算法[9-10]、蟻群算法[11-13]、免疫算法[14]、混合分布估計算法[15-16]、小世界算法[17]、禁忌搜索算法[18-19]和競爭決策算法[20]等，隨著啟發(fā)式算法研究的不斷深入,近年來許多學(xué)者將不同類型的啟發(fā)式算法應(yīng)用于MKP的求解,取得了一定的成果,但仍存在穩(wěn)定性差、成功率低等問題。喻學(xué)才等[21]在背包問題表示的基礎(chǔ)上提出了一種新的構(gòu)造解的規(guī)則，并設(shè)計了一種適合該規(guī)則的新的啟發(fā)式信息，該方法耗用時間少，有良好的尋優(yōu)能力。王凌等[15]提出了一種基于分布估計算法的混合求解算法，引入了一種新概率模型更新機制，設(shè)計了基于問題信息的修復(fù)機制和變步長局部搜索操作，增強算法的局部搜索。針對MKP的特點，吳虎勝等[22]改進(jìn)了傳統(tǒng)基于大懲罰參數(shù)的目標(biāo)函數(shù)，減小了陷入局部極值的概率。王叢佼等[23]對參數(shù)進(jìn)行動態(tài)調(diào)整，提高了算法求解MKP的收斂性能和穩(wěn)定性。楊艷等[24]提出了一種貪心二進(jìn)制獅群優(yōu)化算法，增強了算法局部搜索能力并進(jìn)一步提高了收斂速度。歐陽海濱等[25]修正了和聲搜索算法中的即興創(chuàng)造過程，對參數(shù)PAR進(jìn)行動態(tài)調(diào)整，增強算法的局部搜索，有效平衡了算法的局部搜索和全局搜索。

以上改進(jìn)算法在一定程度上提高了局部搜索能力，避免陷入局部最優(yōu)。但通過深入研究仍有算法尋優(yōu)精度不足，隨著問題規(guī)模增大產(chǎn)生穩(wěn)定性差、成功率低等問題。針對這些問題，本文提出一種解決MKP問題的改進(jìn)二進(jìn)制和聲搜索算法(Improved Binary Harmony Search, IBHS)，首先將伯努利隨機過程應(yīng)用到初始種群，引入新的候選和聲生成算子；然后加入精英局部搜索策略來提高求解精度和收斂速度；最后為修復(fù)和優(yōu)化不可行解，設(shè)計一種新的多維加權(quán)價值密度計算方法；通過MKP問題的仿真實驗驗證算法的有效性。

1 多維背包問題

給定待選物品集合P={1,2,…,n}，MKP描述如下：從集合P中選取一組滿足所有問題約束的子集，使其價值之和最大。MKP公式表述如下：

(1)

其中：n為物品個數(shù)，m為背包維數(shù)；vi為物品i的價值；wij為物品i對背包第j維資源的消耗；xi為決策變量，當(dāng)xi=1時表示物品i被選擇，xi=0時表示不被選擇;bj為每一維背包的資源限制。

2 基本和聲搜索算法

和聲搜索算法的尋優(yōu)思想源于模擬音樂家的即興創(chuàng)作過程，通過經(jīng)驗搜索和有效的探索得到全局最優(yōu)解算法算法步驟可描述為：

Step1產(chǎn)生HMS個初始解，并放入和聲記憶庫中。

Step2對解的各個分量分別以概率HMCR在和聲記憶庫內(nèi)進(jìn)行搜索，以1-HMCR的概率在和聲記憶庫外搜索，期望獲得新解的對應(yīng)分量。

Step3在和聲記憶庫內(nèi)進(jìn)行搜索時，當(dāng)隨機搜索到某一分量后，對該分量以概率PAR進(jìn)行擾動。

Step4最后由搜索后得到的各個分量構(gòu)成新解，若新解優(yōu)于和聲記憶庫中的最差解，則用新解替換和聲記憶庫中最差解。

Step5Step2到Step4循環(huán)，直到滿足終止條件為止。

3 改進(jìn)的二進(jìn)制和聲搜索算法

本節(jié)在基本和聲算法[26]的基礎(chǔ)上，將搜索空間改為離散的0-1空間，并融入候選和聲生成、多維加權(quán)價值密度、精英搜索等算子以提高算法的尋優(yōu)能力。

3.1 候選和聲生成算子

在經(jīng)典的和聲搜索算法中，新的候選和聲的生成主要通過以下3個步驟：1)根據(jù)和聲記憶庫的考慮概率(HMCR)，從和聲記憶庫中學(xué)習(xí)；2)根據(jù)音調(diào)調(diào)整概率及和聲微調(diào)帶寬，在學(xué)習(xí)的基礎(chǔ)上進(jìn)行微調(diào)音調(diào)；3)隨機創(chuàng)作一個音調(diào)。

在連續(xù)變量空間中，精確的變量值決定了一個和聲中包含的位置信息。然而，MKP問題中的決策量均為0或1，精確的變化量就不再有意義，因此，采用了更為合適的候選和聲生成算子。計算過程如下：

Step1計算概率向量，由下式求得

(2)

Step2引入動態(tài)自適應(yīng)參數(shù)p，通過算法參數(shù)p的自適應(yīng)調(diào)整來協(xié)調(diào)算法的全局搜索和局部搜索。迭代初期，設(shè)置較小的p，以便在全局范圍內(nèi)進(jìn)行搜索；迭代后期，設(shè)置較大的p，令算法在局部范圍內(nèi)進(jìn)行搜索，便于局部范圍內(nèi)尋找最優(yōu)解，提高精度。p的自適應(yīng)表達(dá)式如下:

(3)

式中，p_max、p_min分別表示為p的最大值和最小值，0

(4)

其中randi([0,1],1,1)表示隨機生成0和1之間的1個數(shù)。

3.2 音調(diào)調(diào)整

音調(diào)調(diào)整的目的是擴(kuò)大估計范圍，從而獲得更優(yōu)秀的近似解，有效跳出局部極值?；贛KP問題中決策變量的特性，在和聲記憶庫每一維隨機選取2個和聲分量，若和聲分量的值相同則新的和聲保持不變，若2個和聲的值不同，則將新的候選和聲中0變1、1變0。音調(diào)調(diào)整算子設(shè)置為：

(5)

其中k1,k2為[1,HMS]內(nèi)2不等隨機數(shù)。

3.3 多維加權(quán)價值密度

對于MKP問題，物品的約束條件多，每個約束條件的量綱相差大，基于此，本文提出了多維加權(quán)價值密度σi，按照σi的大小順序，來修復(fù)不可行解，優(yōu)化可行解。σi計算步驟如下：

Step1去量綱：

(6)

其中，wij表示第i個物品在第j個約束條件下的重量，bj表示第j個約束條件的最大載重量。

Step2權(quán)重系數(shù)：

(7)

Step3物品的多維加權(quán)價值密度：

(8)

3.4 解的修復(fù)和優(yōu)化

求解MKP時，解空間會產(chǎn)生一部分不滿足約束條件的無效解。對無效解的修復(fù)，是求解MKP問題的關(guān)鍵。鑒于MKP問題的約束條件較多，每個約束條件的量綱相差又較大，據(jù)多維加權(quán)價值密度{σi}的值按降序產(chǎn)生序列T=(T1,T2,…,Tn)，依次對不可行解進(jìn)行修復(fù)。修復(fù)過程主要分為2個階段進(jìn)行：第1階段，針對初始解中決策變量為1的物品，將物品按照T的順序依次檢查放入背包是否超載，若未超載則放入背包，否則移除；第2階段，針對初始解中為0的物品，同樣按照T的順序依次檢查能否放入，在滿足不超載的情況下，貪心放入。

3.5 精英搜索策略

和聲算法是一種貪婪搜索算法，通過將得到的每一個新解與最差解進(jìn)行對比，擇優(yōu)放入記憶庫的方式來進(jìn)行迭代尋優(yōu)。然而，在整個算法設(shè)計過程中，沒有充分利用到最優(yōu)值，局部搜索能力也較弱。

針對這一問題，本文提出精英搜索策略，該策略對迭代所生成的最優(yōu)解進(jìn)行充分利用，并且大大提高算法的局部搜索能力。在和聲搜索過程中，增添一個變量Gbest來記錄最優(yōu)值。再分別對Gbest中的m列進(jìn)行擾動，擇出最優(yōu)個體，將所得的新解分別與記憶庫中的最差值和最優(yōu)值進(jìn)行對比，貪心接納。

3.6 IBHS算法

IBHS算法步驟如下：

Step1初始化算法參數(shù)。設(shè)定和聲記憶庫大小HMS，最大迭代次數(shù)NI，問題維度m，自適應(yīng)調(diào)整參數(shù)p_max、p_min，伯努利參數(shù)q=0.85。

Step2初始化和聲記憶庫HM。

Step4引入多維加權(quán)價值密度算子，對不可行解進(jìn)行修復(fù)和優(yōu)化，使其滿足約束條件。

Step5更新和聲記憶庫。如果得到的新的和聲的適應(yīng)度值優(yōu)于HM中最差的一個和聲，則將新的和聲更新至HM中。

Step6精英局部搜索。

1)Gbest=種群最優(yōu)個體。

2)對Gbest進(jìn)行4次隨機選取2-5位進(jìn)行0、1互換得到新的4個臨時個體。

3)將所得的臨時個體的適應(yīng)度值分別與記憶庫中的最差值和最優(yōu)值進(jìn)行對比，貪心接納。

Step7檢查是否達(dá)到算法終止條件。重復(fù)步驟step3～step6，直到達(dá)到最大迭代次數(shù)NI。

在IBHS算法中，step3～step5是通過新的候選和聲和音調(diào)調(diào)整算子生成一個新的和聲，使用降序排序方法對物品按多維加權(quán)價值密度排序，對不可行解進(jìn)行修復(fù)和優(yōu)化并計算個體適應(yīng)度，總的時間復(fù)雜度為O(Nnm+n2+nlnn)；step6是在精英個體周圍進(jìn)行局部搜索，時間復(fù)雜度為O(Nmn)；故IBHS算法的時間復(fù)雜度為O(MNnm+Mn2)。這里N為種群規(guī)模，M為最大迭代次數(shù)。

IBHS算法流程圖如圖1所示。

圖1 改進(jìn)二進(jìn)制和聲搜索算法流程圖

4 仿真結(jié)果分析

為驗證二進(jìn)制和聲搜索算法的性能，選取多個算例對IBHS進(jìn)行測試，并將結(jié)果與經(jīng)典的貪心二進(jìn)制獅群優(yōu)化算法[24](GBLSO)、改進(jìn)的差分演化算法[27](MBDE)以及二進(jìn)制修正和聲搜索算法[25](BMHS)進(jìn)行比較，算法結(jié)果為實現(xiàn)同樣算法運算結(jié)果。在處理器為Intel(R)Core(TM)i5-6200U，內(nèi)存為4 GB，操作系統(tǒng)Windows10的計算機上使用Matlab2020b進(jìn)行仿真實驗。

實驗用到的5類10個算例均來自ELIB數(shù)據(jù)(http://elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suite/index.html)。

4.1 算法參數(shù)設(shè)置

為充分測試各算法性能，參照文獻(xiàn)[28]，設(shè)置種群皆為N=9，最大迭代次數(shù)皆為10n，其中1為多維背包問題的物品數(shù)量。各算法的特定參數(shù)設(shè)置如表1所示。

表1 智能優(yōu)化算法非通用參數(shù)設(shè)置

4.2 仿真實驗及結(jié)果分析

對每個算例獨立運行20次，記錄20次實驗中的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差、成功率和尋優(yōu)成功迭代次數(shù)，其中本文認(rèn)為尋優(yōu)結(jié)果達(dá)到與全局最優(yōu)解的誤差不大于1%時尋優(yōu)成功，尋優(yōu)成功次數(shù)與試驗次數(shù)之比為成功率。結(jié)果如表2所示。

表2 智能進(jìn)化算法求解典型測試算例性能分析

圖2是IBHS、GBLSO、MBDE和BMHS 4種算法獨立運行20次實驗的平均尋優(yōu)曲線。從圖中可以看出，本文的算法的平均尋優(yōu)收斂速度快，能更好地找到全局最優(yōu)解。

(a) 測試算例weing1

由表2和圖2不難得出：

1)對于背包維度低、物品數(shù)量少的測試算例weing1、weing2而言，改進(jìn)二進(jìn)制和聲算法和貪心二進(jìn)制獅群優(yōu)化算法的尋優(yōu)能力最優(yōu)，能夠快速求得標(biāo)準(zhǔn)最優(yōu)解；其次是二進(jìn)制差分算法，也能較快地求得最優(yōu)值；最后是二進(jìn)制修正和聲搜索算法，平均尋優(yōu)收斂速度較慢。

2)對于背包維度低，物品數(shù)量多的測試算例weing7、weing8而言，隨著物品數(shù)量的增多，二進(jìn)制差分算法的尋優(yōu)能力有了很大的提高，而貪心二進(jìn)制獅群優(yōu)化算法和二進(jìn)制修正和聲搜索算法的尋優(yōu)能力大幅度下降。然而，改進(jìn)二進(jìn)制和聲算法在具有較好尋優(yōu)能力的同時有一定概率落入局部極值。

3)對于背包維度中等、物品數(shù)量少的測試算例pet2、pet3以及背包維度中等、物品數(shù)量中等的測試算例pet5、pet7，隨著背包維度和物品數(shù)量不同程度的不斷增大，二進(jìn)制修正和聲搜索算法尋優(yōu)能力大幅度下降，二進(jìn)制差分算法和貪心二進(jìn)制獅群優(yōu)化算法的尋優(yōu)能力都在一定程度上不斷減弱；改進(jìn)二進(jìn)制和聲算法的尋優(yōu)性能受到的影響并不大。

4)對于背包維度高、物品數(shù)量多的測試算例sent01、sent02，隨著背包維度的大幅度提高，貪心二進(jìn)制獅群優(yōu)化算法、二進(jìn)制修正和聲搜索算法和二進(jìn)制差分算法尋優(yōu)效果均有所下降，求解效果不明顯；而本文的改進(jìn)二進(jìn)制和聲算法平均尋優(yōu)收斂速度快。

隨著問題規(guī)模的增大，在有限次迭代計算中，GBLSO、MBDE和BMHS算法的求解精度和穩(wěn)定性均受到影響，表現(xiàn)為標(biāo)準(zhǔn)差增大，成功率降低等。但I(xiàn)BHS算法無論從求解精度還是求解穩(wěn)定性方面都要優(yōu)于原GBLSO、MBDE和BMHS這3種算法。

5 結(jié)束語

本文提出了一種求解MKP問題的改進(jìn)和聲搜索算法，提出了一種新的多維加權(quán)價值密度計算方法，算法中設(shè)計了精英局部隨機搜索以提高算法探索能力，通過10個覆蓋不同類型的經(jīng)典多維背包算例的仿真對比實驗表明，本文算法具有較好的求解穩(wěn)定性、收斂性和很好的魯棒性，是一種更為有效求解多維背包問題的算法。

下一步研究中可以考慮將改進(jìn)的二進(jìn)制和聲算法進(jìn)一步擴(kuò)大應(yīng)用范圍，例如集合聯(lián)盟背包問題、多背包問題等。