基于新穎S型轉換函數的二進制粒子群優化算法求解具有單連續變量的背包問題

王澤昆，賀毅朝，李煥哲，張發展

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

（*通信作者電子郵箱heyichao@hgu.edu.cn）

0 引言

粒子群優化（Particle Swarm Optimization，PSO）［1］是1995年由Kennedy和Eberhart 提出的一種著名演化算法，具有結構簡單、易于實現和計算成本低等優點，受到眾多學者的關注和研究，已經在神經網絡［2］、約束優化［3］、調度問題［4］等眾多問題中得到了成功應用。為了利用PSO 求解二元優化問題，Kennedy 和Eberhart［5］隨后提出了二進制粒子群優化（Binary Particle Swarm Optimization，BPSO）算法。在BPSO 中，利用Sigmoid 轉換函數將由實向量表示的粒子速度轉換為由0-1向量表示的粒子位置，從而基于粒子速度實現對粒子位置的更新，其中的Sigmoid 轉換函數是BPSO 設計與實現的關鍵所在［6］。

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

本文在已有轉換函數的基礎上，通過進一步的變形，提出了一個新穎S 型轉換函數，并基于這一轉換函數給出了一個新穎的二進制粒子群優化（New Binary Particle Swarm Optimization，NBPSO）算法。為了驗證NBPSO算法的性能，通過與基于已有4 個S 型轉換函數和4 個V 型轉換函數的各種二進制PSO（分別記為S1-BPSO、S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V2-BPSO、V3-BPSO 和V4-BPSO）、具有雙重結構編碼的二進制粒子群優化（Binary Particle Swarm Optimization with Double Structure coding，DS-BPSO）算法［13］以及文獻［11］中的算法S-HBDE、B-HBDE和BPSO求解4類KPC實例［11］的計算結果進行比較，結果顯示NBPSO 在求解KPC 時明顯優于對比算法。

1 KPC定義與數學模型

KPC 的定義為：給定n個物品的集合N={1，2，…，n}和一個基本載重為C的背包，其中物品j∈N具有價值pj和重量wj，背包的可變載重S∈[l，u]，pj、wj和C為正有理數，S、l和u為有理數，且l＜0 ＜u；給定一個系數c＞0 作為懲罰系數。如果可變載重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的描述如下：

顯然模型KPCM2 中不涉及可變載重S。因此，本文利用演化算法基于模型KPCM2 求解KPC 時，可適當降低求解的難度。

2 BPSO與NBPSO

2.1 BPSO

PSO 算法是模擬鳥群飛行覓食的行為，通過個體之間的協作來尋找最優解的進化計算技術。該算法包含粒子的速度更新（式（7））和位置更新（式（8））兩個重要操作：

在BPSO 中，Kennedy 和Eberhart［5］首先引入了Sigmoid 函數（即式（9）），然后再利用式（10）替換PSO中的粒子位置更新操作（即式（8）），使得的值只取0或1。

其中，r3為0～1的隨機數。在式（10）中，利用Sigmoid 函數將粒子速度轉換為概率值，根據轉換后的概率值和r3之間的關系來更新粒子的位置。

2.2 NBPSO

2.2.1 一個新的S型轉換函數

近年來，轉換函數成為二進制演化算法研究的一個熱點，各種的新的轉換函數應運而生。值得一提的是，Mirjalili 等［6］在已有兩個轉換函數的基礎上，提出了6 個新的轉換函數，大大豐富了二進制演化算法的設計方法。目前，已有的轉換函數分為兩種：S 型轉換函數和V 型轉換函數［6，14］，下面給出了8個常用的S 型和V 型轉換函數（分別記為S1、S2、S3、S4、V1、V2、V3和V4）。

雖然S 型和V 型轉換函數的函數值均在［0，1］中，且表示一個概率值，但是S 型和V 型轉換函數明顯具有不同的特點。為了兼具S 型和V 型轉換函數的特性，本文基于V 型轉換函數中的函數V1提出一個新的S型轉換函數NS如下：

實際計算表明（請參考表1～4）：基于S2、S3、S4、V1、V3 等轉換函數的BPSO 求解KPC 的效果較差，為此下面不再考慮這些轉換函數。為了直觀地觀察NS、S1、V2和V4等轉換函數的變化情況，在圖1中給出了這四個轉換函數的圖像。

