基于改進(jìn)的群論優(yōu)化算法求解具有單連續(xù)變量背包問題

李香軍，朱曉斌

（1.河北地質(zhì)大學(xué) 信息工程學(xué)院，河北 石家莊 050031；2.石家莊文化傳媒學(xué)校，河北 石家莊 050000）

0 引言

背包問題是一類重要的 NP難問題，其中包括 0-1背包問題[1]、帶建制的背包問題[2]、折扣0-1背包問題[3]以及具有單連續(xù)變量背包問題（knapsack problem with a single continuous variable，KPC）[4]等多種類型的背包問題，在項目選擇、網(wǎng)絡(luò)阻截問題和資源配置等眾多實際領(lǐng)域[5-8]都有重要的應(yīng)用。KPC問題是由 Marchand和Wolsey[1]在1999年提出的一種帶有連續(xù)變量的擴(kuò)展 0-1背包問題，在物品生產(chǎn)、組織管理以及其他生產(chǎn)分配問題中有很高的應(yīng)用價值。2011年，Lin等人[5]將 KPC問題分解為標(biāo)準(zhǔn) 0-1背包和偽背包問題，分別利用動態(tài)規(guī)劃法和分支定界法進(jìn)行求解。2012年，Buther和 Briskorn[6]利用構(gòu)造法和啟發(fā)式算法求解KPC問題。2018年，He等人[9]利用放縮法將KPC中的連續(xù)變量離散化，基于動態(tài)規(guī)劃求解KPC問題。這些論文皆利用精確算法求解KPC問題，都具有時間復(fù)雜度過高的缺點。之后，He等人[10]在2018年引入了演化算法求解KPC問題的思想，建立了KPCM2和KPCM3兩種新模型，并基于HBDE算法提出S-HBDE和B-HBDE算法分別求解這兩種模型，此方法降低了時間復(fù)雜度，但求解效果欠佳。在 2019年，He等人[11]提出了ETDE算法，將背包的裝載方案和連續(xù)變量作為一個個體，進(jìn)一步提高了求解KPC問題的效率。近日，王澤昆等人[12]提出一個基于新穎S型轉(zhuǎn)換函數(shù)的NBPSO算法求解KPC問題，提高了求解問題的精度與速度。利用演化算法求解KPC問題已經(jīng)取得了不錯的成果，所以利用演化算法求解KPC問題值得深入研究。

群論優(yōu)化算法（Group theory-based optimization algorithm,GTOA）是He等人[13]在2018年提出的新穎算法，將代數(shù)群運算引入背包問題的進(jìn)化過程中，將背包問題的可行解視為群的直積的一個元素，通過群的直積的乘法和逆運算來實現(xiàn)演化過程。GTOA算法在解決集合聯(lián)盟背包問題、折扣{0-1}背包問題和有界背包問題上已有很好的結(jié)果。本文對 GTOA算法進(jìn)行改進(jìn)，基于KPCM2模型[10]求解KPC問題，對不可行解進(jìn)行修復(fù)優(yōu)化，給出求解KPC問題的一個新的高效的方法。

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

KPC問題的描述如下[12]：給定物品集合N={1,2,…,n}和一個背包基本載重 C，物品j(j∈N)的價值為pj＞0，重量為wj＞0。在 KPC問題中，背包載重可變，添加了一個變量S進(jìn)行調(diào)整，文獻(xiàn)[10]基于降維法建立了模型KPCM2，消去了連續(xù)變量S，將解空間的維數(shù)從n+1降為n。KPCM2的數(shù)學(xué)模型如下：

KPCM2數(shù)學(xué)模型更適于二進(jìn)制演化算法求解KPC問題，減少了變量的數(shù)量，降低了求解的難度，所以本文基于 KPCM2模型求解 KPC問題。

2 GTOA 簡介與改進(jìn)

