整數規劃的花授粉算法

謝瑜，高曉智，2（.上海海事大學信息工程學院，上海20306；2.阿爾托大學自動化與系統技術系，芬蘭赫爾辛基FI-00076）

整數規劃的花授粉算法

謝瑜1，高曉智1，2
（1.上海海事大學信息工程學院，上海201306；2.阿爾托大學自動化與系統技術系，芬蘭赫爾辛基FI-00076）

整數規劃是NP困難（Non-deterministic Polynomial-time hard，NP-hard）的經典問題之一。整數規劃的花授粉算法（Integer Flower Pollination Algorithm，IFPA）是采用截斷取整的方法，將最近開發的花授粉算法（Flower Pollination Algorithm，FPA）擴展到求解整數規劃問題。通過對測試函數集進行仿真實驗，結果表明IFPA擁有很好的性能和很強的全局尋優能力，可以作為一種實用方法用于求解無約束整數規劃和有約束整數規劃問題。

無約束整數規劃；約束整數規劃；測試函數；花授粉算法；最優化

0 引言

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

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

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

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

1 基本花授粉算法

1.1 花授粉的特性

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

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

異花生物授粉可能發生在長距離的情況，并且傳粉者如蜜蜂、鳥類以及蒼蠅能飛很長的距離，因此，它們可以被看作是全局授粉。此外，蜜蜂和鳥類可能表現為萊維飛行行為，其飛行步長服從萊維分布[8]。根據兩朵花的相似性或差異性，花恒常可以被用做一個步長增量。

1.2 花授粉算法

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

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

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

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

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

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

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

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

對于一個給定λ，σ2是一個常數。

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

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

圖1 連續50步萊維飛行

大多數花授粉活動都可以發生在局部和全局范圍。在實踐中，相鄰或附近的花相比于距離較遠的花更容易被局部授粉。大多數情況下，P=0.8時可取得較好結果。花授粉算法的基本步驟可以概括為偽代碼如下：

目標函數f（x），x=（x1，…，xd）T

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

尋找初始種群中的當前最優值g*

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

While（t>誤差容量）

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

if rand

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

邊界約束檢查；

else

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

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

邊界約束檢查；

end if

評價所有新的解；

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

end while

2 整數規劃的花授粉算法

整數規劃問題可描述為：

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

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

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

4.改革獲認可，取得良好社會效應。廣西稅務部門代征社會保險費改革試點工作開展以來，各級黨委政府高度重視，一直關注社會保險費代征工作進展和成效，對稅務部門代征社會保險費改革試點工作給予充分肯定。稅務部門提供多元化的繳費方式成為試點工作中繳費人最滿意的地方，試點工作取得了良好的社會效應。

其中，“0”表示第0代，lb（j）和ub（j）分別代表第j個決策變量的上下界，rand（）是一個產生0和1之間隨機數且滿足均勻分布的函數，d為待優化函數f（x）所含決策變量的個數，即維數。

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

最優解為xi*=0，i=1，2，…，d，對應的最優值為f6（x*）=0。最優解為x*=（2，-1），x*=（3，-2），x*=（4，-2），x*=（3，-1），對應的最優值為f7（x*）=-6。對應的目標函數適應值

最優解為x*=（0，12，23，17，6）和x*=（0，11，22，16，6），對應的最優值為f8（x*）=-737。

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

最優解為x*=（1，1，1，1，1），對應的最優值為f10（x*）=0。

最優解為x*=（3，2），對應的最優值為f12（x*）=0。

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

實驗統計指標有7個，前三個是20次獨立運行所得目標函數值的最好值、平均值及最差值；第四到第六個包括這20次成功尋優中使用的最小迭代次數、平均迭代次數、最大迭代次數；最后一個指標是20次獨立循環消耗的總時間（單位：s）。花授粉算法的運行結果見表1。均為d維行向量，fit和Fit均為n維行向量。分別找出fit和Fit中最好的元素（即最小的元素）及其對應的可行解，將fit和Fit中最好的元素分別記為fitbest和Fitbest，fitbest和Fitbest分別對應的可行解記為xbest和Xbest。

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

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

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

（6）評價當前目標函數值Fitbest，并與歷史最優函數值比較，確定當前迭代最優函數值。

（7）轉步驟（3）。

（8）輸出尋優得到的結果。

3 實例驗證

以下實驗過程的運行環境是Window7系統下的MATLAB2 013a。選擇參考文獻[9]中的測試函數來驗證所提出的IFPA在無約束整數規劃問題中的應用；選擇參考文獻[5]中的實例來驗證IFPA在約束整數規劃問題中的應用。

3.1 無約束整數規劃測試函數

最優解為x*=（1，1），對應的最優值為f1（x*）=0。

最優解為x*=（1，1），對應的最優值為f2（x*）=0。

最優解為x*=（0，0，0，0），對應的最優值為f3（x*）=0。

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

表1 IFPA在無約束整數規劃中的實驗結果

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

3.2 有約束整數規劃

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

實例1：

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

圖2 最優個體適應度值變化曲線

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

實例2：

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

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

4 結論

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

圖3 最優個體適應度值變化曲線

[1]杜枯康，英凱.整數規劃問題智能求解算法綜述[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]譚瑛，高慧敏，曾建潮．求解整數規劃問題的微粒群算法[J]．系統工程理論與實踐，2004，24（5）：126-129．

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

[5]祁輝，熊鷹，周樹民.基于粒子群算法的整數規劃問題的求解算法[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]吳炅，健勇.整數規劃的布谷鳥算法[J].學理論與應用，2013，33（3）：99-106.

Flow er pollination algorithm for solving integer programm ing

Xie Yu1，Gao Xiaozhi1，2
（1.College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China；2.Department of Automation and Systems Technology，Aalto University，Helsinki FI-00076，Finland）

Integer programming is a famous NP-hard problem.Integer flower pollination algorithm（IFPA）is the use of rounding off method.It extends the recently developed flower pollination algorithm（FPA）to solve integer programming.The results of simulation experiments on a set of test functions show that IFPA has good performance and strong global optimization ability and can be used as a practical way to solve integer programming problems.

unconstrained integer programming；constrained integer programming；benchmark；flower pollination algorithm；optimization

TP301

A

1674-7720（2015）03-0082-04

2014-10-02）

謝瑜（1987-），女，碩士研究生，主要研究方向：最優化理論應用及其研究。

高曉智（1972-），男，教授，阿爾托大學博士生導師，主要研究方向：軟計算理論及其應用。