Study of Chemical Reaction Based Algorithms for Knapsack Problems.pdf

1、背包問題在眾多工業(yè)領域中都能遇到，諸如交通、物流、切割及包裝、電信、可靠性、廣告、投資、預算分配和生產(chǎn)管理。在這些應用中，背包問題一般作為獨立的問題或復雜的子問題出現(xiàn)。
　　 從化學反應優(yōu)化算法(chemical reaction optimization, CRO)中得到啟發(fā)，本研究提出了兩種啟發(fā)式化學反應算法，并應用于0-1背包問題和多選擇背包問題。首先，化學反應優(yōu)化算法應用于求解0-1背包問題。在該算法中，五個特定化學反應

2、操作算子來實現(xiàn)平衡強化和多元化。
　　 其次，在解決0-1背包問題的化學反應優(yōu)化算法中，提出了一個貪婪的策略。第三，提出了一個新的基于化學反應優(yōu)化的方法解決多選擇背包問題。第四，在多選擇背包問題中，提出了一個并行版本的化學反應優(yōu)化算法。
　　 我們在一個大范圍的數(shù)據(jù)集中使用這些新的方法進行了測試。實驗結果表明，這些算法在解決背包問題等有很大的優(yōu)勢。
　　 論文結構:
　　 論文的結構分為六章。在第一章，介

3、紹了0-1背包問題，并提出了多選擇背包問題。同時提出了兩個元啟發(fā)式化學反應算法。第二章提出了一種新的具有貪婪策略的化學反應優(yōu)化算法來解決0-1背包問題。一個新的集成了貪婪策略和隨機選擇的修復算子用于修復不可行的解方案。第三章提出了一種新的具有貪婪策略化學反應優(yōu)化算法(CROG)來解決0-1背包問題。同時，還討論了CROG算法的算子的設計和參數(shù)的選擇。實現(xiàn)了一個新的具有貪婪策略和隨機選擇的修復函數(shù)用于修復不可行解的方案。第四章提出了一種新

4、的基于元啟發(fā)式的化學反應優(yōu)化算法來解決多選擇背包問題(MCKP)。提出新的方法，在一個MCKP的大測試集中進行測試，與遺傳算法(GA)相比，顯示出了更好的性能。第五章，提出了一個并行的化學反應優(yōu)化算法以解決多選擇背包問題， MCKP是一個著名的NP難問題。仿真結果表明，該方法在解質(zhì)量的優(yōu)化和計算時間兩個方面均要好于CRO，同時新方法也顯示出了解決這一問題的能力。第六章，總結了全文以及對未來的發(fā)展方向做了一個簡單的討論。
　　 第

5、一章
　　 本章介紹了兩種背包問題:0-1背包問題和多選擇背包問題。并對這兩個問題進行了文獻回顧及綜述。
　　 0-1背包問題:Maximize nΣi=1xipi(1) Subject to n∑i=1xiqi≤C,xi∈{0,1},(V)i∈{1,2，…，n}(2)變量xi的值為1或0，代表是選取或非選取第ith項。
　　 多選擇背包問題:minimize mΣi=1niΣj=1cijxij(3)subjec

6、t to m∑i=1ni∑j=1wijxij≤W(4)ni∑j=1xij=1,(V)i∈{1,2，…，m}(5)xij∈{0，1}，(V)i∈{1，2，…，m}，j∈Ni(6)所有的系數(shù)cij，wij，W都是正數(shù)，所有的N1，…，Nm均互不相交文獻回顧
　　 0-1背包問題
　　 在過去的四十年里，研究人員已經(jīng)提出了很多方法來解決0-1背包問題。這些方法中，我們可以分為兩類:精確算法和近似算法。
　　 精確算法包

7、括Bellman提出的[34]動態(tài)規(guī)劃法和Kolesar提出的分支定界法[35]。最近，研究人員，如Kellerer等[32]，所做的工作是尋求完全解決大的背包問題的實例的方法。許多算法都涉及尋求解決背包問題的“核心”方法，然后構建部分解并獲得全部的解。李等提出了一個基于共享存儲器的EREW-SIMD并行算法[56]。
　　 在早期的啟發(fā)式方法， Sahni首次提出了一個“多項式近似方案”來解背包問題[64]。在求解之前的一些有

