改進(jìn)的布谷鳥算法及相應(yīng)罰函數(shù)法的應(yīng)用

臧 睿，劉延龍

（東北林業(yè)大學(xué) 理學(xué)院，黑龍江 哈爾濱150040）

0 引 言

布谷鳥算法 （cuckoo search algorithm，CS）［1－5］作為一種新興的仿生智能算法具有后期收斂速度慢的缺點(diǎn)，本文通過引進(jìn)一種新的慣性權(quán)重對(duì)布谷鳥算法加以改進(jìn)，并且提出了一種罰函數(shù)法與改進(jìn)的布谷鳥算法結(jié)合的新型算法（penalty modified cuckoo search，PMCS）用來解決多約束條件優(yōu)化問題。測(cè)試結(jié)果表明它對(duì)于多約束非線性規(guī)劃問題具有較好的效果。

1 罰函數(shù)法

許多工程應(yīng)用問題都可以轉(zhuǎn)化為非線性規(guī)劃問題。非線性規(guī)劃問題可以描述為

式中：f（x）——目標(biāo)函數(shù)，gj（x）、hj（x）——不等式約束函數(shù)、等式約束函數(shù)，li、ui——決策變量xi的上下界。

無論傳統(tǒng)優(yōu)化算法還是智能優(yōu)化算法在處理約束優(yōu)化問題時(shí)常用的方法是罰函數(shù)法。罰函數(shù)法的核心思想是通過在目標(biāo)函數(shù)中引入懲罰項(xiàng)的方式將約束優(yōu)化問題轉(zhuǎn)化為一系列的無約束優(yōu)化問題進(jìn)行逼近求解［6］。

對(duì)于問題 （1）定義目標(biāo)函數(shù)

式中： G［gu（X）］——不等式約束的懲罰項(xiàng)，H［hu（X）］——等式約束的懲罰項(xiàng)，r（k）——罰因子滿足r（k）→＋∞。對(duì)應(yīng)的罰因子序列｛r（k）｝將問題 （1）轉(zhuǎn)化為一系列的無約束優(yōu)化問題

懲罰項(xiàng)G［gu（X）］和H［hu（X）］滿足：當(dāng)點(diǎn)x 不滿足約束時(shí)候，由約束函數(shù)構(gòu)成的懲罰項(xiàng)的值很大，并且隨著序列｛r（k）｝的變化，懲罰項(xiàng)在整個(gè)罰函數(shù)中逐漸趨于零，從而使對(duì)應(yīng)于罰函數(shù)Φ（x，r（k））的解得序列x（r（k））收斂到我們所要解決的問題 （1）的最優(yōu)解。

從理論角度看罰因子列｛r（k）｝只需滿足單調(diào)遞增且趨向于無窮即可。在實(shí)際計(jì)算中，罰因子列｛r（k）｝的選取方法對(duì)測(cè)試結(jié)果會(huì)產(chǎn)生不同影響。本文結(jié)合模擬退火思想提出一種新的罰因子的選取方法，取得了較好的效果。采用Bao提出的罰因子選取方法［7］，將罰函數(shù)因子取為r（k）＝，T ＝α＊T，隨著T 逐漸減小，r（k）逐漸增大，其增加的速度由參數(shù)α決定。

2 改進(jìn)的布谷鳥算法與罰函數(shù)法

2.1 布谷鳥算法

布谷鳥算法是模擬布谷鳥尋窩產(chǎn)卵隨機(jī)飛行的過程。為了簡(jiǎn)化描述CS算法，可以用下面的三點(diǎn)理想化規(guī)則：①每個(gè)布谷鳥每次只產(chǎn)一個(gè)蛋，并且隨機(jī)選擇鳥巢進(jìn)行孵化；②最優(yōu)的鳥巢將隨著最優(yōu)的鳥蛋保留到下一代；③巢主鳥的數(shù)量是固定的，并且布谷鳥產(chǎn)的蛋被巢主鳥發(fā)現(xiàn)的概率為固定的pa∈［0，1］。在這種情況下，巢主鳥或者把蛋扔出去，或者丟棄這個(gè)鳥窩去別的地方建立新的鳥巢。

基于以上3條規(guī)則，布谷鳥的尋窩路徑和位置更新公式如下

