張 銘，鄧文瀚，林 娟，鐘一文

1.福建農(nóng)林大學(xué) 計(jì)算機(jī)與信息學(xué)院，福州350002

2.智慧農(nóng)林福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室（福建農(nóng)林大學(xué)），福州350002

背包問題（Knapsack Problem，KP）是經(jīng)典的NP-困難問題，它包括多維背包問題、完全背包問題、分組背包問題和折扣{0-1}背包問題（Discounted {0-1} Knapsack Problem，DKP）等多種類型。DKP 在2007 年首先在文獻(xiàn)[1]中提出，它是對(duì)商場(chǎng)促銷行為的抽象，在商業(yè)、投資決策、資源分配和密碼學(xué)等方面都有實(shí)際應(yīng)用價(jià)值。由于DKP是NP-困難的，近幾年許多學(xué)者對(duì)使用智能優(yōu)化算法來求解DKP進(jìn)行了深入的研究，如遺傳算法（Genetic Algorithm，GA）[2-4]、差分進(jìn)化算法（Differential Evolution，DE）[5-6]、二進(jìn)制蝙蝠算法[7]、帝王蝶算法[8-9]、混沌烏鴉算法[10]、蛾類搜索算法[11]、基于群論優(yōu)化算法（Group Theory-based Optimization Algorithm，GTOA）[12]、細(xì)菌覓食算法（Bacterial Foraging Algorithm，BFO）[13]和粒子群優(yōu)化算法[14]等。由于DKP 提出的時(shí)間還不是很長(zhǎng)，關(guān)于該問題的研究在解的精度等方面還存在極大改進(jìn)空間。蟻群優(yōu)化算法（Ant Colony Optimization algorithm，ACO）是求解組合優(yōu)化問題的經(jīng)典群智能優(yōu)化算法，目前尚未發(fā)現(xiàn)ACO 在DKP 上的應(yīng)用研究。同時(shí)，現(xiàn)有的算法大多使用價(jià)值密度來引導(dǎo)解的優(yōu)化，單純使用價(jià)值密度來引導(dǎo)解的優(yōu)化會(huì)導(dǎo)致算法過早收斂，影響其尋優(yōu)能力。針對(duì)在DKP 上的以上不足，本文提出了一個(gè)改進(jìn)的蟻群優(yōu)化（Modified ACO，MACO）算法，算法具備以下幾個(gè)特征：

（1）根據(jù)DKP的構(gòu)造特點(diǎn)，采用組內(nèi)競(jìng)爭(zhēng)方式計(jì)算物品的選擇概率，從而降低算法的時(shí)間復(fù)雜度。

（2）在不降低算法精度的前提下舍去啟發(fā)式信息，從而減少算法所使用的參數(shù)，簡(jiǎn)化參數(shù)設(shè)置。

（3）采用混合基于價(jià)值密度及價(jià)值的優(yōu)化算子，提高算法的尋優(yōu)能力。

（4）基于上述的改進(jìn)模塊設(shè)計(jì)出的算法，在DKP問題的求解中具有良好的性能表現(xiàn)。

1 相關(guān)工作

1.1 折扣{0-1}背包問題的定義以及數(shù)學(xué)模型

DKP是一個(gè)帶約束的組合優(yōu)化問題，有一個(gè)容量為C 的背包和n組物品的集合。每一組i(0 ≤i≤n-1)中包含3 個(gè)物品，這3 個(gè)物品的價(jià)值分別表示為vi,1、vi,2和vi,3，重量分別表示為wi,1、wi,2和wi,3。每組中物品價(jià)值與重量之間的關(guān)系如下：vi,1+vi,2=vi,3、wi,1+wi,2>wi,3、wi,3>wi,1以及wi,3>wi,2。每一組中至多只有一個(gè)物品能放入背包。目標(biāo)是在不超過背包容量的情況下使放入背包中的物品價(jià)值總和最大。由于每組中至多只有一個(gè)物品能放入背包，使得該問題有多種編碼方式，目前對(duì)DKP 的描述有3 種數(shù)學(xué)模型。Guldan[1]提出了DKP 的第一種數(shù)學(xué)模型，該模型以0、1方式進(jìn)行編碼，0表示物品不在背包里面，1則表示物品在背包里面。賀毅朝等[2]提出了DKP 的第二種模型和第三種模型。在第二種模型中，以四進(jìn)制數(shù)進(jìn)行編碼，該編碼表示每組物品i被選擇的物品編號(hào)。第三種模型沒有指定編碼方式，用存儲(chǔ)已經(jīng)放入背包的物品集合表示解，該解只是一個(gè)潛在解，只有滿足DKP約束的解才是可行解。這里使用文獻(xiàn)[2]提出的第二數(shù)學(xué)模型：

