第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·719· 滑模位置为 向按照游走步长step前进一步继续侦察；如果此时探 (L. w,e0,r） 狼感知的猎物气味浓度为ft,peH,H={L,2,…,h, =L×(1-w小，∈(r1,(I-2)×r） (13) 则自主决策后沿着猎物留下的气味最浓且大于当 2,w,∈(I-2)×1,1） 前位置p:的方向p前移一步，同时对探狼的位置 p进行更新。反复执行上述行为，直到t>t,或 式中：表示滑模交叉结束量子位。可见，候选头 者游走次数T达到最大游走的次数Tx。其中选 狼为最优解时ω，参数最小，滑模位置交叉得到的 择的方向p应满足式(16)： 新解空间越邻近现有值；反之，ω，参数最大，滑模 p'∈max{it,peH 位置交叉得到的新解空间变化越大。 fit?>fito (16) 1.2.4狼群位置更新 在人工狼群中存在的个体探狼有着不同差 在QWPEA中，当滑模交叉结束后，采用上次 异，嗅探猎物资源的方式也不同，因此可取不同 迭代过程中的最优解对狼群中的每一个量子位进 的h值，h可取ham,hma之间的随机整数。而在d维 行量子旋转门更新，更新过程如式(14)。 空间中，探狼沿着p(p=1,2,…,h)个游走方向前 cos(） cos(△） -sin(△dg） cos() 移一步后所处的空间位置为 sin(e） sin(△) cos(△片) sin() (14) 名=u+ysim2红x)xcp (17) 式中：cos()和sin()表示第t+1次迭代的第个 式中：p表示判断游走的方向数；y表示在[-1,1间 量子位的概率幅；△表示第j个量子位的旋转角 均匀分布的随机数；step为第d维的游走步长； 度，i=1,2,…,N,j=1,2,…,d,其大小和方向是由 x表示探狼的位置。 量子人工狼群的行为规则确定的。 2)嚎叫召唤行为 由此可知，量子旋转门是通过改变描述量子 假设量子人工头狼的当前状态为P,头狼采 人工狼位置的相位角来实现人工狼在搜索空间位 用嚎叫召唤行为召集周围的Mm匹猛狼向其位置 置的同步移动。 集合，其中Mnm=N-Sm-l;接到头狼召唤的猛 1.2.5量子狼群变异 狼都以较大的奔袭步长step快速逼近头狼所在的 为了避免算法陷人局部最优解状态，维持狼 位置P,即在第d维空间，猛狼经历第k+1次迭代 群的多样性，以平衡d维猎场空间内随机分布的 的位置为 人工狼和决策变量可行域为基础，实施智能猎杀 =+stepa((p-xa)/pa-xa) (18) 行为后，基于优胜劣汰的生存法则，会有R匹人工 式中：p表示第k代狼群体中头狼的d维空间位置： 狼被淘汰，并会有新的R匹人工狼存活下来，但 x表示猛狼的当前位置；step%(p-xa)p-a) 存活与淘汰的人工狼数量要相等，这样既可维持 表示猛狼向头狼的聚集趋势。 狼群规模数量，也可避免算法的过早收敛和全局 猛狼在向头狼聚拢的过程中，如果猛狼感知 搜索能力差的问题。因此，狼群中个体狼的变异 的猎物气味浓度t,>t,则令t=t,此时猛狼转 过程采用量子非门实现，其表达形式为 换为头狼并发起召唤行为；如果<t,则猛狼继 续快速奔袭，且与头狼t间的距离d.<d 5】 时，即转人围攻。则判定距离d可表示为 1 D 式中：0表示量子旋转角；i=1,2,…,N;j=1,2,…,d -.lmax-min (19) 假设变异概率为Pm,每个人工狼在(0,1)之间 Dw 给定一个随机数random,如果random<pm,则随机 式中：w为距离判定因子；D为空间维数；maxa、minu 选择若干个量子比特，用量子非门交换两个概率 分别为待寻优的第维空间变量的最大值和最小值。 幅，而其旋转角度向量保持不变。 3)智能猎杀行为 1.2.6量子人工狼群行为描述 假设量子人工头狼的当前状态为P,将距离 1)四处游走行为 猎物资源最近的头狼所在位置P看作猎物的位 假设量子人工探狼的当前状态为P,在其感 置。t可视为在第k代狼群中在第d维空间中猎 知的目标猎物资源信息为，=f(x)的范围内随机 物的位置信息，狼群的智能猎杀行为表达为 选择一个位置状态P,如果t,<t,这时探狼代替 =点+y:step·ht-x (20) 头狼发起召唤行为；如果>t,则探狼向P个方 式中：y∈[-1,1]为均匀分布的随机数；step表示人滑模位置为 j sl i =    L, ωi ∈ [ 0,I −1 ) ⌊L×(1−ωi)⌋, ωi ∈ ( I −1 ,(I −2)× I −1 ) 2, ωi ∈ ( (I −2)× I −1 ,1 ) (13) j sl i ωi ωi 式中： 表示滑模交叉结束量子位。可见，候选头 狼为最优解时 参数最小，滑模位置交叉得到的 新解空间越邻近现有值；反之， 参数最大，滑模 位置交叉得到的新解空间变化越大。 1.2.4 狼群位置更新 在 QWPEA 中，当滑模交叉结束后，采用上次 迭代过程中的最优解对狼群中的每一个量子位进 行量子旋转门更新，更新过程如式 (14)。   cos( θ t+1 i j ) sin( θ t+1 i j )   =   cos( ∆θ t+1 i j ) −sin( ∆θ t+1 i j ) sin( ∆θ t+1 i j ) cos( ∆θ t+1 i j )   ×   cos( θ t i j) sin( θ t i j)   (14) cos( θ t+1 i j ) sin( θ t+1 i j ) t+1 j ∆θ t+1 i j j i = 1,2,··· ,N j = 1,2,··· ,d 式中： 和 表示第 次迭代的第 个 量子位的概率幅； 表示第 个量子位的旋转角 度， ， ，其大小和方向是由 量子人工狼群的行为规则确定的。 由此可知，量子旋转门是通过改变描述量子 人工狼位置的相位角来实现人工狼在搜索空间位 置的同步移动。 1.2.5 量子狼群变异 d R 为了避免算法陷入局部最优解状态，维持狼 群的多样性，以平衡 维猎场空间内随机分布的 人工狼和决策变量可行域为基础，实施智能猎杀 行为后，基于优胜劣汰的生存法则，会有 匹人工 狼被淘汰，并会有新的 R 匹人工狼存活下来，但 存活与淘汰的人工狼数量要相等，这样既可维持 狼群规模数量，也可避免算法的过早收敛和全局 搜索能力差的问题。因此，狼群中个体狼的变异 过程采用量子非门实现，其表达形式为 [ 0 1 1 1 ] [ cos( θi j) sin( θi j) ] =   cos( π 2 −θi j) sin( π 2 −θi j)   (15) θi j 式中： 表示量子旋转角； i = 1,2,··· ,N ； j = 1,2,··· ,d。 pm (0,1) random<pm 假设变异概率为 ，每个人工狼在 之间 给定一个随机数 random，如果 ，则随机 选择若干个量子比特，用量子非门交换两个概率 幅，而其旋转角度向量保持不变。 1.2.6 量子人工狼群行为描述 1) 四处游走行为 fiti = f ( xi) pj fiti<fitj i fiti>fitj i 假设量子人工探狼的当前状态为 pi，在其感 知的目标猎物资源信息为 的范围内随机 选择一个位置状态 ，如果 ，这时探狼 代替 头狼发起召唤行为；如果 ，则探狼 向 P 个方 stepd s i fitp i , p ∈ H,H = {1,2,··· ,h} pi p ∗ i pi fiti>fitj T Tmax p ∗ 向按照游走步长 前进一步继续侦察；如果此时探 狼 感知的猎物气味浓度为 ， 则自主决策后沿着猎物留下的气味最浓且大于当 前位置 的方向 前移一步，同时对探狼 的位置 进行更新。反复执行上述行为，直到 ，或 者游走次数 达到最大游走的次数 。其中选 择的方向 应满足式（16）： { p ∗ ∈ max{fitp i , p ∈ H} fitp i >fiti0 (16) h h [hmin,hmax] d i p( p = 1,2,··· ,h) 在人工狼群中存在的个体探狼有着不同差 异，嗅探猎物资源的方式也不同，因此可取不同 的 值， 可取 之间的随机整数。而在 维 空间中，探狼 沿着 个游走方向前 移一步后所处的空间位置为 x p id = xid +γ ·sin( 2π× p h ) ×stepd s (17) p γ [−1,1] stepd s d x p id 式中： 表示判断游走的方向数； 表示在 间 均匀分布的随机数； 为第 维的游走步长； 表示探狼的位置。 2) 嚎叫召唤行为 pi Mnum Mnum = N −S num −1 stepd b pd d j k+1 假设量子人工头狼的当前状态为 ，头狼采 用嚎叫召唤行为召集周围的 匹猛狼向其位置 集合，其中 ；接到头狼召唤的猛 狼都以较大的奔袭步长 快速逼近头狼所在的 位置 ，即在第 维空间，猛狼 经历第 次迭代 的位置为 x k+1 jd = x k jd +stepd b · ( ( p k d − x k jd) /   p k d − x k jd    ) (18) p k d k d x k jd j stepd b · ( ( p k d − x k jd) /   p k d − x k jd    ) 式中： 表示第 代狼群体中头狼的 维空间位置； 表示猛狼 的当前位置； 表示猛狼向头狼的聚集趋势。 j fiti>fitj fiti = fitj j fiti<fitj j fitj dis < dnear dnear 猛狼在向头狼聚拢的过程中，如果猛狼 感知 的猎物气味浓度 ，则令 ，此时猛狼 转 换为头狼并发起召唤行为；如果 ，则猛狼 继 续快速奔袭，且与头狼 间的距离 时，即转入围攻。则判定距离 可表示为 dnear = 1 Dω · ∑D d=1 |maxd −mind| (19) ω D maxd、mind d 式中： 为距离判定因子； 为空间维数； 分别为待寻优的第 维空间变量的最大值和最小值。 3) 智能猎杀行为 pi pd fitk id k d 假设量子人工头狼的当前状态为 ，将距离 猎物资源最近的头狼所在位置 看作猎物的位 置。 可视为在第 代狼群中在第 维空间中猎 物的位置信息，狼群的智能猎杀行为表达为 x k+1 id = x k id +γ ·stepd i ·   fitk id − x k id    (20) γ ∈ [−1,1] stepd 式中： 为均匀分布的随机数； i 表示人 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·719·