混合人工化學反應優化算法求解0-1背包問題

王建輝，鄭光勇，徐雨明

(1.長沙南方職業學院 民航學院，湖南 長沙 410208；2.湖南大學 信息科學與工程學院，湖南 長沙 410208；3.衡陽師范學院 計算機科學與技術學院，湖南 衡陽 421002；4.長沙師范學院 信息科學與工程學院，湖南 長沙 410001)

0 引 言

0-1背包問題(knapsack problem)是一個典型的組合優化問題，即給定n個物品，每個物品重量為gi,價值為ui，從中選出若干個物品，使得選出物品的總價值V最大但總重量W不超過背包的重量總量C。背包問題在實際中有很多應用，如切割問題、調度問題[1]、密碼問題[2-3]等。這些都是NP難問題，因此不可能有多項式時間算法，除非P=NP[4]。背包問題的模型表示如下：

總價值為：

(1)

總重量為：

(2)

其中，xi取值為1或0，表示第i個物品的選擇或不選擇。

求解KP01問題的方法可以分為精確算法和近似算法兩類。精確算法研究包括Bellman[1]提出的動態規劃、Kolesar提出的分支定界法等。在早期的啟發式算法中[5]，Sahni最先提出了用多項式近似方法求解背包問題[6]，Ibarra和Kim改進為完全多項式近似方法[7]。

近年來，針對背包問題提出了大量的元啟發式算法。例如，呂曉峰等提出了一種求解0-1背包問題的改進遺傳算法[8]；吳迪等提出了基于改進的蜂群遺傳算法求解多選擇背包問題[9]；喻學才等提出了多維背包問題的蟻群優化算法(ACO)[10]；高尚等提出了背包問題的混合粒子群優化算法[11]；Han等提出了量子進化算法(QEA)[12]；Liu等提出了一種模式指導的進化算法(SGEA)[13]；Zou等提出了全局調和的搜索算法[14]。

文中提出在ACROA算法中融入貪心算法思想來解決KP01問題。ACROA算法具有很強的搜索能力，在高效性和多樣化兩個特征上表現出色[15-16]。因為化學反應算子中使用了與遺傳算法操作算子中相似的交叉和變異算子，使得ACROA算法也具有了GA的優點。在修正算子的階段采用貪心思想，在其他階段則采用文獻[12]中用到的隨機方法。文中提及的修復函數有兩個優勢：一是貪心思想使得算法具有更快的收斂性；二是通過隨機搜索保證多方向覆蓋，有效避免局部最優解。

1 人工化學反應優化算法(ACORA)

ACORA是Alatas受化學反應過程的啟發[15]提出的一種啟發式算法。在化學反應過程中，系統傾向于最高的熵和最低的焓。化學反應中所擁有的有效對象、狀態、過程和事件，可以被設計為一種計算方法。焓或潛在的能量(對于最小化問題)、熵(對于最大化問題)可以作為相關問題的目標函數。算法1給出了ACROA算法的輪廓。更多的細節可以參考文獻[15-16]。

算法1：ACROA algorithm

Output：The best solution

1 formreacNum calculate enthalpye(mi);

2 initial{f→δ,E→φ,T→max};

3 Setting the initial reactantsR0={q1,q2,…,qn}、R1={l1,l2,…,ln} and evaluation;

4 whileTnot met do;

5 {for bimolecular reactions do

{binary encoding synthesis reaction;

binary encoding displacement reaction;

binary encoding redox2 reaction;

calculatefandE;}

for monomolecular reactions do

{binary encoding decomposition reaction;

binary encoding redox1 reaction;

calculatefandE;}

}

6 if(f<δ) andE>Φthen

{

Apply reversible reaction update Φ of enthalpy,

updateδof functionf，Rset of reactants，maximum number of iterationT，dimensions of the problemD;

goto 4;}

else

{output the best solution; }

7 end if

8 end while

1.1 化學反應

在ACROA中，有兩種化學反應類型，即單分子反應和雙分子反應。單分子反應只需要一個反應物參與，包含redox1反應和分解反應兩種。雙分子反應包含合成反應、redox2反應和置換反應三種，需要兩種反應物參與。對于ACORA，采用二進制編碼。上述5種化學反應的運算分別描述如下：

1.1.1 二進制編碼合成反應

具體規則是：兩個反應物通過比特位運算(相同為1，不同為0)，產生一個新的反應物。這種運算的過程如圖1所示。

圖1 二進制編碼的合成反應

1.1.2 二進制編碼置換反應

該運算由兩種初始反應物產生兩種新的反應物。兩種反應物二進制串的每個比特位都通過基于隨機生成的掩碼進行變換，以實現兩種反應物之間的信息交換。對于掩碼為0的位，兩種反應物對應位的值相交換，否則不變，如圖2所示。

圖2 二進制編碼置換反應

1.1.3 二進制編碼氧化還原反應2

首先隨機選擇兩個交叉點，對應位的數據交換即可，如圖3所示。

圖3 二進制編碼氧化還原反應2

