謝 瑜1，高曉智1，2

（1.上海海事大學 信息工程學院，上海 201306； 2.阿爾托大學 自動化與系統(tǒng)技術系，芬蘭 赫爾辛基 FI-00076）

　　摘  要： 整數(shù)規(guī)劃是NP困難（Non-deterministic Polynomial-time hard，NP-hard）的經(jīng)典問題之一。整數(shù)規(guī)劃的花授粉算法（Integer Flower Pollination Algorithm，IFPA）是采用截斷取整的方法，將最近開發(fā)的花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）擴展到求解整數(shù)規(guī)劃問題。通過對測試函數(shù)集進行仿真實驗，結果表明IFPA擁有很好的性能和很強的全局尋優(yōu)能力，可以作為一種實用方法用于求解約束整數(shù)規(guī)劃" title="無約束整數(shù)規(guī)劃" target="_blank">無約束整數(shù)規(guī)劃和有約束整數(shù)規(guī)劃問題。

　　關鍵詞： 無約束整數(shù)規(guī)劃；約束整數(shù)規(guī)劃；測試函數(shù)；花授粉算法；最優(yōu)化

0 引言

　　整數(shù)規(guī)劃問題是運籌學中的一個重要研究課題，它廣泛存在于各個領域，如機械、化工、經(jīng)濟、生物、軍事等。

　　對于變量維數(shù)較小的整數(shù)規(guī)劃問題，傳統(tǒng)的求解方法[1]有分支界定法、割平面法以及將兩者結合起來的分支割平面算法、隱枚舉法等；對于較大規(guī)模的問題，傳統(tǒng)的計算方法比較耗時，通常先采用實數(shù)域的一些優(yōu)化算法，再將計算結果進行取整后作為整數(shù)規(guī)劃的近似解。但在實際應用中，取整運算常常導致約束的不滿足或遠離最優(yōu)解。進化計算方法提出以后，已有許多學者應用遺傳算法、蜂群算法[2]、粒子群算法[3-5]等求解整數(shù)規(guī)劃問題。

　　花授粉算法[6]（Flower Pollination Algorithm，F(xiàn)PA）是劍橋大學的Yang Xinshe受啟發(fā)于花授粉過程提出的一種具有全局收斂的新型搜索算法，該算法主要優(yōu)點是參數(shù)少、操作簡單、易實現(xiàn)、隨機搜索路徑和尋優(yōu)能力強等。目前，對花授粉算法的研究還處于起步階段，主要集中在連續(xù)函數(shù)的優(yōu)化問題[6-7]。

　　本文的主要目的是拓展連續(xù)函數(shù)優(yōu)化中的花授粉算法，從而開發(fā)出整數(shù)規(guī)劃的花授粉算法（Integer Flower Pollination Algorithm，IFPA）。通過仿真實驗驗證了所提算法的有效性，結果表明該算法具有良好的全局尋優(yōu)能力和良好的收斂速度。

1 基本花授粉算法

　　1.1 花授粉的特性

　　花授粉可以采取兩種主要形式：非生物傳粉和生物傳粉。約90％的花卉屬于生物授粉，約10％的授粉采取非生物形式，不需要任何傳粉者。傳粉者是非常多樣的。據(jù)估計，至少有兩百萬種傳粉者，它們也可以開發(fā)出所謂的花恒常。即這些傳粉者往往只拜訪某種特定的花卉品種，而繞過其他花種。

　　授粉可以通過自花授粉或異花授粉來實現(xiàn)。異花授粉意味著授粉可發(fā)生于不同植物的花粉，而自花授粉是一朵花的受精來自同一種植物的同一朵或不同朵花的花粉，如桃花。

　　異花生物授粉可能發(fā)生在長距離的情況，并且傳粉者如蜜蜂、鳥類以及蒼蠅能飛很長的距離，因此，它們可以被看作是全局授粉。此外，蜜蜂和鳥類可能表現(xiàn)為萊維飛行行為，其飛行步長服從萊維分布[8]。根據(jù)兩朵花的相似性或差異性，花恒?？梢员挥米鲆粋€步長增量。

　　1.2 花授粉算法

　　花授粉算法是受啟發(fā)于開花植物的花授粉過程，已經(jīng)擴展到多目標的優(yōu)化。為了模擬該過程，需要做以下假設：

　?。?）生物異花授粉被認為是全局授粉過程，且傳粉者以萊維飛行的方式傳粉。

　?。?）非生物自花授粉被認為是局部授粉。

