量子衍生布谷鸟搜索算法①

李盼池,杨淑云,刘显德,潘俊辉,肖 红,曹茂俊

(东北石油大学 计算机与信息技术学院,大庆 163318)

量子衍生布谷鸟搜索算法①

李盼池,杨淑云,刘显德,潘俊辉,肖 红,曹茂俊

(东北石油大学 计算机与信息技术学院,大庆 163318)

为提高布谷鸟搜索算法的寻优能力,通过在经典布谷鸟搜索算法中入量子计算机制,提出了一种量子衍生布谷鸟搜索算法.该算法采用量子比特编码个体,采用泡利矩阵确定旋转轴,采用Levy飞行原理确定旋转角度,采用量子比特在Bloch球面上的绕轴旋转实现个体更新.标准函数极值优化的实验结果表明,与传统布谷鸟搜索算法相比,该算法的搜索能力确有明显提升.

仿生智能优化;群智能优化;布谷鸟算法;量子衍生优化;算法设计

2009年,英国剑桥大学学者提出了一种新的启发式智能优化算法:布谷鸟搜索算法(cuckoo search algorithm,CS)[1].该算法基于布谷鸟寻找鸟巢放置鸟蛋的行为和鸟类飞行的Levy行为建立搜索机制.近几年来,国内学者已对布谷鸟算法展开深入研究.2011年,西安工程大学王凡提出了基于高斯扰动的布谷鸟算法[2],有效提高了算法的收敛速度.2012年,中国矿业大学的李明提出了布谷鸟和差分进化相融合的优化算法[3],有效提高了原算法的优化能力.随后在理论算法方面,先后提出了基于细菌觅食行为中的趋化搜索策略的布谷鸟全局优化算法[4],具有动态惯性策略的布谷鸟搜索算法[5],多目标布谷鸟搜索算法[6,7],基于多种群粒子群和布谷鸟搜索的联合寻优算法[8],基于梯度的自适应快速布谷鸟搜索算法[9],基于种群特征反馈的布谷鸟搜索算法[10].在算法应用方面,布谷鸟搜索算法已成功应用在飞行器容错控制[11],人工神经网络训练[12],水库优化调度[13],干扰资源分配[14]等众多应用领域.

尽管后前国内外文献已提出多种有关布谷鸟搜索算法性能的改进策略,然而有关量子计算与布谷鸟搜索的融合研究尚不多见.本文提出一种新颖的量子衍生布谷鸟搜索算法,其编码机制为采用带两个相位参数量子比特编码个体,寻优机制为采用量子比特在Bloch球面上的绕轴旋转模拟布谷鸟的搜索行为.其中旋转角度采用Levy飞行策略决定.采用CEC2013的28个标准测试函数做为优化对象,仿真结果验证了提出算法的优越性.

1 布谷鸟搜索算法

标准布谷鸟搜索算法是通过模拟布谷鸟借窝产蛋的繁殖习性有效求解最优化问题的全局搜索算法.该算法中,一个鸟巢代表一个候选解,首先基于当前解采用Levy飞行得到新解,然后根据鸟蛋被发现的概率丢弃一些现有的解,并重新生成相同数后的新解.最后进行种群评估,更新全局最优解,完成一次迭代.

布谷鸟搜索算法采用Levy飞行理论产生新解,具体方法为:

其中a0是常数(通常取0.01),Xb是当前最优解.

综合式(1)-式(4),在 Levy 随机搜索中,布谷鸟算法采用下式生成新解:

按发现概率丢弃部分解之后,采用随机游走方式重新生成与丢弃数后相同的新解:

2 量子衍生布谷鸟搜索算法

本节提出一种量子衍生布谷鸟搜索算法(Quantum Inspired Cuckoo Search Algorithm,QICS),包括个体的编码机制和搜索机制两部分,下面分别予以介绍.

2.1 QICS的编码机制

(1)基于量子比特的鸟巢编码

