改進的量子粒子群優化算法對多維多選擇背包問題的求解

楊 雪, 董紅斌, 董宇欣

(哈爾濱工程大學 計算機科學與技術學院, 哈爾濱 150001)

多維多選擇背包(multi-choice knapsack problem, MMKP)是0-1背包的一種變體. 在MMKP問題中, 一些同時占有多種類型資源的物品被分成不同組, 這些物品對應不同的價值. 在每組內選擇一個物品放入背包, 使得在滿足所有資源限制條件下背包的總價值最小. 這種對不同物品和資源的組合利用使得多維多選擇背包問題應用廣泛, 如關鍵字拍賣、 路徑規劃、 傳感器網絡配置等. MMKP是典型的NP難問題, 即使只對二維問題也不存在多項式時間解(polynomial-time approximation scheme, EPTAS), 除非P=NP. 對于MMKP問題通常有兩種求解思路： 直接求解或啟發式算法求解. 直接求解旨在求解目標問題的精確全局最優值[1-3]. 但由于MMKP問題是一種基于約束限制的NP難問題, 所以通常采用啟發式算法, 以便在可行時間內獲得可接受的近似最優解, 但由于MMKP問題的可行域分散, 啟發式算法易陷入局部最優解.

文獻[4]提出了使用兩種近似算法求解多維多選擇背包問題： 第一種是簡單應用局部搜索的方法； 第二種使用了一個記憶列表替代原局部搜索策略. 雖然第二種方法的運行速度較慢, 但實際求解結果遠好于第一種方法, 在多數情況下都能找到全局最優值. Htiouech等[5]提出了一種代理信息作為選擇規則的啟發式方法, 該方法是從可行域的兩側進行搜索, 并使用一種約束規范化的方法加強約束. 該方法在有限時間內求解的精度較高. 在群智能算法求解多選擇背包問題上, 文獻[6]提出了兩種新的蟻群克隆算法進行求解, 通過增加隨機局部搜索, 提高局部搜索能力和收斂速度.

在求解背包問題時如何保證種群的多樣性是算法設計的關鍵. 演化算法的提出為多項式時間內求解約束優化問題提供了一種新途徑. 粒子群算法(PSO)是對鳥類行為模擬基礎上提出的一種解空間搜索算法[7-8], 由于其參數少、 易控制、 收斂速度快等優點被廣泛應用. 但粒子群算法被證明不能保證收斂到全局最優解[9]. Sun等[10]提出的量子粒子群優化算法(QPSO), 將粒子群中的粒子視為具有動量和能量的粒子, 用波函數表示其運動狀態, 通過Monte Carlo測定方法確定粒子的最終位置, 提高了粒子群算法的全局搜索能力[11-12]. 由于QPSO算法高效的全局搜索能力, 在圖像處理[13]和聚類[14]等領域中應用廣泛.

1 預備知識

1.1 多維多選擇背包問題

多維多選擇背包問題是指存在一些物品, 這些物品被分成l種不同的類, 第i類有li個物品. 每個物品有一定的價值σi, 并占用m種不同類的資源, 則第i類中第j個物品所占用的資源可用向量rij=(rij1,rij2,…,rijm)表示. 從每類中選擇至多一個物品放入背包中, 使背包中的物品所占用的資源數小于可提供的總資源數b=(b1,b2,…,bm), 并使背包內物品的總價值最高. 多維多選擇背包問題可以形式化地描述為

(1)

其中σij表示第i類中第j個物品的價值.

1.2 QPSO算法

PSO算法的形式化描述為： 在一個N維的搜索空間中有k個粒子, 第i個個體的屬性由兩個向量組成(xi,vi), 其中向量xi=(xi1,xi2,…,xin)表示粒子i目前所處的位置; 向量vi=(vi1,vi2,…,vin)表示粒子的速度. 對于第i個粒子, 還記憶兩個共享值： 該粒子搜索到的最優位置pi={pi1,pi2,…,pin}和整個種群搜索到的最優位置pgd.

粒子群優化算法步驟如下：

