摘  要： 針對(duì)整數(shù)規(guī)劃問(wèn)題的特點(diǎn)，在對(duì)模擬諧振子算法進(jìn)行分析的基礎(chǔ)上，將其應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題。通過(guò)參數(shù)設(shè)置以及在不同階段使用不同的新解產(chǎn)生方法，使全局尋優(yōu)與局部尋優(yōu)較好地結(jié)合。實(shí)驗(yàn)結(jié)果驗(yàn)證了算法應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題，可以提高搜索效率和精度。
關(guān)鍵詞： 整數(shù)規(guī)劃；模擬諧振子；全局尋優(yōu)；局部尋優(yōu)

　整數(shù)規(guī)劃作為規(guī)劃論的一個(gè)分支，是運(yùn)籌學(xué)中的一個(gè)重要內(nèi)容。整數(shù)規(guī)劃問(wèn)題廣泛應(yīng)用于工程領(lǐng)域與管理領(lǐng)域，如資源管理、生產(chǎn)調(diào)度、可靠性優(yōu)化、目標(biāo)分配、資本預(yù)算、股票分析、超大規(guī)模集成電路設(shè)計(jì)等[1-2]。
　對(duì)于變量規(guī)模較小的整數(shù)規(guī)劃問(wèn)題，傳統(tǒng)的求解方法有分支定界法、割平面法和隱枚舉法等。但對(duì)于較大規(guī)模的問(wèn)題，傳統(tǒng)方法的計(jì)算非常耗時(shí)且結(jié)果常不能令人滿意，如經(jīng)常采用的方法是把用線性規(guī)劃方法所求得的非整數(shù)解進(jìn)行取整處理，而這在實(shí)際工作中所得到的解可能不是原問(wèn)題的可行解或整數(shù)最優(yōu)解。參考文獻(xiàn)[3]在傳統(tǒng)的分支定界法的基礎(chǔ)上，提出了新的切割與分支算法進(jìn)行求解，但由于在分支過(guò)程中采用的是經(jīng)典的分支定界算法，故其效率仍受到分支準(zhǔn)則的影響。近年來(lái)，許多學(xué)者應(yīng)用遺傳算法、模擬退火算法、粒子群優(yōu)化算法、蟻群優(yōu)化算法等方法求解整數(shù)規(guī)劃問(wèn)題[1-2，4]，取得了一定的效果，但問(wèn)題規(guī)模較大時(shí)，在收斂的最優(yōu)性和收斂速度方面仍有改進(jìn)的必要。
　模擬諧振子SHO（Simulated Harmonic Oscillator）算法是近來(lái)提出的新的智能算法，目前已在解決旅行商問(wèn)題、多項(xiàng)目調(diào)度問(wèn)題時(shí)表現(xiàn)出了良好的效果[5-6]，但在其他領(lǐng)域的應(yīng)用尚待研究和實(shí)踐。本文將其應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題，通過(guò)設(shè)定振幅、初始步長(zhǎng)、基態(tài)步長(zhǎng)，確定差解接受規(guī)則、步長(zhǎng)變化規(guī)則，控制各階段的最大計(jì)算次數(shù)和解無(wú)變化次數(shù)的上限，以及在不同階段使用不同的新解產(chǎn)生方法，使全局尋優(yōu)與局部尋優(yōu)較好地結(jié)合。測(cè)試結(jié)果表明了該算法應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題，當(dāng)問(wèn)題規(guī)模較大時(shí)具有高質(zhì)量的搜索效率和精度。
1 SHO算法簡(jiǎn)介
　SHO算法是由模擬自然諧振子運(yùn)動(dòng)的物理規(guī)律演化而來(lái)的一種通用的隨機(jī)搜索算法。簡(jiǎn)諧振動(dòng)系統(tǒng)中，彈簧質(zhì)點(diǎn)在由端點(diǎn)運(yùn)動(dòng)到平衡點(diǎn)的過(guò)程中，其位置狀態(tài)與勢(shì)能狀態(tài)一一對(duì)應(yīng)。由于質(zhì)點(diǎn)的運(yùn)動(dòng)是連續(xù)的，故其一定會(huì)經(jīng)過(guò)系統(tǒng)的每個(gè)位置狀態(tài)。對(duì)應(yīng)地，系統(tǒng)的整個(gè)勢(shì)能空間也將被遍歷。如果將質(zhì)點(diǎn)的位置狀態(tài)對(duì)應(yīng)于優(yōu)化問(wèn)題中的某個(gè)解狀態(tài)，則理論上通過(guò)遍歷質(zhì)點(diǎn)位置狀態(tài)就可以遍歷優(yōu)化問(wèn)題的解空間，從而求得最優(yōu)解。

　算法分為初始化過(guò)程、經(jīng)典簡(jiǎn)諧振動(dòng)過(guò)程和在基態(tài)附近的量子簡(jiǎn)諧振動(dòng)過(guò)程。對(duì)于一個(gè)計(jì)算問(wèn)題的求解，算法首先在解空間以一定的次數(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)解的趨近。算法的基本步驟見(jiàn)參考文獻(xiàn)[5]。