群論優(yōu)化算法（Group theory-based optimization algorithm,GTOA）是利用Z/nZ的加法群（n為整數(shù)取得模，Z為整數(shù)集）生成群的直積來設(shè)計的一種新的進(jìn)化算法。從代數(shù)觀點看，無論背包問題屬于哪一類，其可行解的每個分量都可以看作是Z/nZ可加群中的一個元素，可簡化為Zn={0,1,…,n–1}，n其中n為正整數(shù)，n≥2。在此基礎(chǔ)上，提出了一種代數(shù)方法來設(shè)計 EAs，并利用群的直積提出了一種基于群論的優(yōu)化算法（GTOA）。GTOA算法可以直接求解整數(shù)規(guī)劃問題，在離散空間[m1+1,m2+1,…,mn+1]上求解，[m1+1,m2+1,…,mn+1]={0,1,…,m1}×{0,1,…,m2}×…×{0,1,…,mn}，具有普適性，不僅易于實現(xiàn)，而且效率很高，適合于求解KPs。

GTOA算法主要包含隨機(jī)線性組合算子（the Random Linear Combination Operator,RLCO）和變異算子。

RLCO算子：

其中Y、V、W是群Z中隨機(jī)選擇的三個不同的元素，Y=(y1,y2,…,yn)，V=(v1,v2,…,vn)，W=(w1,w2,…,wn)，即種群中三個不同的個體，F(xiàn)=(f1,f2,…,fn)={–1,0,1}n是組合系數(shù)向量，為隨機(jī)向量，X=(x1,x2,…,xn)是線性組合生成的新個體。新個體的產(chǎn)生為xj=yj⊕ [fj(vj⊕ (mj+1–wj))]，j=1,2,…,n。當(dāng)m=1時，解空間為[2,2,…,2]={0,1}n。本文為求解KPC問題，KPC問題是0–1向量問題，所以解空間為[2,2,…,2]。

變異算子分為兩種：反轉(zhuǎn)與隨機(jī)變異算子(the Inversion and Random Mutation Operator,IRMO)和選擇變異算子（the Switch Mutation Operator,SMO）。當(dāng)解空間為(m1+1,m2+1,…,mn+1)，md≥1，d=1,2,…,n時，使用IRMO算子，當(dāng)解空間為(2,2,…,2)，使用 SMO 算子。由于本文是基于IGTOA算法求解KPC問題，所以使用的是SMO算子，偽代碼描述本文不再贅述。

為了提升算法的全局搜索能力，本文將式（4）改為式（5），從而提出了IGTOA算法。

3 利用IGTOA求解KPC問題

由以上描述可得出IGTOA算法求解KPC問題的偽代碼描述如算法1所示。

算法1 IGTOA算法。

在算法1中，第1步的時間復(fù)雜度為O(NP*n)，M2-GROA算法的時間復(fù)雜度為O(n2)，令O(f)表示計算f(Xi)的時間復(fù)雜度，所以第2步時間復(fù)雜度為NP×O(f)+NP×O(n2)，第5步的時間復(fù)雜度為O(n)，第6步的時間復(fù)雜度為O(n)，第7步的時間復(fù)雜度為O(n2)，所以第 3～13步的時間復(fù)雜度為MIT×NP×(O(n)+O(n)+O(n2)+O(f))，故改進(jìn)的GTOA算法的時間復(fù)雜度為O(NP×n)+NP×O(f)+NP×O(n2)+MIT×NP×(O(n)+O(n)+O(n2)+O(f))，當(dāng)MIT、NP和O(f)是關(guān)于n的多項式時，此算法是多項式時間復(fù)雜度。

4 實驗結(jié)果與分析

所有的計算均在配置為 Intel(R) Core(TM)i7-3770 CPU @ 3.40GHz和8GB內(nèi)存的微型計算機(jī)上進(jìn)行。操作系統(tǒng)為Windows 7旗艦版。本實驗的編程語言為C，編譯環(huán)境為Code:Blocks，使用Python語言繪制曲線圖。

4.1 四類KPC實例

本文使用的實例為：逆強(qiáng)相關(guān)實例（ikpc）、強(qiáng)相關(guān)實例（skpc）、不相關(guān)實例（ukpc）、弱相關(guān)實例（wkpc），數(shù)據(jù)的規(guī)模為 100～2000，來自于文獻(xiàn)[10]。

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