8、解質(zhì)量保障的解方案，被認為是合適的解。正因為如此，隨著解質(zhì)量要求的提高，工作量也迅速增大。緊接著，權衡了解質(zhì)量和效率之間的關系，Ibarra和Kim提出了一個完全多項式近似解決方案，以保持均衡。Martello和Toth提出了一個特殊解決方案來解背包問題，并產(chǎn)生了一些改變的算法[34]。
　　 近年來，許多啟發(fā)式算法已被廣泛應用來解決0-1背包問題:周等[30]提出了一種蟻群優(yōu)化(ACO);施等[31]提出了修改參數(shù)的蟻群優(yōu)化模

9、型來適應求解0-1背包問題;李等[57]提出了基于多變異策略的二進制粒子群優(yōu)化(MMBPSO)來解決背包問題;Han和Kim[63]提出了一種量子啟發(fā)式進化算法(QEA)來解0-1背包問題;劉等[10]提出了一個模式引導的進化算法(SGEA)來解決0-1背包問題，鄒等[44]發(fā)明了全局和諧搜索算法來解決0-1背包問題。
　　 多選擇背包問題
　　 解決MCKP問題的算法也可以分為兩類:精確算法和近似算法。
　　

10、對于精確算法，分支界限法是一種枚舉的方法，通過排除不可能的解方案來減少搜索空間。在文獻[4、15、17]中討論了分支界限法算法和它的變種。在文獻[3、16]中提出了動態(tài)規(guī)劃算法。在文獻[5、16]中提出了動態(tài)規(guī)劃和分支界限法的混合型算法。
　　 因為MCKP是一個NP難問題。精確算法的時間復雜度是一個指數(shù)函數(shù)。啟發(fā)式算法更有優(yōu)勢在多項式時間內(nèi)找到近似最優(yōu)解。一個著名的啟發(fā)式算法是遺傳算法[12]。雖然，GA首先解決了MCKP但它

11、仍然是遇見了一個缺點，它容易陷入局部最優(yōu)解。
　　 第二章0-1背包問題的化學反應優(yōu)化算法
　　 本研究提出了一種新的基于貪婪策略的化學反應優(yōu)化算法來解決0-1背包問題?；瘜W反應優(yōu)化(ACROA)受化學反應過程的啟發(fā)來實現(xiàn)局部和全局搜索。本文提出了一個新的結合了貪婪策略和隨機選擇的修復算子，用于修復不可行的解方案。實驗結果證明ACROA算法性能優(yōu)越于遺傳算法(GA)算法和量子啟發(fā)進化算法(QEA)。
　　 盡管通

12、過已有的研究方法，許多0-1背包問題已經(jīng)圓滿地解決了，但研究它們?nèi)匀皇侵匾?，因為一些新的和更困難的0-1背包問題隱藏在現(xiàn)實世界中尚未解決。許多算法提供解決0-1背包問題的可能性，但他們是以犧牲效率為前提來解決，這是它們的不足。例如，最近提出解決0-1背包問題的方法，只能解決非常低維度的背包問題，但他們可能無法解決高維度的0-1背包問題。
　　 鑒于以上考慮，我們設計了一個基于ACROA和貪婪策略的算法來求解0-1背包問題。AC

13、ROA具有良好的搜索能力，展示了優(yōu)秀的操作算子，其性能表現(xiàn)在兩個重要的元啟發(fā)式優(yōu)化特征值:集約化和多樣化。此外，它還結合了遺傳算法的交叉算子和變異算子的優(yōu)勢。同時，本研究中，在修復算子的一個階段采用貪婪策略，但在另一個階段則采用一個隨機方法[63]。本文中提到修復算子所采用的兩個優(yōu)點，首先通過使用貪婪策略使該算法具有快速收斂性，其次是通過隨機搜索保證多樣性[20]。
　　 第三章0-1背包問題的具有貪婪策略的化學反應優(yōu)化算法

