改進的布谷鳥算法及相應罰函數(shù)法的應用

臧 睿，劉延龍

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

0 引 言

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

1 罰函數(shù)法

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

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

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

對于問題 （1）定義目標函數(shù)

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

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

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

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

2.1 布谷鳥算法

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

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

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

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

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

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

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

While（t＜Gmax）

通過列維飛行得到一個布谷鳥i；

評估這個布谷鳥Fi；

隨機選擇一個鳥窩j；

if（Fi＞Fj） then

用新的解代替j；

end if

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

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

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

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

end while

2.2 改進的布谷鳥算法

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

其中

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

2.3 改進的布谷鳥算法與罰函數(shù)法結合

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

（PMCS）。

具體步驟如下：

步驟1 設k：＝0。

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

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

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

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

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

3 仿真實驗與數(shù)值分析

為驗證PMCS算法的有效性，本文選取兩個標準測試函數(shù)［9］和兩個結構優(yōu)化設計問題［10］進行測試與求解驗證比較。

3.1 標準測試函數(shù)測試

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

表1 4種算法對標準測試函數(shù)F1 的尋優(yōu)結果比較

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

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

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

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

3.2 結構設計優(yōu)化問題

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

表2 4種算法對標準測試函數(shù)F2 的尋優(yōu)結果比較

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

中，一個標準的彈簧設計有3個變量，彈簧圈平均直徑，金屬絲直徑，長度，如圖3 所示。彈簧設計的目的是要彈簧的重量達到最小。該問題被描述為

圖3 張力彈簧

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

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

表3 4種算法對彈簧設計問題的最優(yōu)結果比較

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

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

圖5 壓力容器

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

表4 4種算法對壓力容器設計問題的最優(yōu)結果比較

表5 4種算法對壓力容器設計問題的最優(yōu)結果比較

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

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

4 結束語

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

［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)化中的應用 ［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）.［鮑江宏.用遺傳算法實現(xiàn)罰函數(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）.［龍文，梁昔明，徐松金，等.聚類佳點集交叉的約束優(yōu)化混合進化算法 ［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］.計算機應用，2014，34 （2）：523－527.］