王澤昆，賀毅朝，李煥哲，張發(fā)展

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

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

0 引言

粒子群優(yōu)化（Particle Swarm Optimization，PSO）［1］是1995年由Kennedy和Eberhart 提出的一種著名演化算法，具有結(jié)構(gòu)簡(jiǎn)單、易于實(shí)現(xiàn)和計(jì)算成本低等優(yōu)點(diǎn)，受到眾多學(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］隨后提出了二進(jìn)制粒子群優(yōu)化（Binary Particle Swarm Optimization，BPSO）算法。在BPSO 中，利用Sigmoid 轉(zhuǎn)換函數(shù)將由實(shí)向量表示的粒子速度轉(zhuǎn)換為由0-1向量表示的粒子位置，從而基于粒子速度實(shí)現(xiàn)對(duì)粒子位置的更新，其中的Sigmoid 轉(zhuǎn)換函數(shù)是BPSO 設(shè)計(jì)與實(shí)現(xiàn)的關(guān)鍵所在［6］。

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

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

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＜0 ＜u；給定一個(gè)系數(shù)c＞0 作為懲罰系數(shù)。如果可變載重S＞0，即背包容量加S，則總價(jià)值將減去cS；反之，如果可變載重S＜0，即背包容量減|S|，則總價(jià)值加|cS|。KPC 目標(biāo)是確定S的取值，使得裝入物品的重量之和在不超過背包載重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，文獻(xiàn)［11］基于降維法建立了KPC 的一個(gè)新數(shù)學(xué)模型KPCM2，該模型通過消去連續(xù)變量S使解空間的維數(shù)由n+1降低為n。數(shù)學(xué)模型KPCM2的描述如下：

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

2 BPSO與NBPSO

2.1 BPSO

PSO 算法是模擬鳥群飛行覓食的行為，通過個(gè)體之間的協(xié)作來(lái)尋找最優(yōu)解的進(jìn)化計(jì)算技術(shù)。該算法包含粒子的速度更新（式（7））和位置更新（式（8））兩個(gè)重要操作：

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

其中，r3為0～1的隨機(jī)數(shù)。在式（10）中，利用Sigmoid 函數(shù)將粒子速度轉(zhuǎn)換為概率值，根據(jù)轉(zhuǎn)換后的概率值和r3之間的關(guān)系來(lái)更新粒子的位置。

2.2 NBPSO

2.2.1 一個(gè)新的S型轉(zhuǎn)換函數(shù)

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

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

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

圖1 S1、V2、NS和V4轉(zhuǎn)換函數(shù)Fig.1 Transfer functions S1，V2，NS and V4

2.2.2 NBPSO

Lee 等［15］對(duì)BPSO 進(jìn)行了改進(jìn)，在保持PSO 的速度更新公式和位置更新公式的基礎(chǔ)上，利用位置值的概率對(duì)粒子的位置進(jìn)行第二次更新操作?；谶@一方法，并結(jié)合所給出的新S 型轉(zhuǎn)換函數(shù)NS，本文提出了一個(gè)新的二進(jìn)制粒子群優(yōu)化算法NBPSO。在NBPSO 的進(jìn)化過程中，首先利用式（7）更新粒子的速度，接著利用式（8）對(duì)粒子位置進(jìn)行第一次更新。然后，利用第一次位置更新后的位置值根據(jù)式（20）來(lái)計(jì)算粒子位置向量變化的概率值。

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

根據(jù)以上描述，容易給出NBPSO的實(shí)現(xiàn)步驟如下：

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

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

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

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

步驟5 計(jì)算更新后每個(gè)粒子的適應(yīng)度。

步驟6 判斷是否滿足終止條件。若不滿足，則t←t+1，轉(zhuǎn)步驟3；若滿足，則輸出全局最好位置對(duì)應(yīng)的解以及它的目標(biāo)函數(shù)值。

設(shè)O（f）表示計(jì)算個(gè)體適應(yīng)的時(shí)間復(fù)雜度。其中步驟2的時(shí)間復(fù)雜度為O(N*n) +N*O(f)，步驟3～5 的時(shí)間復(fù)雜度為MIter*(N*(O(n) +O(f) +O(n)) +N*O(n))。當(dāng)N、MIter和O(f)是關(guān)于n的多項(xiàng)式時(shí)，NBPSO 是一個(gè)具有多項(xiàng)式時(shí)間復(fù)雜度的隨機(jī)近似算法。

3 利用NBPSO求解KPC

在利用演化算法求解KPC 時(shí)，不可避免地將會(huì)產(chǎ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)度值。基于NBPSO 求解KPC 的算法的步驟如下：

步驟1 將n個(gè)物品項(xiàng)利用Quicksort［16］按照物品的價(jià)值密度比降序排序，并將排序后的物品項(xiàng)的下標(biāo)依次存入一維數(shù)組H[1，2，…，n]中。

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

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

步驟4 利用M2-GROA 處理初始化時(shí)產(chǎn)生的不可行解，并計(jì)算粒子的適應(yīng)度值。

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

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

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

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

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

在上述步驟中，步驟1利用快速排序QuickSort［16］實(shí)現(xiàn)，時(shí)間復(fù)雜度為O(nlogn)；步驟3 的時(shí)間復(fù)雜度為O(N*n)；步驟4的時(shí)間復(fù)雜度為O(N*n2)；步驟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 Core i7-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 四類KPC實(shí)例

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

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

由于基于S2、S3、S4、V1、V3 五個(gè)轉(zhuǎn)換函數(shù)的二進(jìn)制PSO和DS-BPSO［13］求解KPC 的效果極差（請(qǐng)參考表1～4），因此，只對(duì) 算 法NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO進(jìn)行實(shí)驗(yàn)比較分析。

在NBPSO、S1-BPSO、V2-BPSO 和V4-BPSO 中，各算法的種群規(guī)模均為N=20，最大迭代次數(shù)均為MIter=6*n，n為KPC 實(shí)例中物品的個(gè)數(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 實(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ì)誤差。在表5～8中給出了各算法求解四類KPC 實(shí)例的計(jì)算結(jié)果，并根據(jù)表5～8 中的計(jì)算結(jié)果比較NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO等七個(gè)算法計(jì)算結(jié)果的優(yōu)劣。

記Bnum表 示NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE 和BPSO 的Best值達(dá)到OPT值的實(shí)例個(gè)數(shù)，Mnum表示NBPSO、S1-BPSO、V2-BPSO、V4-BPSO、S-HBDE、B-HBDE和BPSO的Mean值達(dá)到OPT值的實(shí)例個(gè)數(shù)，在表9對(duì)各算法的這兩個(gè)指標(biāo)進(jìn)行了比較。

表1 S2-BPSO、S3-BPSO、S4-BPSO、V1-BPSO、V3-BPSO和DS-BPSO求解ukpc類實(shí)例的計(jì)算結(jié)果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類實(shí)例的計(jì)算結(jié)果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類實(shí)例的計(jì)算結(jié)果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類實(shí)例的計(jì)算結(jié)果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類實(shí)例的計(jì)算結(jié)果Tab.5 S-HBDE，B-HBDE，NBPSO，S1-BPSO，V2-BPSO，V4-BPSO and BPSO calculation results of ukpc class instances

續(xù)表

表7 S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO和BPSO求解wkpc類實(shí)例的計(jì)算結(jié)果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類實(shí)例的計(jì)算結(jié)果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可以看出，對(duì)于40個(gè)KPC 實(shí)例，從算法的Best和Mean來(lái)看，NBPSO、S1-BPSO和V2-BPSO均有一半以上實(shí)例的Best值達(dá)到OPT值，V4-BPSO 相較于NBPSO、S1-BPSO和V4-BPSO 較 差。在40個(gè)實(shí)例中，NBPSO 有22個(gè)實(shí)例的Mean值達(dá)到OPT值，達(dá)到OPT值的實(shí)例個(gè)數(shù)是最多的，其次是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個(gè)KPC實(shí)例中Best值達(dá)到OPT值的實(shí)例最多，求解精度最高，其次是B-HBDE，最后是NBPSO。但從Mnum來(lái)看，NBPSO 在保證所有KPC 實(shí)例中一半以上實(shí)例的Best值達(dá)到OPT值的基礎(chǔ)上，相較于B-HBDE 將求得Mean值達(dá)到OPT值的實(shí)例個(gè)數(shù)提高了4.5 倍；相較于BPSO 將求得Mean值達(dá)到OPT值的實(shí)例個(gè)數(shù)提高了約2.7 倍；相較于S-HBDE 將求得Mean值達(dá)到OPT值的實(shí)例個(gè)數(shù)提高了約2.1 倍。由于在評(píng)價(jià)演化算法時(shí)，指標(biāo)Mean比指標(biāo)Best更能說(shuō)明問題演化算法的性能優(yōu)劣，因此NBPSO比S-HBDE、B-HBDE和BPSO求解KPC的性能更佳。

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

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

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

從圖3 不難看出，S1-BPSO 除了求解實(shí)例ikpc700 的結(jié)果較差外，對(duì)于其他實(shí)例的計(jì)算結(jié)果均較好；V2-BPSO除了求解實(shí)例ikpc800 的結(jié)果較好外，對(duì)其他實(shí)例的計(jì)算結(jié)果，與NBPSO、V4-BPSO 相比均較差；NBPSO 和V4-BPSO 求解所有實(shí)例的結(jié)果相差不大且比其他算法要好；BPSO 相比其他6 個(gè)算法表現(xiàn)最差。

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

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

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

從圖5 不難看出，S-HBDE 和B-HBDE 求解實(shí)例skpc800的計(jì)算結(jié)果較差，但對(duì)于其他實(shí)例的計(jì)算結(jié)果較好；V4-BPSO求解實(shí)例skpc500 和skpc800 的計(jì)算結(jié)果較差；NBPSO、S1-BPSO 和V2-BPSO 求解所有實(shí)例的結(jié)果幾乎達(dá)到最優(yōu)值且比其他算法的要好；BPSO相比其他6個(gè)算法表現(xiàn)最差。

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

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

在圖6～9 中給出了S-HBDE、B-HBDE、NBPSO、S1-BPSO、V2-BPSO、V4-BPSO 和BPSO 的StD對(duì)應(yīng)的曲圖，從中可以看出，對(duì)于ukpc、ikpc、wkpc 和skpc 四類實(shí)例，NBPSO 的算法穩(wěn)定性總的來(lái)說(shuō)比S-HBDE、B-HBDE、S1-BPSO、V2-BPSO、V4-BPSO 和BPSO 的要好；雖然對(duì)于個(gè)別實(shí)例，NBPSO 的穩(wěn)定性比S1-BPSO、V4-BPSO、S-HBDE 和B-HBDE 的要差，但是對(duì)于絕大部分其他實(shí)例，NBPSO 的穩(wěn)定性明顯要比其他算法的好。

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

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

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

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

綜上所述，NBPSO 的計(jì)算結(jié)果與算法穩(wěn)定性均比S-HBDE、B-HBDE、S1-BPSO、V2-BPSO、V4-BPSO和BPSO的更好，它是求大規(guī)模KPC實(shí)例的一個(gè)新的高效演化算法。

5 結(jié)語(yǔ)

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