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

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

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

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

整數(shù)規(guī)劃是NP困難（Non-deterministic Polynomial-time hard，NP-hard）的經(jīng)典問題之一。整數(shù)規(guī)劃的花授粉算法（Integer Flower Pollination Algorithm，IFPA）是采用截?cái)嗳≌姆椒?，將最近開發(fā)的花授粉算法（Flower Pollination Algorithm，F(xiàn)PA）擴(kuò)展到求解整數(shù)規(guī)劃問題。通過(guò)對(duì)測(cè)試函數(shù)集進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明IFPA擁有很好的性能和很強(qiáng)的全局尋優(yōu)能力，可以作為一種實(shí)用方法用于求解無(wú)約束整數(shù)規(guī)劃和有約束整數(shù)規(guī)劃問題。

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

0 引言

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

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

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

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

1 基本花授粉算法

1.1 花授粉的特性

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

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

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

1.2 花授粉算法

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

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

（2）非生物自花授粉被認(rèn)為是局部授粉。

（3）花恒?？梢员徽J(rèn)為是正比于某兩朵相似性的繁殖概率。

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

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

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

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

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

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

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

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

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

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

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

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

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

While（t>誤差容量）

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

if rand

取一個(gè)遵守萊維飛行的步長(zhǎng)矢量L（d維）；

邊界約束檢查；

else

取一個(gè)服從均勻分布的ε；

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

邊界約束檢查；

end if

評(píng)價(jià)所有新的解；

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

end while

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

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

其中Zd為所有d維格子點(diǎn)組成的點(diǎn)集，S為問題的所有可行解集。在求解過(guò)程中，可采取兩種截?cái)嗳≌姆椒ǎ阂皇窃谘h(huán)迭代的過(guò)程中，先將每個(gè)花粉的位置進(jìn)行取整操作，然后計(jì)算其對(duì)應(yīng)的函數(shù)值，此外的其他過(guò)程則完全與連續(xù)域函數(shù)優(yōu)化的過(guò)程一致；二是保持連續(xù)域函數(shù)優(yōu)化的過(guò)程，只在比較和評(píng)價(jià)目標(biāo)函數(shù)值的過(guò)程中，對(duì)花粉位置取整并計(jì)算取整后的位置所對(duì)應(yīng)的目標(biāo)函數(shù)適應(yīng)值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（5）利用步驟（2）中方法，計(jì)算種群中每個(gè)花粉對(duì)應(yīng)的目標(biāo)函數(shù)適應(yīng)值，即確定fitbest、Fitbest、xbest和Xbest。

（6）評(píng)價(jià)當(dāng)前目標(biāo)函數(shù)值Fitbest，并與歷史最優(yōu)函數(shù)值比較，確定當(dāng)前迭代最優(yōu)函數(shù)值。

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

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

3 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

實(shí)例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。程序仿真時(shí)，每次迭代的最優(yōu)值隨迭代次數(shù)的函數(shù)關(guān)系如圖2所示。

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

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

實(shí)例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í)例仿真函數(shù)關(guān)系如圖3所示。

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

4 結(jié)論

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

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

[1]杜枯康，英凱.整數(shù)規(guī)劃問題智能求解算法綜述[J].計(jì)算機(jī)應(yīng)用研究，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)工程理論與實(shí)踐，2004，24（5）：126-129．

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

[5]祁輝，熊鷹，周樹民.基于粒子群算法的整數(shù)規(guī)劃問題的求解算法[J].江漢大學(xué)學(xué)報(bào)，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].學(xué)理論與應(yīng)用，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)化理論應(yīng)用及其研究。

高曉智（1972-），男，教授，阿爾托大學(xué)博士生導(dǎo)師，主要研究方向：軟計(jì)算理論及其應(yīng)用。