在QICS中,鸟巢采用基于Bloch球面描述的量子比特编码.设鸟巢数量为 N,空间维数为 D,记第 t代种群为,则第 i个鸟巢的初始编码可写为:

(2)量子鸟巢到经典鸟巢的变换

对于量子比特编码的鸟巢,只有转换为具体的数值向量才能评价解的优劣,这可以通过对量子鸟巢的投影测量及解空间变换获得.具体方法为首先采用泡利矩阵对量子鸟巢实施投影测量得到Bloch球面上的坐标鸟巢,然后通过解空间变换,将这些坐标鸟巢映射为具体的鸟巢位置.泡利矩阵的定义式为:

(3)坐标鸟巢的解空间变换

在QICS中,每个量子鸟巢都对应到三个坐标鸟巢,然而这三个坐标鸟巢并不是彼此独立的.这是因为三者之间存在的约束关系.因此若一组坐标(例如xij)较优,则另外两组(yij,zij)一般会较差.因此在QICS中,对于第i个量子鸟巢测量之后得到的三个坐标鸟巢我们只采用

2.2 QICS的搜索机制

在QICS中,搜索机制采用量子比特在Bloch球面上的绕轴旋转实现,其中旋转角度采用Levy飞行理论决定,旋转轴采用泡利矩阵决定.具体旋转方法如下.

(1)基于Levy飞行理论产生新解

根据量子计算原理,旋转算子为一个二维酉矩阵,该矩阵由旋转轴、旋转角度共同决定.

其中a0为控制参数(通常取0.1),为服从标准正态分布的随机数按式(4)计算.

其中t为迭代步数.

(2)基于发现概率的抛弃解的补充

在QICS中,依鸟巢被宿主发现的概率舍弃一些解,同时补充相同数量的新解,以保持种群规模不变.这一过程本质上是一种类似于差分进化策略的局部搜索.具体实现方法为,首先生成一个均匀分布的随机数,若该随机数小于发现概率,则抛弃当前解,同时补充新解.补充方法如下:

2.3 QICS的终止条件

关于群智能优化算法的终止条件,通常有多种.例如精度控制:当优化结果达到某一精度阈值,算法终止;误差控制,当优化结果与精确结果的绝对误差小于给定阈值,算法终止;进化速度控制:若连续若干代优化结果无变化,算法终止;步数控制:若寻优步数达到限定步数,算法终止.本文提出的QICS采用步数控制作为终止条件.

2.4 QICS的实施方案

关于本文提出的QICS,具体实施方案如下.

Step1.初始化:鸟蛋被巢主鸟发现的概率 Pa;种群规模 NP;空间维数 D;限度步数 M;初始种群.

Step2.计算目标函数值,记录最优解,置步数 t=0.

Step3.主循环开始

Step3.1.所有个体执行Levy飞行;

Step3.2.所有个体按概率Pa替换为新解;

Step3.3.更新全局最优解;t=t+1;若 t>M,转Step4;否则转 Step3.1.

Step4.保存全局最优解,结束.

3 对比实验

3.1 测试函数

采用CEC2013定义的28个标准函数[16]作为优化对象,如表1所示.其中(S)表示该函数的变量是可分离的,(N)表示变量是不可分离的,n表示该函数由其他n个基本函数复合而成,所有函数均为极小值优化.

3.2 对比方案

为体现所提出的QICS算法的优良性能,所有函数的优化结果将与普通布谷鸟搜索算法(CS)[1]、基于高斯扰动的布谷鸟搜索算法(Gauss-based Cuckoo Search Algorithm,GCS)[2],混合 CS 算法的 DE 算法(CSDE)[3]进行对比.为保证对比结果客观公正,四种算法采用相同的种群规模.考虑到群智能优化算法具有随机性,为尽量提高对比结果的可信度,所有函数的维数均取D=30维,且每个函数均用4种算法各自独立优化30次,取30次优化的平均结果作为对比指标.

