一種布谷鳥-交叉熵混合優化算法及其性能仿真

李國成， 肖慶憲

(1.上海理工大學管理學院，上海 200093；2.皖西學院金融與數學學院，六安 237012)

一種布谷鳥-交叉熵混合優化算法及其性能仿真

李國成1，2， 肖慶憲1

(1.上海理工大學管理學院，上海 200093；2.皖西學院金融與數學學院，六安 237012)

為了提高布谷鳥搜索算法在求解復雜優化問題時的收斂速度和搜索精度，基于交叉熵方法，構建了一種新的布谷鳥-交叉熵混合優化算法.該算法將基于模型的交叉熵隨機優化算法和基于種群的布谷鳥搜索進行有機融合，采用協同演化策略，既提升了混合算法收斂速度，又改善了其全局優化能力.對經典測試函數和PID控制器整定問題的仿真結果表明，新算法具有全局搜索能力強、求解精度高和魯棒性好等特性，是一種求解復雜優化問題的可行和有效算法.

布谷鳥搜索；交叉熵；混合優化；高維函數；控制器整定

隨著科學技術的快速發展，人們在現實世界中面臨著更加復雜多變的系統，如電力系統、蛋白質結構、醫學圖像匹配系統以及金融市場等[1].這些復雜系統的優化問題常常在高維空間進行，而高維數值優化問題都較為復雜，采用一般的智能算法很難獲得全局最優解[2].為此，許多改進算法紛紛被提出，如動態多群體粒子群優化[3]、自適應協同演化微分進化算法[4]、遺傳和細菌覓食混合算法[5].

最近，Yang等[6]基于布谷鳥孵育寄生的繁殖行為和Lévy飛行特性提出一種新的啟發式搜索算法——布谷鳥搜索(cuckoo search，CS).該算法因仿生能力強、控制參數少和極易實現而廣泛應用于工程設計、結構參數選擇和生產調度等方面[6-11].與此同時，學者們也從不同角度對CS算法進行了改進，如文獻[12]提出自適應Lévy飛行步長和個體間信息交換以提高CS的收斂速度，文獻[13]采用動態飛行步長和發現概率，文獻[14]提出了二進制CS算法.這些改進雖然取得了很好的應用效果，但還都局限于低維簡單優化問題.

布谷鳥搜索是基于種群的元啟發式搜索算法，盡管具有很好的仿生性能和尋優效率，但其求解復雜系統優化問題和高維函數優化問題時的全局優化能力和收斂速度仍待改善.而Rubinstein等[15]提出的交叉熵(cross-entropy，CE)方法是一種基于模型的全局隨機優化算法，具有很強的全局優化性能和魯棒性，在復雜網絡可靠性分析、函數優化和工程設計優化方面都取得了很好的應用效果[16].為此，本文探尋用基于種群的CS算法融合基于模型的交叉熵算法，構建一種新的收斂速度更快、搜索精度更高和全局優化性能更好的布谷鳥-交叉熵混合算法(CSCE)，以求解復雜函數優化問題.

1 布谷鳥-交叉熵混合算法

1.1 布谷鳥搜索算法

布谷鳥搜索算法是Yang等[6]于2009年提出的一種新的啟發式搜索算法，該算法通過提煉出3個理想化規則形成優化工具，并應用于工程優化和非線性系統優化，取得了很好的效果[7-11].其規則如下:

a.每只布谷鳥隨機選取一個宿主鳥巢并產下一枚卵，該卵代表著優化問題的一個候選解x；

b.位置較好的宿主鳥巢(最優解xbest)將被延續到下一代；

c.宿主鳥巢的數目n是固定的，且宿主以一定概率Pa發現并丟棄“外來者”或重新筑巢.

布谷鳥搜索的尋優路徑和位置更新是通過實施Lévy飛行來實現的，具體為