式中：xti——第i個(gè)鳥窩在第t代的鳥窩位置；α——步長(zhǎng)比例因子，一般取為0.1；⊕——點(diǎn)乘；L（λ）——隨機(jī)飛行步長(zhǎng)，服從Lévy分布；N 為鳥巢數(shù)量。

布谷鳥算法算法流程如下：

目標(biāo)函數(shù)f（x），x ＝（x1，x2，…，xn）T

種群迭代次數(shù)t＝1；

初始化一個(gè)具有N 個(gè)鳥巢的種群xi，（i＝1，2，…，N）；

While（t＜Gmax）

通過列維飛行得到一個(gè)布谷鳥i；

評(píng)估這個(gè)布谷鳥Fi；

隨機(jī)選擇一個(gè)鳥窩j；

if（Fi＞Fj） then

用新的解代替j；

end if

丟棄較差的鳥窩；并通過列維飛行建立新的鳥窩；

保留最優(yōu)解到下一代；

將所有的解排列，并選出最優(yōu)解；

更新迭代次數(shù)t＝t＋1；

end while

2.2 改進(jìn)的布谷鳥算法

在基本的布谷鳥算法中，布谷鳥的飛行路徑是隨機(jī)的，在后期會(huì)導(dǎo)致收斂速度慢等問題。針對(duì)這一問題，F(xiàn)an等通過引入非線性慣性權(quán)重予以改進(jìn)并已經(jīng)驗(yàn)證了改進(jìn)的布谷鳥算法的收斂速度快于布谷鳥算法［8］。考慮到較大的慣性權(quán)重可以使得算法跳出局部最優(yōu)，較小的慣性權(quán)重可以加快后期收斂速度，本文在布谷鳥位置更新公式時(shí)引入一種改進(jìn)的非線性慣性權(quán)重

其中

這里w0為充分大的正常數(shù)，t為迭代次數(shù)，t0為取定的正整數(shù)。

2.3 改進(jìn)的布谷鳥算法與罰函數(shù)法結(jié)合

本文提出改進(jìn)的布谷鳥算法與罰函數(shù)法結(jié)合的算法

（PMCS）。

具體步驟如下：

步驟1 設(shè)k：＝0。

步驟2 隨機(jī)產(chǎn)生n個(gè)鳥窩x ＝（x1，x2，…，xn），并且按目標(biāo)函數(shù)Φ（x，r（k））進(jìn)行測(cè)試，選出初始最優(yōu)位置，并且保留到下一代。

步驟3 利用位置更新式 （5）進(jìn)行位置更新，并按Φ（x，r（k））進(jìn)行測(cè)試，與上一代的位置進(jìn)行對(duì)比，將最優(yōu)的保留到下一代。

步驟4 隨機(jī)產(chǎn)生一個(gè)均勻的分部數(shù)r∈（0，1），與布谷鳥的鳥蛋被發(fā)現(xiàn)的概率pa＝0.25 進(jìn)行比較，如果r ＞pa，則對(duì)進(jìn)行列維隨機(jī)改變，反之不變。再對(duì)新的位置進(jìn)行測(cè)試，將最優(yōu)的位置x＊保留到下一代。

步驟5 判斷f（x＊）是否滿足終止條件，如果滿足則跳出循環(huán)，到步驟6。如果不滿足，則返回到步驟2 重新進(jìn)行。

步驟6 滿足停機(jī)條件，停止，否則，k＝k＋1，返回到步驟2。

3 仿真實(shí)驗(yàn)與數(shù)值分析

為驗(yàn)證PMCS算法的有效性，本文選取兩個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)［9］和兩個(gè)結(jié)構(gòu)優(yōu)化設(shè)計(jì)問題［10］進(jìn)行測(cè)試與求解驗(yàn)證比較。

3.1 標(biāo)準(zhǔn)測(cè)試函數(shù)測(cè)試

PMCS算法參數(shù)設(shè)置為：N ＝25，T＝0.99，Pa＝0.25。對(duì)F1運(yùn)行30 次實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果見表1。表1 中給出了PMCS算法與其它算法［11－13］的結(jié)果比較。

表1 4種算法對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)F1 的尋優(yōu)結(jié)果比較

從表1中可以得出，對(duì)于函數(shù)F1，與HGA 與HCS相比，從解的質(zhì)量上看，要更加優(yōu)，與HEA 相比略差一些。但是總體上來說，這4 種算法相比之下，PMCS算法屬于比較好的一種。說明了PMCS算法的有效性與可行性。圖1給出了PMCS算法對(duì)函數(shù)F1的尋優(yōu)迭代曲線。

