一種具有單連續(xù)變量的背包問題的新V型轉(zhuǎn)換函數(shù)二進(jìn)制粒子群算法求解方法

王澤昆

(河北地質(zhì)大學(xué) 信息工程學(xué)院，河北 石家莊 050031)

0 引言

粒子群優(yōu)化算法（PSO）[1]是1995年由Kennedy和Eberhart提出的一種著名群智能算法。該算法具有參數(shù)少，易實現(xiàn)和結(jié)構(gòu)簡單等優(yōu)點，備受廣大專家學(xué)者的關(guān)注。已經(jīng)在神經(jīng)網(wǎng)絡(luò)[2]、約束優(yōu)化[3]、調(diào)度問題[4]等眾多問題中得到了成功應(yīng)用。為了使 PSO算法能夠求解離散組合優(yōu)化問題，Kennedy和Eberhart[5]于 1997年提出了二進(jìn)制粒子群優(yōu)化算法（BPSO）。在BPSO中，利用Sigmoid轉(zhuǎn)換函數(shù)將由實向量表示的粒子速度轉(zhuǎn)換為由0-1向量表示的粒子位置，從而基于粒子速度實現(xiàn)對粒子位置的更新，可以說 Sigmoid轉(zhuǎn)換函數(shù)是BPSO的設(shè)計與實現(xiàn)的關(guān)鍵所在[6]。

具有單連續(xù)變量的背包問題（KPC）[7]是1999年由Marchand和Wolsey提出的一個帶有連續(xù)變量S的組合優(yōu)化問題。目前，國內(nèi)外學(xué)者對KPC的求解算法進(jìn)行了研究，Lin等[8]首先將 KPC轉(zhuǎn)化為一個偽背包問題和標(biāo)準(zhǔn) 0-1背包問題的組合形式，然后分別利用動態(tài)規(guī)劃算法和分支定界法進(jìn)行求解。He等[9]首先利用放縮法將 KPC中的連續(xù)變量離散化，將它轉(zhuǎn)化為帶有實函數(shù)的變載重背包問題的一個特例，然后基于動態(tài)規(guī)劃法提出了一個精確算法DP-KPC。Zhao和Li[10]將KPC分解為兩個具有標(biāo)準(zhǔn) 0-1背包問題形式的子問題進(jìn)行求解，提出了一個時間復(fù)雜度為 O(n2)的 2-近似算法。最近，He等[11]提出了基于演化算法求解 KPC的新思路，首先基于降維法建立了 KPC的一個適于串行計算的數(shù)學(xué)模型和一個適用于并行求解的數(shù)學(xué)模型，然后基于混合編碼二進(jìn)制差分演化算法（HBDE）[12]給出了求解KPC的兩個高效離散演化算法，具有混合編碼的單種群二進(jìn)制差分演化算法（S-HBDE）和具有混合編碼的雙種群二進(jìn)制差分演化算法（B-HBDE）。顯然，求解KPC的已有算法分為兩類：精確算法和非精確算法。文獻(xiàn)[8-9]中的精確算法具有偽多項式時間復(fù)雜度，不適用于求解大規(guī)模KPC實例。文獻(xiàn)[10-11]中非精確算法特別是演化算法不僅求解 KPC的速度快，而且計算結(jié)果完全能夠滿足實際應(yīng)用要求，因此探討利用演化算法求解KPC的高效方法是一個值得研究與探討的問題。

本文在已有的轉(zhuǎn)換函數(shù)的基礎(chǔ)上，通過進(jìn)一步的變形，提出了一個新穎S型轉(zhuǎn)換函數(shù)，并基于這一轉(zhuǎn)換函數(shù)給出一個新穎的二進(jìn)制粒子群優(yōu)化算法（NVBPSO）。為了驗證 NVBPSO算法的性能，通過與文獻(xiàn)[11]中的算法S-HBDE、B-HBDE和 BPSO求解4類 KPC實例的計算結(jié)果進(jìn)行比較，根據(jù)比較結(jié)果指出NVBPSO在求解KPC時比其他算法所具有更大的優(yōu)越性能。

1 KPC 的定義和數(shù)學(xué)模型

KPC的定義為：給定 n個物品的集合 N={1,2,…,n}和一個基本載重為C的背包。其中物品j∈N具有價值pj和重量wj，背包的可變載重S∈[l,u]。pj，wj和 C為正有理數(shù)，S，l和 u為有理數(shù)，且l<00作為懲罰系數(shù)。如果可變載重S>0，即背包容量加S，則總價值將減去cS。反之，如果可變載重S<0，即背包容量減|S|，則總價值加|cS|。KPC目標(biāo)是確定S的取值，使得裝入物品的重量之和在不超過背包載重C+S的前提下價值之和減去cS最大。

根據(jù)上述定義，KPC的基本數(shù)學(xué)模型KPCM1[11]描述如下：

其中，Y=[y1,y2,…,yn]∈{0,1}n，yj=1(j=1,2,…,n)表示物品 j被裝入了背包中。為了便于利用二進(jìn)制演化算法求解KPC問題，文獻(xiàn)[11]基于降維法建立了KPC的一個新數(shù)學(xué)模型KPCM2，該模型通過消去連續(xù)變量S使解空間的維數(shù)由n+1降低為n。數(shù)學(xué)模型KPCM2的描述如下：