本節(jié)為 IGTOA、ETDE、S-HBDE、B-HBDE算法求解KPC實例的情況，并對這些實驗結(jié)果進(jìn)行分析比較。表1給出IGTOA、ETDE、S-HBDE、B-HBDE 4個算法的參數(shù)設(shè)置，其中NP為種群規(guī)模，n為問題實例的維數(shù)，MIT為迭代次數(shù)，Run為每個例子獨立計算次數(shù)，CR為交叉因子，F(xiàn)S、F為縮放因子，ETDE、S-HBDE、B-HBDE中[–A,A]為問題每維的取值范圍。

表1 IGT OA、ETDE、S-HBDE、B-HBDE算法參數(shù)設(shè)置Tab.1 The parameter settings of IGTOA、ETDE、S-HBDE and B-HBDE

記 Best、Average、Std分別為算法獨立運行50次的得到結(jié)果的最好值、平均值、標(biāo)準(zhǔn)差，OPT為每類實例的最優(yōu)值，表2～表5為各算法求解規(guī)模為100～1000的四類kpc實例的結(jié)果，其中加*號代表可以達(dá)到最優(yōu)值，表現(xiàn)最好的用加粗標(biāo)示。

表2 ETDT、S-HBDE、B-HBDE和IGTOA求解ikpc類實例的計算結(jié)果Tab.2 ETDT 、S-HBDE、B-HBDE and IGTOA calculation results of ikpc class instances

表3 ETDT、S-HBDE、B-HBDE和IGTOA求解skpc類實例的計算結(jié)果Tab.3 ETDT 、S-HBDE、B-HBDE and IGTOA calculation results of skpc class instances

表4 ETDT、S-HBDE、B-HBDE和IGTOA求解ukpc類實例的計算結(jié)果Tab.4 ETDT 、S-HBDE、B-HBDE and IGTOA calculation results of ukpc class instances

表5 ETDT、S-HBDE、B-HBDE和IGTOA求解wkpc類實例的計算結(jié)果Tab.5 ETDT 、S-HBDE、B-HBDE and IGTOA calculation results of wkpc class instances

從表2中可以看出，對于ikpc類實例，ETDT、S-HBDE、B-HBDE、IGTOA算法所求的最好值Best的個數(shù)分別為 1、8、7、10個，可以看出 IGTOA算法求解 ikpc類實例的精度最高；ETDT、S-HBDE、B-HBDE、IGTOA算法所求的平均值A(chǔ)verage的個數(shù)分別為1、2、1、8個，所以IGTOA算法求解ikpc類實例的平均性能最好；而對于標(biāo)準(zhǔn)差Std，IGTOA算法求解的標(biāo)準(zhǔn)差10個實例里有 8個達(dá)到了 0，而其他算法只有一個或兩個實例可以達(dá)到0，所以IGTOA算法求解問題的穩(wěn)定性很好?？傮w而言，IGTOA算法求解ikpc類實例比其他算法都好，精度高，求解效果平均性能很好，穩(wěn)定性最好。

從表3中可以看出，對于skpc類實例，ETDT、S-HBDE、B-HBDE、IGTOA 算法所求的最好值Best的個數(shù)分別為1、10、10、10個，可以看出ETDT算法求解 skpc類實例時精度最差，S-HBDE、B-HBDE、IGTOA算法10個實例都可以求解到最好值；ETDT、S-HBDE、B-HBDE、IGTOA算法所求的平均值A(chǔ)verage的個數(shù)分別為0、3、1、4個，所以IGTOA算法求解skpc類實例的平均性能最好；而對于標(biāo)準(zhǔn)差 Std，IGTOA算法求解10個實例的標(biāo)準(zhǔn)差都幾乎接近于0，其余算法求解問題的標(biāo)準(zhǔn)差略大，穩(wěn)定性很好?？傮w而言，IGTOA算法求解 skpc類實例在精度上高于ETDT算法，和S-HBDE、B-HBDE算法精度相同，在平均性能和穩(wěn)定性上比其他算法都好。