　?。?）花恒常可以被認為是正比于某兩朵相似性的繁殖概率。

　　（4）局部授粉和全局授粉由轉移概率P∈[0，1]控制。由于物理的近似性和其他因素（例如風），局部授粉在整體授粉活動中有顯著的偏重P。

　　基于以上假設，可以給出基本FPA的更新方程。在全局授粉中，花粉通過傳粉者（例如昆蟲）傳播，并且花粉可移動很長的距離。因此，假設（1）和（3）可以用數(shù)學公式表示為：

　　其中，x是花粉i在迭代次數(shù)t下的位置矢量，g*是當前所有位置中的最優(yōu)，γ是控制移動步長的比例因子。這里L（λ）是表示花粉強度的參數(shù)，使基于萊維飛行的步長大小更具體。因為昆蟲可以以不同的距離步長移動很長的距離，因此萊維飛行可用于有效地模擬這種特性。L>0的萊維分布為：

　　其中Γ（λ）是標準伽馬函數(shù)，其分布對較大步長s>0是有效的。理論上須|s0|>>0，但是實際上s0可以小至0.1。產(chǎn)生步長最有效的方法是曼特尼亞算法，通過使用兩個高斯分布的U和V變換計算步長大小s：

　　這里U~N（0，σ2）是指高斯正態(tài)分布具有零均值和σ2的方差。方差可由下式計算：

　　對于一個給定λ，σ2是一個常數(shù)。

　　在數(shù)學上已經(jīng)證明了曼特尼亞算法可以產(chǎn)生服從萊維分布的偽隨機樣本。參考文獻[7]中使用該偽隨機數(shù)的算法繪制了一個連續(xù)50步大小的萊維飛行，如圖1所示。

　　對于局部授粉，假設（2）和（3）均可表示為：

　　這里表示同一品種不同花上的花粉。這實質上是模仿有限鄰里的花恒常。在數(shù)學上，如果是在同一品種或同一群體中選擇出來的，并定義ε是在[0，1]上的均勻分布，則局部授粉即為局部的隨機游走。

　　大多數(shù)花授粉活動都可以發(fā)生在局部和全局范圍。在實踐中，相鄰或附近的花相比于距離較遠的花更容易被局部授粉。大多數(shù)情況下，P=0.8時可取得較好結果?；ㄊ诜鬯惴ǖ幕静襟E可以概括為偽代碼如下：

　　目標函數(shù)f（x），x=（x1，…，xd）T

　　初始花粉種群xi（i=1，2，…，n）和vi（i=1，2，…，n）

　　尋找初始種群中的當前最優(yōu)值g*

　　定義轉移概率P∈[0，1]

　　While（t>誤差容量）

　　for i=1：n（種群中所有的n個花粉）

　　if rand<p

　　取一個遵守萊維飛行的步長矢量L（d維）；

　　通過更新所有花粉的位置；

　　邊界約束檢查；

　　else

　　取一個服從均勻分布的ε；

　　在所有解決方案（花粉）中隨機選擇j和k；

　　通過更新局部花粉的位置；

　　邊界約束檢查；

　　end if

　　評價所有新的解；

　　如果新的解較好，接受新的解；

　　end for

　　end while

　　2 整數(shù)規(guī)劃的花授粉算法

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

　　min/maxf（x），x∈S?哿Zd（6）

　　其中Zd為所有d維格子點組成的點集，S為問題的所有可行解集。在求解過程中，可采取兩種截斷取整的方法：一是在循環(huán)迭代的過程中，先將每個花粉的位置進行取整操作，然后計算其對應的函數(shù)值，此外的其他過程則完全與連續(xù)域函數(shù)優(yōu)化的過程一致；二是保持連續(xù)域函數(shù)優(yōu)化的過程，只在比較和評價目標函數(shù)值的過程中，對花粉位置取整并計算取整后的位置所對應的目標函數(shù)適應值。

　　經(jīng)實驗驗證，第二種方法的效果明顯優(yōu)于第一種方法。所以，將第二種方法的思想應用到基本FPA中，可得本文提出的整數(shù)規(guī)劃的花授粉算法。其主要步驟如下：

　　（1）參數(shù)和種群初始化。迭代次數(shù)t=0，給定種群數(shù)量n，局部授粉和全局授粉的轉移概率P。然后隨機產(chǎn)生一個種群，產(chǎn)生方式為：

　　x=low（j）+（ub（j）-lb（j））×rand（），i=1，2，…，n，j=1，2，…，d（7）