　SHO算法作為一種通用的智能算法，其應(yīng)用于求解整數(shù)規(guī)劃問(wèn)題的特定領(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)用于劃分問(wèn)題的能級(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ī)則跳躍，也可以逐步衰減（衰減方式的選擇依賴于具體問(wèn)題）。對(duì)于此階段的求解整數(shù)規(guī)劃問(wèn)題，振幅應(yīng)選取為某個(gè)變量的取值范圍，初始步長(zhǎng)的取值為振幅的倍數(shù)（倍數(shù)的大小與變量的規(guī)模和取值范圍有關(guān)），基態(tài)步長(zhǎng)取正整數(shù)1為宜。諧振子端點(diǎn)與振源通過(guò)一定次數(shù)的隨機(jī)取解粗略確定（計(jì)算過(guò)程中最大的目標(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ī)劃問(wèn)題，這些新解產(chǎn)生方法并不適用，需要重新設(shè)計(jì)。在解的生成上，利用隨機(jī)函數(shù)產(chǎn)生新解是一種常用的方法，但是要得到高精度的解則需要很大的計(jì)算次數(shù)，特別是當(dāng)變量規(guī)模較大時(shí)。在求解整數(shù)規(guī)劃問(wèn)題的新解產(chǎn)生方法的設(shè)計(jì)中，初始化階段以及全局尋優(yōu)的前期階段使用了利用隨機(jī)函數(shù)產(chǎn)生新解的方法；當(dāng)步長(zhǎng)L=2時(shí)，設(shè)計(jì)了通過(guò)利用隨機(jī)函數(shù)確定當(dāng)前最小解的某個(gè)分量并對(duì)其值分別作減3、增3、減2、增2的擾動(dòng)產(chǎn)生新解的方法，該方法可以在全局搜索的后期加快收斂速度并提高精度；當(dāng)步長(zhǎng)L=1時(shí)，設(shè)計(jì)了通過(guò)利用隨機(jī)函數(shù)確定當(dāng)前最小解的某個(gè)分量并對(duì)其值分別作減1、增1擾動(dòng)產(chǎn)生新解的方法，該方法適宜于基態(tài)時(shí)的局部尋優(yōu)。通過(guò)測(cè)試對(duì)比，設(shè)計(jì)的這些新解產(chǎn)生方法，比較適合整數(shù)規(guī)劃問(wèn)題的求解。

　差解接受規(guī)則表明，當(dāng)新解與整個(gè)勢(shì)能的比例小于近似基態(tài)能級(jí)占整個(gè)勢(shì)能的比例（或者說(shuō)當(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ī)劃問(wèn)題的SHO算法的步驟設(shè)計(jì)如下：
　（1）設(shè)定振幅A的值為某個(gè)變量的取值范圍的長(zhǎng)度、初始步長(zhǎng)L0的值為振幅的倍數(shù)、基態(tài)步長(zhǎng)LS的值為1，步長(zhǎng)變化規(guī)則采用逐步遞減的方式（通過(guò)L0遞減實(shí)現(xiàn)）。同時(shí)，分別設(shè)定在確定振源和端點(diǎn)、步長(zhǎng)L∈[Ls，L0]階段、L=2以及L=1時(shí)求解的最大計(jì)算次數(shù)和解無(wú)變化次數(shù)的上限。
　（2）利用隨機(jī)函數(shù)產(chǎn)生新解s，以目標(biāo)函數(shù)值f（s）最大的為端點(diǎn)End，最小的為振源Init。如果未達(dá)到此階段設(shè)定的最大計(jì)算次數(shù)或解無(wú)變化次數(shù)的上限，則繼續(xù)步驟（2）的操作。

　算法采用Java語(yǔ)言編程實(shí)現(xiàn)，開(kāi)發(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)通過(guò)L0遞減的方式實(shí)現(xiàn)變化。以尋找到全局最優(yōu)點(diǎn)為收斂標(biāo)準(zhǔn)。規(guī)定最大迭代次數(shù)為10 000次，否則稱為不收斂。其中，確定振源和端點(diǎn)階段最大計(jì)算次數(shù)為200，控制解無(wú)變化次數(shù)的上限為100；L∈[Ls，L0]階段最大求解次數(shù)為500，控制解無(wú)變化次數(shù)的上限為200；L=2階段最大計(jì)算次數(shù)為500，控制解無(wú)變化次數(shù)的上限為200；L=1階段控制解無(wú)變化次數(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中“－”表示該種情況，算法不完全收斂，該項(xiàng)指標(biāo)無(wú)法統(tǒng)計(jì)。表1顯示出本文所設(shè)計(jì)的應(yīng)用于整數(shù)規(guī)劃問(wèn)題的SHO算法在收斂的最優(yōu)性和收斂速度方面均具有較好的性能，特別是當(dāng)變量規(guī)模較大時(shí)，而且算法的穩(wěn)定性較好，維數(shù)與變量取值區(qū)間的變化對(duì)計(jì)算結(jié)果所造成的波動(dòng)不大。
　對(duì)于變量規(guī)模較大的整數(shù)規(guī)劃問(wèn)題的求解，傳統(tǒng)方法存在計(jì)算耗時(shí)與誤差大的問(wèn)題，而一些智能計(jì)算方法在收斂的最優(yōu)性和收斂速度方面也存在不足。本文在SHO算法的基礎(chǔ)上，設(shè)計(jì)了針對(duì)整數(shù)規(guī)劃問(wèn)題求解的SHO算法并進(jìn)行實(shí)驗(yàn)。從實(shí)驗(yàn)結(jié)果及對(duì)比可以看出，SHO算法巧妙地將簡(jiǎn)諧振動(dòng)思想應(yīng)用于求解復(fù)雜問(wèn)題，將全局搜索與局部搜索進(jìn)行了較完美的結(jié)合，具有較高的解質(zhì)量，并且算法的時(shí)間代價(jià)小，應(yīng)用是可行的。
參考文獻(xiàn)
[1] 高尚，楊靜宇．群智能算法及其應(yīng)用[M]．北京：中國(guó)水利水電出版社，2006.
[2] 譚瑛，高慧敏，曾建潮．求解整數(shù)規(guī)劃問(wèn)題的微粒群算法[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.