圖1 S1、V2、NS和V4轉換函數Fig.1 Transfer functions S1，V2，NS and V4

2.2.2 NBPSO

Lee 等［15］對BPSO 進行了改進，在保持PSO 的速度更新公式和位置更新公式的基礎上，利用位置值的概率對粒子的位置進行第二次更新操作。基于這一方法，并結合所給出的新S 型轉換函數NS，本文提出了一個新的二進制粒子群優化算法NBPSO。在NBPSO 的進化過程中，首先利用式（7）更新粒子的速度，接著利用式（8）對粒子位置進行第一次更新。然后，利用第一次位置更新后的位置值根據式（20）來計算粒子位置向量變化的概率值。

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

根據以上描述，容易給出NBPSO的實現步驟如下：

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

步驟2 隨機初始化種群。使粒子位置的每一分量隨機取0 或1，粒子速度的每一分量在[-vmax，vmax]內隨機取值。計算種群中所有個體的適應度。

步驟3 分別利用式（7）和式（8）更新每個粒子的速度和位置。

步驟4 利用式（20）計算每個粒子的位置向量的概率，利用式（21）二次更新粒子的位置向量。

步驟5 計算更新后每個粒子的適應度。

步驟6 判斷是否滿足終止條件。若不滿足，則t←t+1，轉步驟3；若滿足，則輸出全局最好位置對應的解以及它的目標函數值。

設O（f）表示計算個體適應的時間復雜度。其中步驟2的時間復雜度為O(N*n) +N*O(f)，步驟3～5 的時間復雜度為MIter*(N*(O(n) +O(f) +O(n)) +N*O(n))。當N、MIter和O(f)是關于n的多項式時，NBPSO 是一個具有多項式時間復雜度的隨機近似算法。

3 利用NBPSO求解KPC

在利用演化算法求解KPC 時，不可避免地將會產生不可行解。為了解決這一問題，賀毅朝等［11］給出了一種時間復雜度為O（n2）的修復與優化算法M2-GROA 來處理KPC 的不可行解。由于M2-GROA在文獻［11］中的成功應用，因此本文利用M2-GROA處理NBPSO在求解KPC時所產生的不可行解。

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

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

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

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

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

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

步驟6 利用式（20）計算改變粒子位置向量的概率。

步驟7 利用式（21）中二次更新粒子的位置向量。

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

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

在上述步驟中，步驟1利用快速排序QuickSort［16］實現，時間復雜度為O(nlogn)；步驟3 的時間復雜度為O(N*n)；步驟4的時間復雜度為O(N*n2)；步驟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 Core i7-3770 CPU@3.40 GHz和8 GB RAM 的微型計算機上進行；用C 語言進行編程，編譯環 境 為Code：Blocks；使 用Python 在 編 譯 環 境JetBrains PyCharm下繪制折線圖。

4.1 四類KPC實例

四 類KPC 實 例［11］分 別 為：ukpc 類，編 號 為ukpc100～ukpc1000；ikpc 類，編號為ikpc100～ikpc1000；wkpc 類，編號為wkpc100～wkpc1000；skpc 類，編號為skpc100～skpc1000。所有KPC 實例的數據都來自https：//www.researchgate.net/project/KPC-problem-and-Its-algorithms。

4.2 計算結果比較與分析

由于基于S2、S3、S4、V1、V3 五個轉換函數的二進制PSO和DS-BPSO［13］求解KPC 的效果極差（請參考表1～4），因此，只對 算 法NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO進行實驗比較分析。

在NBPSO、S1-BPSO、V2-BPSO 和V4-BPSO 中，各算法的種群規模均為N=20，最大迭代次數均為MIter=6*n，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 實例的計算結果的平均值與最優值之間的絕對誤差。在表5～8中給出了各算法求解四類KPC 實例的計算結果，并根據表5～8 中的計算結果比較NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO等七個算法計算結果的優劣。

記Bnum表 示NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE 和BPSO 的Best值達到OPT值的實例個數，Mnum表示NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO的Mean值達到OPT值的實例個數，在表9對各算法的這兩個指標進行了比較。