14、r>　　 0-1背包問題(KP01)是一個著名的組合優(yōu)化問題。它是一個NP難問題，在計算理論和在許多現(xiàn)實生活中都扮演著重要的角色。化學反應優(yōu)化(CRO)是一種新的優(yōu)化框架，靈感來自于大自然的化學反應。CRO在解決許多工程問題上有著優(yōu)良的性能，如二次分配問題、神經(jīng)網(wǎng)絡訓練、多通道連續(xù)問題等。本文提出了一種新的結合貪婪策略的化學反應優(yōu)化算法(CROG)來解決0-1背包問題。同時，還討論了CROG算法的算子的設計和參數(shù)的選擇。實現(xiàn)了一個新的

15、具有貪婪策略和隨機選擇的修復函數(shù)用于修復不可行的解方案。實驗結果證明CROG算法比遺傳算法(GA)，蟻群優(yōu)化(ACO)和量子激發(fā)了進化算法(QEA)等具有優(yōu)越的性能。本章的內(nèi)容發(fā)表在文獻[18]。
　　 第四章多選擇背包問題的化學反應優(yōu)化算法
　　 本研究提出一個新的解多選擇背包問題的基于元啟發(fā)式化學反應優(yōu)化的算法(MCKP)。MCKP是一個著名的NP難問題，在現(xiàn)實和理論上它有很多應用?；瘜W反應優(yōu)化(CRO)是一種模擬化

16、學反應過程的新的優(yōu)化方法。最近，在連續(xù)和離散兩個領域，CRO已被證明比很多其他的方法優(yōu)秀。提出的新方法，在一個大的MCKP問題測試集上實驗，與遺傳算法(GA)相比，顯示了更好的性能。
　　 我們觀察的收斂曲線的是強相關的測試集中的三個測試實例。這三個測試實例是(m=10，n=10)，(m=100，n=100)和(m=1000，n=1000)。如圖4.2所示，圖中顯示的是在3個測試實例中運行25次的平均總成本。它表明了算法具有全局

17、搜索能力和收斂能力。幾個觀察值如下:
　　 在(m=10，n=10)的情況下，如圖4.2a所示，GA的收斂曲線與CRO相近，但CRO仍然好一些。在(m=100，n=100)的情況下，如圖4.2b所示，CRO比GA有著更快的收斂速度。對于大的測試實例，(m=1000，n=1000)，如圖4.2c所示，當GA收斂速度很慢時，CRO仍然有著較好的收斂速度。
　　 從圖4.2中可知，CRO對于解大型的MCKP問題，比GA有更好的

18、收斂速度和解質(zhì)量。
　　 第五章多選擇背包問題的并行化學反應優(yōu)化算法
　　 提出了一個并行的化學反應優(yōu)化算法來解決多選擇背包問題，多選擇背包問題是一個著名的NP難問題。該算法使用了四個具體的反應算子。仿真實驗結果表明，該方法在解質(zhì)量優(yōu)化和計算時間等兩個方面均要好于化學反應算法。新方法顯示了對于這一難題的潛在解決能力。在未來，我們將研究基本反應算子和參數(shù)選擇對PCRO算法的影響。
　　 實驗環(huán)境為AMD Opter

19、on6134處理器，主頻2.3 GHz，8 GB內(nèi)存，二個CPU，每個包含8個核。操作系統(tǒng)是Windows XP。所有的算法都用MatlabR2011b和Java語言編程，其中Java使用的JDK為1.6.0.33版本。
　　 為了對PCRO和CRO算法的計算時間進行比較，我們使用了加速比值，定義如下:Speedupk=E[T1]/E[Tk](7)其中，k代表并行結點的數(shù)量。E[Ti]， i=1,(..)(k)是PCRO算法的平

20、均計算時間。分別對于表5.1和表5.2的實例進行仿真實驗，結果表明PCRO不僅加快了運行時間，同時也提高了解的質(zhì)量。
　　 CRO[2]是一個模仿化學反應過程的元啟發(fā)式方法。在CRO算法中，一個分子(M)包含勢能(PE)，動能(KE)，撞擊數(shù)及其他特征，它代表了一種潛在的解方案。在化學反應過程中，它模擬了四種類型的化學反應包括:撞墻，分解，分子間碰撞和合成，并在化學反應過程中，勢能(PE)向最低狀態(tài)轉(zhuǎn)換，并達到一個最佳平衡。對于