　　其中，“0”表示第0函數(shù)，d為待優(yōu)化函數(shù)f（x）所含決策變量的個數(shù)，即維數(shù)。

　?。?）計算目標函數(shù)適應值。令X=round（x），分別計算x對應的目標函數(shù)適應值fit（i）=f（xi0）和Fit（i）=f（Xi0）。這里，xi0和Xi0均為d維行向量，fit和Fit均為n維行向量。分別找出fit和Fit中最好的元素（即最小的元素）及其對應的可行解，將fit和Fit中最好的元素分別記為fitbest和Fitbest，fitbest和Fitbest分別對應的可行解記為xbest和Xbest。

　?。?）判斷是否滿足算法結束條件，如果滿足，即Fitbest等于全局最優(yōu)值時，則轉步驟（8），否則，轉步驟（4）。

　?。?）利用轉移概率P與一個隨機產(chǎn)生的介于0和1之間的隨機數(shù)比較結果，實現(xiàn)對種群位置的再次更新：當隨機數(shù)大于P時利用式（1）對種群位置進行更新，否則利用式（2）更新。

　?。?）利用步驟（2）中方法，計算種群中每個花粉對應的目標函數(shù)適應值，即確定fitbest、Fitbest、xbest和Xbest。

　?。?）評價當前目標函數(shù)值Fitbest，并與歷史最優(yōu)函數(shù)值比較，確定當前迭代最優(yōu)函數(shù)值。

　?。?）轉步驟（3）。

　?。?）輸出尋優(yōu)得到的結果。

3 實例驗證

　　以下實驗過程的運行環(huán)境是Window7系統(tǒng)下的MATLAB2013a。選擇參考文獻[9]中的測試函數(shù)來驗證所提出的IFPA在無約束整數(shù)規(guī)劃問題中的應用；選擇參考文獻[5]中的實例來驗證IFPA在約束整數(shù)規(guī)劃問題中的應用。

　　3.1無約束整數(shù)規(guī)劃測試函數(shù)

　　f1（x）=100（x2-x12）+（1-x1）2（8）

　　最優(yōu)解為x*=（1，1），對應的最優(yōu)值為f1（x*）=0。

　　f2（x）=（9x12+2x22-11）2+（3x12+4x22-7）2（9）

　　最優(yōu)解為x*=（1，1），對應的最優(yōu)值為f2（x*）=0。

　　f3（x）=（x1+10x2）2+5（x3-x4）2+（x2-2x3）4+10（x1-x4）4（10）

　　最優(yōu)解為x*=（0，0，0，0），對應的最優(yōu)值為f3（x*）=0。

　　f4（x）=-3 803.84-138.08x1-232.92x2+123.08x12+203.64x22+182.25x1x2（11）

　　最優(yōu)解為x*=（0，1），對應的最優(yōu)值為f4（x*）=-3 833.12。

　　f5（x）=‖x‖1=|x1|+|x2|+…+|xd|（12）

　　最優(yōu)解為xi*=0，i=1，2，…，d，對應的最優(yōu)值為f5（x*）=0。

　　f6（x）=xTx=x12+x22+…+xd2（13）

　　最優(yōu)解為xi*=0，i=1，2，…，d，對應的最優(yōu)值為f6（x*）=0。

　　f7（x）=2x12+3x22+4x1x2-6x1-3x2（14）

　　最優(yōu)解為xi*=0，i=1，2，…，d，對應的最優(yōu)值為f9（x*）=0。

　　f10（x）=100（x2-x12）2+90（x4-x32）2+（1-x3）2+10.1（x2-1）2+19.8（x2-1）（x4-1）（17）

　　最優(yōu)解為x*=（1，1，1，1，1），對應的最優(yōu)值為f10（x*）=0。

　　f11（x）=（1.5-x1（1-x2））2+（2.25-x1（1-x22））2+（2.625- x1（1-x23））2（18）

　　最優(yōu)解為x*=（2，0），對應的最優(yōu)值為f11（x*）=0.703 13。

　　f12（x）=（x12+x2-11）2+（x22+x1-7）2（19）

　　最優(yōu)解為x*=（3，2），對應的最優(yōu)值為f12（x*）=0。

　　在給定誤差容量為10-5時，用整數(shù)花授粉算法來找到以上實例中各函數(shù)的最優(yōu)解。IFPA中種群規(guī)模n取為40，其轉移概率P取0.8，該算法獨立運行20次。