其中，xi表示第i組中放入背包物品的編號(hào)，0 表示該組沒有物品放入背包。式（2）保證了每一組至多只有一個(gè)物品放入背包；式（3）則保證了放入背包的物品重量之和不會(huì)超出背包的容量。

1.2 蟻群優(yōu)化算法求解0-1背包問題

ACO 算法是經(jīng)典的構(gòu)造型群智能優(yōu)化算法，螞蟻根據(jù)以往螞蟻所留下的信息素和啟發(fā)式信息構(gòu)造解。在開始提出時(shí)，ACO 算法用于求解旅行商問題[15]，現(xiàn)在被廣泛運(yùn)用于許多領(lǐng)域優(yōu)化問題的求解，如旅行商問題[16-17]、路徑規(guī)劃[18-20]和函數(shù)優(yōu)化[21]等。雖然現(xiàn)在還沒有ACO算法在DKP上的研究，但是已經(jīng)有許多ACO算法在其他KP問題上的應(yīng)用研究。文獻(xiàn)[22]針對(duì)旅行商問題（Traveling Salesman Problem，TSP）和0-1 背包問題（0-1 Knapsack Problem，0-1KP）等NP-困難問題，提出了一種基于蟻群系統(tǒng)的信息素矩陣優(yōu)化策略，加速了算法的正反饋過程，有助于最優(yōu)解的探索。文獻(xiàn)[23]將ACO 算法運(yùn)用在0-1KP 上，將問題表示成相應(yīng)的構(gòu)造圖，并根據(jù)該圖設(shè)計(jì)狀態(tài)轉(zhuǎn)移公式，蟻群根據(jù)該公式在圖中移動(dòng)至死亡，所經(jīng)過的路徑成為問題的一個(gè)解，在這其中還加入了禁忌列表存放螞蟻所經(jīng)過的線段，避免冗余。文獻(xiàn)[24]將量子計(jì)算與ACO 算法相結(jié)合對(duì)0-1KP 進(jìn)行求解。把量子計(jì)算中的態(tài)矢量和量子旋轉(zhuǎn)門加入到ACO算法中，達(dá)到加快算法的收斂速度，并且加入了量子交叉策略，避免了算法過早的陷入局部最優(yōu)。該文還利用MapReduce 模型實(shí)現(xiàn)算法的并行化。文獻(xiàn)[25]將ACO 算法與拉格朗日松弛混合求解多維背包問題。首先求解問題的拉格朗日對(duì)偶問題，獲得各對(duì)象的拉格朗日價(jià)值；再利用KP中核的概念，根據(jù)拉格朗日價(jià)值構(gòu)建該問題的核問題，減少了問題的規(guī)模，使得問題的求解速度變快。最后利用ACO算法進(jìn)行種群迭代搜索，在螞蟻構(gòu)造的每個(gè)候選解中，在保證解可行的前提下，以高價(jià)值的物品替換低價(jià)值的物品，進(jìn)行局部搜索，以便進(jìn)一步提升解的質(zhì)量。文獻(xiàn)[26]利用改進(jìn)的遺傳蟻群混合算法求解多維0-1KP，將遺傳算法與ACO算法結(jié)合互補(bǔ)。在算法的每次迭代過程中，挑選幾只表現(xiàn)比較好的螞蟻，對(duì)它們進(jìn)行遺傳算法搜索，并將該結(jié)果反饋回蟻群，為其他螞蟻的尋優(yōu)提供了一個(gè)指引。在ACO 算法的迭代過程中加入了輪盤賭方式、禁忌表交換和信息素的混沌更新策略，增加了種群的多樣性，并保證種群能夠有效收斂。

