基于量子粒子群算法求解整數規劃

摘 要：通過引入量子行為來增強粒子的全局收斂能力，提出了量子粒子群優化算法（QPSO），并用于求解整數規劃問題。測試函數的仿真結果表明，通過適當的參數設置，并將每次迭代所生成的實數值截至整數值后進行下一次迭代，可以保證QPSO算法求解的精度，提高收斂速度且能有效避免早熟。

關鍵詞：粒子群算法； 量子粒子群算法； 整數規劃

中圖分類號：O22文獻標志碼：A

文章編號：1001—3695(2007)03—0079—03

IP（Integer Programming， 整數規劃）是要求決策變量取整數值的優化問題，在解決任務調度、資金分配、股票分析、網絡設計和VLSI電路設計等問題中具有重要的應用。Gall等人[1]早在20世紀六七十年代就曾用進化算法(EA)解決整數規劃問題。較之于其他幾種方法，如分枝限界法、割平面法、完全枚舉法等，在處理規模較大的整數規劃問題時，EA具有計算量小的優點，因此應用越來越普遍。但這種方法也存在自身的局限性。Rudolph[2]運用遺傳算法，發現用一個固定長度的二進制位串來表示一個在非約束整數空間進行搜索而得到二進制位串編碼的可能解的方法不可行；另一種通過進化策略(ES)，將搜索空間Zn嵌入到Sn并且將實數截至整數的方法也不是經常有效的。原因在于這些用于搜索實數最小值的進化算法的某些特性在整數搜索空間中并不需要，因為在l1準則中兩點的最小距離為1，這樣，只有步長大于1時才進行搜索。因此EA解決IP應該直接在整數空間進行。

因此本文考慮如下一般形式的整數規劃問題：

其中，Z是整數集，S是一個無約束的可行性區域。事實上，整數規劃問題的最大化在文獻中也很普遍，但在本文中將僅僅考慮IP的無約束最小化情況，這是因為一個最大化問題可以很容易地轉換成一個最小化問題。PSO（Particle Swarm Optimization，粒子群算法）是一種群體智能算法，是繼遺傳算法等進化算法以后新出現的一類智能優化算法。它模擬鳥類的覓食行為，是受到生物群體模型啟發而設計的一種智能算法。該算法最大的特點是容易實現，且控制參數少、計算速度快。

本文采用改進的粒子群優化算法——量子粒子群算法，提出了解決整數規劃問題的新方法。

1 PSO算法和QPSO算法

1.1 PSO算法

Kennedy和 Eberhart于1995年提出的PSO算法是一種基于群體的具有全局搜索能力的隨機優化算法[3]。粒子群算法與其他進化算法類似，也采用群體和進化的概念，同樣也是依據個體（粒子）的適應值大小進行操作。所不同的是，粒子群算法不像其他進化算法那樣對于個體使用進化算子，而是將每個個體X_i=(x_i1，x_i2，…，x_iD)看做是在D維搜索空間中的一個沒有體積和重量的粒子，并在搜索空間中以一定的速度V_i=(v_i1，v_i2，…，v_iD)飛行。該飛行速度由個體的最好位置P_i=(p_i1，p_i2，…，p_iD)和群體的最好位置pgd進行動態調整。粒子狀態更新操作如下：

其中，學習因子φ₁和φ₂決定社會群體p_g和個體認知p_i的相互影響。

自PSO算法提出后，學者們也進行了大量有關提高算法收斂性和多樣性的工作。一般來說，對于基于群體的搜索優化方法，適當地控制全局搜索和局部搜索能力對有效地找到最優解起到關鍵作用。Eberhart 和Shi[4]發現PSO可以有效地進行廣域搜索但缺乏精確搜索，因此他們引進了線性變化的慣性權重參數ω，在時間上動態地調整速度并慢慢地將PSO聚焦在局部搜索。

在大多數文獻中將帶慣性權重的PSO算法稱之為PSO算法的標準版本，或簡稱標準PSO；而將Kennedy提出的基本PSO算法稱為PSO的初始版本。另外，Maurice Clerc[5]于1999年提出了收縮因子參數K。該方法描述了一種選擇ω，φ₁和φ₂值的方法，防止粒子搜索到可行性區域可能的范圍之外，以確保算法收斂。其中系數