2 BPSO和NVPSO

2.1 BPSO

PSO算法受鳥群飛行覓食的行為而產(chǎn)生靈感，協(xié)作來尋找最優(yōu)解的進(jìn)化計算技術(shù)。PSO主要包含粒子的速度更新（如式（7））和位置更新（如式（8））兩個重要操作。

其中，r3為0～1之間的隨機(jī)數(shù)。

2.2 NVBPSO

近年來，轉(zhuǎn)換函數(shù)成為二進(jìn)制演化算法研究的熱點問題。目前，已有的轉(zhuǎn)換函數(shù)可以分為兩類：S型傳遞函數(shù)和 V型傳遞函數(shù)[13-14]。在表 1中分別給出了4個S型轉(zhuǎn)換函數(shù)（記為S1-S4）和4個V型轉(zhuǎn)換函數(shù)（記為V1-V4）。

表1 S型轉(zhuǎn)換函數(shù)和V型轉(zhuǎn)換函數(shù)Tab.1 S-shape and V-shape transfer functions

本文為了兼具S型和V型轉(zhuǎn)換函數(shù)的特性，基于S2轉(zhuǎn)換函數(shù)提出了一個新V型轉(zhuǎn)換函數(shù)NV：

3 利用NVBPSO求解KPC

3.1 NVBPSO

Lee等[15]改進(jìn)了BPSO，他們在保持PSO的速度更新公式和位置更新公式的基礎(chǔ)上，利用位置值的概率對粒子的位置進(jìn)行第二次更新操作。基于這一方法，并結(jié)合所給出的新V型轉(zhuǎn)換函數(shù)NV，提出了一個新的二進(jìn)制粒子群優(yōu)化算法NVBPSO。

在NBPSO的進(jìn)化過程中，首先利用式（7）更新粒子的速度，接著利用式（8）對粒子位置進(jìn)行第一次更新。然后，利用第一次位置更新后的位置值根據(jù)式（12）來計算粒子位置向量變化的概率值。

最后，根據(jù)求得的粒子位置向量變化的概率值，利用式（13）對粒子進(jìn)行第二次位置更新。

3.2 利用NVBPSO求解KPC

在利用NVBPSO求解KPC問題時，不可行解的產(chǎn)生是不可避免的。為了解決這一問題，文獻(xiàn)[11]給出了一種時間復(fù)雜度為O(n2)的修復(fù)與優(yōu)化算法M2-GROA來處理KPC的不可行解。由于M2-GROA在文獻(xiàn)[11]中的成功的應(yīng)用，本文利用M2-GROA處理NBPSO在求解KPC時所產(chǎn)生的不可行解。

設(shè)Yb∈[0,1]n表示求得KPC實例的當(dāng)前最優(yōu)解。f(Yb)表示Yb所對應(yīng)的適應(yīng)度值。基于NBPSO求解KPC的算法的步驟如下。

基于NBPSO求解KPC的步驟：

Step.1將n個物品項利用Quicksort[16]按照物品的價值密度比降序排序，并將排序后的物品項的下標(biāo)依次存入一維數(shù)組H[1,2,…,n]中；

Step.2初始化參數(shù)。設(shè)置最大迭代次數(shù)MIter，種群規(guī)模N，慣性參數(shù)W，加速系數(shù)c1，c2和vmax；令 t←0。

Step.3隨機(jī)初始化種群。使粒子位置的每一分量隨機(jī)取 0或 1，粒子速度的每一分量在[-vmax,vmax]內(nèi)隨機(jī)取值。

Step.4 利用M2-GROA處理初始化時產(chǎn)生的不可行解，并計算粒子的適應(yīng)度值；

Step.5對于所有粒子，分別利用式（7）和式（8）更新它的速度和位置；

Step.6 利用式（12）計算改變粒子位置向量的概率；

Step.7利用式（13）中二次更新粒子的位置向量；

Step.8利用 M2-GROA處理粒子更新后所產(chǎn)生的不可行解，并計算它的適應(yīng)度值。

Step.9判斷是否滿足終止條件。若不滿足，則t←t+1，轉(zhuǎn)Step.5；若滿足，則輸出(Yb,f(Yb))。

在上述步驟中，Step.1利用快速排序QuickSort[16]實現(xiàn)，其時間復(fù)雜度為 O(nlogn)；Step.3的時間復(fù)雜度為O(N×n)；Step.4的時間復(fù)雜度為O(N×n2)；Step.4～9的時間復(fù)雜度為 O(MIter×N×n2)；因此NBPSO求解 KPC的時間復(fù)雜度為 O(nlogn)+O(N×n)+O(N×n2)+O(MIter×N×n2)，其中 MIter 和N是關(guān)于n的多項式，故為多項式時間復(fù)雜度。

4 計算結(jié)果與分析

