李国成， 肖庆宪

(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