圖1 PMCS算法對(duì)函數(shù)F1 的尋優(yōu)迭代曲線

PMCS算法參數(shù)設(shè)置為：N ＝25，T＝0.99，Pa＝0.25。對(duì)F2運(yùn)行30 次實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果見表2。表2 中給出了PMCS算法與其它算法的結(jié)果比較。

從表2中可以得出，對(duì)于函數(shù)F2，與HGA、HEA 和MBA 算法相比，PMCS算法較好的結(jié)果，得出的平均值、最優(yōu)值和最小值都要比其它4 種算法的結(jié)果要優(yōu)，說明PMCS算法的優(yōu)越性。圖2給出了PMCS算法對(duì)函數(shù)F2的尋優(yōu)迭代曲線。

3.2 結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題

（1）彈簧設(shè)計(jì)最優(yōu)化問題：彈簧在被廣泛應(yīng)用于工程

表2 4種算法對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)F2 的尋優(yōu)結(jié)果比較

圖2 PMCS算法對(duì)函數(shù)F2 的尋優(yōu)迭代曲線

中，一個(gè)標(biāo)準(zhǔn)的彈簧設(shè)計(jì)有3個(gè)變量，彈簧圈平均直徑，金屬絲直徑，長(zhǎng)度，如圖3 所示。彈簧設(shè)計(jì)的目的是要彈簧的重量達(dá)到最小。該問題被描述為

圖3 張力彈簧

利用PMCS算法對(duì)彈簧設(shè)計(jì)問題獨(dú)立運(yùn)行20次進(jìn)行求解，PMCS算法參數(shù)設(shè)置為：并與其它算法 （SiC＿PSO，CS）的求解結(jié)果比較，N ＝25，T＝0.99，Pa＝0.25，結(jié)果見表3。

從表3結(jié)果中可以看出PMCS算法的結(jié)果比SiC＿PSO與CS 算法得出的結(jié)果有較為顯著的改善。圖4 給出了PMCS算法對(duì)彈簧設(shè)計(jì)最優(yōu)化問題的尋優(yōu)迭代曲線。

表3 4種算法對(duì)彈簧設(shè)計(jì)問題的最優(yōu)結(jié)果比較

圖4 PMCS算法對(duì)彈簧設(shè)計(jì)最優(yōu)化問題的尋優(yōu)迭代曲線

（2）壓力容器設(shè)計(jì)問題：在壓力容器設(shè)計(jì)問題中，目標(biāo)是使得所有成本達(dá)到最小值，包括物料，成型和焊接。圓柱形容器，加由半球形頭部的蓋在兩端組成，如圖5所示，壓力容器問題被描述為

圖5 壓力容器

利用PMCS算法對(duì)壓力容器設(shè)計(jì)問題獨(dú)立運(yùn)行10次進(jìn)行求解，PMCS算法參數(shù)設(shè)置為：N ＝25，T ＝0.99，Pa＝0.25，并與其它算法 （GA3，CPSO，MBA）的求解結(jié)果比較，結(jié)果見表4、表5。

表4 4種算法對(duì)壓力容器設(shè)計(jì)問題的最優(yōu)結(jié)果比較

表5 4種算法對(duì)壓力容器設(shè)計(jì)問題的最優(yōu)結(jié)果比較

從表4和表5中可以看出4種算法對(duì)壓力容器設(shè)計(jì)問題優(yōu)化的對(duì)比，PMCS算法對(duì)壓力容器設(shè)計(jì)問題的求解不管是最優(yōu)值、平均值還是最差值都要比GA3和CPSO 種算法對(duì)壓力容器問題的求解值優(yōu)等，PMCS的最優(yōu)值略遜色于MBA 的最優(yōu)值，但是PMCS的最差值與最優(yōu)值都要比MBA 的要優(yōu)。圖6給出了PMCS算法對(duì)壓力容器設(shè)計(jì)問題的尋優(yōu)迭代曲線。

圖6 PMCS算法對(duì)壓力容器問題尋優(yōu)迭代曲線

4 結(jié)束語(yǔ)

