姚明

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

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

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

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

1 SHO算法簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

2.3 差解接受規(guī)則

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

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

2.4 算法步驟

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

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

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

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

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

3 實(shí)例計(jì)算

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

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

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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