一種具有單連續變量的背包問題的新V型轉換函數二進制粒子群算法求解方法

王澤昆

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

0 引言

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

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

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

1 KPC 的定義和數學模型

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

根據上述定義，KPC的基本數學模型KPCM1[11]描述如下：

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

2 BPSO和NVPSO

2.1 BPSO

PSO算法受鳥群飛行覓食的行為而產生靈感，協作來尋找最優解的進化計算技術。PSO主要包含粒子的速度更新（如式（7））和位置更新（如式（8））兩個重要操作。

其中，r3為0～1之間的隨機數。

2.2 NVBPSO

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

表1 S型轉換函數和V型轉換函數Tab.1 S-shape and V-shape transfer functions

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

3 利用NVBPSO求解KPC

3.1 NVBPSO

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

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

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

3.2 利用NVBPSO求解KPC

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

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

基于NBPSO求解KPC的步驟：

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

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

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

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

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

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

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

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

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

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

4 計算結果與分析

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

4.1 四類KPC實例

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

4.2 計算結果比較與分析

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

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

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

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

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

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

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

5 結論

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

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