根據(jù)罰函數(shù)思想，本文提出了一種罰函數(shù)與改進(jìn)的布谷鳥算法結(jié)合的新型算法 （PMCS），并且通過引入一類非線性慣性權(quán)重，擴(kuò)展了算法的全局勘探尋解能力，加快了算法的收斂速度。通過對(duì)兩個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)與兩個(gè)具體設(shè)計(jì)優(yōu)化問題的測(cè)試，對(duì)比已有若干啟發(fā)式算法的測(cè)試結(jié)果，得到了較高精度的最優(yōu)解，結(jié)果表明了該算法具有較好的有效性與可行性。在應(yīng)用部分，本文主要關(guān)注PMCS算法在連續(xù)優(yōu)化問題中的效果，考慮到離散優(yōu)化問題在各類實(shí)際問題中的廣泛性，該算法在離散優(yōu)化問題中的應(yīng)用效果也是值得關(guān)注的研究方向之一。

［1］Yang X S，Deb S.Cuckoo search via Lévy flights ［C］／／World Congress on Nature ＆Biologically Inspired Computing.IEEE，2009：210－214.

［2］Yang X S，Deb S.Engineering optimisation by cuckoo search［J］.International Journal of Mathematical Modelling and Numerical Optimisation，2010，1 （4）：330－343.

［3］Tuba M，Subotic M，Stanarevic N.Modified cuckoo search algorithm for unconstrained optimization problems ［C］／／Proceedings of the 5th European Conference on European Computing Conference.World Scientific and Engineering Academy and Society，2011：263－268.

［4］Yang X S，Deb S.Multiobjective cuckoo search for design optimization ［J］.Computers ＆ Operations Research，2013，40（6）：1616－1624.

［5］Tiwari V.Face recognition based on cuckoo search algorithm［J］.Image，2012，7 （8）：401－405.

［6］LUO Zhigao，WANG Xiang，LI Ju，et al.Application of genetic algorithm and penalty function method in roll－forming process parameters optimization ［J］.Chinese Mechanical Engineering，2009，20 （14）：1705－1707 （in Chinese）.［駱志高，王祥，李舉，等.遺傳算法與懲罰函數(shù)法在輾軋成形工藝參數(shù)優(yōu)化中的應(yīng)用 ［J］.中國(guó)機(jī)械工程，2009，20 （14）：1705－1707.］

［7］BAO Jianghong.Solution to multiple－choice knapsack problem using penalty function method implemented by genetic algorithm［J］.Computer Engineering and Design，2008，29 （17）：4518－4520 （in Chinese）.［鮑江宏.用遺傳算法實(shí)現(xiàn)罰函數(shù)法解多選擇背包問題 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2008，29 （17）：4518－4520.］

［8］Fan S K S，Chiu Y Y.A decreasing inertia weight particle swarm optimizer ［J］.Engineering Optimization，2007，39（2）：203－228.

［9］Sadollah A，Bahreininejad A，Eskandar H，et al.Mine blast algorithm：A new population based algorithm for solving constrained engineering optimization problems ［J］.Applied Soft Computing，2013，13 （5）：2592－2612.

［10］Cagnina L C，Esquivel S C，Coello C A C.Solving engineering optimization problems with the simple constrained particle swarm optimizer ［J］.Informatica （Slovenia），2008，32（3）：319－326.

［11］Long W，Liang X，Huang Y，et al.A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization［J］.Computer－Aided Design，2013，45 （12）：1562－1574.

［12］LONG Wen，LIANG Ximing，XU Songjin，et al.A hybrid evolutionary algorithm based on clustering good－point set crossover for constrained optimization ［J］.Journal of Computer Research and Development，2012，49 （8）：1753－1761（in Chinese）.［龍文，梁昔明，徐松金，等.聚類佳點(diǎn)集交叉的約束優(yōu)化混合進(jìn)化算法 ［J］.計(jì)算機(jī)研究與發(fā)展，2012，49 （8）：1753－1761.］

［13］CHEN Le，LONG Wen.Hybrid cuckoo search algorithm for solving constrained chemical engineering optimization problems［J］.Journal of Computer Applications，2014，34 （2）：523－527 （in Chinese）. ［陳樂，龍文.求解約束化工優(yōu)化問題的混合布谷鳥搜索算法 ［J］.計(jì)算機(jī)應(yīng)用，2014，34 （2）：523－527.］