式中，t為Lévy飛行更新代數；a＞0，為Lévy飛行步長縮放控制參數；算子⊕為點對點乘法；Lévy(λ)為隨機搜索路徑；λ為Lévy分布參數，其隨機步長u服從分布由此產生的隨機游走路徑是一條馬爾可夫鏈，它的下一個狀態或位置只取決于當前位置和轉換概率.該路徑長短和方向都是不確定的，其中產生的短步長加速局部搜索，而長步長則產生在距離局部最優值較遠的地方，這就確保算法不容易陷入局部最小值，從而使得它在探索解空間時會更加有效.

1.2 交叉熵方法

交叉熵方法[15]是Rubinstein在研究復雜隨機網絡中的小概率事件估計問題時提出的一種全局隨機優化方法.該方法采用重要度抽樣，引入Kullback-Leibler距離來度量兩個概率分布的交叉熵并使之最小，用以求解組合優化、稀有事件估計以及機器學習等問題，具有很好的隨機性、自適應性和魯棒性[16]，在復雜網絡可靠性分析、組合優化，以及工程設計和控制等方面取得了很好的應用效果[17-18].對于如下最優化問題

交叉熵算法將其關聯到相關的概率估計問題，根據一族定義在X上的概率密度函數{f(x；v)，v∈ν}隨機化問題(3)(v為概率分布參數，ν為概率分布參數集或空間)，得到其輔助隨機問題為

式中，E是期望算子；I為示性函數；γ為自適應更新參數.

為了減小樣本數量，CE采用重要度抽樣法，將式(4)轉化為

式中，N為樣本容量；xi為重要度抽樣密度g(x)生成的樣本.

為求得最優的重要度抽樣密度，引入Kullback-Leibler距離來度量兩個概率分布f(x；v)與g(x)間距離即交叉熵，并最小化交叉熵為

從而得到最優的g*(x)，即為式(3)所描述的問題的最優解x*的概率密度函數.

CE全局隨機優化算法的實施過程為:

1.3 布谷鳥-交叉熵混合算法

a.算法原理

本文將交叉熵方法嵌入到布谷鳥搜索中，通過協同演化共同更新種群，以有效增強算法搜索過程中種群的多樣性，提高算法的全局優化能力.CSCE通過CS和CE兩個優化迭代算子實現，其中CE算子利用共同更新后的種群來刷新自己的抽樣概率分布的參數，加快均值和方差的演化速度.這樣利用協同演化的種群來加速CSCE算法的演化進程，大幅減少抽樣樣本數，進而降低計算成本，充分發揮自己的全局優化能力，為協同演化提供全局更優的種群.同時，CS算子通過協同演化獲得更好的個體，極大地豐富了種群的多樣性，從而提高CSCE算法的收斂速度，并增強全局優化能力.具體算法流程見圖1.

b.算法步驟

基于布谷鳥搜索方法和交叉熵隨機優化算法所融合而成的新型啟發式算法(CSCE)的具體算法步驟如下:

步驟1 確定搜索空間，設置CS基本參數:鳥巢數目N，發現概率Pa，步長因子α，搜索精度εCS或最大搜索次數MCS；設置CE基本參數:樣本容量Nc和有效樣本數Ne，搜索精度εCE或最大迭代次數MCE，初始化概率分布參數均值μ和標準方差σ.隨機生成初始種群XCS，評估每個個體，得到最優位置xbest和最優適應度值fmin.

步驟2 檢測迭代終止條件1，若不滿足，則啟動CS優化迭代算子，否則迭代結束.

(a)利用Lévy飛行機制，按式(1)得到一組新的鳥巢位置，并與上一代進行比較替換，得到一組更優的鳥巢位置；

(b)利用發現遺棄機制，更新鳥巢位置，產生隨機數r∈[0，1]，若r＞Pa，則放棄舊巢另建新巢，否則維持原狀；

(c)評估鳥巢，更新最優位置和最優適應度值.

步驟3 檢測迭代終止條件2，若不滿足，則啟動CE優化迭代算子，否則轉到步驟2.

(b)啟動協同演化，混合XCS和XCE并進行排序，更新XCS和XCE，更新最優位置和最優適應度值；