由于目前尚未發(fā)現(xiàn)ACO 求解DKP 的研究文獻(xiàn)，這里以文獻(xiàn)[22]中所描述的求解0-1KP的ACO算法為例，來描述ACO算法的基本思想。τ和η是存儲(chǔ)信息素和啟發(fā)式信息的兩個(gè)向量，其中τi表示物品i的信息素值，ηi則表示物品i的啟發(fā)式信息。在構(gòu)造解的每一步，螞蟻根據(jù)信息素與啟發(fā)式信息，對(duì)每個(gè)還未放入背包的物品用式（4）計(jì)算選擇概率，然后通過輪盤賭策略選擇放入背包的物品。

其中，α與β是兩個(gè)參數(shù)，用來控制信息素與啟發(fā)式信息的重要性，啟發(fā)式信息用vi/wi表示，B是一個(gè)集合，存放已經(jīng)放入背包的物品。

使用以上的方法來構(gòu)造解是一個(gè)全局競(jìng)爭(zhēng)的選擇，每一個(gè)物品與其他未放入背包的物品競(jìng)爭(zhēng)選擇。該選擇過程的最壞時(shí)間復(fù)雜度計(jì)算如下：在第i步，要計(jì)算n-i+1 個(gè)選擇概率。每只螞蟻構(gòu)造一個(gè)解總共要計(jì)算次選擇概率。所以構(gòu)造一個(gè)解所需的最壞時(shí)間復(fù)雜度為O(n2)。

當(dāng)螞蟻構(gòu)造完一個(gè)解或者所有螞蟻構(gòu)造完解時(shí)，信息素也要隨之更新。在文獻(xiàn)[22]中，所有螞蟻構(gòu)造完解后，信息素根據(jù)當(dāng)前代的最好解的適應(yīng)值進(jìn)行更新，如式（5）所示：

其中，ρ是信息素蒸發(fā)率，Δτi是第i個(gè)物品上的信息素的數(shù)量，其表達(dá)式如下：

其中，B表示常數(shù)，bs表示當(dāng)前代所取得的最優(yōu)解。bsi為1表示在解bs中物品i在背包里面。

1.3 DKP的修復(fù)與優(yōu)化算子

DKP一共有3種數(shù)學(xué)模型，由于第二種數(shù)學(xué)模型的編碼方式，使得第二種數(shù)學(xué)模型的存儲(chǔ)空間是第一種數(shù)學(xué)模型的1/3，同樣通過該模型編碼的解不會(huì)違反式（2）。在文獻(xiàn)[2，5-6，12-13]中都是使用DKP的第二種數(shù)學(xué)模型。文獻(xiàn)[2]首次使用群智能算法求解DKP，并提出了DKP的第二種數(shù)學(xué)模型和第三種數(shù)學(xué)模型。這篇文章使用了遺傳算法，針對(duì)DKP的兩種數(shù)學(xué)模型，提出了第一遺傳算法（FirEGA）和第二遺傳算法（SecEGA）來求解DKP，并分別采用修復(fù)優(yōu)化的方法提高解的質(zhì)量，其中FirEGA 取得更好的結(jié)果。文獻(xiàn)[5]使用DE 算法求解DKP，采用的方法是對(duì)選擇操作進(jìn)行優(yōu)化：如果兩個(gè)個(gè)體都是可行解，選擇適應(yīng)值高的個(gè)體進(jìn)入下一代；如果兩個(gè)個(gè)體，一個(gè)是可行解，一個(gè)是不可行解，選擇可行解進(jìn)入下一代；如果兩個(gè)個(gè)體都是不可行解，選擇違反約束程度較低的個(gè)體進(jìn)入下一代。對(duì)不可行解不進(jìn)行修復(fù)。但是該文章沒有使用DKP 的4 種測(cè)試用例進(jìn)行測(cè)試，而是隨機(jī)生成測(cè)試用例，所以沒有與其他的論文進(jìn)行比較。文獻(xiàn)[6]使用DE 算法求DKP 的第一種數(shù)學(xué)模型和第二種數(shù)學(xué)模型，對(duì)于第一種數(shù)學(xué)模型，分別提出混合編碼的二進(jìn)制DE（Binary DE with Hybrid encoding，HBDE）算法和第一離散DE（First Discrete DE，F(xiàn)DDE）；對(duì)于第二種數(shù)學(xué)模型，提出第二離散DE（Second Discrete DE，SDDE）算法，并根據(jù)編碼方式的不同采取修復(fù)優(yōu)化的方法提高解的質(zhì)量，3個(gè)算法的性能比較，HBDE 取得更好的結(jié)果。文獻(xiàn)[12]用GTOA分別求解了3種KP：Set Union KP（SUKP）、DKP和Bounded KP（BKP），這里只關(guān)注DKP。該文章將可行解作為群直積的一個(gè)元素，利用群直積的乘法和逆運(yùn)算來實(shí)現(xiàn)進(jìn)化過程，并對(duì)不可行解進(jìn)行修復(fù)和優(yōu)化。文獻(xiàn)[13]使用BFO 求解DKP，對(duì)DKP 的兩種數(shù)學(xué)模型分別采用二進(jìn)制編碼和四進(jìn)制編碼。為了提高算法的搜索速度，對(duì)初始種群進(jìn)行貪心優(yōu)化，在兩種編碼方式下，均對(duì)不可行解進(jìn)行了修復(fù)和優(yōu)化。

