模擬諧振子算法在求解整數規劃問題中的應用

姚明

（廣東石油化工學院 計算機科學與技術系，廣東 茂名 525000）

整數規劃作為規劃論的一個分支，是運籌學中的一個重要內容。整數規劃問題廣泛應用于工程領域與管理領域，如資源管理、生產調度、可靠性優化、目標分配、資本預算、股票分析、超大規模集成電路設計等[1-2]。

對于變量規模較小的整數規劃問題，傳統的求解方法有分支定界法、割平面法和隱枚舉法等。但對于較大規模的問題，傳統方法的計算非常耗時且結果常不能令人滿意，如經常采用的方法是把用線性規劃方法所求得的非整數解進行取整處理，而這在實際工作中所得到的解可能不是原問題的可行解或整數最優解。參考文獻[3]在傳統的分支定界法的基礎上，提出了新的切割與分支算法進行求解，但由于在分支過程中采用的是經典的分支定界算法，故其效率仍受到分支準則的影響。近年來，許多學者應用遺傳算法、模擬退火算法、粒子群優化算法、蟻群優化算法等方法求解整數規劃問題[1-2，4]，取得了一定的效果，但問題規模較大時，在收斂的最優性和收斂速度方面仍有改進的必要。

模擬諧振子 SHO （Simulated Harmonic Oscillator）算法是近來提出的新的智能算法，目前已在解決旅行商問題、多項目調度問題時表現出了良好的效果[5-6]，但在其他領域的應用尚待研究和實踐。本文將其應用于求解整數規劃問題，通過設定振幅、初始步長、基態步長，確定差解接受規則、步長變化規則，控制各階段的最大計算次數和解無變化次數的上限，以及在不同階段使用不同的新解產生方法，使全局尋優與局部尋優較好地結合。測試結果表明了該算法應用于求解整數規劃問題，當問題規模較大時具有高質量的搜索效率和精度。

1 SHO算法簡介

SHO算法是由模擬自然諧振子運動的物理規律演化而來的一種通用的隨機搜索算法。簡諧振動系統中，彈簧質點在由端點運動到平衡點的過程中，其位置狀態與勢能狀態一一對應。由于質點的運動是連續的，故其一定會經過系統的每個位置狀態。對應地，系統的整個勢能空間也將被遍歷。如果將質點的位置狀態對應于優化問題中的某個解狀態，則理論上通過遍歷質點位置狀態就可以遍歷優化問題的解空間，從而求得最優解。

在簡諧振動系統中，彈簧質點處于平衡點時彈性勢能最小（其值為0），在任意一個端點時彈性勢能最大為系統總能量。可根據質點到平衡點的距離，將系統劃分為多個能量等級。設振幅為A，某個能級處質點離平衡點的相對位移為x，系統勢能被劃分為A個等級，可以證明，在彈簧質點與平衡點的距離成等差數列形式變化的情況下，簡諧振動系統的勢能能級以遞減的方式進行；另外，從量子物理的角度看諧振子即微觀振動，當諧振子系統位于能量最低的基態時，波函數為高斯函數，此時可認為解將會以高斯分布方式出現[5]。由此可知，彈簧質點離平衡點越近，能級差越小；當算法系統的最終目標達到系統基態時，最有可能找到最優解。

算法分為初始化過程、經典簡諧振動過程和在基態附近的量子簡諧振動過程。對于一個計算問題的求解，算法首先在解空間以一定的次數查找端點和振源即近似的最差解和最優解，獲得系統的近似最大勢能。然后以基態步長為分界線，步長大于基態步長時為全局尋優階段，對應于經典諧振子的振動。此階段，算法在解空間隨機搜索近似最優解，并采用接受規則對差解進行取舍，這樣可使鄰域解在局部山峰間平行跳躍，從而有效控制算法全局搜索的隨意性并避免陷入局部搜索的陷阱。步長小于基態步長時為局部尋優階段，對應于量子諧振子的振動，此時系統總體處于平衡態附近的量子振動狀態，算法在解空間不會再有大的跳躍，對差解采用直接拋棄的策略，完成在基態附近向最優解的趨近。算法的基本步驟見參考文獻[5]。