表1 S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V3-BPSO和DS-BPSO求解ukpc類實例的計算結果Tab.1 S2-BPSO，S3-BPSO，S4-BPSO，V1-BPSO，V3-BPSO and DS-BPSO calculation results of ukpc class instances

表2 S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V3-BPSO和DS-BPSO求解ikpc類實例的計算結果Tab.2 S2-BPSO，S3-BPSO，S4-BPSO，V1-BPSO，V3-BPSO and DS-BPSO calculation results of ikpc class instances

表3 S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V3-BPSO和DS-BPSO求解wkpc類實例的計算結果Tab.3 S2-BPSO，S3-BPSO，S4-BPSO，V1-BPSO，V3-BPSO and DS-BPSO calculation results of wkpc class instances

表4 S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V3-BPSO和DS-BPSO求解skpc類實例的計算結果Tab.4 S2-BPSO，S3-BPSO，S4-BPSO，V1-BPSO，V3-BPSO and DS-BPSO calculation results of skpc class instances

表5 S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO和BPSO求解ukpc類實例的計算結果Tab.5 S-HBDE，B-HBDE，NBPSO，S1-BPSO，V2-BPSO，V4-BPSO and BPSO calculation results of ukpc class instances

續表

表7 S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO和BPSO求解wkpc類實例的計算結果Tab.7 S-HBDE，B-HBDE，NBPSO，S1-BPSO，V2-BPSO，V4-BPSO and BPSO calculation results in solving wkpc class instances

表8 S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO和BPSO求解skpc類實例的計算結果Tab.8 S-HBDE，B-HBDE，NBPSO，S1-BPSO，V2-BPSO，V4-BPSO and BPSO calculation results in solving skpc class instances

表9 各算法比較分析Tab 9 Comparison and analysis of various algorithms

由表5～8和表9可以看出，對于40個KPC 實例，從算法的Best和Mean來看，NBPSO、S1-BPSO和V2-BPSO均有一半以上實例的Best值達到OPT值，V4-BPSO 相較于NBPSO、S1-BPSO和V4-BPSO 較 差。在40個實例中，NBPSO 有22個實例的Mean值達到OPT值，達到OPT值的實例個數是最多的，其次是S1-BPSO，然后是V2-BPSO，V4-BPSO 的最少。因此，NBPSO 算法明顯比S1-BPSO、V2-BPSO 和V4-BPSO 求解KPC的效果更佳。

由表5～8和表9還可看出，NBPSO 與S-HBDE、B-HBDE 和BPSO 相比較，S-HBDE 的Bnum值最大，即在40個KPC實例中Best值達到OPT值的實例最多，求解精度最高，其次是B-HBDE，最后是NBPSO。但從Mnum來看，NBPSO 在保證所有KPC 實例中一半以上實例的Best值達到OPT值的基礎上，相較于B-HBDE 將求得Mean值達到OPT值的實例個數提高了4.5 倍；相較于BPSO 將求得Mean值達到OPT值的實例個數提高了約2.7 倍；相較于S-HBDE 將求得Mean值達到OPT值的實例個數提高了約2.1 倍。由于在評價演化算法時，指標Mean比指標Best更能說明問題演化算法的性能優劣，因此NBPSO比S-HBDE、B-HBDE和BPSO求解KPC的性能更佳。

為了更直觀地比較，在圖2～5 中繪制了S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO 和BPSO 算法的AR擬合曲線，根據AR擬合曲線對它們作進一步比較。

從圖2 可以看出，S1-BPSO 在求解實例ukpc100、ukpc700～ukpc900 的結果較差；V2-BPSO 除了求解實例ukpc300 的結果較差外，對其他實例的計算結果較好；V4-BPSO 僅求解實例ukpc400～ukpc600 和ukpc1000 的結果較好，對其他實例的計算結果略差；NBPSO 在求解實例ukpc200～ukpc600 和ukpc1000 的結果較好，大部分實例的計算結果比S-HBDE、B-HBDE和BPSO要好。

圖2 求解實例ukpc100～ukpc1000的AR擬合曲線Fig.2 AR fitting curves in solving instances ukpc100-ukpc1000