所有計算均在配置為Inter(R)Corei7-3770 CPU@3.40 GHz和8 GB RAM的微型計算機(jī)上進(jìn)行。利用C語言進(jìn)行編程，編譯環(huán)境為Code:Blocks。使用Python在編譯環(huán)境JetBrains PyCharm下繪制折線圖。

4.1 四類KPC實例

四類不同的KPC實例為ukpc類、ikpc類、wkpc類和 skpc類，編號為 ukpc100-ukpc1000，ikpc100-ikpc1000，wkpc100-wkpc1000，skpc100-skpc1000。所有KPC實例的具體數(shù)據(jù)都來自URL https://www.researchgate.net/project/KPC-problemand-Its-algorithms

4.2 計算結(jié)果比較與分析

在 NVBPSO算法中，設(shè)置種群規(guī)模均為N=20，最大迭代次數(shù)均為MIter=6n，n為KPC實例中物品的個數(shù)；此外，慣性參數(shù) W=1.5，加速系數(shù)c1=c2=1.8，粒子速度向量中各維分量的取值范圍為[-2,2]。S-HBDE、B-HBDE和BPSO的種群規(guī)模均為N=20，三個算法其他參數(shù)與文獻(xiàn)[11]中相同。

記OPT是利用文獻(xiàn)[9]中方法求得KPC實例的最優(yōu)值。Best為算法獨立計算實例50次所得計算結(jié)果中的最好值，Mean和StD分別為50次所得計算結(jié)果的平均值和標(biāo)準(zhǔn)差。AR=|OPT-Mean|表示算法求解 KPC實例的計算結(jié)果的平均值與最優(yōu)值之間的絕對誤差。在表2～表5中給出了各算法求解四類 KPC實例的計算結(jié)果，并根據(jù)表2～表5中的計算結(jié)果，利用它們比較NVBPSO、S-HBDE、B-HBDE和BPSO算法計算結(jié)果的優(yōu)劣。

表2 NVBPSO、S-HBDE、B_HBDE和BPSO求解ukpc類實例的計算結(jié)果Tab.2 NVBPSO,S-HBDE,B-HBDE and BPSO calculation results of ukpc class instances

表3 NVBPSO、S-HBDE、B_HBDE和BPSO求解ikpc類實例的計算結(jié)果Tab.3 NVBPSO,S-HBDE,B-HBDE and BPSO calculation results of ikpc class instances

表4 NVBPSO、S-HBDE、B_HBDE和BPSO求解wkpc類實例的計算結(jié)果Tab.4 NVBPSO,S-HBDE,B-HBDE and BPSO calculation results of wkpc class instances

表5 NVBPSO、S-HBDE、B_HBDE和BPSO求解skpc類實例的計算結(jié)果Tab.5 NVBPSO,S-HBDE,B-HBDE and BPSO calculation results of skpc class instances

由表2可以看出，對于ukpc類實例NVBPSO在求解ukpc100、ukpc500、ukpc700-ukpc1000實例時，雖然部分Best值未達(dá)到OPT值，但是Mean值相對于其他三個算法均有較大的提高。從表 3可以看出，對于 ikpc類實例 NVBPSO在求解ikpc300-ikpc1000實例時，在大部分 Best值達(dá)到OPT值的基礎(chǔ)上，取得的Mean值均優(yōu)于其它三個算法。從表4可以看出，NVBPSO在求解wkpc類實例時取得的 Mean值其它三個算法。從表 5可以看出，NVBPSO在求解 skpc類實例，除skpc300實例外，其他實例取得的 Best值均達(dá)到OPT值且大部分實例的Mean值均優(yōu)于其它三個算法。由于在評價演化算法時，指標(biāo) Mean比指標(biāo)Best更能說明問題演化算法的性能優(yōu)劣，因此NVBPSO相比于S-HBDE、B-HBDE和BPSO求解KPC問題的性能更佳。

5 結(jié)論

本文介紹了常見的8個S型和V型轉(zhuǎn)換函數(shù)，并受這兩類轉(zhuǎn)換函數(shù)的啟發(fā)，提出了一種新V型轉(zhuǎn)換函數(shù)NV。在此基礎(chǔ)上，給出了一種基于新V型轉(zhuǎn)換函數(shù)的二進(jìn)制粒子群優(yōu)化化算（NVBPSO）。為了驗證NVBPSO的求解性能，本文通過求解4類大規(guī)模KPC實例，驗證了算法的高效性和有效性，并通過與已有算法的計算結(jié)果比較表明：NVBPSO比S-HBDE、B-HBDE和BPSO的求解結(jié)果優(yōu)，算法的魯棒性更佳，非常適用于求解大規(guī)模KPC實例。

通過實驗證明，本文所提出的新V型轉(zhuǎn)換函數(shù)是可行的，有效的。同時為連續(xù)演化算法離散化提供了一種新V型函數(shù)。在未來研究中，我們將探索新V型轉(zhuǎn)換函數(shù)對其他二進(jìn)制算法的影響，如灰狼算法（GWO）[17]和鴿群優(yōu)化算法（PIO）[18]等。此外，我們將繼續(xù)嘗試?yán)肗VBPSO求解其他組合優(yōu)化問題，例如設(shè)施選址問題[19]，集合覆蓋問題[20]等。