　　實驗統(tǒng)計指標有7個，前三個是20次獨立運行所得目標函數(shù)值的最好值、平均值及最差值；第四到第六個包括這20次成功尋優(yōu)中使用的最小迭代次數(shù)、平均迭代次數(shù)、最大迭代次數(shù)；最后一個指標是20次獨立循環(huán)消耗的總時間（單位：s）?；ㄊ诜鬯惴ǖ倪\行結果見表1。

　　由表1可以看出，IFPA具有較強的全局搜索能力，能夠在更短的時間范圍內(nèi)收斂到全局最優(yōu)值，即IFPA可以很好地解決無約束整數(shù)規(guī)劃問題。

　　3.2 有約束整數(shù)規(guī)劃

　　花授粉算法不僅可以解決無約束整數(shù)規(guī)劃問題，同樣可以解決有約束的整數(shù)規(guī)劃問題。

　　實例1：

　　maxf（x）=3x1+2x2

　　s.t.2x1+3x2≤2 0054x1+x2≤3 001x1，x2≥0，x1，x2∈Z

　　理論上，該線性整數(shù)規(guī)劃的最優(yōu)解為（700，201），最優(yōu)值為2 502。若去掉整數(shù)的約束，則線性規(guī)劃的最優(yōu)解為（699.8，201.8）。利用IFPA可以很容易找到與理論相同的解x*=（700，201），f（x*）=2 502。程序仿真時，每次迭代的最優(yōu)值隨迭代次數(shù)的函數(shù)關系如圖2所示。

　　從圖2可見，前270代當前最優(yōu)值呈上升趨勢，花授粉算法對有約束非線性整數(shù)規(guī)劃的求解有很快的收斂速度。

　　實例2：

　　maxf（x）=x12+x22+3x32+4x42+2x52-8x1-2x2-3x3-x4-2x5

　　s.t.x1+x2+x3+x4+x5≤400x1+2x2+2x3+x4+6x5≤8002x1+x2+6x3≤200x3+x4+5x5≤2000≤xi≤99（i=1，…，5）

　　理論上，該非線性整數(shù)規(guī)劃的最優(yōu)解為（50，99，0，99，20），最優(yōu)值為51 568。利用IFPA很容易找到與理論相同的解x*=（50，99，0，99，20），f（x*）=51 568。該實例仿真函數(shù)關系如圖3所示。

　　從圖3中前140代當前最優(yōu)值的上升趨勢來看，可行域內(nèi)的整數(shù)規(guī)劃花授粉算法對有約束非線性整數(shù)規(guī)劃的求解也有很快的收斂速度。

4 結論

　　在工程和工業(yè)中解決整數(shù)規(guī)劃問題往往是具有挑戰(zhàn)性的，因此需要特殊的技術來解決。近年來，啟發(fā)式方法已經(jīng)顯示出其前景并得到了普及。本文提出了一種整數(shù)規(guī)劃的花授粉算法（IFPA），將最近提出的花授粉算法拓展到解決整數(shù)規(guī)劃的問題中。經(jīng)過標準測試函數(shù)和實例的驗證，說明了該算法能夠很好地解決有約束整數(shù)規(guī)劃和無約束整數(shù)規(guī)劃問題。

參考文獻

　　[1] 杜枯康，英凱.整數(shù)規(guī)劃問題智能求解算法綜述[J].計算機應用研究，2010，27（2）：408-412.

　　[2] LIU Y， MA L． Bee colony foraging algorithm for integer programming[C]. Business Management and Electronic Information（BMEI）， 2011 International Conference on． IEEE，2011，5： 199-201．

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

　　[4] 高尚，楊靜宇．非線性整數(shù)規(guī)劃的粒子群優(yōu)化算法[J].計算機應用，2007，28（2）：126-130．

　　[5] 祁輝，熊鷹，周樹民.基于粒子群算法的整數(shù)規(guī)劃問題的求解算法[J].江漢大學學報，2009，37（1）：25-29．

　　[6] YANG X S. Flower pollination algorithm for global optimization[J]. In Unconventional Computation and Natural Computation， 2012，7445：240-249.

　　[7] YANG X S， KARAMANOGLU M， HE X S. Multi-objective flower algorithm for optimization[J]. Procedia Computer Science，2013（18）：861-868.

　　[8] YANG X S. Review of Meta-heuristics and generalised evolutionary walk algorithm[J]. International Journal of Bio-Inspired Computation，2011，3 （2）：77-84.

　　[9] 吳炅，健勇.整數(shù)規(guī)劃的布谷鳥算法[J].學理論與應用，2013，33（3）：99-106.