從圖3 不難看出，S1-BPSO 除了求解實例ikpc700 的結果較差外，對于其他實例的計算結果均較好；V2-BPSO除了求解實例ikpc800 的結果較好外，對其他實例的計算結果，與NBPSO、V4-BPSO 相比均較差；NBPSO 和V4-BPSO 求解所有實例的結果相差不大且比其他算法要好；BPSO 相比其他6 個算法表現最差。

圖3 求解實例ikpc100～ikpc1000的AR擬合曲線Fig.3 AR fitting curves in solving instances ikpc100-ikpc1000

從圖4可以看出，S1-BPSO 求解實例wkpc400、wkpc600和wkpc1000 的結果較差，但對其他實例的計算結果較好；V4-BPSO 僅求解實例wkpc100、wkpc500、wkpc700 和wkpc900 的計算結果較好，對其他實例的計算結果均較差；NBPSO 求解大部分實例的結果比S-HBDE、B-HBDE、S1-BPSO、V2-BPSO、V4-BPSO和BPSO的要好。

圖4 求解實例wkpc100～wkpc1000的AR擬合曲線Fig.4 AR fitting curves in solving instances wkpc100-wkpc1000

從圖5 不難看出，S-HBDE 和B-HBDE 求解實例skpc800的計算結果較差，但對于其他實例的計算結果較好；V4-BPSO求解實例skpc500 和skpc800 的計算結果較差；NBPSO、S1-BPSO 和V2-BPSO 求解所有實例的結果幾乎達到最優值且比其他算法的要好；BPSO相比其他6個算法表現最差。

圖5 求解實例skpc100～skpc1000的AR擬合曲線Fig.5 AR fitting curves in solving instances skpc100-skpc1000

通過以上比較可以看出：NBPSO 在求解四類KPC 實例時，雖然部分Best達不到OPT，但是大部分Mean和部分Best相比S-HBDE、B-HBDE 和BPSO 均有所改善，而且明顯優于S1-BPSO、V2-BPSO和V4-BPSO等演化算法。

在圖6～9 中給出了S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO 和BPSO 的StD對應的曲圖，從中可以看出，對于ukpc、ikpc、wkpc 和skpc 四類實例，NBPSO 的算法穩定性總的來說比S-HBDE、B-HBDE、S1-BPSO、V2-BPSO、V4-BPSO 和BPSO 的要好；雖然對于個別實例，NBPSO 的穩定性比S1-BPSO、V4-BPSO、S-HBDE 和B-HBDE 的要差，但是對于絕大部分其他實例，NBPSO 的穩定性明顯要比其他算法的好。

圖6 求解實例ukpc100～ukpc1000的StD曲線Fig.6 StD curves in solving instances ukpc100-ukpc1000

圖7 求解實例ikpc100～ikpc1000的StD曲線Fig.7 StD curves in solving instances ikpc100-ikpc1000

圖8 求解實例wkpc100～wkpc1000的StD曲線Fig.8 StD curves in solving instances wkpc100-wkpc1000

圖9 求解實例skpc100～skpc1000的StD曲線Fig.9 StD curves in solving instance skpc100-skpc1000

綜上所述，NBPSO 的計算結果與算法穩定性均比S-HBDE、B-HBDE、S1-BPSO、V2-BPSO、V4-BPSO和BPSO的更好，它是求大規模KPC實例的一個新的高效演化算法。

5 結語

本文首先介紹了常見的S型和V型轉換函數，然后基于V型轉換函數給出了一種新的S 型轉換函數。在此基礎上，提出了一種基于新的S 型轉換函數的二進制PSO 算法NBPSO。為了驗證NBPSO 的性能，對四類大規模KPC 實例進行了仿真計算，計算結果表明：NBPSO 與基于其他轉換函數的二進制PSO、DS-BPSO、S-HBDE、B-HBDE 和BPSO 相比，在平均計算結果和魯棒性方面有著明顯地改善，因此是求解KPC 的一個高效新算法。在未來研究中，我們將探索新S 型轉換函數對其他二進制算法的影響，如二進制差分算法［12］、二進制灰狼優化算法［17］等。此外，利用NBPSO 求解其他組合優化問題如集合覆蓋問題［18］、設施選址問題［19］等也是一個值得今后探討的問題。