3.3 参数设置

关于本文提出的QICS,除入量子计算机制外,并未增加新的控制参数,其控制参数个数与普通CS是相同的.关于这些算法的参数设置:发现概率Pa=0.25;种群规模NP=50;空间维数D=30;CS-DE中的交叉概率Pc=0.9,加权因子F=0.5.

3.4 对比结果

由于本文提出的QICS,需要计算旋转矩阵,计算量较大,因此首先考察相同迭代步数下QICS与CS的优化性能对比.迭代步数取1000,每个函数采用两种算法分别优化30次的平均结果对比如表2所示.

在表2中,粗体数字表示该结果优于对比算法的结果.由此可知,全部 28 个函数中,QICS 有 27 个函数的优化结果优于CS,只有第15个函数的优化结果劣于CS.实验结果充分展示了QICS的优势.以函数5、8、10、24为例,两种算法30次优化的平均结果随迭代步数的变化情况如图1所示.

表2 QICS和CS每个函数30次优化的平均结果对比

图1 两种算法30次优化的平均结果对比

为充分验证QICS的优势,有必要在相同运行时间下对比优化结果.因此,在下面的仿真中,在保持QICS迭代步数不变(仍然为1000步)的前提下,将CS、GCS、CS-DE三种算法的迭代步数均设为5000步,然后将每种算法分别独立运行30次,四种算法的平均结果对比如表3所示.

表3 四种算法每个函数30次优化的平均结果对比

在表3中,QICS列的粗体数字表示该结果是四种算法中最优的.而其他三列中的粗体数字表示该结果优于QICS算法.由此可知,QICS优于CS的函数个数为24个,优于GCS的函数个数为22个,优于CSDE的函数个数为20个.实验结果表明QICS明显优于三种对比算法.

3.5 对结果的分析

在28个测试函数中,前5个函数为单峰函数,这类函数寻优难度较低,除变量不可分离的F2外,对于其他4个,QICS均优于对比算法.对于15个基本多峰函数函数F6-F20,除F11和F17外都是变量不可分离的.这些函数寻优难度较大,除 F14-F16 外,对于其他12个,QICS均优于对比算法.对于最后8个变量不可分离的复合函数,寻优难度最大,此时QICS仍有4个函数优于对比算法.实验结果进一步揭示了量子计算机制的入对寻优能力提高的促进作用.

QICS的优良性能在于其编码方式和寻优机制.首先,基于Bloch球面描述的量子比特的编码机制,将优化变量的每一维数值,都映射为Bloch球面上的某一点.这样就将传统方法中优化变量在优化空间每一维上的线性搜索,转化为Bloch球面上的搜索.根据Bloch球面性质,优化空间中全局最优解每一维的数值,都对应于Bloch球面上的一个圆周.只要搜索到该圆周上的任意一点,都等价于找到了该维的全局最优解.因此这种编码方式在一定程度上提高了QICS获得全局最优解的概率.第二,QICS的搜索机制采用了量子比特绕轴旋转的方法,这种方法可以自动实现量子比特的两个相位参数θ和的最佳匹配,从而保证了量子比特在Bloch球面上沿着最短路径向着目标位置逼近,而基于Levy飞行理论的旋转角度确定方法,有效提高了种群的多样性,一定程度上可以避免早熟收敛,从以进一步提升了QICS的搜索能力.

4 结论

经典布谷鸟搜索算法的搜索能力有待于进一步提高.本文尝试将量子计算机制入经典布谷鸟搜索算法,用量子比特编码鸟巢位置,用量子比特在Bloch球面上的绕轴旋转代替经典布谷鸟搜索算法在优化空间中的随机游动,以期较大幅度地提高其优化能力.实验结果表明,这种尝试是成功的,新算法的确呈现出明显优于原算法的性能,从而揭示出,在原算法中入量子计算机制,是提高其优化性能的有效途径.