2 求解整數規劃的SHO算法

整數規劃問題可描述為[1]：

其中 Z 為整數空間，ai，bi（i＝1，2，…，n）為整數，li=bi-ai+1為xi的可能取的個數。每個變量取一個值就構成一個解。

SHO算法作為一種通用的智能算法，其應用于求解整數規劃問題的特定領域時，在算法參數初始化、新解產生方法以及差解接受準則等方面需要有針對性地進行設置和定義。

2.1 算法參數初始化

SHO算法在初始化階段需要設置振幅、初始步長和基態步長，確定步長變化規則以及確定諧振子端點和振源。其中，初始步長用于劃分問題的能級并對應能級的最大處，其值代表著整個勢能空間范圍；基態步長代表某一較低的低能能級，其值代表著從基態到基態步長間能級總和；一個步長對應一個能級差，其變化可以為不規則跳躍，也可以逐步衰減（衰減方式的選擇依賴于具體問題）。對于此階段的求解整數規劃問題，振幅應選取為某個變量的取值范圍，初始步長的取值為振幅的倍數（倍數的大小與變量的規模和取值范圍有關），基態步長取正整數1為宜。諧振子端點與振源通過一定次數的隨機取解粗略確定（計算過程中最大的目標函數值對應的解為端點，最小的目標函數值對應的解為振源）。

2.2 新解產生方法

SHO算法的隨機性主要體現在新解的產生上。求解目的、搜索策略以及新解的搜索鄰域不同，產生新解的方法也不同。新解產生的方法對算法的效率與精度有較大的影響。產生新解的方法很多，SHO算法使用的方法有：均勻隨機法、2交換（2-opt）法、兩兩隨機交換法、隨機插入法[5]等。對于求解整數規劃問題，這些新解產生方法并不適用，需要重新設計。在解的生成上，利用隨機函數產生新解是一種常用的方法，但是要得到高精度的解則需要很大的計算次數，特別是當變量規模較大時。在求解整數規劃問題的新解產生方法的設計中，初始化階段以及全局尋優的前期階段使用了利用隨機函數產生新解的方法；當步長L＝2時，設計了通過利用隨機函數確定當前最小解的某個分量并對其值分別作減3、增3、減 2、增 2的擾動產生新解的方法，該方法可以在全局搜索的后期加快收斂速度并提高精度；當步長L＝1時，設計了通過利用隨機函數確定當前最小解的某個分量并對其值分別作減1、增1擾動產生新解的方法，該方法適宜于基態時的局部尋優。通過測試對比，設計的這些新解產生方法，比較適合整數規劃問題的求解。

2.3 差解接受規則

差解接受規則是算法的核心，可控制算法的收斂方向。由于初始步長L0的值代表著整個勢能空間范圍，基態步長LS的值代表著近似基態能級，又因為簡諧振動過程中勢能與距離的平方成正比，因此可用表示近似基態能級占整個勢能的比例。假定s為當前近似最優解，s′為通過新解產生方法得到的另一解，則 f（s）為當前解對應的勢能（其可近似為基態），f（s′）為新狀態的勢能，Δf＝f（s′）-f（s）可近似看成是新解勢能與基態的能級差；再假定 End 為端點，則 f（End）-f（s）可近似為整個勢能空間范圍，可看成是新解與整個勢能的比例。差解接受規則定義如下：

差解接受規則表明，當新解與整個勢能的比例小于近似基態能級占整個勢能的比例（或者說當新解相對勢能在近似基態能級范圍內）時，則接受新解（即使新解比當前解差），因為此時新解比舊解在能級上更低，符合算法尋找系統基態的目標要求。

2.4 算法步驟

求解整數規劃問題的SHO算法的步驟設計如下：

（1）設定振幅A的值為某個變量的取值范圍的長度、初始步長L0的值為振幅的倍數、基態步長LS的值為1，步長變化規則采用逐步遞減的方式（通過L0遞減實現）。同時，分別設定在確定振源和端點、步長 L∈[Ls，L0]階段、L＝2 以及 L＝1 時求解的最大計算次數和解無變化次數的上限。