即使在PSO算法基礎上提出了各種各樣的改進算法，但是PSO算法本身存在缺陷，其中最根本的就是它已經被證明不是一個全局收斂的算法[6]。從動力學的角度來說，粒子群算法中粒子的收斂過程是以p點為吸引子，隨著速度的減小不斷地接近p點，最后跌落到p點。因此在整個過程中，在p點處實際上存在某種形式的勢能場吸引該粒子，這正是整個粒子群保持聚集性的原因。但由于在經典的PSO系統中，粒子的收斂是以軌道形式實現的，并且粒子的速度總是有限的，在搜索過程中粒子的搜索空間是一個有限的區域，不能覆蓋整個可行空間。一般的PSO算法不能保證以概率1收斂到全局最優解，這正是一般PSO算法的最大缺陷。為了更好地解決這個問題，在PSO算法的基礎上提出了量子粒子群算法[7]。與在量子空間中粒子滿足聚集態的性質完全不同，它可以在整個可行解空間中進行搜索，因而量子PSO算法的全局搜索性能遠遠優于一般的PSO算法。

遵循PSO算法的思想，粒子的狀態在量子空間中不再用位置矢量和速度矢量表示，而是用波函數來描述。由于測不準原理，粒子的位置和速度不能同時精確測定，可以不考慮速度，而在空間表象中考查粒子。粒子出現在位置x的概率就由概率密度函數表示，而不限于既定的軌道函數。

取決于勢阱能量強度的參數L(t+1)=2α×|p-x(t)|指定了一個粒子的搜索范圍。從L的表達式可以看出，將一個粒子的最好位置p_i應用于整個種群是不明智的，因為當種群數目較小時，一個粒子不穩定和參差不齊的收斂速度將導致算法早熟。此時引入mbest（Mean Best Position， 平決最好位置）概念作為所有粒子的重心[5]，即

其中M是種群數目，P_i是第i個粒子的最好位置，這樣L的值就表示成L(t+1)=2β×|mbest*-x(t)|。可以看出在這個算法中只有唯一的參數，即創造系數β，其影響單個粒子的收斂速度和算法性能。對于評價一個粒子適應值至關重要的粒子位置，由概率密度函數經蒙特卡羅隨機模擬方法可以得到x(t)=p±L/2ln(1/u)。將參數L代入， 量子粒子群演化的迭代方程為

2 實驗仿真

2.1 實驗設置

下面將通過計算機仿真來評價本文所提出的基于量子粒子群算法的整數規劃的性能，測試函數F₁—F₇如表1所示。各函數所對應的維數、種群數目和最大迭代次數如表2所示。

算法的初始化參數如下：初始種群均勻分布在[-100，100]D。其中D是對應測試函數的維數。為了評價算法的性能，每個測試函數將被重復運行50次，并記錄所得正確解的成功率和每個測試函數的平均迭代次數。種群中的每個粒子將分別遵循PSO算法式（2）和QPSO算法式（8）進行演化，并將所得結果值截至整數。

2.2 PSO算法設置

仿真實驗中PSO算法的學習因子φ₁=φ₂=2，慣性參數ω在三個不同的區間[1.2，0.4]、[1.0，0.4]、[0.8，0.4]內都隨迭代次數的增加而線性減少。

2.3 QPSO算法設置

QPSO算法僅有一個參數，即創造系數β，它在三個不同區間[1.2，0.4]、[1.0，0.4]、[0.8，0.4]內均隨迭代次數的增加而線性減少。

2.4 實驗結果分別用PSO算法和QPSO算法來測試函數F₁—F₇的實驗結果如表3和表4所示。從成功率角度來看，PSO算法當ω從1.0—0.4線性減小時為最佳選擇；而對QPSO算法，β取區間[1.2，0.4]要優于其他兩個區間。

然而如表5所示，基于100%成功率的基礎上，從平均迭代次數來看，大多數情況下QPSO要比PSO更快地到達正確解。但對于測試函數F1，當維數達到高維時結果顯示PSO迭代次數要小于QPSO算法，這可能是由于QPSO算法更適應全局搜索，尤其是高維、多粒子的緣故。

測試函數的收斂性如圖1所示，橫坐標表示迭代次數，縱坐標表示測試函數值。圖1表明QPSO算法在大多數情況下更快更早于PSO算法搜索到最優解。

3 結束語

通過幾個測試函數的仿真實驗表明，PSO算法和QPSO算

法經過適當的ω和β參數設置均可以有效地解決整數規劃問題，并在搜索過程中沒有出現早熟現象，而QPSO算法在大多數情況下更快更早于PSO算法搜索到最優解。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。