從表4中可以看出，對于ukpc類實例，ETDT、S-HBDE、B-HBDE、IGTOA 算法所求的最好值Best的個數(shù)分別為8、8、8、6個，ETDT算法求解ukpc類實例時在求解精度上略差于其他算法；ETDT、S-HBDE、B-HBDE、IGTOA算法所求的平均值A(chǔ)verage的個數(shù)分別為3、3、2、6個，所以IGTOA算法求解ukpc類實例的平均性能最好，比其他算法都好；對于標(biāo)準(zhǔn)差 Std，IGTOA算法求解10個實例的標(biāo)準(zhǔn)差比其他算法小，其他算法求解問題的的標(biāo)準(zhǔn)差都較大，所以IGTOA算法求解問題穩(wěn)定性最好?？傮w而言，IGTOA算法求解ukpc類實例在精度上比其他算法略差，在平均性能和穩(wěn)定性上比其他算法都好。

從表5中可以看出，對于wkpc類實例，ETDT、S-HBDE、B-HBDE、IGTOA算法所求的最好值Best的個數(shù)分別為1、5、4、6個，ETDT算法求解 wkpc類實例時在求解精度上高于其他算法；ETDT、S-HBDE、B-HBDE、IGTOA算法所求的平均值A(chǔ)verage的個數(shù)分別為1、0、0、9個，可以明顯看出IGTOA算法的平均性能最好；對于標(biāo)準(zhǔn)差 Std，IGTOA算法也比其他算法小，穩(wěn)定性很好?？傮w而言，IGTOA算法求解wkpc類實例在精度、平均性能和穩(wěn)定性上比其他算法都好。

平均性能更能代表一個算法求解問題的效果如何，為了更直觀的觀察各算法的平均性能的好壞，圖1給出了 ETDT、B-HBDE、S-HBDE、IGTOA算法求解 ikpc500、skpc500、ukpc500、wkpc500實例的平均收斂曲線圖，從中可以看出，對于每一類實例，IGTOA算法都可以更快的求得最優(yōu)解，所需要的時間最短，IGTOA算法在求解四類實例時收斂速度最快，在迭代150次之前基本就可以找到最優(yōu)解，而其余算法都需要在迭代 150次之后才能找到最優(yōu)解，所以，IGTOA算法比ETDT、S-HBDE、B-HBDE算法在求解kpc問題時效果好很多。

圖1 ikpc500,skpc500,ukpc500和wkpc500實例的平均收斂曲線Fig.1 The average convergence curve of instance ikpc500, skpc500, ukpc500 and wkpc500

總體而言，IGTOA算法在求解 ikpc、wkpc類實例時在精度、平均性能、穩(wěn)定性上比其他算法都好；在求解skpc類實例時，在求解精度上，比ETDT好，和S-HBDE、B-HBDE效果相當(dāng)，在平均性能、穩(wěn)定性上比其他算法都好；在求解ukpc類實例時，求解精度比 ETDT、S-HBDE、B-HBDE算法略差一些，但平均性能、穩(wěn)定性上都高于其他算法，所以 IGTOA算法是一個求解KPC問題的高效算法。

5 總結(jié)

本文基于群論優(yōu)化算法（GTOA)在模型KPCM2的基礎(chǔ)上求解KPC問題，首先對GTOA算法進(jìn)行改進(jìn)，擴(kuò)大算法的全局搜索范圍，從而提出了改進(jìn)的群論優(yōu)化算法（IGTOA)。為了證明IGTOA算法在求解 KPC問題時效果更好，采用文獻(xiàn)[10]中的40個實例進(jìn)行驗證，將IGTOA算法與ETDE、S-HBDE、B-HBDE算法的求解結(jié)果進(jìn)行比較，表明IGTOA算法在求解KPC問題時，精度高、平均性能好、穩(wěn)定性高、收斂速度很快，是一個求解 KPC問題的高效算法。由于 IGTOA算法是一種新穎的演化算法，在求解組合優(yōu)化問題時仍需要探討和研究，今后將嘗試?yán)肐GTOA算法求解其它整數(shù)規(guī)劃問題，并進(jìn)一步探討將GTOA改進(jìn)的高效方法。