2009年剑桥大学学者YANG和拉曼工程大学Deb模拟布谷鸟的寻窝产卵行为, 提出了一种新的智能优化算法——布谷鸟搜索算法(Cuckoo Search, CS), 该算法依赖于布谷鸟的巢寄生性和莱维飞行(Lévy flight)搜索原理[1].布谷鸟算法简单易行, 参数较少, 解决特殊问题时无须重新匹配大量参数, 因此在解决许多优化问题上比粒子群算法(PSO)和遗传算法(GA)等更胜一筹[2].但布谷鸟算法的局部搜索能力较差, 许多局部区域的优化信息不能得到充分利用, 使得CS后期搜索速度较慢, 收敛精度不高, 因此需要进一步完善[3].而混沌现象介于确定性和随机性之间, 有着精致的内在结构[4-5].它是一种具有遍历性、规律性、随机性的渐进现象, 混沌优化算法既能克服早熟收敛, 保证搜索到全局最优值, 又能保证搜索速度, 使算法具有良好的性能[6].若利用混沌变量进行优化搜索, 无疑会比随机搜索更具优越性.目前已有学者将混沌算法引入到遗传算法[7]、模拟退火算法[8]、粒子群算法[9]以及花粉算法中[10]并取得了较好的结果.本文将混沌序列引入到布谷鸟算法中, 提出了一种基于混沌序列的布谷鸟搜索算法(BCS).
1 算法改进 1.1 布谷鸟搜索算法在布谷鸟算法中, 为了模拟布谷鸟寻巢方式, 可以用以下三点理想化条件:(1)每只布谷鸟一次只产一个蛋, 并且随机选择一个鸟窝来存放; (2)最好的鸟窝(解)将会被保留到下一代; (3)可用鸟窝的数量n是固定的, 鸟窝主人发现外来鸟蛋的概率是Pα, 其中Pα∈[0, 1].在这种情况下, 鸟窝主人可以将该鸟蛋丢弃, 或者放弃这个鸟窝, 在新的地方重新建立一个鸟窝.在以上3个理想化条件下, 布谷鸟根据Lévy飞行进行搜索, 步长更新公式为
|
(1) |
|
(2) |
式(1)中⊕表示点对点乘法, 式(2)中s0表示初始步长.CS的具体操作步骤详见文献[2].
1.2 基于混沌序列的布谷鸟算法混沌优化算法首先使优化变量处于混沌状态, 其次把优化变量从混沌空间变换到解空间, 最后利用混沌现象的遍历性进行优化搜索[11].选择不同的混沌序列会对全局最优解产生不同的影响[12], 前期分别将表 1中的混沌序列[13]引入标准CS中，通过实验模拟，比较其效果，最终采用效果最优的混沌序列——Logistic混沌映射进行迭代.
Logistic映射的定义为
|
(3) |
式中μ是控制变量.研究表明当3.56＜μ≤4时, 映射处于混沌状态.当μ=4时, 轨道y(n)为混沌的, 即Logistic映射完全处于混沌状态[14].本文利用混沌迭代生成布谷鸟的初始鸟窝位置, 然后再进行优化搜索.
引入混沌序列的布谷鸟算法步骤如下:
(1) 随机产生一个鸟窝位置Y1(0)=(y11, y12, …, y1d), 将Y1(0)的每一维按式(3)进行n-1次迭代产生n-1个混沌变量Y2(0), …, Yn-1(0), Yn(0).
(2) 将式(1)中n个变量按照式(4)映射到解空间，即
|
(4) |
这样就得到了n个鸟窝的位置, 记为P0=[X1(0), X2(0), …, Xn(0)].
(3) 计算步骤(2)中的适应值, 选出初始全局最优位置Xbest(0), best∈{1, 2, …, n}和fmin.
(4) 保留上一代最好的鸟窝位置Xbest(t-1), 利用式(1), (2)对其他鸟窝进行位置更新, 然后得到一组新的鸟窝位置Pt，对这组鸟窝位置进行测试, 与上一代鸟窝位置Pt-1=[X1(t-1), X2(t-1), …，Xn(t-1)]比较, 用测试值较好的鸟窝位置替代测试值较差的鸟窝位置, 从而得到一组较优的鸟窝位置P=[X1(t), X2(t), …，Xn(t)].
(5) 产生服从均匀分布的随机数r∈(0, 1), 与布谷鸟的鸟蛋被鸟窝主人发现的概率Pα对比, 保留P中发现概率较小的鸟窝位置, 对概率较大的鸟窝位置进行随机改变, 从而得到一组新的鸟窝位置.对这组鸟窝位置进行测试, 与P中每个鸟窝位置的测试值进行比较, 用测试值较好的鸟窝位置替代测试值较差的鸟窝位置, 从而得到全局最优鸟窝位置P′=[X1(t), X2(t), …，Xn(t)], 计算其适应度函数值.
(6) 判断是否满足终止条件, 若满足终止条件, 则P′是全局最优解, 否则返回第(4)步.
2 仿真与结果分析本文从Benchmarks测试函数中选取6个典型的测试函数来进行测试[15], 如表 2所示.其中Zakharov函数和Aekley函数为多峰函数，其他为单峰函数.
| 函数名称 | 测试函数 | 全局最优值 |
| Sphere |  |
min(f(X*))=f(0, 0, …, 0)=0 |
| Step |  |
min(f(X*))=f(0, 0, …, 0)=0 |
| Schwefel 2.22 |  |
min(f(X*))=f(0, 0, …, 0)=0 |
| Rosenborck |  |
min(f(X*))=f(1, 1, …, 1)=0 |
| Zakharov |  |
min(f(X*))=f(0, 0, …, 0)=0 |
| Ackley |  |
min(f(X*))=f(0, 0, …, 0)=0 |
种群规模n=25, 鸟窝主人发现外来鸟蛋的概率Pα=0.25, 参数β=1.5, 控制步长α取1, 其他参数根据具体情况设定.
|
| 图 1 Sphere函数的寻优曲线 Fig.1 Optimization curve of Sphere function |
|
| 图 2 Step函数的寻优曲线 Fig.2 Optimization curve of Step function |
|
| 图 3 Schwefel 2.22函数的寻优曲线 Fig.3 Optimization curve of Schwefel 2.22 function |
|
| 图 4 Rosenborck函数的寻优曲线 Fig.4 Optimization curve of Rosenborck function |
|
| 图 5 Zakharov函数的寻优曲线 Fig.5 Optimization curve of Zakharov function |
|
| 图 6 Ackley函数的寻优曲线 Fig.6 Optimization curve of Ackley function |
从图 1~3可以看出, 对于15维的Sphere函数、Step函数及Schwefel 2.22函数，CS和BCS都能成功收敛, 同样的500次迭代下, BCS的收敛速度明显快于标准CS的收敛速度; 当维数增加到30维时, 也可以看出BCS的这一优势.Rosenborck函数是一个单峰函数又可以用于检测算法的局部搜索能力, 从图 4可以看出, 对于15维的Rosenborck函数, 迭代次数为1 000次时BCS收敛速度明显比标准CS收敛速度快, BCS能收敛到最优值, CS还不能收敛到最优值.随着维数的增加, CS和BCS的收敛效果都不太好.
图 6是Ackley函数寻优图, 维数为15维时, 迭代次数为500次, BCS的收敛速度快于标准CS.当维数为30维, 迭代次数为1 000时, 可以明显看出BCS的收敛速度比标准CS快.从图 5可看出CS与BCS两种算法用于不同维数的Zakharov函数结果与Ackley函数很相似, 维数越高越能体现BCS的优势.
表 3是CS和BCS的全局平均最优值对比.分别设置函数维数为15维和30维, 独立运行20次, 取这20次的平均值进行对比.对于不同维数的Sphere函数和Zakharov函数, BCS维数的在计算精度上都高出标准CS一个数量级.然而对于不同维数的Step函数, BCS维数的在计算精度上都高出标准CS至少3个数量级.对于Schwefel 2.22函数、Rosenborck函数和Ackley函数, BCS的平均最优值比CS的平均最优值小的多.综合图 1~6以及表 3可以得出，BCS在性能上优于标准CS.
| 测试函数 | 维数 | 算法 | 平均最优值 |
| Sphere | 15 | CS | 1.285 9×10-5 |
| BCS | 5.269 9×10-6 | ||
| 30 | CS | 0.0172 | |
| BCS | 0.000 53 | ||
| Step | 15 | CS | 1.866 7×10-6 |
| BCS | 2.583 7×10-9 | ||
| 30 | CS | 2.022 6×10-5 | |
| BCS | 5.6665×10-9 | ||
| Schwefel 2.22 | 15 | CS | 0.760 1 |
| BCS | 0 | ||
| 30 | CS | 0.024 4 | |
| BCS | 0 | ||
| Rosenborck | 15 | CS | 39.967 8 |
| BCS | 18.696 1 | ||
| 30 | CS | 27.4728 | |
| BCS | 6.8533 | ||
| Zakharov | 15 | CS | 0.001 3 |
| BCS | 1.633 5×10-4 | ||
| 20 | CS | 0.266 0 | |
| BCS | 0.006 29 | ||
| Ackley | 15 | CS | 0.044 3 |
| BCS | 0.005 3 | ||
| 30 | CS | 0.744 8 | |
| BCS | 0.079 4 |
将Logistic混沌映射引入布谷鸟算法中来优化布谷鸟算法的初值, 建立基于混沌序列的布谷鸟算法.通过6个基准函数进行性能测试, 并比较两种维数的测试函数结果, 最终表明标准CS和BCS都有较强的寻优能力, 但是BCS比标准CS具有更快的收敛速度、更高的收敛精度和更好的全局最优值.
| [1] | YANG Xinshe, DEB S.Cuckoo search via Lévy flights[C]//2009 World Congress on Nature & Biologically Inspired Computing, World Congress on IEEE:210-214. |
| [2] |
赵玉新, 杨新社, 刘利强.
新兴元启发式优化方法[M]. 北京: 科学出版社, 2013.
ZHAO Yuxin, YANG Xinshe, LIU Liqiang. Emerging heuristic optimization method for emerging elements[M]. Beijing: Science Press, 2013. |
| [3] | YANG Xinshe. Nature-inspired metaheuristic algorithms[M]. 2nd edition. United Kingdom: Luniver Press, 2010. |
| [4] |
李兵, 蒋慰孙. 混沌优化方法及其应用[J].
控制理论与应用, 1997, 14(4): 613-615 LI Bing, JIANG Weisun. Chaos optimization method and its application[J]. Control Theory & Applications, 1997, 14(4): 613-615 |
| [5] | CHOI C. Chaotic local search algorithm[J]. Artificial Life & Robottics, 1998, 2(1): 41-47 |
| [6] | LU Huijuan, ZHANG Houming, MA Longhua. A new optimization algorithm based on chaos[J]. Journal of Zhejiang University Science A, 2006, 7(4): 539-542 DOI:10.1631/jzus.2006.A0539 |
| [7] |
费春国, 韩正之. 一种改进的混沌优化算法[J].
控制理论与应用, 2001, 23(3): 471-474 FANG Chunguo, HAN Zhengzhi. Improved chaos optimization algorithm[J]. Control Theory & Applications, 2001, 23(3): 471-474 |
| [8] |
王子才, 张彤. 基于混沌变量的模拟退火优化方法[J].
控制与决策, 1997, 14(4): 381-384 WANG Zicai, ZHANG Tong. Simulation annealing optimization method based on chaos variables[J]. Control and Decision, 1997, 14(4): 381-384 |
| [9] |
高鹰, 谢胜利. 混沌粒子群优化算法[J].
计算机科学, 2001, 31(8): 13-15 GAO Ying, XIE Shengli. Chaotic particle swarm optimization algorithm[J]. Computer Science, 2001, 31(8): 13-15 |
| [10] |
乔现伟, 贺兴时. 基于混沌的花粉算法[J].
纺织高校基础科学学报, 2015, 28(3): 330-334 QIAO Xianwei, HE Xingshi. Chaos-based flower algorithm[J]. Basic Sciences Journal of Textile Universities, 2015, 28(3): 330-334 |
| [11] |
王丽侠. 混沌优化算法在组合优化问题中的应用[J].
计算机工程, 2007, 33(21): 192-196 WANG Lixia. Application of chaos optimization algorithm in combinatorial optimization problem[J]. Computer Engineering, 2007, 33(21): 192-196 DOI:10.3969/j.issn.1000-3428.2007.21.068 |
| [12] |
高雷阜, 胡行华. 不同混沌序列对全局最优解的搜索影响[J].
辽宁工程技术大学学报(自然科学版), 2008, 27(4): 629-631 GAO Leifu, HU Xinghua. Effects of different chaotic sequences on search of global optimal solutions[J]. Journal of Liaoning Technical University(Natural Science Edition), 2008, 27(4): 629-631 |
| [13] | GANDOMI A H, YUN Gunjin, YANG Xinshe, et al. Chaos-enhanced accelerated particle swarm optimization[J]. Communications in Nonlinear Science & Numerical Simulation, 2013, 18(2): 327-340 |
| [14] |
冯春, 谢进, 李柏林. 混沌优化算法的研究[C]//第十四届全国机构学学术研讨会暨第二届海峡两岸机构学学术交流会论文集. 重庆, 2004: 304-306.
FENG Chun, XIE Jin, LI Bolin.Survey on chaos optimization algorithm[C]//The 14th National Symposium on Mechanisms & the 2nd Symposium on Cross-Strait Institutional Research.Chongqing, 2004:304-306. |
| [15] | JAMIL M, YANG Xinshe. A literature survey of benchmark functions for global optimization problems[J]. International Journal of Mathematical Modelling & Numerical Optimisation, 2013, 4(2): 150-194 |