(c)選取位置最好的Ne個鳥巢來計算參數μ和σ，并用式(7)和式(8)平滑更新μ和σ，返回到步驟3.

步驟4 迭代結束，輸出最優鳥巢位置(最優解)和最優適應度值(最優值).

圖1 CSCE算法流程圖Fig.1 Flow chart for CSCE algorithm

2 CSCE性能仿真測試

2.1 測試問題與比較對象

為了驗證CSCE算法求解復雜函數優化問題時的性能，選取6個經典的標準測試函數來進行測試，解空間維數分別取50和100兩種情形，并與CS算法、文獻[12]提出的布谷鳥改進算法(modified cuckoo search，MCS)和文獻[13]提出的改進算法(improved cuckoo search，ICS)進行對比，各測試函數的具體表達式、定義域及最優值如表1所示.實驗硬件環境為Intel(R)Core(TM)i3 CPU M 2.27 GHz，2 GB RAM；軟件環境為Windows 7和Matlab 2012b.

表1 6個標準測試函數Tab.1 Six benchmar k functions

2.2 參數設置與測試結果

4種算法相關參數設置為:鳥巢數目設定為解空間維數d，CS，MCS和ICS這3種算法的最大迭代次數均為2 050，迭代停止標準為達到最大迭代次數，其它參數分別同文獻[6，12-13]；CSCE算法中CS的最大迭代次數為50，其它參數設置同文獻[6]；CE樣本容量Nc和有效樣本數Ne分別為d和30，最大迭代次數為40.如此設置參數使得4種算法具有相同的函數評價次數，以便于對比.4種算法對每個測試函數獨立運行30次，測試和對比結果見表2和表3(見下頁).表中第一列為6個測試函數，平均值反映了算法的尋優能力，標準差反映了算法尋優能力的穩定性，其最好值均以藍色字體標識.

從表2和表3可以看出:a.6個經典測試函數兩種維數取值的測試結果中CSCE算法在f1，f2，f 4和f5這4個函數上完全勝出，優勢顯著，在f3上略遜于其它3個函數，但求解精度仍在一個數量級上，求解仍然是有效的，只是函數f6的求解效果要差于其它3種算法，同時可以看出，另外兩種改進算法的效果并不明顯；b.CSCE算法的搜索精度非常高，對f5的求解已到達理論最優值，同時所有求解的標準差都很小，表明該算法穩定性好、魯棒性強；c.隨著維數的增加，CSCE算法的尋優效能并沒有發生明顯的減弱，表明該算法更適合于求解高維函數優化問題.

4種算法收斂特征曲線如下頁圖2和圖3所示，鑒于篇幅所限僅給出d=50時f1和f5的迭代過程.其中，橫軸為迭代次數，縱軸為最優函數值，且縱軸采用對數刻度.

表2 變量維數d=50時4種算法測試結果對比Tab.2 Comparison of test results of four algorithms with dimension d=50

表3 變量維數d=100時4種算法測試結果對比Tab.3 Comparison of test results of four algorithms with dimension d=100

圖2 f1的4種算法收斂特征曲線對比Fig.2 Comparison curves of convergence performance of four algorithms for f1

從圖2和圖3可以看出CSCE算法的收斂速度明顯快于CE，MCS和ICS 3種算法，同時其求解精度也是最高的.進一步表明CSCE算法不僅提高了搜索精度，增強了算法穩定性，同時也改善了算法收斂速度.

圖3 f5的4種算法收斂特征曲線對比Fig.3 Comparison curves of convergence performance of four algorithms for f5

3 CSCE算法在PID控制器參數整定中的應用

3.1 PID控制器參數整定問題

PID控制器參數整定問題是工業工程中一個難解的優化問題.常用的整定方法有經典的Ziegler-Nichols法和智能算法(如GA，PSO等)，但優化效果都不理想.為此，很多學者提出了一些改進方法，如文獻[19]的基于強化緩沖算子的灰色預測PID控制以及文獻[20]的分數階PID控制，這些方法較傳統的PID控制都有所改進.本文采用CSCE算法來進行PID參數整定，并與CS，MCS和ICS 3種算法進行比較.