對(duì)于DKP 的第二種數(shù)學(xué)模型，在處理違反約束的解時(shí)大多用基于價(jià)值密度的貪心修復(fù)優(yōu)化策略[2，6，12-13]，如算法1和算法2所示。這里的價(jià)值密度以vi,j/wi,j表示，將物品根據(jù)價(jià)值密度降序排序存放入列表h，其中(hk/3,hk%3+1)表示第hk/3 組的第hk%3+1 個(gè)物品。在修復(fù)算子中，從尾部開始遍歷列表h，如果物品在背包里面，則將其取出，直至背包內(nèi)的物品重量和沒有超出背包容量。在優(yōu)化算子中，從頭開始遍歷列表h，在不違反DKP 約束的情況下，將不在背包的物品放入背包，以得到更優(yōu)質(zhì)的解。但是這種單一的選取方式在背包裝入部分物品之后，會(huì)使得那些具有較大價(jià)值且重量較大的物品無(wú)法進(jìn)入背包，從而導(dǎo)致算法在得到一個(gè)局部較好解后更新困難，而導(dǎo)致算法過早收斂。

2 改進(jìn)蟻群優(yōu)化算法求解折扣{0-1}背包問題

2.1 信息素表示和選擇概率

螞蟻在構(gòu)造解時(shí)以式（4）競(jìng)爭(zhēng)選擇每一個(gè)物品放入背包的概率，最壞的時(shí)間復(fù)雜度為O(n2)。但對(duì)于DKP，每個(gè)物品是否放入背包與其他組的物品沒有直接聯(lián)系反之僅與組內(nèi)其他物品有直接競(jìng)爭(zhēng)關(guān)系。根據(jù)這一特性，適當(dāng)改造原經(jīng)典算法中的概率選擇公式，可以在不降低算法性能的前提下將螞蟻構(gòu)造解的時(shí)間復(fù)雜度降為O(n)。

DKP要求每一組至多只有一個(gè)物品放入背包，根據(jù)式（2），每一組物品i的值xi有4種可能：0、1、2和3。每一組獨(dú)立選擇該組的物品放入背包，不與其他組競(jìng)爭(zhēng)。因此，可以用一個(gè)n×4 的矩陣τ來表示信息素，其中τi,0、τi,1、τi,2和τi，3分別表示第i組物品中，不選擇、選擇第一個(gè)物品、選擇第二個(gè)物品和選擇第三個(gè)物品的偏好，利用該信息素矩陣，每組物品的選擇概率計(jì)算如下：

其中，pi存放第i組的4 種選擇的概率，根據(jù)概率以輪盤賭選擇來確定第i組物品的選取，α是調(diào)節(jié)信息素相對(duì)強(qiáng)度的參數(shù)。

式（7）所描述的選擇概率計(jì)算實(shí)現(xiàn)了組內(nèi)選擇，即每個(gè)物品只和組內(nèi)的其他物品競(jìng)爭(zhēng)，并不和其他組的物品直接競(jìng)爭(zhēng)。通過該公式，每只螞蟻在構(gòu)造解時(shí)，只需計(jì)算選擇概率4n次，大大減少了算法的運(yùn)行時(shí)間。在式（7）中，沒有使用啟發(fā)式信息：一方面，對(duì)不選擇物品的情況很難采用直觀的構(gòu)造方法定義合適的啟發(fā)式信息；另一方面，不使用啟發(fā)式信息在保證MACO算法的性能的前提下，減少了算法參數(shù)的數(shù)量，從而有效地簡(jiǎn)化了算法的實(shí)現(xiàn)。啟發(fā)式信息的作用主要是在初期可以更好地引導(dǎo)螞蟻構(gòu)造出優(yōu)質(zhì)解，提高算法的收斂速度，在MACO算法中，因?yàn)樾迯?fù)與優(yōu)化算子可以保證MACO 算法的收斂速度，所以可以不使用啟發(fā)式信息，而且，如果同時(shí)使用啟發(fā)式信息和修復(fù)與優(yōu)化算子，可能使算法快速陷入局部最小，影響算法的全局尋優(yōu)能力。

