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

王澤昆

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

0 引言

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

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

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

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

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

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

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

2 BPSO和NVPSO

2.1 BPSO

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

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

2.2 NVBPSO

近年來(lái)，轉(zhuǎn)換函數(shù)成為二進(jìn)制演化算法研究的熱點(diǎn)問(wèn)題。目前，已有的轉(zhuǎn)換函數(shù)可以分為兩類(lèi)：S型傳遞函數(shù)和 V型傳遞函數(shù)[13-14]。在表 1中分別給出了4個(gè)S型轉(zhuǎn)換函數(shù)（記為S1-S4）和4個(gè)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ù)提出了一個(gè)新V型轉(zhuǎn)換函數(shù)NV：

3 利用NVBPSO求解KPC

3.1 NVBPSO

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

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

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

3.2 利用NVBPSO求解KPC

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

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

基于NBPSO求解KPC的步驟：

Step.1將n個(gè)物品項(xiàng)利用Quicksort[16]按照物品的價(jià)值密度比降序排序，并將排序后的物品項(xiàng)的下標(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處理初始化時(shí)產(chǎn)生的不可行解，并計(jì)算粒子的適應(yīng)度值；

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

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

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

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

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

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

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

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

4.1 四類(lèi)KPC實(shí)例

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

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