1.1.4 二進制編碼分解反應

在原反應物二進制串中隨機選取兩個隨機點，把這兩個點之間的每個位反轉，即0變成1，1變成0。如圖4所示，隨機選取的是第2、6位隨機點，將它們之間的每位反轉。

圖4 二進制編碼分解反應

1.1.5 二進制編碼氧化還原反應1

具體規則是：隨機選取一位取反，如圖5所示。

圖5 二進制編碼氧化還原反應1

1.2 反應物更新

這一步驟來源于可逆化學反應，進行化學平衡測試。如果新生成的反應物具有更好的功能價值，則新反應物被保留，否則被排斥，這樣有助于反應物趨向最優解。當終止條件滿足時，ACROA報告最好的解，否則，重復前面的化學反應過程。

2 KP01問題的ACROA算法設計

該算法用二進制編碼表示解的結構，求解KP01問題的ACROA算法描述如下：

2.1 解的表示

所求KP01問題的解用一個二進制串來表示，第i位為1表示第i項物品被選擇，為0則表示未被選擇。二進制解串的長度等于問題中的物品個數n。

2.2 目標函數

在反應中，熵(entropy)是非負的且在反應過程中遞增，定義如下：

(3)

2.3 約束處理

使用二進制串有時會使得產生的解違反約束條件，通常用懲罰和修復兩種技術解決這個問題。第一種方法是懲罰系數[14]。雖然這種方法可以幫助算法找到足夠的解，但它并不有助于改進解的質量。下面引入的修復函數正是用來克服這個缺點。

修復算子是基于重復隨機選擇直到滿足背包約束，這可能會在某些情況下消耗大量的CPU時間。相反地，傳統的貪婪策略也帶有背包問題中的其他一些缺點，詳細分析見文獻[8]。文中使用一個新的修復算子，它依賴于貪婪策略和隨機選擇[17]。此修復程序的優點是在CPU時間成本和擺脫局部最優之間取得了平衡。將問題中的物品按價值重量比率ui/gi(i=1,2,…,n)從大到小排序，即：

(4)

這種修復操作包括兩個階段。第一階段(稱為增加階段)按照價值重量比ui/gi遞減的順序檢查每個變量xi，只要不違背約束，就將變量的值0變為1。第二階段(稱為減少階段)隨機檢查一個變量，如果違背約束，將這個變量的值1變為0.減少階段的目標是把非可行解變為可行解；而增加階段是改進可行解的價值最大化。修復算子描述見算法2。

算法2：Repair(ω)

Input：原解ω

Output：經修復算子處理后的解ω'

2i=1;

3 while(m>0 andi≤n) do

4 if(m≥gi) then

5ωi=1;

6m=m-gi;

7i=i+1;

8 end if

9 end while

11 while(k>0) do

12 隨機從背包選擇一項，假設為第i項;

13ωi=0;

14k=k-gi;

15 end while

16ω'←ω//ω經處理后變為ω'

3 仿真實驗

采用8個KP01問題來證明ACROA算法的有效性。所有的算法用C#2010實現。采用PC機，Pentium E5500 CPU/2.8 GHz、2G RAM，運行Windows7操作系統。

3.1 三種算法求解小維度規模0-1背包問題的性能

在這一部分，采用文獻[14]中使用的5個測試函數。在表1中，5個測試函數的維度分別是4、10、7、5和20。

這5個測試函數的實驗獨立運行30次。ACROA算法中僅有參數reacNum需要調整，并且設置為5。終止條件設置為100 000。對于所有的函數，算法找出最優解的成功率為100%。

為了進一步研究ACORA算法的性能，還應用了3個大維度的強相關實例。

表1 5個測試集的維度大小和設置參數

3.2 三種算法求解大維度規模0-1背包問題的性能

為了測試ACROA算法求解大維度KP01問題的性能，與GA算法和QEQEA算法進行比較實驗。在這些測試案例中，采用強相關的數據集。物品的重量gi、價值ui和背包容量C由下式計算得出：

gi=rand[1,10]

(5)

ui=gi+5,i=1,2,…,n

(6)

(7)

其中，rand[1,10]隨機產生1到10的整數，服從均勻分布。

實驗采用3個測試實例，分別是200、600和1 000個物品。圖6～圖8顯示了在3個實例中運行30次得到的平均最大總價值中，ACROA算法都是最好的，證明了ACROA算法的全局搜索能力和收斂能力都明顯優于GA和QEA。

圖6 最大利益情況(迭代200次)

圖7 最大利益情況(迭代600次)

圖8 最大利益情況(迭代1 000次)

4 結束語

基于人工化學反應和貪心策略提出了有效求解0-1背包問題的一種新算法。其中仔細設計了5個特定問題的基本化學反應，基于貪婪策略給出了一個新的修復函數及其有效算法。通過5個基準實例和3個強相關數據集實例的仿真實驗，將ACROA算法與GA、QEA算法進行了比較，驗證了ACROA算法的性能優于其他算法。