2.2 信息素更新

為了更好地平衡算法的多樣性和集中性，使用每只螞蟻至當(dāng)前迭代為止所取得的最好的解pb來對(duì)信息素值進(jìn)行更新。在所有螞蟻構(gòu)造完解之后，根據(jù)式（8）和式（9）更新信息素矩陣。采用最大-最小螞蟻算法[27]的思想，信息素設(shè)定范圍為[MINPHE，MAXPHE]，MINPHE表示信息素最小邊界值，MAXPHE表示信息素最大邊界值，當(dāng)信息素值超出邊界時(shí)以邊界值替換，防止信息素值過大或過小而影響螞蟻對(duì)最優(yōu)值的探索。

其中，Δτi是所有螞蟻在j狀態(tài)下放置在i項(xiàng)上的信息素的數(shù)量，計(jì)算公式如下：

其中，K表示種群中螞蟻的數(shù)量；pbk表示第k只螞蟻到當(dāng)前迭代為止所取得的最好的解；gb表示整個(gè)種群至當(dāng)前迭代為止所取得的最好的解；函數(shù)iif()基于對(duì)第一個(gè)參數(shù)的求值返回第二個(gè)或第三個(gè)參數(shù)。

2.3 解的構(gòu)造

算法3 是螞蟻構(gòu)造解的偽代碼。它首先創(chuàng)建一個(gè)空解s，s包含3個(gè)屬性s.x、s.v和s.w.其中s.x是一個(gè)n維的數(shù)組，每個(gè)元素s.x[i]表示所選擇的第i組物品，0表示不選取該組的物品，s.w和s.v分別表示放入背包中的物品重量之和和價(jià)值之和。

將MACO 與其他群智能算法，如標(biāo)準(zhǔn)ACO[22]和FirEGA[2]、GPSO[14]、GTOA[12]、HBDE[6]和SG[4]，比較這些算法生成新的種群的時(shí)間復(fù)雜度，K表示種群中的個(gè)體數(shù)，如表1 所示。因?yàn)镵與問題規(guī)模無(wú)關(guān)，所以MACO 算法的時(shí)間復(fù)雜度優(yōu)于標(biāo)準(zhǔn)ACO，而與其他智能優(yōu)化算法相當(dāng)。

表1 MACO算法與其他算法時(shí)間復(fù)雜度比較

2.4 解的修復(fù)和混合優(yōu)化

DKP是約束優(yōu)化問題，由智能優(yōu)化算法生成的解可能是不可行的，現(xiàn)有研究均使用修復(fù)優(yōu)化算子對(duì)解進(jìn)行進(jìn)一步處理，通過修復(fù)優(yōu)化操作不僅保證了解的可行性，也能提高算法的尋優(yōu)能力。在現(xiàn)有研究中，對(duì)解進(jìn)行修復(fù)優(yōu)化時(shí)，大多都是基于價(jià)值密度來決定物品的選取順序。在文獻(xiàn)[28]中對(duì){0-1}KP 的研究發(fā)現(xiàn)，混合使用價(jià)值密度和價(jià)值來決定物品的選取順序有助于提高算法的尋優(yōu)能力。受此啟發(fā)，本文在對(duì)解進(jìn)行優(yōu)化時(shí)，以一定概率使用價(jià)值作為物品選取順序的依據(jù)，以提高算法的尋優(yōu)能力。如算法4所示，算法的3到12行根據(jù)價(jià)值密度從高到低的順序選擇螞蟻選中的物品，在計(jì)算解的重量和價(jià)值時(shí)保證解的合法性，在對(duì)解進(jìn)行優(yōu)化時(shí)，算法13行到17行根據(jù)概率pd選擇是根據(jù)價(jià)值密度還是價(jià)值將降序排序的物品放入列表h，調(diào)用算法2，從頭開始遍歷列表h，在不違反約束的情況下將物品放入背包，使解的質(zhì)量得到提高。