1) 在N維解空間內初始化m個粒子.

2) 對種群內所有的粒子根據

(2)

3) 計算種群的適應度.

4) 更新粒子歷史最優位置和全局歷史最優位置.

5) 判斷種群是否符合終止條件, 符合則算法結束, 否則轉2).

由于傳統粒子群優化算法存在收斂過快等問題, 所以提出了量子粒子群優化算法. 在量子粒子群優化算法中, 假設粒子群系統是一個量子粒子系統, 每個粒子具有量子行為狀態, 用波函數Ψ(X,t)描述, 其物理意義是： 波函數模的平方是粒子空間某一點出現的概率密度. 在確定了粒子的分布概率密度后, 根據Monte Carlo隨機模擬的方式測定粒子位置. 與粒子群優化算法不同, 量子粒子群優化算法通過下列公式進行參數更新：

pij(t)=φj(t)·pij(t)+(1-φj(t))·Gj(t)，φj(t)～U(0,1)，

(3)

(5)

其中:φ,β,u是[0,1]內的隨機數;Pi是粒子i的個體最好位置. 在量子粒子群優化算法中, 只有α為唯一的控制參數, 稱為收縮擴張(contraction-expansion, CE)系數. 文獻[10]研究表明,α<1.781是算法單個粒子有界性的充要條件.

2 精英保留協同量子粒子群優化算法

圖1 一個二維最大值尋優問題Fig.1 Two-dimensional maximum optimization problem

多維多選擇背包問題的強約束性質導致標準量子粒子群優化算法易陷入局部最優值, 特別是對于高維問題, 可行域被分成多個離散空間, 使得啟發式算法易局部收斂. 在標準量子粒子群中, 粒子在產生下一代個體時, 沒有經過選擇過程而是根據全局最優解和粒子歷史最優位置而產生的中心吸引點, 在該吸引點附近進行擴張. 但在粒子的進化過程中, 父代個體中較好的基因可能被丟棄, 會損失部分種群多樣性, 算法的優化過程將持續在局部最優解附近搜索. 因此, 如何衡量每個粒子的有效性并增加種群多樣性是提高QPSO算法對MMKP求解的關鍵. 基于此, 本文提出一種新的協同進化框架, 當主進化種群內的個體種群多樣性降低時, 在保留了進化歷史上優質基因個體的副種群中選擇個體對主種群中的個體進行變異.

2.1 基于位置信息的粒子可用性度量

為分析粒子群優化算法中的種群多樣性, 首先分析一個簡單的二維最大值尋優問題： 設在連續問題中Δx為一個無窮小量, 在離散問題中Δx為自變量改變的最小步長,x(t)是第t代的一個個體,x(t+1)是該個體的子代個體,f(x)是問題的適應度函數, 則一個二維問題可表示為如圖1所示.

同理, 當x(t+1)向x(t)增加一個小的增量Δx(此時Δx為負值)時, 也可獲得與上述定義相同的3種運動趨勢. 根據父代個體與子代個體形成的6種不同運動趨勢, 粒子與子代個體中可能的運動情形如圖2所示.

定義2(吸引運動) 當兩個個體相互之間有趨向運動, 即a→b且b→a時, 稱兩個個體相互吸引, 記為Att(a,b), 如圖2(A)所示.

定義5(無指導運動) 當父代個體a或子代個體b無運動趨勢時, 即a∝b或b∝a時, 稱為無指導運動, 記為No-m(a,b), 如圖2(D),(E),(F)所示.

圖2 粒子運動趨勢Fig.2 Moving trends between particles

由圖2可見: 當父代個體與子代個體進行吸引運動、 追逐運動和無指導運動時, 兩個個體趨向于在同一個峰值上共同尋優, 所以進行選擇時僅保留適應度最大的個體即可保留種群的多樣性; 當父代個體與子代個體進行排斥運動時, 父代個體與子代個體可能在不同峰值上尋優, 則需要同時保留父代個體與子代個體, 將父代個體保留至副種群中, 保留基因的多樣性. 同理, 粒子的運動也可以推廣到多維空間.