（2）利用隨機函數產生新解 s，以目標函數值 f（s）最大的為端點 End，最小的為振源 Init。如果未達到此階段設定的最大計算次數或解無變化次數的上限，則繼續步驟（2）的操作。

（3）利用隨機函數產生一個新解 s′，計算Δf＝f （s′）-f （s）。 若 Δf≤0， 或 Δf＞0 且≥0，則接受并記憶s′為當前解。如果未達到此階段設定的最大計算次數或解無變化次數的上限，則 L0遞減，在 L0≥LS條件下繼續全局尋優；其中，當時L0＝2，新解通過利用隨機函數確定當前最小解的某個分量并對其值分別作減3、增 3、減 2、增 2的擾動產生。

（4）當步長 L＝1時，通過利用隨機函數確定當前最小解的某個分量并對其值分別作減1、增1擾動產生新解；若Δf≤0，則接受新解 s′為當前解。如果未達到此階段設定的最大計算次數或解無變化次數的上限，繼續局部尋優；否則，輸出當前解為近似最優解，算法結束。

3 實例計算

[1]中測試粒子群優化算法求解整數規劃所用的2個函數為例進行實例計算并對比。這些函數的全局最優點都是 xi＝0，fi（x）＝0。 另外，還將 f2（x）按與參考文獻[2]的設置進行計算對比。

算法采用Java語言編程實現，開發工具為Eclipse IDE for Java Developers （Version：Indigo Service Release 1），運行環境為 Java（TM）SE Runtime Environment（build 1.7.0_07-b10）。設振幅 A＝21，初始步長 L0為 A的 n倍，基態步長LS＝1，步長通過L0遞減的方式實現變化。以尋找到全局最優點為收斂標準。規定最大迭代次數為10 000次，否則稱為不收斂。其中，確定振源和端點階段最大計算次數為 200，控制解無變化次數的上限為 100；L∈[Ls，L0]階段最大求解次數為500，控制解無變化次數的上限為200；L＝2階段最大計算次數為 500，控制解無變化次數的上限為200；L＝1階段控制解無變化次數的上限為2 000。另外，在將 f2（x）按參考文獻[2]的設置進行計算時，修改 f2（x）變量取值范圍為-100≤xi≤100，并相應設振幅A＝201。對函數在維數為 15、20、30時的各種情況，算法均運行20次。其結果及對比如表1所示。

表1 f1（x）、f2（x）計算結果

表1中“－”表示該種情況，算法不完全收斂，該項指標無法統計。表1顯示出本文所設計的應用于整數規劃問題的SHO算法在收斂的最優性和收斂速度方面均具有較好的性能，特別是當變量規模較大時，而且算法的穩定性較好，維數與變量取值區間的變化對計算結果所造成的波動不大。

對于變量規模較大的整數規劃問題的求解，傳統方法存在計算耗時與誤差大的問題，而一些智能計算方法在收斂的最優性和收斂速度方面也存在不足。本文在SHO算法的基礎上，設計了針對整數規劃問題求解的SHO算法并進行實驗。從實驗結果及對比可以看出，SHO算法巧妙地將簡諧振動思想應用于求解復雜問題，將全局搜索與局部搜索進行了較完美的結合，具有較高的解質量，并且算法的時間代價小，應用是可行的。

參考文獻

[1]高尚，楊靜宇.群智能算法及其應用[M].北京：中國水利水電出版社，2006.

[2]譚瑛，高慧敏，曾建潮.求解整數規劃問題的微粒群算法[J].系統工程理論與實踐，2004，24（5）：126-129.

[3]高培旺.整數線性規劃的切割與分支算法[J].計算機工程與設計，2010，31（12）：2930-2932.

[4]楊榮華，劉建華.量子粒子群算法求解整數規劃的方法[J].科學技術與工程，2011，33（11）：8195-8198.

[5]王鵬.云計算的關鍵技術與應用實例[M].北京：人民郵電出版社，2010.

[6]倪霖，段超，鐘輝.基于模擬諧振子算法的多項目調度[J].計算機應用，2011，31（9）：2559-2562.