2.5 MACO算法的偽代碼

算法5 是MACO 算法的偽代碼，其中G為種群的迭代次數(shù)，K為種群中的螞蟻個(gè)數(shù)，INIPHE是初始信息素。在5到14行，首先使用算法3構(gòu)造一個(gè)新解s，再用算法4對(duì)s進(jìn)行修復(fù)優(yōu)化，在整個(gè)種群都構(gòu)造完解后，更新信息素。因?yàn)樗惴? 的時(shí)間復(fù)雜度為O(8×n)，算法4的時(shí)間復(fù)雜度為O(6×n)，所以5到14行的時(shí)間復(fù)雜度為O(14×K×n)；第15行的時(shí)間復(fù)雜度為O(4×K×n)。從5 到16 行的時(shí)間復(fù)雜度為O(18×K×n)。整個(gè)種群要迭代G，所以完整的MACO 算法的時(shí)間復(fù)雜度為O(G×18×K×n)。

3 實(shí)驗(yàn)與結(jié)果

DKP有4種測(cè)試用例，根據(jù)每一組的第三個(gè)物品與前兩個(gè)物品之間的關(guān)系，分為不相關(guān)測(cè)試用例（Uncorrelated test instances，UDKP）、弱相關(guān)測(cè)試用例（Weakly correlated test instances，WDKP）、強(qiáng)相關(guān)測(cè)試用例（Strongly correlated test instances，SDKP）和逆強(qiáng)相關(guān)測(cè)試用例（Inversely strongly correlated test instances，IDKP），每種測(cè)試用例中根據(jù)問題規(guī)模的大小，一共有10個(gè)測(cè)試用例，在接下來的實(shí)驗(yàn)中將以這4種測(cè)試用例來進(jìn)行實(shí)驗(yàn)。

在MACO算法中，主要的參數(shù)符號(hào)及其取值如表1所示。為了公平地與其他算法進(jìn)行比較，MACO算法與其他算法使用相同的評(píng)價(jià)次數(shù)，以文獻(xiàn)[6]為例，該文獻(xiàn)設(shè)置的種群大小為50，種群迭代次數(shù)為3n，所以總的評(píng)價(jià)次數(shù)為150n，MACO 算法種群大小與種群迭代次數(shù)跟文獻(xiàn)[6]相同。參數(shù)MINPHE和MAXPHE的比對(duì)MACO 算法多樣性與集中性的平衡有重要影響，而它們具體的數(shù)值與種群大小、信息素分泌和信息素蒸發(fā)率相關(guān)，根據(jù)實(shí)驗(yàn)，將MINPHE和MAXPHE的比設(shè)置為0.001，因?yàn)榉N群大小為50，根據(jù)式（9），每次迭代最多分泌信息素50，為保證信息素不超過MAXPHE，將MAXPHE設(shè)置為1 000，而ρ設(shè)置為0.05，同時(shí)，為了保證在算法開始階段有足夠的多樣性，將信息素的初始值設(shè)為5 000，這樣，因?yàn)楫?dāng)信息素大于1 000時(shí)，蒸發(fā)的信息素總是多于分泌的信息素，所以，除了開始階段外，經(jīng)式（8）修改得到的信息素均不超過1 000，如果經(jīng)式（8）得到的信息素小于1，MACO 算法將它設(shè)置為1。除此之外，另外兩個(gè)參數(shù)α（信息素調(diào)節(jié)因子）和pd（混合優(yōu)化策略中選取價(jià)值密度的概率）通過組合實(shí)驗(yàn)來獲得其最優(yōu)設(shè)置。實(shí)驗(yàn)中α的取值范圍是{0.7，0.8，0.9，1，1.1，1.2}，pd的取值范圍是{0，0.2，0.4，0.6，0.8，1}。為了增加算法的通用性，不采用為每一種測(cè)試用例選取最好的參數(shù)組合的方法，而是選擇一組總體性能最好的參數(shù)。根據(jù)實(shí)驗(yàn)結(jié)果，當(dāng)α設(shè)置為1，pd設(shè)置為0.6 時(shí)，MACO算法在這4種測(cè)試用例上的總體性能最好。

表2 MACO算法的參數(shù)設(shè)置