21、優(yōu)化問題，化學反應過程中的勢能用于表示問題的一個次優(yōu)解，勢能(PE)通常作為目標函數(shù)的適應度。
　　 CRO，由于其好過許多現(xiàn)有的進化算法，在最近幾年已經(jīng)成功地解決了許多問題。CRO已經(jīng)成功應用于二次分配問題[2]，資源受限項目調(diào)度問題[2]，在無線MESH網(wǎng)絡通道分配問題[34]、在對等流中的種群過渡問題[35]，感知的無線電頻譜分配問題[36]，電網(wǎng)調(diào)度問題[37、38]，標準連續(xù)基準函數(shù)[39]，股票投資組合的選擇問題[4

22、0]，人工1神經(jīng)網(wǎng)絡訓練[41]、網(wǎng)絡編碼優(yōu)化[42]等許多其他問題。
　　 修復算子
　　 修復算子是基于重復性的隨機選擇，直到背包約束得到滿足，盡管在某些情況下，這可能消耗大量的CPU時間。對于背包問題中，在文獻[23]中分析了傳統(tǒng)的貪婪策略的一些缺點。在本文中，一個新的修復算子采用了基于貪婪的策略和隨機選擇策略。這個修復過程的優(yōu)勢是平衡了CPU時間成本和不陷入局部最優(yōu)解。根據(jù)價值重量比pi/qi(i=1，2，…，n

23、)非增序排序。這意味著:pi/qi≥pj/qjfori＜j這個修復算子由兩個階段組成。第一階段(稱為ADD)，每個變量按pj/qj的降序排序，并在不違反可行性原則下變化從0到1。第二階段(稱為DROP)檢查，如果違反了可行性，隨機將一個變量從1變?yōu)?。DROP階段的目的是從一個不可行解中獲得一個可行的解決方案，而ADD尋求改善適應度高的可行解。修復算子的偽代碼在算法8中給出。
　　 PCRO結構
　　 PCRO的流程圖如

24、圖5.1所示。這個算法包括三個階段，初始階段，并行階段，交換和終止階段。在初始階段，加載系統(tǒng)參數(shù)、創(chuàng)建初始種群。在并行階段，化學反應算法在計算節(jié)點上執(zhí)行。經(jīng)過一定次數(shù)的循環(huán)后，全局最好的分子被廣播，在每個節(jié)點上最壞的分子被丟棄。
　　 基本操作
　　 1)撞墻算子
　　 這個操作被ON-wall ineffective collision reaction所調(diào)用。在{1，…，m}中隨機選取第i也位置，并且yi用一

25、個在{1，…，ni}范圍內(nèi)的隨機數(shù)代替。
　　 2)分子間碰撞
　　 通過兩個w1和w2，采用兩點交叉算子，獲得兩個新解w1'和w2'。
　　 3)分解算子
　　 通過分解操作可以從一個原始解變換出兩個新解w1'和w2'。這個操作算子的作用使得算法具有多樣化和使算法可以搜索解空間。分解算子的設計是受“HALF-TOTAL-EXCHANGE”算子啟發(fā)，主要用于解決信道分配問題[2]。
　　 4)合成

26、算子
　　 在本算法中，使用了合成算子[74]。這個算子的作用是將兩個解w1和w2合成一個分子w1'，每一個w'(i)是隨機從w1(i)和w2(i)選取的。
　　 第六章多選背包問題的人工化學反應優(yōu)化算法
　　 一、簡介
　　 背包問題(MCKP)是一個著名的np困難問題，它有很多應用在現(xiàn)實和理論。在這項研究中，一個人工化學反應優(yōu)化算法(ACROA)，使用整數(shù)字符串代碼來解決MCKP開發(fā)。四個具體反應算子

27、的設計包含了局部和全局搜索。一種新的罰函數(shù)，旨在迫使算法在搜索空間可行和不可行的空間中都能搜索。這個實驗表明，ACROA MCKP測試組優(yōu)于遺傳算法。更多的細節(jié)關于這個研究可以發(fā)現(xiàn)在[104]。
　　 二、目標和罰函數(shù)
　　 設x是在當前種群中的染色體，并且xij是與其相應的決策變量。在反應中，這些焓是非負的，且焓是反應過程是減少的。對于焓，設置如下:enthalpy(x)=∑mi=1∑nii=1cijxij(8)其中g

