第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·721· 现的次数多，则me对应的值为0，否则为1，如图4 Pid=Pbesi+bes (30) 所示。 式中y∈【-1,1]内的随机数。由此可构造出直接计 P110101100010 算pa与pa值的函数。 2.2基于CA的量子旋转角选取策略 P010110110111 在QWPEA算法中，新一代个体狼的概率幅 是由上一代个体的概率幅与量子旋转门U(更新 计算获得，更新过程如式(31)： P001011010100 Tcos(△跨） U(0= -sin(ae若）) (31) Ps101010011001 sin(△e） cos(△6) mea100011110001 [um& (32) 图4人工狼与猎物之间的平均最优位置值 在QWPEA中，旋转变异的量子旋转角0可通 Fig.4 The optimal average position between the artificial 过查表获得。但查表操作需要多次比较，运算 wolf and prey 耗费时间长。因此，采用元胞自动机演化规则对 从图4中可知，狼群中有5个最优位置值，每 量子旋转角进行快速调整，将量子狼群视为 个个体狼当前的最优个体信息分别为Peai、Pe2 CA模型，每匹狼视为1个元胞个体，并将其放入二 PeB、Pe4、Pest5,其第1列对应的二进制位值为 维空间区域内四，然后采用元胞邻居结构，对元胞 1、0、1、0、1,依据概率统计方法，则me对应的 邻域范围内的每匹狼的最优解代替自身最优解。 第1列二进制值为1，以此类推。由此获得的 设每匹狼i的n-1个邻居构成的集合为S:(①= me的值为1000011110001。特别地，如果对应的 {:(①)，（①），…，x()。在解算个体狼的邻居集合 每一列中的二进制位数中出现相同的0或1，则 最优解时引入以下演化规则： m随机选择0或l。由此可构造出CQWPEA算 法中mken的函数值。 -1则s=6经 (33) 在QWPEA算法中，式(17)、(18)是探狼和猛 狼在整个搜索空间的局部位置信息，其值表示了局 s0s-6 式中：S与S+1分别表示t与t+1时刻元胞状态；s表 部搜索算子pa,Pa∈(Phes8ed,Pa={P,P2,…,Pol 示元胞邻居集合中状态为1的元胞个数。设第 位于(pew、oe)之间的对角线两端的超矩形中， Pa到pet,gbe的距离需小于对角线的长度，即 g代狼群当前解集X=(后…，x)i=1,2,…,n), Ipid-pbesilpuesti-gbestl (27) 第i匹狼的局部最优解为P=(p,p品…，P)i= Ipid-ghestlpbesui-gbeal (28) L,2,…,n,狼群的全局最优解为Pg=(p,P…Pa 通过对p值的计算，可使种群产生多样性，并 则量子门旋转角的更新策略如式(34)所示： 可使算法跳出局部搜索空间。在OWPEA算法 △=△(c(p-)+c2(P-) (34) 中，局部搜索算子pa的产生主要取决于上一代种 式中：g、g+1表示迭代次数；p表示第匹人工狼 群的P和ge✉中的每一个量子位的随机交叉，形 第j位在第g代邻居集合的局部最优解；p表示整 成下一代的搜索算子pa,显然Pa满足定义I的曼 体狼群第j位在第g代的全局最优解；x,表示第匹 哈顿距离，如图5所示。 人工狼第j位在第g代的当前解；c,和c2表示搜索速 P001001011100 度系数，通常取c1=1,c2=2;△0表示量子旋转角，该 角度根据式(35)计算，可从0.01π~0.04π动态减小。 8101000010001 t11111111111 A0=0.04x-0.04-0.01m)7 (35) P101001011101 式中T与Tx分别表示当前迭代次数和最大进化 图5人工狼的多点交叉算子 迭代次数。 Fig.5 Multi-point crossover operator of wolf 为了增强量子狼群演化算法搜索范围，将量 探狼和猛狼的局部搜索算子，p、p的每一位 子旋转角进一步扩展到[-入，，使狼群遍历范围呈 编码可由式(29)与(30)计算获得： 现双向性。另外，由于量子态经测量后获得二进 Pid=pbesuyxid+ghestyxid (29) 制编码，因此按式(36)进行取值：现的次数多，则mbest对应的值为 0，否则为 1，如图 4 所示。 0 1 0 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 Pbest1 Pbest2 Pbest3 Pbest4 Pbest5 mbest 图 4 人工狼与猎物之间的平均最优位置值 Fig. 4 The optimal average position between the artificial wolf and prey Pbest1 Pbest2 Pbest3 Pbest4 Pbest5 mbest mbest mbest mbest 从图 4 中可知，狼群中有 5 个最优位置值，每 个个体狼当前的最优个体信息分别为 、 、 、 、 ，其第 1 列对应的二进制位值为 1、 0、1、 0、 1，依据概率统计方法，则 对应的 第 1 列二进制值为 1，以此类推。由此获得的 的值为 1000011110001。特别地，如果对应的 每一列中的二进制位数中出现相同的 0 或 1，则 随机选择 0 或 1。由此可构造出 CQWPEA 算 法中 的函数值。 pid pid ∈ (pbesti ,gbestd) pid = {pi1, pi2,··· , piD} (pbesti、gbest) pid pbesti ,gbest 在 QWPEA 算法中，式 (17)、(18) 是探狼和猛 狼在整个搜索空间的局部位置信息，其值表示了局 部搜索算子 ， ， 位于 之间的对角线两端的超矩形中， 到 的距离需小于对角线的长度，即 |pid − pbesti | ⩽ |pbesti −gbest| (27) |pid −gbest| ⩽ |pbesti −gbest| (28) pid pid pbesti gbest pid pid 通过对 值的计算，可使种群产生多样性，并 可使算法跳出局部搜索空间。在 QWPEA 算法 中，局部搜索算子 的产生主要取决于上一代种 群的 和 中的每一个量子位的随机交叉，形 成下一代的搜索算子 ，显然 满足定义 1 的曼 哈顿距离，如图 5 所示。 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 1 0 1 1 1 0 1 Pbesti gbest Pi 图 5 人工狼的多点交叉算子 Fig. 5 Multi-point crossover operator of wolf p d i 、p d 探狼和猛狼的局部搜索算子， j 的每一位 编码可由式 (29) 与 (30) 计算获得： pid = pbestiγx p id +gbestγx p id (29) pjd = pbestix k jd +gbestx k+1 jd (30) γ ∈ [−1,1] pid pjd 式中 内的随机数。由此可构造出直接计 算 与 值的函数[6]。 2.2 基于 CA 的量子旋转角选取策略 U(θ) 在 QWPEA 算法中，新一代个体狼的概率幅 是由上一代个体的概率幅与量子旋转门 更新 计算获得，更新过程如式 (31)： U(θ) =   cos( ∆θ t+1 i j ) −sin( ∆θ t+1 i j ) sin( ∆θ t+1 i j ) cos( ∆θ t+1 i j )   (31) [ α ′ i β ′ i ] = U (θ) [ αi βi ] (32) 在 QWPEA 中，旋转变异的量子旋转角 θ 可通 过查表获得[11]。但查表操作需要多次比较，运算 耗费时间长。因此，采用元胞自动机演化规则对 量子旋转角进行快速调整，将量子狼群视 为 CA 模型，每匹狼视为 1 个元胞个体，并将其放入二 维空间区域内[12] ，然后采用元胞邻居结构，对元胞 邻域范围内的每匹狼的最优解代替自身最优解。 i n−1 S i(t) = {x1 (t), x2 (t),··· , xn (t)} 设每匹狼 的 个邻居构成的集合为 。在解算个体狼的邻居集合 最优解时引入以下演化规则[13] ：    S t = 1, 则S t+1 = { 1, s = 2,3 0, s , 2,3 S t = 0, 则S t+1 = { 1, s = 3 0, s , 3 (33) S t S t+1 t t+1 s g X g i = ( x g i1 , x g i2 ,··· , x g id) (i = 1,2,··· ,n) i P g i = ( p g i1 , p g i2 ,··· , p g id) (i = 1,2,··· ,n) P g g = ( p g g1 , p g g2 ,··· p g gd) 式中： 与 分别表示 与 时刻元胞状态； 表 示元胞邻居集合中状态为 1 的元胞个数。设第 代狼群当前解集 ， 第 匹狼的局部最优解为 ，狼群的全局最优解为 ， 则量子门旋转角的更新策略如式 (34) 所示： △θ g+1 i j =△θ ( c1 ( p g i j − x g i j) +c2 ( p g g j − x g i j)) (34) g、g+1 p g i j i j g p g gi j g x g i j i j g c1 c2 c1 = 1, c2 = 2 ∆θ 0.01π ∼ 0.04π 式中： 表示迭代次数； 表示第 匹人工狼 第 位在第 代邻居集合的局部最优解； 表示整 体狼群第 位在第 代的全局最优解； 表示第 匹 人工狼第 位在第 代的当前解； 和 表示搜索速 度系数，通常取 ； 表示量子旋转角，该 角度根据式 (35) 计算，可从 动态减小。 ∆θ = 0.04π− (0.04π−0.01π)T Tmax (35) 式中 T 与 Tmax分别表示当前迭代次数和最大进化 迭代次数。 [−λ, λ] 为了增强量子狼群演化算法搜索范围，将量 子旋转角进一步扩展到 ，使狼群遍历范围呈 现双向性。另外，由于量子态经测量后获得二进 制编码，因此按式 (36) 进行取值： 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·721·