3.1 參數(shù)α的影響

為了分析α對(duì)算法收斂性的影響，使用3個(gè)不同的α值來比較MACO算法的收斂性能，每種測(cè)試用例中選取第五個(gè)測(cè)試用例進(jìn)行測(cè)試，圖1 到圖4 是最優(yōu)解的收斂過程。以圖3為例，當(dāng)α的取值為1時(shí)，MACO算法取得最好的結(jié)果。從算法收斂性方面分析，從這些圖中可以看出，參數(shù)α對(duì)算法的收斂速度有明顯的影響。如果α太大，算法收斂速度太快，則容易導(dǎo)致早熟收斂；反之，如果α太小，收斂速度太慢，不利于種群對(duì)最優(yōu)解的探索。而且從圖中可以看出，α的取值太小時(shí)所得出的結(jié)果也很不理想。由此可見，一個(gè)合適的α值對(duì)算法的性能至關(guān)重要。

圖1 在UDKP5上MACO算法收斂性與參數(shù)α 的關(guān)系

圖2 在WDKP5上MACO算法收斂性與參數(shù)α 的關(guān)系

圖3 在SDKP5上MACO算法收斂性與參數(shù)α 的關(guān)系

圖4 在IDKP5上MACO算法收斂性與參數(shù)α 的關(guān)系

3.2 參數(shù)pd 的影響

為了分析在優(yōu)化算子中加入價(jià)值作為物品選取的依據(jù)是否能提高算法的性能，使用每種測(cè)試用例的第五個(gè)測(cè)試用例，以不同的pd值對(duì)MACO算法的性能進(jìn)行測(cè)試。pd為0表示在混合優(yōu)化算子中只用價(jià)值作為物品選取的依據(jù)，為1則表示只以價(jià)值密度作為物品選取的依據(jù)。由于問題的規(guī)模較大，相對(duì)應(yīng)的解的值也較大，為了更直觀地說明所求得的解與已知最優(yōu)解之間的差距，這里使用解f與最優(yōu)解f*之間的百分誤差（Percentage Error，PE）作為評(píng)價(jià)解的標(biāo)準(zhǔn)，PE 定義為PE=(f*-f)/f*×100。在每個(gè)測(cè)試用例上運(yùn)行MACO算法10 次，圖5 到圖8 是在4 個(gè)測(cè)試用例上所獲得結(jié)果的直方圖。從這些圖可以看出，盡管在各個(gè)測(cè)試用例上最佳的pd值是不同的，但相較于在優(yōu)化算子只以價(jià)值密度為依據(jù)，只要選取恰當(dāng)?shù)膒d值，均可以提高解的質(zhì)量。

圖5 在UDKP05上MACO算法的性能與參數(shù)pd 的關(guān)系

圖6 在WDKP05上MACO算法的性能與參數(shù)pd 的關(guān)系

圖7 在SDKP05上MACO算法的性能與參數(shù)pd 的關(guān)系

圖8 在IDKP05上MACO算法的性能與參數(shù)pd 的關(guān)系

3.3 MACO算法尋優(yōu)行為分析

為觀察和分析MACO 算法的尋優(yōu)行為，以每個(gè)測(cè)試集的第一個(gè)測(cè)試用例為例，分別比較MACO 與ACO的收斂過程。這里的ACO算法使用1.2節(jié)的式（4）、（5）和式（6）來構(gòu)造解以及更新信息素，并用算法4 來對(duì)解進(jìn)行修復(fù)優(yōu)化。由于MACO 與ACO 的編碼方式的不同，在算法4的實(shí)現(xiàn)上存在細(xì)微的差別。ACO的參數(shù)設(shè)置為：pd=0.2,α=0.9,β=1，其余參數(shù)設(shè)置與MACO相同。圖9到圖12是MACO算法與ACO算法的最優(yōu)解的收斂過程。從圖中可以看出，由于ACO 算法同時(shí)使用了啟發(fā)式信息和修復(fù)優(yōu)化算子，雖然能一開始很快地找到優(yōu)解，但在之后的迭代過程中就會(huì)陷入局部最優(yōu)，進(jìn)入停滯狀態(tài)。而MACO則能在迭代過程中始終保持尋優(yōu)狀態(tài)。

圖9 在UDKP01上MACO算法與ACO算法的收斂情況