28、(x)是焓函數(shù)，具體如下:g(x)={0if(4)is satified;Ω0+(∑mi=1∑nii=1ωijxij-W) otherwise.(9)Ω0是一個給定的正常數(shù)。思想是對于違反的解決方案將會有更大的焓。它迫使搜索算法搜索整個空間，不管是可行和不可行域。
　　 三、操作算子
　　 合成
　　 這個操作算子將從兩個原始反應物合成一個反應物。為了使算法能向多元化發(fā)展，合成算子是針對這個問題重新設計的[96]

29、。合成算子的偽代碼描述見算法11。
　　 位移
　　 這個操作算子從兩個原始反應物中創(chuàng)建兩個新的反應物。兩個反應物字符串的每個位置都是考慮基于隨機生成的MASK信息交換，其類似于在均勻交叉遺傳算法中使用MASK一樣。在MASK的位置值為0時，反應物值交換，否則反應物值不變。
　　 redoX2
　　 有源的交叉是遺傳算法常用的。這個操作算子體現(xiàn)了強化功能。
　　 分解
　　 在反應物字符串

30、中隨機選擇兩個點，在這兩個點之間的值都進行逆轉(zhuǎn)。這個算子代表了算法多元化。
　　 redox1
　　 這個操作算子實現(xiàn)多元化操作。一個新的反應物（解決方案）從一個原始反應物中生成出來。
　　 評估。
　　 四、實驗結果
　　 所有的算法都用Matlab R2011b實現(xiàn)了。
　　 測試環(huán)境:在個人電腦E6700奔騰CPU在3.2 GHz CPU，2 g內(nèi)存，操作系統(tǒng)Windows XP。<

31、br>　　 我們已經(jīng)考慮算法在不同問題大小，測試實例和數(shù)據(jù)范圍的測試用例。我們對對于強烈相關的測試集合進行實驗，觀察到三個測試實例的收斂曲線。在實驗中采用了這三個實例(m=10;n=10)、(m=100;n=100)、和(m=1000;n=100)。圖6.2顯示了對于這三個測試實例，運行25次的總成本最好的均值情況。它表明了算法具有全局搜索能力和較好的收斂能力。幾個觀察到的實驗情況如下:在案例(m=10;n=10)，a）GA的收斂曲線

32、與CRO相當，但CRO更好。對于(m=100;n=100)、無花果。圖6.2 b）表明，與遺傳算法進行比較CRO有更快速的收斂性。對于較大的實例(m=1000;n=100)、圖6.2 c顯示，CRO仍有很好的收斂性，而遺傳算法顯示了一個非常緩慢的收斂。從圖6.2顯示，在解決大的MCKP時，CRO比GA有更好的收斂率和解的質(zhì)量。
　　 第七章結論和未來的工作
　　 背包問題在眾多工業(yè)領域中都能遇到，諸如交通、物流、切割及包

33、裝、電信、可靠性、廣告、投資、預算分配和生產(chǎn)管理。在這些應用中，背包問題一般作為獨立的問題或復雜的子問題出現(xiàn)。
　　 從化學反應過程中得到啟發(fā)，本研究提出了兩種啟發(fā)式化學反應算法，并應用于0-1背包問題和多選擇背包問題。論文的主要貢獻有四個方面:
　　 首先，化學反應優(yōu)化算法應用于求解0-1背包問題。在該算法中，五個特定化學反應操作算子來實現(xiàn)平衡強化和多元化。
　　 其次，在解決0-1背包問題的化學反應優(yōu)化算法中

34、，提出了一個貪婪的策略。
　　 第三，提出了一個新的基于化學反應優(yōu)化的方法解決多選擇背包問題。
　　 最后，在多選擇背包問題中，提出了一個并行版本的化學反應優(yōu)化算法。我們在一個大范圍的數(shù)據(jù)集中使用這些新的方法進行了測試。實驗結果表明，這些算法在解決背包問題等有很大的優(yōu)勢。
　　 在未來，我們將進一步在以下三方面進行研究:一是將在許多不同并行平臺去實現(xiàn)及并行化這些算法，達到讓這些運行得更快的目的;二是研究如何通過設