假設某二階延遲系統被控對象傳遞函數為[21]

式中，s為傳遞函數的自變量；0.01≤kp≤20，ki≥0.01，kd≤2為3個待整定參數，通過調整這3個參數使得系統滿足優化指標要求.

本文參照文獻[22]采用如下優化指標來衡量參數整定效果的優劣，即

其PID控制器數學模型為

3.2 PID控制器參數整定仿真

如上文所描述的PID控制器參數整定問題是一種優化問題，其解空間維數為3，適應度函數如式(11)所定義.4種算法的參數設置:鳥巢數目為40；CS，MCS和ICS的最大迭代次數為100，CSCE中CS和CE最大迭代次數均為10，迭代終止條件為達到最大迭代次數；CE中的樣本數和有效樣本數分別為36和15；4種算法的其它參數如前所設.如此設定以使得它們具有相同的函數評價次數4 000次，仿真結果如表4所示.

表4 4種算法的PID控制參數整定結果對比Tab.4 Comparison of tuning results of four algorithms for PID control parameters

4種算法對性能指標J的優化過程及控制對象的單位階躍響應曲線如圖4和圖5所示(y為輸出信號，t為時間).

圖4 性能指標J的4種算法優化過程對比Fig.4 Comparison of optimization process of four algorithms for performance index J

圖5 系統單位階躍響應曲線Fig.5 Unit-step response curve of system

由圖4可見，采用本文所提出的整定方法性能指標優化速度最快，且精度高于其它3種算法.圖5表明采用本文方法整定參數時系統的超調量很微小且響應衰減迅速，穩定時間短，體現了控制器具有較好的抗干擾能力，同時也表明本文所建算法求解PID參數整定問題是可行和有效的.

4 結束語

針對布谷鳥搜索求解復雜函數優化問題的優化性能不強的缺陷，基于交叉熵全局隨機優化算法和協同演化的思想，構建了一種新的布谷鳥-交叉熵混合算法.該算法將交叉熵隨機優化技術嵌入到布谷鳥搜索過程中，利用交叉熵方法的隨機性、自適應性和魯棒性來改善布谷鳥搜索的全局尋優能力.同時，通過協同演化利用布谷鳥搜索來加快交叉熵算法概率分布參數的收斂速度，從而有力地保證新算法能快速獲得全局最優解.標準測試函數和PID控制參數整定問題的仿真實驗結果表明，CSCE具有比CS算法本身及其一些改進算法更好的尋優性能和穩定性，搜尋精度高，收斂速度快，用其來求解復雜函數優化問題是可行和有效的.

[1] Schoen F.Global optimization methods for highdimensional problems[J].European Journal of Operational Research，1999，119(2):345-352.

[2] Grosan C，Abraham A，Hassainen A E.A line search approach for high dimensional function optimization [J].Telecommunication Systems，2011，46(3):217-243.

[3] Zhao S Z，Liang J J，Suganthan P N，et al.Dynamic multi-swarm particle swarm optimizer with local search for large scale global optimization evolutionary computation[C]∥Proceedings of the 2008 IEEE Congress on Evolutionary Computation.Hong Kong: IEEE Computer Press，2008:3845-3852.

[4] Yang Z Y，Tang K，Yao X.Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences，2008，178(15):2985-2999.

[5] Kim D H，Abraham A，Cho J H.A hybrid genetic algorithm and bacterial foraging approach for global optimization[J].Information Science，2007，177(18): 3918-3937.

[6] Yang X S，Deb S.Cuckoo search via Lévy flights[C]∥Proceedings of the 2009 World Congress on Nature& Biologically Inspired Computing.Coimbatore:IEEEComputer Press，2009:210-214.

[7] Moravej Z，Akhlaghi A.A novel approach based on cuckoo search for DG allocation in distribution network[J].International Journal of Electrical Power &Energy Systems，2013，44(1):672-679.