圖10 在WDKP01上MACO算法與ACO算法的收斂情況

圖11 在SDKP01上MACO算法與ACO算法的收斂情況

圖12 在IDKP01上MACO算法與ACO算法的收斂情況

3.4 與其他算法的比較

為了觀察MACO 算法的競(jìng)爭(zhēng)性，將MACO 算法與FirEGA[2]、GPSO[14]、GTOA[12]、HBDE[6]和SG[4]進(jìn)行比較，其實(shí)驗(yàn)結(jié)果如表3到表6所示。表的Ins、Num和Opt列分別表示DKP 的測(cè)試實(shí)例、問題規(guī)模以及這些測(cè)試實(shí)例的最佳值。在Result 列中，best、mean 和worst 分別表示各個(gè)測(cè)試用例獨(dú)立運(yùn)行25 次所得到的最好值、平均值及最差值。在這些表格中加粗的數(shù)字表示在這6 個(gè)算法比較中取得的最優(yōu)值。

如表3 和表4 所示，在UDKP 測(cè)試集和WDKP 測(cè)試集上，MACO算法在所有的測(cè)試用例上均獲得最優(yōu)的最好值、平均值和最差值；如表5所示，在SDKP測(cè)試集上，MACO算法分別在10個(gè)、9個(gè)和9個(gè)測(cè)試用例上獲得最優(yōu)的最好值、平均值和最差值；如表6 所示，在IDKP 測(cè)試集上，MACO算法分別在9個(gè)、8個(gè)和5個(gè)測(cè)試用例上獲得最優(yōu)的最好值、平均值和最差值。為了判斷MACO算法與其他算法在性能上是否存在顯著差異，使用顯著水平為0.05的Wilcoxon秩和檢驗(yàn)比較MACO算法和其他算法在所有測(cè)試用例上的平均值，在UDKP 測(cè)試集上，計(jì)算得到的p值分別為0.005、0.005、0.005、0.005和0.005；在WDKP測(cè)試集上，計(jì)算得到的p值分別為0.005、0.005、0.005、0.007 和0.005；在SDKP 測(cè)試集上，計(jì)算得到的p值分別為0.005、0.005、0.005、0.005 和0.005；在IDKP 測(cè)試集上，計(jì)算得到的p值分別為0.005、0.032、0.005、0.007 和0.028。它們均小于0.05，表明MACO 算法顯著優(yōu)于其他5個(gè)算法。

表3 在UDKP上的性能比較

表4 在WDKP上的性能比較

表5 在SDKP上的性能比較

表6 在IDKP上的性能比較

MACO是構(gòu)造型算法，相較于其他改進(jìn)型群智能算法，種群能保持足夠的多樣性，更有利于算法在整個(gè)搜索空間中找尋優(yōu)質(zhì)區(qū)域?？梢詫⑿迯?fù)和優(yōu)化算子看成局部搜索機(jī)制，它有效保證了MACO 算法的局部求精能力。MACO 算法充分利用了構(gòu)造型算法的全局搜索能力和局部搜索算法的局部求精能力，表現(xiàn)出良好的全局尋優(yōu)能力。

4 結(jié)論

本文提出了一個(gè)求解DKP 的MACO 算法，根據(jù)DKP組內(nèi)物品競(jìng)爭(zhēng)的特點(diǎn)，采用組內(nèi)選擇策略以降低算法構(gòu)造解的時(shí)間復(fù)雜性，棄用啟發(fā)式信息以減少M(fèi)ACO算法參數(shù)，從而簡(jiǎn)化算法的參數(shù)調(diào)節(jié)；MACO 算法使用個(gè)體歷史最優(yōu)解來修改信息素，更好地平衡了算法的多樣性和集中性。同時(shí)，在貪婪優(yōu)化時(shí)中引入混合價(jià)值引導(dǎo)操作以提高算法的尋優(yōu)能力。仿真結(jié)果表明MACO算法的性能優(yōu)于現(xiàn)有其他同類算法。本文提出的混合價(jià)值密度引導(dǎo)和價(jià)值引導(dǎo)的貪婪優(yōu)化是一個(gè)通用的策略，在今后的研究中計(jì)劃在改進(jìn)的MACO 算法及其他同類智能優(yōu)化算法中，應(yīng)用該策略去高效地求解更大規(guī)模的DKP，并推廣至其他相似問題的求解。