Study of Chemical Reaction Based Algorithms for Knapsack Problems.pdf

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

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

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

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

5、一章
　　 本章介紹了兩種背包問題:0-1背包問題和多選擇背包問題。并對(duì)這兩個(gè)問題進(jìn)行了文獻(xiàn)回顧及綜述。
　　 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項(xiàng)。
　　 多選擇背包問題: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均互不相交文獻(xiàn)回顧
　　 0-1背包問題
　　 在過去的四十年里，研究人員已經(jīng)提出了很多方法來解決0-1背包問題。這些方法中，我們可以分為兩類:精確算法和近似算法。
　　 精確算法包

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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