2.2 位置擾動

在量子粒子群優化算法中, 中心吸引子的位置在歷史最優位置和全局最優位置的聯合作用下產生, 隨著迭代次數的增加, 新的粒子將會隨著種群的多樣性增加移動到相同位置. 為了避免這種現象, 在QPSO算法中加入位置擾動.

首先, 當進化種群的多樣性低于閾值時, 從副種群中隨機選擇個體對主進化種群中的最優個體基因進行替換. 本文選取按照位置重心的方法計算種群多樣性, 定義如下：

2) 對于每一維, 通過

(9)

2.3 協同量子粒子群進化算法

基于對量子粒子群優化算法的改進, 本文提出一種精英保留量子粒子群優化算法(D-QPSO). 設在N維搜索空間內有k個粒子, 粒子i由向量(xi,vi)確定, 其中:xi=(xi1,xi2,…,xin)表示粒子i當前的位置;vi=(vi1,vi2,…,vin)表示粒子i的速度. 此外, 粒子也會存儲其歷史搜索的最優位置pi={pi1,pi2,…,pin}及全局搜索的最優位置pg. 在算法運行過程中, 在每一維度上使用Sigmoid函數將粒子的位置二值化：

(10)

利用粒子迭代過程中產生的啟發式信息衡量粒子的可用性. 若兩個粒子位置間形成了互斥的運行態勢, 則表明兩個粒子在不同的峰值上進行尋優, 此時需要將兩個位置都記錄下來, 從而保證種群的多樣性. 引入輔助種群, 將需保留的父代粒子存入輔助種群中. 當整個種群的多樣性降低時, 則使用副種群內的粒子信息對粒子位置增加擾動.

圖3 D-QPSO動態多樣精英算法流程Fig.3 Flow chart of D-QPSO dynamic and varied elite algorithm

D-QPSO算法的基本流程如圖3所示. D-QPSO算法步驟如下:

1) 隨機初始化k個粒子{xi(0)=(xi1,xi2,…,xin),i=1,2,…,k}; 設置初始輔助種群A=?;

2) 更新個體最優位置pi={pi1,pi2,…,pin}和全局最優位置pg;

3) 通過式(3)～(5)產生新的粒子xi(t+1), 并保留上一代粒子位置;

4) 如果前一代粒子的位置和新的粒子有互斥趨勢, 則將上一代粒子移入輔助種群,A={A,xi(t+1)}, 否則轉5);

5) 計算新粒子種群{xi(t+1)}的多樣性, 如果多樣性小于閾值參數γ, 則按式(9)對前t個位置進行擾動;

6) 如果種群滿足結束條件則停止, 否則轉2).

3 實驗結果與分析

下面使用OR-library標準測試數據集測試D-QPSO算法在求解MMKP問題上的性能. 實驗比較7種不同算法的結果準確度、 收斂速度及運行時間. 實驗使用MATLAB平臺, 在處理器為Intel Core 2, 2.66 GHz, 內存為2 GB, 操作系統Windows 7的PC機上運行.

OR-library上的13個標準多維多選擇背包測試函數列于表1. 這13個測試用例按個體的分類從5種類別到400種類別不等. 表1中N和n分別表示物品的數量和類數,r表示每類物品內的物品數,m表示資源數量.

表1 數據集參數Table 1 Parameters of data sets

3.1 最優值比較

實驗比較傳統粒子群優化算法、 量子粒子群優化算法及兩個帶有基因變異策略算法的性能. 表2比較了7種不同算法的表現, 包括heu,Cpc,Aut-R,PSO,QPSO,D-PSO和D-QPSO算法. 在參數選擇方面, Ant-R算法的參數選擇與設置一致; PSO算法是在粒子的運行過程中, 對一定概率的粒子進行Gauss擾動, 慣性權重在運行過程中從0.9到0.4遞減, 學習因子C1=C2=0.8,R1和R2是遵循0～1均勻分布的隨機數; QPSO算法的吸引收縮因子在[0.5,1]內線性遞減; D-QPSO算法中的精英飽和代數定義為t=5, 加速系數rand1和rand2為兩個在[0,1]內變化的隨機數.