1 Yang XS,Deb S.Cuckoo search via Levy flights.Proc.of World Congress on Nature &Biologically Inspired Computing.India.2009.210–214.

2 王凡,贺兴时,王燕.基于高斯扰动的布谷鸟搜索算法.西安工程大学学报,2011,25(4):566–569.

3 李明,曹德欣.混合CS算法的DE算法.计算机工程与应用,2012,49(9):57–60.

4 马卫,孙正兴.采用搜索趋化策略的布谷鸟全局优化算法.电子学报,2015,43(12):2429–2439.[doi:10.3969/j.issn.0372-2112.2015.12.013]

5 周欢,李煜.具有动态惯性权重的布谷鸟搜索算法.智能系统学报,2015,10(4):645–651.

6 贺兴时,李娜,杨新社,等.多目标布谷鸟搜索算法.系统仿真学报,2015,27(4):731–737.

7 杨辉华,谢谱模,张晓凤,等.求解多目标优化问题的改进布谷鸟搜索算法.浙江大学学报(工学版),2015,49(8):1600–1608.

8 高云龙,闫鹏.基于多种群粒子群算法和布谷鸟搜索的联合寻优算法.控制与决策,2016,31(4):601–608.

9 李荣雨,刘洋.基于梯度的自适应快速布谷鸟搜索算法.运筹学学报,2016,20(3):45–56.

10 贾云璐,刘胜,宋颖慧.基于种群特征反馈的布谷鸟搜索算法.控制与决策,2016,31(6):969–975.

11 董朝阳,路遥,江未来,等.基于布谷鸟搜索算法的一类变体飞行器容错控制.航空学报,2015,36(6):2047–2054.

12 倪百秀,张翠翠,周本达.基于改进布谷鸟搜索的人工神经网络及其性能仿真.江汉大学学报(自然科学版),2015,43(1):41–50.

13 明波,黄强,王义民,等.基于改进布谷鸟算法的梯级水库优化调度研究.水利学报,2015,46(3):341–349.

14 李东升,高扬,雍爱霞.基于改进离散布谷鸟算法的干扰资源分配研究.电子与信息学报,2016,38(4):899–905.

15 Benenti G,Casati G,Strini G.Principles of quantum computation and information (Volume I:Basic Concepts).Singapore:World Scientific Publishing,2004:100–112.

16 Liang JJ,Qu BY,Suganthan PN,et al.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization.http://www3.ntu.edu.sg/home/EPNSugan/index_files/CEC2013/Definitions%20of%2 0%20CEC%2013%20benchmark%20suite%200117.pdf.

Quantum-Inspired Cuckoo Search Algorithm

LI Pan-Chi,YANG Shu-Yun,LIU Xian-De,PAN Jun-Hui,XIAO Hong,CAO Mao-Jun

(School of Computer &Information Technology,Northeast Petroleum University,Daqing 163318,China)

In order to improve the search ability of the cuckoo search algorithm,this paper proposes a quantum-inspired cuckoo search algorithm by introducing the quantum computing mechanism into the classical cuckoo search algorithm..In the proposed algorithm,the qubits are used to encode individuals,and the Pauli matrixes are employed to determine rotation axis.The Levy flight principle is applied to obtain rotation angle,and the rotation of the qubits on the Bloch sphere is used to update the individuals.The experimental results of extreme optimization of benchmark test functions show that the proposed algorithm is obviously superior to the classical cuckoo search algorithm in optimization ability.

bionic intelligent optimization;swarm intelligence optimization;cuckoo algorithm;quantum-inspired optimization;algorithm design

李盼池,杨淑云,刘显德,潘俊辉,肖红,曹茂俊.量子衍生布谷鸟搜索算法.计算机系统应用,2017,26(9):122–127.http://www.c-sa.org.cn/1003-3254/5915.html

①基金项后:黑龙江省教育厅科学技术研究项后(12541059)

2016-12-19;采用时间:2017-01-05