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

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

謝瑜1，高曉智1，2
（1.上海海事大學信息工程學院，上海201306；2.阿爾托大學自動化與系統(tǒng)技術(shù)系，芬蘭赫爾辛基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ù)集進行仿真實驗，結(jié)果表明IFPA擁有很好的性能和很強的全局尋優(yōu)能力，可以作為一種實用方法用于求解無約束整數(shù)規(guī)劃和有約束整數(shù)規(guī)劃問題。

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

0 引言

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

對于變量維數(shù)較小的整數(shù)規(guī)劃問題，傳統(tǒng)的求解方法[1]有分支界定法、割平面法以及將兩者結(jié)合起來的分支割平面算法、隱枚舉法等；對于較大規(guī)模的問題，傳統(tǒng)的計算方法比較耗時，通常先采用實數(shù)域的一些優(yōu)化算法，再將計算結(jié)果進行取整后作為整數(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）。通過仿真實驗驗證了所提算法的有效性，結(jié)果表明該算法具有良好的全局尋優(yōu)能力和良好的收斂速度。

1 基本花授粉算法

1.1 花授粉的特性

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

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

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

1.2 花授粉算法

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

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

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

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

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

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

其中Γ（λ）是標準伽馬函數(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所示。

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

圖1 連續(xù)50步萊維飛行

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

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

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

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

定義轉(zhuǎn)移概率P∈[0，1]

While（t>誤差容量）

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

if rand

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

邊界約束檢查；

else

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

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

邊界約束檢查；

end if

評價所有新的解；

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

end while

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

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

其中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，局部授粉和全局授粉的轉(zhuǎn)移概率P。然后隨機產(chǎn)生一個種群，產(chǎn)生方式為：

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

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

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

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

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

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

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

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

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

實驗統(tǒng)計指標有7個，前三個是20次獨立運行所得目標函數(shù)值的最好值、平均值及最差值；第四到第六個包括這20次成功尋優(yōu)中使用的最小迭代次數(shù)、平均迭代次數(shù)、最大迭代次數(shù)；最后一個指標是20次獨立循環(huán)消耗的總時間（單位：s）?；ㄊ诜鬯惴ǖ倪\行結(jié)果見表1。均為d維行向量，fit和Fit均為n維行向量。分別找出fit和Fit中最好的元素（即最小的元素）及其對應的可行解，將fit和Fit中最好的元素分別記為fitbest和Fitbest，fitbest和Fitbest分別對應的可行解記為xbest和Xbest。

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

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

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

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

（7）轉(zhuǎn)步驟（3）。

（8）輸出尋優(yōu)得到的結(jié)果。

3 實例驗證

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

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

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

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

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

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

表1 IFPA在無約束整數(shù)規(guī)劃中的實驗結(jié)果

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

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

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

實例1：

理論上，該線性整數(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ù)關(guān)系如圖2所示。

圖2 最優(yōu)個體適應度值變化曲線

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

實例2：

理論上，該非線性整數(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ù)關(guān)系如圖3所示。

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

4 結(jié)論

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

圖3 最優(yōu)個體適應度值變化曲線

[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.

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，F(xiàn)inland）

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-），女，碩士研究生，主要研究方向：最優(yōu)化理論應用及其研究。

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