表2 不同算法在13個數據集上的求解準確性比較Table 2 Accuracy comparison of different algorithms on 13 data sets

*表示精確解尚未明確.

由表2可見, D-QPSO算法的求解更接近于全局最優解, 特別當多選擇背包內的物品維度較高時優勢更明顯. 在前7個測試實例中, 由于背包維度不高(n≤100), 所有算法都能獲得較好結果. 但當多選擇背包內的物品數量增多時, D-QPSO算法獲得的值更優. 表明在數據維度增加時, 維度之間的限制更嚴格, D-QPSO算法跳出局部搜索能力更強, 更易收斂到全局最優解. 雖然在I03,I06和I07上, D-QPSO算法的求解僅次于Ant-R算法, 但兩種算法解的差異性較小(0.12%,2.1%,0.03%). 產生這種結果的原因是由于D-QPSO算法在初始化時隨機初始化粒子, 而最終結果受初始化影響.

為了更直觀地表示, 將所有結果與已有最優值用

(11)

進行歸一化比較, 結果如圖4所示. 由圖4可見, Ant-R,D-PSO和D-QPSO算法的誤差率基本小于2%. 加入了精英基因保留策略(D-PSO/D-QPSO)的算法求解值明顯好于普通的粒子群優化算法和量子粒子群優化算法, 說明在進化過程中, 采取對有價值信息的保留方法進行變異可增強算法的尋優能力. 當類別數較多時(n>100), D-PSO算法的求解值好于Ant-R算法.

3.2 收斂速度

在背包數量為4 000, 物品種類為400, 每類個體為10個的情形下， 將D-QPSO算法與其他3種算法的收斂情況進行比較, 分別將每種算法運行100次， 計算每種算法每代獲得的最優值平均值， 結果如圖5所示. 由圖5可見, PSO和QPSO算法在處理背包問題時收斂速度較快, 但較易收斂到局部最優解. Ant-R和D-QPSO算法收斂速度較慢, 但能搜索到更優值. 這是因為在D-QPSO算法中增加了對種群多樣性的判斷, 當種群多樣性降低時, 算法加入擾動, 增加了調出局部最優值的可能性, 進而收斂到更優結果.

圖4 不同算法的結果誤差率比較Fig.4 Comparison of error rates of different algorithms

圖5 PSO,QPSO,Ant-R和D-QPSO算法的收斂曲線Fig.5 Convergence curves of PSO,QPSO,Ant-R and D-QPSO algorithms

3.3 運行時間

圖6 不同算法在13個數據集上的平均運行時間Fig.6 Average running time of different algorithms on 13 data sets

圖6是將D-QPSO算法與Ant-R,PSO,QPSO算法分別在13個數據集上運行50次所得的平均運行時間比較結果. 由圖6可見, D-QPSO算法的求解時間高于傳統的PSO和QPSO算法, 但多數情形下低于Ant-R算法(31.5%). 表明使用量子粒子群優化算法保證了算法的收斂速度. 圖6中兩條虛線對比了加入精英保留策略與未加入精英保留策略的量子粒子群優化算法求解時間. 結果表明, 雖然增加了精英基因保留策略的算法所消耗的時間高于原始的量子粒子群優化算法, 但隨著問題維數的增加, 其增加的時間是多項式倍數的, 可以接受.

綜上所述, 本文針對多維多選擇背包問題面臨的強約束限制、 復雜性高、 易收斂到局部最優解的問題, 提出了一種改進的量子粒子群優化算法. 該算法在進行迭代過程中增加了對基因有效性的判斷, 保留了對種群進化意義較大的染色體. 當種群的多樣性降低時, 根據已保留的精英基因對現有種群內的個體進行變異, 使算法更易跳出局部最優解. 對本文算法在標準測試數據集上進行了測試, 證明了算法的有效性. 雖然增加了基因有效性判斷使算法的時間復雜度增加, 但仍在可接受的范圍內.