模擬諧振子算法在求解整數(shù)規(guī)劃問題中的應(yīng)用

姚明

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

整數(shù)規(guī)劃作為規(guī)劃論的一個分支，是運籌學中的一個重要內(nèi)容。整數(shù)規(guī)劃問題廣泛應(yīng)用于工程領(lǐng)域與管理領(lǐng)域，如資源管理、生產(chǎn)調(diào)度、可靠性優(yōu)化、目標分配、資本預(yù)算、股票分析、超大規(guī)模集成電路設(shè)計等[1-2]。

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

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

1 SHO算法簡介

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

在簡諧振動系統(tǒng)中，彈簧質(zhì)點處于平衡點時彈性勢能最?。ㄆ渲禐?），在任意一個端點時彈性勢能最大為系統(tǒng)總能量?？筛鶕?jù)質(zhì)點到平衡點的距離，將系統(tǒng)劃分為多個能量等級。設(shè)振幅為A，某個能級處質(zhì)點離平衡點的相對位移為x，系統(tǒng)勢能被劃分為A個等級，可以證明，在彈簧質(zhì)點與平衡點的距離成等差數(shù)列形式變化的情況下，簡諧振動系統(tǒng)的勢能能級以遞減的方式進行；另外，從量子物理的角度看諧振子即微觀振動，當諧振子系統(tǒng)位于能量最低的基態(tài)時，波函數(shù)為高斯函數(shù)，此時可認為解將會以高斯分布方式出現(xiàn)[5]。由此可知，彈簧質(zhì)點離平衡點越近，能級差越??；當算法系統(tǒng)的最終目標達到系統(tǒng)基態(tài)時，最有可能找到最優(yōu)解。

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

2 求解整數(shù)規(guī)劃的SHO算法

整數(shù)規(guī)劃問題可描述為[1]：

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

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

2.1 算法參數(shù)初始化

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

2.2 新解產(chǎn)生方法

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

2.3 差解接受規(guī)則

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

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

2.4 算法步驟

求解整數(shù)規(guī)劃問題的SHO算法的步驟設(shè)計如下：

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

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

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

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

3 實例計算

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

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

表1 f1（x）、f2（x）計算結(jié)果

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

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

參考文獻

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

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

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

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

[5]王鵬.云計算的關(guān)鍵技術(shù)與應(yīng)用實例[M].北京：人民郵電出版社，2010.

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