[8] Gandomi A H，Yang X S，Alavi A H.Cuckoo search algorithm:a metaheuristic approach to solve structural optimization problems[J].Engineering with Computers，2013，29(1):17-35.

[9] Chandrasekaran K，Simon S P.Multi-objective scheduling problem:hybrid approach using fuzzy assisted cuckoo search algorithm[J].Swarm and Evolutionary Computation，2012，5:1-16.

[10] 李煜，馬良.新型元啟發式布谷鳥搜索算法[J].系統工程，2012，30(8):64-69.

[11] 劉長平，葉春明.求解置換流水車間調度問題的布谷鳥算法[J].上海理工大學學報，2013，35(1):17-20.

[12] Walton S，Hassan O，Morgan K，et al.Modified cuckoo search:a new gradient free optimisation algorithm[J]. Chaos，Solitons&Fractals，2011，44(9):710-718.

[13] Valian E，Tavakoli S，Mohanna S，et al.Improved cuckoo search for reliability optimization problems [J].Computers&Industrial Engineering，2013，64 (1):459-468.

[14] 馮登科，阮奇，杜利敏.二進制布谷鳥搜索算法[J].計算機應用，2013，33(6):1566-1570.

[15] Rubinstein R Y，Kroese D P.The cross-entropy method:a unified approach to combinatorial optimization，Monte Carlo simulation and machine learning[M].New York:Springer-Verlag，2004.

[16] Kroese D P，Portsky S，Rubinstein R Y.The crossentropy method for continuous multi-extremal optimization[J].Methodology and Computing in Applied Probability，2006，8(3):383-407.

[17] 李潔，柴天佑，宮經寬.基于交叉熵算法的PID控制器設計[J].控制與決策，2011，26(5):794-796.

[18] Yildiz T，Yercan F.The cross-entropy method for combinatorial optimization problems of seaport logistics terminal[J].Transport，2010，25(4):411-422.

[19] 朱堅民，黃之文，翟東婷，等.基于強化緩沖算子的灰色預測PID控制仿真研究[J].上海理工大學學報，2012，34(4):327-332.

[20] 于蓮芝，成羚羚.分數階PID控制運用于勵磁控制系統[J].上海理工大學學報，2013，35(4):404-408.

[21] 張朝龍，江巨浪，江善和，等.一種自適應混合粒子群優化算法及其應用[J].計算機應用研究，2011，28 (5):1696-1698.

[22] 劉金琨.先進PID控制及其Matlab仿真[M].3版.北京:電子工業出版社，2011.

(編輯:丁紅藝)

Hybrid Optimization Algorithm Based on Cuckoo Search and Cross Entropy and Its Performance

LIGuocheng1，2， XIAOQingxian1
(1.Business School，University of Shanghai for Science and Technology，Shanghai 200093，China；2.School of Finance&Mathematics，West Anhui University，Lu’an 237012，China)

In order to improve the rate of convergence and obtain high optimization precision of cuckoo search，a hybrid optimization algorithm for solving complicated optimization problems was proposed.The proposed algorithm combines model-based cross-entropy method with populationbased cuckoo search.The hybrid algorithm not only improves the rate of convergence but also enhances the global search ability by adopting the co-evolution strategy.Simulated experiments were conducted on classical benchmarks and PID controller tuning problem.The results show that the proposed algorithm possesses more powerful global search capacity，higher optimization precision and robustness，and is feasible and effective for solving complicated optimization problems.

cuckoo search；cross entropy；hybrid optimization；high-dimensional fu nction；controller tuning

O 229

A

2013-10-04

國家自然科學基金資助項目(11171221)；上海市一流學科建設資助項目(XTKX2012)

李國成(1976-)，男，博士研究生.研究方向:計算智能與金融優化.E-mail:ligc313@163.com

肖慶憲(1956-)，男，教授.研究方向:金融工程.E-mail:qxxiao@163.com

1007-6735(2015)02-0180-07

10.13255/j.cnki.ju sst.2015.02.016