在人工智能计算和系统工程等领域中，许多离散空间优化问题常具有解的多样性、动态性以及目标函数收敛速度慢等特点。为了在有限的空间环境下快速搜寻到优化问题的最优解，学者们已对多种智能算法进行融合并展开了广泛的研究和应用。

狼群演化算法(wolf pack evolutionary algorithm，WPEA)作为模拟自然界群狼分工协作捕猎的启发式智能优化算法，1970年美国著名专家Mech^[1]在其著作中对狼群的行为特征进行了详细的描述；2014年Mirjalili等^[2]将该算法与金字塔模型进行结合，提出了一种具有等级森严的狼群捕猎层次模型，该算法在解决实数空间问题的应用效果明显。此后针对离散空间优化问题，文献[3]针对分类特征子集的优化问题，提出了二进制狼群演化算法；文献[4-5]提出了一种改进的二进制狼群演化算法，扩展了狼群演化算法的应用范围；Srikanth等^[6]在深入分析狼群演化算法的基础上，针对组合调度优化问题，提出了二进制量子狼群演化算法(quantum wolf pack evolutionary algorithm，QWPEA)。QWPEA算法相对于WPEA算法具有原理简单、参数设置少、收敛速度快、较强的全局搜索能力等特点，在测试函数和实际工程应用中取得了突出的效果^[7-8]。但这些应用都是以固定的搜索空间和种群个体位置的静态更新为基础进行优化求解，对于离散空间中局部和全局的并行演化以及狼群中的个体狼的量子位置旋转角的动态选取和调整问题，QWPEA算法并没有一个有效的解决方法。

元胞自动机(cellar automation，CA)最早由冯诺伊曼在1966年提出^[9]，CA是一种根据简单的并行演化规则和协同更新方法，采用元胞来模拟复杂的离散系统动力学方法^[10]，CA具有时空动态性、状态离散性和同步性等基本特征。

为了解决有限的离散空间内狼群演化算法的收敛速度慢、搜索能力弱以及易于陷入局部最优等问题，提出了一种求解离散优化问题的元胞量子狼群演化算法(cellar quantum-behaved wolf pack evolutionary algorithm，CQWPEA)，该算法主要采用二进制编码方式和元胞自动机中的演化规则，分别实现量子狼群中的个体狼位置与猎物之间的距离以及量子旋转角的选取和调整，并给出了头狼与猎物资源位置的编码方式，同时给出了探狼和猛狼局部搜索算子的编码方式，分析了编码规则。另外，采用泛函分析方法对该算法的收敛性进行了证明，最后通过6个测试函数验证了CQWPEA算法的有效性和合理性。

1 量子狼群演化算法

为了使量子狼群算法适应离散搜索空间寻优问题，受二进制编码量子粒子群演化算法^[11]的启示，在量子狼群演化算法中引入二进制编码，融合元胞自动机演化规则，提出了求解离散优化问题的元胞量子行为狼群演化算法。为分析方便，首先对元胞自动机原理、二进制量子狼群演化算法中的狼群行为规则、头狼产生规则、狼群更新和变异等演化方程进行描述。

1.1 元胞自动机原理

元胞自动机通过利用大量元胞的并行演化规则来模拟复杂结构和过程，成为探索复杂系统的有效工具^[12]。CA协同更新元胞空间中的所有元胞，协同更新的规则：下一个时刻元胞 $i$ 的状态是由自身和邻居在前一时刻的状态来决定的。元胞状态集、邻居、元胞空间以及局部演化规则作为CA的基本组成要素，其邻接类型主要有两种，即Von.Neumann 型和 Moore 型，如图1所示。

元胞自动机的动态演化规则以元胞的动态时间状态变化集合为基础，其可表示为

$F: S_t^Z \to S_{t + 1}^Z $

(1)

式中： $S$ 表示元胞状态的有限集合； $Z$ 表示取整数集的一维空间； $t$ 表示时间值。

元胞的局部演化函数 $f$ 对于元胞的动态演化规则具有决定性作用，在取整数的一维空间中，元胞与其邻居可用 $ S^{2r + 1} $ 来表示，元胞的局部演化函数 $f$ 可表示为

$f: S_t^{2r + 1} \to S_{t + 1}$

(2)

元胞局部演化函数 $f$ 都是在有限的元胞状态集上输入和输出的，将局部演化函数与元胞空间内的每个元胞进行组合优化，这样就形成了一个全局演化规则：

$ {F(c}_{t + 1}^i ) = f( c_t^{i - r} ,c_t^{i - r + 1}, \cdots , c_t^i , \cdots , c_t^{i + r} )$

(3)

式中： $ c_t^i $ 表示在位置 $i$ 处的元胞， $r$ 表示邻居半径。

CA由一个标准的四元组构成，其形式为

$A = ( H_D ,S,M,f)$

(4)

式中： $A$ 为一个CA； $H$ 和 $D$ 为一个元胞空间和维度数； $S$ 为元胞的离散状态有限集； $M$ 为所有元胞(邻域和中心元胞)的组合，其可表示为

$N = ( S_1 , S_2 , \cdots , S_n )$

(5)

式中： $n$ 表示一个元胞空间内的元胞邻居数； $ S_i $ 是一个取值为 $1 \sim n$ 的整数集； $f$ 表示局部演化函数在 $ S^n \to S$ 的映射过程；确定元胞空间中的所有元胞位置采用 $ Z^d $ 整数矩阵。

1.2 量子狼群算法 1.2.1 量子狼群编码

在量子狼群演化算法中，人工狼编码是以一组量子位和二进制表示，每个量子位的状态可用式表（6）示：

$\left| \mu \right\rangle = \alpha \left| 0 \right\rangle + \beta \left| 1 \right\rangle $

(6)

式中 $\alpha $ 与 $\beta $ 表示量子位对应状态的概率幅。

人工狼当前位置的编码可通过量子位的概率幅表示，考虑到狼群初始化时编码的随机性，假设采用量子方式编码的个体为 $ p_i $ ，则编码方式为

${p} = \left[ \begin{array}{l} \alpha _1 \quad {\alpha }_2 \quad \cdots \quad \alpha _d \\ \beta _1 \quad \beta _2 \quad \cdots \quad \beta _d \\ \end{array} \right]$

(7)

式中： $ {\left| \alpha \right|}^2 $ 表示量子态被观测为 $\left| 0 \right\rangle $ 态概率， $ {\left| \beta \right|}^2 $ 为量子态被观测为 $\left| 1 \right\rangle $ 态概率，满足 $ {\left| \alpha _i \right|}^2 + {\left| \beta _i \right|}^2 = 1$ ；i = $ 1,2,d;$ $d$ 为编码位数。

由此可知，量子狼群可表示为 $Q(q) = ( q_1^g , q_2^g , \cdots , q_n^g )$ , 其中， $g$ 表示进化代数， $n$ 表示个体狼数量； $ {{q}}_i^g (i = 1,2, \cdots ,n)$ 表示第 $g$ 代狼群中第 $i$ 只狼，即

${{q}}_i^g = \left[ \begin{array}{l} \alpha _{i1}^g \quad {\alpha }_{i2}^g \quad \cdots \quad \alpha _{id}^g \\ \beta _{i1}^g \quad \beta _{i2}^g \quad \cdots \quad \beta _{id}^g \\ \end{array} \right]$

(8)

最后通过对 $Q(q)$ 进行量子测量，获得一组确定的解 $p(g) = ( x_1^g , x_2^g , \cdots , x_n^g )$ ，其中 $ x_i^g (i = 1,2, \cdots ,n)$ 为一匹狼通过量子测量到确定状态的二进制序列，若该二进制序串的位数为 $d$ ，那么 $ x_i^g $ 可以表示为 $ x_i^g = ( x_{i1}^g , x_{i2}^g , \cdots , x_{id}^g )$ 。

1.2.2 双策略的初始量子位生成过程

在初始化狼群演化过程中，狼群中每匹狼位置的所有量子位对应态的概率幅可采用Logistic混沌映射产生，其产生的基本过程为：

1) 设狼群规模为 $n$ ，个体狼位置编码的长度为 $d$ ；

2) 随机产生 $d$ 个混沌变量初始值 $ x_i^j (i = 1,2, \cdots ,n$ ； $j = 1,2, \cdots ,d)$ ;

3) 对式(9)采用迭代计算获得相应的混沌变量序列 $ x_k^j (k = 1,2, \cdots ,n;j = 1,2, \cdots ,d)$ ，用这 $n$ 个混沌变量来初始化狼群：

$x_{k + 1}^j = \mu x_k^j (1 - x_k^j ),\quad k = 0,1, \cdots ,n$

(9)

式中：μ为混沌因子， $ 0 \leqslant \mu \leqslant 4$ ；k为迭代次数。当 $\mu \!=\! 4$ ， $0 \leqslant x_k^j \leqslant 1$ 时，Logistic完全处于混沌状态。

4) 采用2种策略将式(8)中的 $ \alpha _{id}^g $ 、 $ \beta _{id}^g $ 分别初始化为 $\cos (2 x_k^j {\text{π}})$ 、 $\sin (2 x_k^j {\text{π}})$ 和 $ x_i^j $ 、 $\sqrt { { {1 - (x}_k^j )}^2 } $ ，由此获得 $ 2^n $ 个全部个体；

5) 计算全部 $ 2^n $ 个个体的适应度值并进行排序，选取 $n$ 个适应度值高的个体狼构成初始狼群。

1.2.3 头狼产生规则

在初始解空间中，将最接近猎物资源(或最优目标函数)的个体狼视为头狼，头狼直接进入迭代过程。算法运行中，通过比较每匹人工狼的量子位状态 $ s_j $ ，获得当前狼群迭代过程中的最优个体狼作为头狼，最终求解得到头狼的位置和最佳适应度。第 $j$ 个位上的量子位状态可表示为

$ s_j = \left\{ \begin{aligned} & 0,\quad {\rm{random}}\left[ {0,1} \right]> {\left| { \alpha _j } \right|}^2 \\& 1,\quad {\rm{random}}\left[ {0,1} \right] \leqslant {\left| { \alpha _j } \right|}^2 \\ \end{aligned} \right.$

(10)

式中： $ ( s_1,s_2, \cdots, s_j )$ 表示量子状态位对应于人工狼的二进制表示形式； ${\rm{random}}\left[ {0,1} \right]$ 表示在 $\left[ {0,1} \right]$ 之间的随机数， $j = 1,2, \cdots ,d$ 。

在传统的进化算法中，与狼群算法的“优胜劣汰生存”规则和遗传算法的“轮盘赌”规则不同的是，本文设计了一种基于滑模原理的交叉量子位遗传演化方法，用于将选择之后产生的候选头狼集合 $ Z^{od} $ 中的个体头狼按优秀程度降序排序，然后从染色体右端低量子位开始与头狼染色体按照滑模方式交叉，式(11)和式(12)表示交叉参数 $ \omega _i $ 呈高斯分布，随着候选个体头狼逐渐陷入局部解，如图2所示，交叉点滑模按照式(13)向左移动，用于分别与新一代头狼迭代，产生更优秀后代头狼。

交叉权值分布函数为

$ f_{\rm{gs}} \left( {\left. { e_i } \right)} \right. = \frac{1}{{\sqrt {2{\text{π}}\sigma } }}\exp \left[ {\left. { - \frac{{ {\left( {\left. { e_i - \mu } \right)} \right.}^2 }}{{2 \sigma ^2 }}} \right]} \right.$

(11)

式中： $ Z_i^{\rm{od}} = ( Z_{i,1}^{\rm{od}} , Z_{i,2}^{\rm{od}} , \cdots , Z_{i,j}^{\rm{od}} ),j \in L$ 表示第 $i$ 匹候选头狼染色体量子位 $j$ 从最优至次优串排列； $i = 1,2, \cdots ,N;j = 1,2,\; \cdots ,d$ 。

交叉权值为

$\left\{ \begin{aligned} & \omega _i = \int\limits_{\frac{i}{I}\sigma }^{\frac{{i + 1}}{I}\sigma } { f_{\rm{gs}} \left( {\left. { e_i } \right)} \right.{\rm{d}} e_i ,\quad i \in I} \\ &\displaystyle\sum\limits_{i = 1}^I { \omega _i = 1} \\ \end{aligned} \right.$

(12)

式中I表示当前候选头狼数量。

滑模位置为

$j_i^{\rm{sl}} = \left\{ \begin{aligned}& L, \quad \omega _i \in \left[ {0, I^{ - 1} } \right) \\ &\left\lfloor {L \times \left( {\left. {1 - \omega _i } \right)} \right.} \right\rfloor , \quad \omega _i \in \left( { I^{ - 1} ,(I - 2) \times I^{ - 1} } \right) \\ &2, \quad \omega _i \in \left( {(I - 2) \times I^{ - 1} ,1} \right) \\ \end{aligned} \right.$

(13)

式中： $ j_i^{sl} $ 表示滑模交叉结束量子位。可见，候选头狼为最优解时 $ \omega _i $ 参数最小，滑模位置交叉得到的新解空间越邻近现有值；反之， $ \omega _i $ 参数最大，滑模位置交叉得到的新解空间变化越大。

1.2.4 狼群位置更新

在QWPEA中，当滑模交叉结束后，采用上次迭代过程中的最优解对狼群中的每一个量子位进行量子旋转门更新，更新过程如式(14)。

$\left[ \begin{array}{l} \!\!\! \cos \left( {\left. { \theta _{ij}^{t + 1} } \right)} \right. \!\!\! \\\!\!\! \sin \left( {\left. { \theta _{ij}^{t + 1} } \right)} \right. \!\!\! \\ \end{array} \right] = \left[ \begin{array}{l} \!\!\! \cos \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right.\;\;\;\; - \sin \left( {\left. { {\Delta \theta }_{ij}^{t + 1} } \right)} \right. \!\!\! \\ \!\!\! \sin \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right.\;\;\;\;\;\;\cos \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right.\!\!\! \\ \end{array} \right] \times \left[ \begin{array}{l} \!\!\! \cos \left( {\left. { \theta _{ij}^t } \right)} \right.\!\!\! \\ \!\!\! \sin \left( {\left. { \theta _{ij}^t } \right)} \right. \!\!\! \\ \end{array} \right]$

(14)

式中： $\cos \left( {\left. { \theta _{ij}^{t + 1} } \right)} \right.$ 和 $\sin \left( {\left. { \theta _{ij}^{t + 1} } \right)} \right.$ 表示第 $t + 1$ 次迭代的第 $j$ 个量子位的概率幅； $ {\Delta \theta }_{ij}^{t + 1} $ 表示第 $j$ 个量子位的旋转角度， $i = 1,2, \cdots ,N$ ， $j = 1,2, \cdots ,d$ ，其大小和方向是由量子人工狼群的行为规则确定的。

由此可知，量子旋转门是通过改变描述量子人工狼位置的相位角来实现人工狼在搜索空间位置的同步移动。

1.2.5 量子狼群变异

为了避免算法陷入局部最优解状态，维持狼群的多样性，以平衡 $d$ 维猎场空间内随机分布的人工狼和决策变量可行域为基础，实施智能猎杀行为后，基于优胜劣汰的生存法则，会有 $R$ 匹人工狼被淘汰，并会有新的R匹人工狼存活下来，但存活与淘汰的人工狼数量要相等，这样既可维持狼群规模数量，也可避免算法的过早收敛和全局搜索能力差的问题。因此，狼群中个体狼的变异过程采用量子非门实现，其表达形式为

$\left[ \begin{array}{l}0\;\;\;1\\1\;\;\;\;1\end{array} \right]\left[ \begin{array}{l}\cos \left( {\left. { \theta _{ij} } \right)} \right.\\\sin \left( {\left. { \theta_{ij} } \right)} \right.\end{array} \right] = \left[ \begin{array}{l}\cos \left( {\left. { {\displaystyle{{\frac{\text{π}}{2}}} -} {\theta _{ij}} } \right)} \right.\\\sin \left( {\left. { {\displaystyle{{\frac{\text{π}}{2}}}- }{\theta _{ij}} } \right)} \right.\end{array} \right]$

(15)

式中： $ \theta _{ij} $ 表示量子旋转角； $i = 1,2, \cdots ,N$ ； $j = 1,2, \cdots ,d$ 。

假设变异概率为 $ p_m $ ，每个人工狼在 $\left( {\left. {0,1} \right)} \right.$ 之间给定一个随机数random，如果 $ {{\rm{random}}{\text{<}} p}_m $ ，则随机选择若干个量子比特，用量子非门交换两个概率幅，而其旋转角度向量保持不变。

1.2.6 量子人工狼群行为描述

1) 四处游走行为

假设量子人工探狼的当前状态为p_i，在其感知的目标猎物资源信息为 $ {\rm{fit}}_i = f\left( {\left. { x_i } \right)} \right.$ 的范围内随机选择一个位置状态 $ p_j $ ，如果 $ {\rm{fit}}_i {\text{<}} {\rm{fit}}_j $ ，这时探狼 $i$ 代替头狼发起召唤行为；如果 $ {\rm{fit}}_i {\text{>}} {\rm{fit}}_j $ ，则探狼 $i$ 向P个方向按照游走步长 $ {\rm{step}}_s^d $ 前进一步继续侦察；如果此时探狼 $i$ 感知的猎物气味浓度为 $ {\rm{fit}}_i^p,p \in H,$ $ H = \{ 1,2, \cdots ,h\} $ ，则自主决策后沿着猎物留下的气味最浓且大于当前位置 $ p_i $ 的方向 $ p^ * $ 前移一步，同时对探狼 $i$ 的位置 $ p_i $ 进行更新。反复执行上述行为，直到 $ {\rm{fit}}_i {\text{>}} {\rm{fit}}_j $ ，或者游走次数 $T$ 达到最大游走的次数 $ T_{\max } $ 。其中选择的方向 $ p^ * $ 应满足式（16）：

$\left\{ \begin{array}{l} \!\!\! p^ * \in \max \{ {{\rm{fit}}_i^p} ,p \in H\} \\ \!\!\!{{\rm{fit}}_i^p}{\text{>}} {{\rm{fit}}_i}_{0} \\ \end{array} \right.$

(16)

在人工狼群中存在的个体探狼有着不同差异，嗅探猎物资源的方式也不同，因此可取不同的 $h$ 值， $h$ 可取 $[ h_{\min } , h_{\max } ]$ 之间的随机整数。而在 $d$ 维空间中，探狼 $i$ 沿着 $p\left( {\left. {p = 1,2, \cdots ,h} \right)} \right.$ 个游走方向前移一步后所处的空间位置为

$ x_{id}^p = x_{id} + \gamma \cdot \sin \left( {\left. {2{\text{π}} \times \frac{p}{h}} \right)} \right. \times {{\rm{step}}}_s^d $

(17)

式中： $p$ 表示判断游走的方向数； $\gamma $ 表示在 $\left[ { - 1,1} \right]$ 间均匀分布的随机数； $ {{\rm{step}}}_s^d $ 为第 $d$ 维的游走步长； $ x_{id}^p $ 表示探狼的位置。

2) 嚎叫召唤行为

假设量子人工头狼的当前状态为 $ p_i $ ，头狼采用嚎叫召唤行为召集周围的 $ M_{{\rm{num}}} $ 匹猛狼向其位置集合，其中 $ M_{{\rm{num}}} = N - S_{{\rm{num}}} - 1$ ；接到头狼召唤的猛狼都以较大的奔袭步长 $ {\rm{step}}_b^d $ 快速逼近头狼所在的位置 $ p_d $ ，即在第 $d$ 维空间，猛狼 $j$ 经历第 $k + 1$ 次迭代的位置为

$ x_{jd}^{k + 1} = x_{jd}^k + {\rm{step}}_b^d \cdot \left( {\left. {\left( {\left. { p_d^k - x_{jd}^k } \right)/\left| { p_d^k - x_{jd}^k } \right|} \right.} \right)} \right.$

(18)

式中： $ p_d^k $ 表示第 $k$ 代狼群体中头狼的 $d$ 维空间位置； $ x_{jd}^k $ 表示猛狼 $j$ 的当前位置； $ {{\rm{step}}}_b^d \cdot \left( {\left. {\left( {\left. { p_d^k - x_{jd}^k } \right)/\left| { p_d^k - x_{jd}^k } \right|} \right.} \right)} \right.$ 表示猛狼向头狼的聚集趋势。

猛狼在向头狼聚拢的过程中，如果猛狼 $j$ 感知的猎物气味浓度 $ {\rm{fit}}_i {\text{>}} {\rm{fit}}_j $ ，则令 $ {\rm{fit}}_i = {\rm{fit}}_j $ ，此时猛狼 $j$ 转换为头狼并发起召唤行为；如果 $ {\rm{fit}}_i {\text{<}} {\rm{fit}}_j $ ，则猛狼 $j$ 继续快速奔袭，且与头狼 $ {\rm{fit}}_j $ 间的距离 $ d_{{\rm{is}}} < d_{{\rm{near}}} $ 时，即转入围攻。则判定距离 $ d_{{\rm{near}}} $ 可表示为

$ d_{{\rm{near}}} = \frac{1}{{D\omega }} \cdot \sum\limits_{d = 1}^D {\left| { {\max }_d - {\min }_d } \right|} $

(19)

式中： $\omega $ 为距离判定因子； $D$ 为空间维数； $ {\max }_d {\text{、}}\!\!{\min }_d $ 分别为待寻优的第 $d$ 维空间变量的最大值和最小值。

3) 智能猎杀行为

假设量子人工头狼的当前状态为 $ p_i $ ，将距离猎物资源最近的头狼所在位置 $ p_d $ 看作猎物的位置。 $ {\rm{fit}}_{id}^k $ 可视为在第 $k$ 代狼群中在第 $d$ 维空间中猎物的位置信息，狼群的智能猎杀行为表达为

$ x_{id}^{k + 1} = x_{id}^k + {\gamma \cdot {\rm{step}}}_i^d \cdot \left| { {\rm{fit}}_{id}^k - x_{id}^k } \right|$

(20)

式中： $\gamma \in \left[ { - 1,1} \right]$ 为均匀分布的随机数； $ {\rm{step}}_i^d $ 表示人工狼 $i$ (猛狼和探狼)在 $d$ 维空间中智能步长数。

假设在第 $d$ 个变量的取值范围为 $\left[ { {\max }_d , {\min }_d } \right]$ ，则从狼群算法中抽象出的3种智能行为所涉及的游走步长 $ {\rm{step}}_s^d $ 、奔袭步长 $ {\rm{step}}_b^d $ 和猎杀步长 $ {\rm{step}}_i^d $ 之间的关系为

$ {{\rm{step}}}_s^d = 2 \cdot {{\rm{step}}}_i^d = {{ {{\rm{step}}}_b^d } / {2 = }}{{\left| { {\max }_d , {\min }_d } \right|} / S}$

(21)

式中： $S$ 表示步长因子， $S$ 值越小人工探狼搜索越精细。

2 元胞量子狼群演化算法

在CQWPEA算法中，人工狼(头狼、探狼和猛狼)的位置表示为一组0、1构成的二进制编码向量，首先通过使用概率统计方法对个体狼与猎物之间的最优平均位置值进行编码，并记录编码位中出现的0、1次数，实现局部搜索算子编码位的计算；然后，采用元胞自动机选取和调整人工狼群位置的量子位旋转角，增强元胞量子狼群演化算法的搜索空间，加快算法的收敛速度。

CQWPEA的设计思路是，将散布在猎场空间中的量子狼群中的探狼朝着猎物遗留的气味浓度强和环境信息方向进行嗅探，一旦发现猎物，探狼需要判断自身与头狼距离猎物资源的位置，如果探狼与猎物的量子位置旋转角比头狼与猎物的量子位置旋转角大，则探狼代替头狼发起嚎叫召唤行为，否则向头狼报告猎物的位置信息；猛狼收到嚎叫召唤信号后，猛狼迅速向头狼所在位置或猎物所在位置靠拢，同时对猎场的周围环境进行探测，量子狼群进化算法中的人工狼之间以嚎叫信息实现相互通信，并通过元胞机中的局部演化规则不断调整人工狼的位置旋转角度，更好地调节人工狼群的搜索范围和定位猎物的位置，随着局部搜索过程的不断推进，人工狼群向着全局最优解逼近，最终通过计算头狼与猎物的平均最优位置来实现目标函数的优化求解。

2.1 个体狼位置的二进制编码

在二进制编码的元胞量子狼群演化算法中，为了精确描述狼群中头狼与猎物资源之间的距离关系，将元胞空间作为量子狼群演化算法的搜索空间，将距离猎物资源最近的头狼所在位置 $ p_d $ 看作猎物资源(目标函数)的位置，使用量子狼群进化算法中的探狼、猛狼搜索到的局部最优解和猎杀攻击后的全局最优解分别作为元胞空间内一个元胞，并采用扩展Moore邻居类型，采用数学语言对元胞量子狼群演化算法进行形式化描述。

定义1　设以 $N \times m$ 维欧式空间作为量子狼群演化算法的搜索空间，人工狼的位置为

${X_i} = \left\{ {{x_{i1}},{x_{i2}}, \cdots ,{x_{im}}{\rm{|}}i \in \left\{ {1,2, \cdots ,N;j \in 1,2, \cdots ,m} \right\}} \right\}$

(22)

式中： $N$ 表示人工狼总数， $m$ 表示编码长度； $ x_{ij} $ 表示人工狼的第 $ X_i $ 个位置的第 $j$ 个编码位置，通过反置赋值操作且只能取0、1；头狼 $p$ 和猎物资源 $q$ 之间的曼哈顿距离可表示为

$L\left( {p,q} \right) = \sum \limits_{j = 1}^m \left| {{x_{pj}} - {x_{qj}}} \right|,\quad p,q \in \left\{ {1,2, \cdots ,N} \right\}$

(23)

定义2　移动算子^[5]，设人工狼 $i$ 的位置为 ${X_i} = $ $ \{ {x_{i1}},{x_{i2}}, \cdots ,{x_{ij}}, \cdots ,{x_{im}}\} $ ； $M$ 表示非空的反置编码位，即表达了人工狼的位置； $r$ 是非空的反置编码位数，即游走步长；运动算子 $\theta \left( {{X_i},M,r} \right)$ 表示在人工狼 $i$ 的位置 $ X_i $ 中，从 $M$ 个编码位中随机选择 $r$ 个编码位并对其进行反置操作。

定义3　设集合 $C = \left( {{c_1},{c_2}, \cdots ,{c_i}, \cdots ,{c_n}} \right),{c_i} \in \left\{ {0,1} \right\}$ ， ${c_i}$ 的排列组合构成元胞空间，其具体形式为

$L = \left\{ {{\rm{Cell}}X = \left( {{c_1},{c_2}, \cdots ,{c_i}, \cdots ,{c_n}} \right){\rm{|}}{c_i} \in \left\{ {0,1} \right\}} \right\}$

(24)

式中CellX表示由 ${c_i}$ 所组合的元胞。

定义4^[7] 　扩展Moore邻居类型

$ N_{{\rm{moore}}} = \left\{ {{\rm{Cell}}\left. Y \right|{\rm{diff}}\left( {\left. {{\rm{cell}}Y - {\rm{cell}}\;X} \right)} \right. \leqslant r,{\rm{cell}}X,{\rm{cell}}Y \in L} \right\}$

(25)

式中：任意两个 ${c_i}{\text{、}}\!\!{c_{i + 1}}$ 的排序组合的差异度为 ${\rm{diff}}\left( {{\rm{cell}}Y - {\rm{cell}}X} \right) \leqslant r$ ， $r$ 为差异度，本文取 $r = 2$ 。

在二进制编码的元胞量子狼群演化算法中，为了精确表达头狼和猎物资源之间的距离，根据定义1，假设头狼和猎物的位置为 $\left( {{X_1},{X_2}} \right)$ ，它们分别有两个决策变量 $\left( {{X_{11}},{X_{12}}} \right)$ 、 $\left( {{X_{21}},{X_{22}}} \right)$ ，采用6位二进制编码对每个决策变量进行表示，如图3所示。

在CQWPEA算法中，定义头狼与猎物(目标函数)含有决策变量的个数即为元胞空间的维数；例如， ${X_{id}}$ 表示狼群中第 $i$ 匹头狼的 $d$ 个决策变量， ${X_i}{\text{、}}\!\!{X_{id}}$ 的二进制编码长度分别用 $l$ 和 $ l_d $ 表示，则

$l = \sum \limits_{i = 1}^d {l_i},\quad d = 1,2, \cdots ,D$

(26)

根据量子狼群演化算法，通过修改算法中的头狼和猎物之间的平均最优位置 ${m_{{\rm{best}}}}$ 的值，生成CQWPEA中的 ${m_{{\rm{best}}}}$ ，并用二进制位串表示种群中全部最优个体狼位置，通过概率统计方法^[6]，记录二进制编码位中0、1出现的概率次数，如果0出现的次数多，则 ${m_{\rm{best}}}$ 对应的值为0，否则为1，如图4所示。

从图4中可知，狼群中有5个最优位置值，每个个体狼当前的最优个体信息分别为 ${P_{{\rm{best1}}}}$ 、 ${P_{{\rm{best2}}}}$ 、 ${P_{{\rm{best3}}}}$ 、 ${P_{{\rm{best4}}}}$ 、 ${P_{{\rm{best5}}}}$ ，其第1列对应的二进制位值为1、0、1、0、1，依据概率统计方法，则 ${m_{\rm{best}}}$ 对应的第1列二进制值为1，以此类推。由此获得的 ${m_{\rm{best}}}$ 的值为1000011110001。特别地，如果对应的每一列中的二进制位数中出现相同的0或1，则 ${m_{\rm{best}}}$ 随机选择0或1。由此可构造出CQWPEA算法中 ${m_{\rm{best}}}$ 的函数值。

在QWPEA算法中，式(17)、(18)是探狼和猛狼在整个搜索空间的局部位置信息，其值表示了局部搜索算子 ${p_{id}}$ ， ${p_{id}} \in \left( {{p_{{\rm{best}}i}},{g_{{\rm{best}}d}}} \right)$ ， ${p_{id}} = \left\{ {{p_{i1}},{p_{i2}}, \cdots ,{p_{iD}}} \right\}$ 位于 $\left( {{p_{{\rm{best}}i}}{\text{、}}\!\!{g_{\rm{best}}}} \right)$ 之间的对角线两端的超矩形中， ${p_{id}}$ 到 ${p_{{\rm{best}}i}},{g_{\rm{best}}}$ 的距离需小于对角线的长度，即

$\left| {{p_{{id}}} - {p_{{\rm{best}}i}}} \right| \leqslant \left| {{p_{{\rm{best}}i}}} - {g_{\rm{best}}} \right|$

(27)

$\left| {{p_{{id}}} - {g_{\rm{best}}}} \right| \leqslant \left| {{p_{{\rm{best}}i}} - {g_{\rm{best}}}} \right|$

(28)

通过对 ${p_{id}}$ 值的计算，可使种群产生多样性，并可使算法跳出局部搜索空间。在QWPEA算法中，局部搜索算子 ${p_{id}}$ 的产生主要取决于上一代种群的 ${p_{\rm{best}i}}$ 和 ${g_{\rm{best}}}$ 中的每一个量子位的随机交叉，形成下一代的搜索算子 ${p_{id}}$ ，显然 ${p_{id}}$ 满足定义1的曼哈顿距离，如图5所示。

探狼和猛狼的局部搜索算子， $ p_i^d {\text{、}}\!\!p_j^d $ 的每一位编码可由式(29)与(30)计算获得：

${p_{id}} = {p_{{{\rm{best}}}i}}\gamma x_{id}^p + {g_{{\rm{best}}}}\gamma x_{id}^p$

(29)

${p_{jd}} = {p_{{{\rm{best}}}i}}x_{jd}^k + {g_{{\rm{best}}}}x_{jd}^{k + 1}$

(30)

式中 $\gamma \in \left[ { - 1,1} \right]$ 内的随机数。由此可构造出直接计算 ${p_{id}}$ 与 ${p_{jd}}$ 值的函数^[6]。

2.2 基于CA的量子旋转角选取策略

在QWPEA算法中，新一代个体狼的概率幅是由上一代个体的概率幅与量子旋转门 $U(\theta )$ 更新计算获得，更新过程如式(31)：

${{U}}(\theta ) = \left[ \begin{aligned}& \cos \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right.\;\;\; - \sin \left( {\left. { {\Delta \theta }_{ij}^{t + 1} } \right)} \right. \\ & \sin \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right.\;\;\;\;\;\cos \left( {\left. {\Delta \theta _{ij}^{t + 1} } \right)} \right. \\ \end{aligned} \right]$

(31)

$\left[ {\begin{array}{*{20}{c}} {\alpha _i'} \\ {\beta _i'} \end{array}} \right] = U\left( \theta \right)\left[ {\begin{array}{*{20}{c}} {{\alpha _i}} \\ {{\beta _i}} \end{array}} \right]$

(32)

在QWPEA中，旋转变异的量子旋转角 $\theta $ 可通过查表获得^[11]。但查表操作需要多次比较，运算耗费时间长。因此，采用元胞自动机演化规则对量子旋转角进行快速调整，将量子狼群视为CA模型，每匹狼视为1个元胞个体，并将其放入二维空间区域内^[12]，然后采用元胞邻居结构，对元胞邻域范围内的每匹狼的最优解代替自身最优解。

设每匹狼 $i$ 的 $n - 1$ 个邻居构成的集合为 ${S_i}\left( t \right) = $ $ \left\{ {{x_1}\left( t \right),{x_2}\left( t \right), \cdots ,{x_n}\left( t \right)} \right\}$ 。在解算个体狼的邻居集合最优解时引入以下演化规则^[13]：

$\left\{ {\begin{aligned}&{{S^t} = 1,\quad{\text{则}}{S^{t + 1}} = \left\{ {\begin{aligned}{1,\;\;s = 2,3}\\{0,\;\;s \ne 2,3}\end{aligned}} \right.}\\&{{S^t} = 0,\quad{\text{则}}{S^{t + 1}} = \left\{ {\begin{aligned}{1,\;\;s = 3}\\{0,\;\;s \ne 3}\end{aligned}} \right.}\end{aligned}} \right.$

(33)

式中： $ S^t $ 与 $ S^{t + 1} $ 分别表示 $t$ 与 $t + 1$ 时刻元胞状态； $s$ 表示元胞邻居集合中状态为1的元胞个数。设第 $g$ 代狼群当前解集 $X_i^g = \left( {x_{i1}^g,x_{i2}^g, \cdots ,x_{id}^g} \right)\left( {i = 1,2, \cdots ,n} \right)$ ，第 $i$ 匹狼的局部最优解为 $P_i^g = \left( {p_{i1}^g,p_{i2}^g, \cdots ,p_{id}^g} \right) \left( {i =}\right.$ $\left. {1,2, \cdots ,n} \right)$ ，狼群的全局最优解为 $P_g^g = \left( {p_{g1}^g,p_{g2}^g, \cdots p_{gd}^g} \right)$ ，则量子门旋转角的更新策略如式(34)所示：

$\vartriangle \!\theta _{ij}^{g + 1} = \vartriangle \!\theta \left( {{c_1}\left( {p_{ij}^g - x_{ij}^g} \right) + {c_2}\left( {p_{gj}^g - x_{ij}^g} \right)} \right)$

(34)

式中： $g{\text{、}}\!\!g + 1$ 表示迭代次数； $p_{ij}^g$ 表示第 $i$ 匹人工狼第 $j$ 位在第 $g$ 代邻居集合的局部最优解； $p_{gi}^g$ 表示整体狼群第 $j$ 位在第 $g$ 代的全局最优解； $x_{ij}^g$ 表示第 $i$ 匹人工狼第 $j$ 位在第 $g$ 代的当前解； $ c_1 $ 和 ${c_2}$ 表示搜索速度系数，通常取 ${c_1} = 1,{c_2} = 2$ ； $\Delta \theta $ 表示量子旋转角，该角度根据式(35)计算，可从 $0.01{\text{π}} \sim 0.04{\text{π}}$ 动态减小。

$\Delta \theta = 0.04{\text{π}} - \frac{{\left( {0.04{\text{π}} - 0.01{\text{π}} } \right)T}}{{{T_{{\rm{max}}}}}}$

(35)

式中 $T$ 与 ${T_{{\rm{max}}}}$ 分别表示当前迭代次数和最大进化迭代次数。

为了增强量子狼群演化算法搜索范围，将量子旋转角进一步扩展到 $\left[ { - \lambda ,\lambda } \right]$ ，使狼群遍历范围呈现双向性。另外，由于量子态经测量后获得二进制编码，因此按式(36)进行取值：

$\Delta \theta _{ij}^{g + 1} = \left\{ {0,\;\; \pm \Delta \theta ,\;\; \pm 2\Delta \theta ,\;\;3\Delta \theta } \right\}$

(36)

由式(36)可知，本文算法中的量子旋转角扩大了3倍，呈现双向性，避免了混沌序列的迭代计算和多次比较的查表操作，节省了运算时间。

2.3 CQWPEA算法的步骤

1) 初始化参数，根据1.2.2节的双策略对量子狼群的初始量子位进行初始化，并采用二进制序串的形式初始化狼群中的个体狼位置 $x_{id}^k$ ，使 ${p_{\rm{best}}} = $ $ x_{id}^k$ ，计算初始狼群个体的适应度值，同时对算法的基本参数进行初始化操作。

2) 根据 ${m_{\rm{best}}}$ 函数计算人工狼与猎物资源之间的平均最优位置值 ${m_{\rm{best}}}$ 。

3) 根据方程式(29)、(30)计算局部搜索算子 ${p_{id}},{p_{jd}}$ 的值。

4) 根据初始狼群的适应度函数值计算种群中每个个体狼位置值，并与上一次迭代的局部最优值进行比较，如果适应度值 ${\rm{fit}}\left( {\left. {{X_i}} \right)} \right.{{<}}f\left( {{p_{{\rm{best}}i}}} \right)$ ，则用 ${p_{{\rm{best}}i}} = {X_i}$ 更新局部最优位置；反之，则不更新；转入步骤5) 。

5) 量子人工狼按照式(31)~(36)进行元胞邻域搜索，并计算狼群体中新的适应度值。将狼群的全局最优位置值 ${g_{{\rm{best}}id}}$ 与上一次的全局最优位置值 ${g_{{\rm{best}}i - 1}}$ 进行比较，如果 $f\left( {{g_{{{\rm{best}}}id}}} \right){{<}} f\left( {{g_{{\rm{best}}i - 1}}} \right)$ ，则替换原最优位置值，反之，不更新。另外在量子旋转角中，如果 $\Delta \theta = 0$ ，对狼群的量子编码位进行交叉，交换量子位概率幅 $\alpha $ 与 $\beta $ 。

6) 按头狼产生规则和猎物气息元胞邻居空间的演化规则对头狼位置 ${p_d}$ 进行更新，邻域搜索同4)。

7) 将局部搜索算子 ${p_{id}}{\text{、}}\!\!{p_{jd}}$ 的值转换为全局最优位置值。

8) 判断是否满足迭代次数 ${k_{{\rm{max}}}}$ 要求，如果满足，则输出头狼的位置 ${p_d}$ ，即所求解问题的最优解，否则转入2)。

9) 输出目前的最优解集和最优值。

3 CQWPEA算法的收敛性分析

本节将用泛函分析方法^[13-14]对CQWPEA算法的收敛性进行分析证明。令二进制编码字符集 $k{\rm{ = }}\left\{ {0,1} \right\}$ ，采用长度为 $D$ 的二进制位串表示头狼位置编码，编码空间 $S = {\left\{ {0,1} \right\}^D},\left| S \right| = {2^D}$ 。假设狼群规模为 $M$ ，狼群单钱位置集合为 $X$ ，头狼最佳位置集合为 $P$ ，则狼群的当前位置空间可表示为

${S^X} = \left\{ {\left( {{X_1},{X_2}, \cdots ,{X_M}} \right),{X_j} \in S,j = 1,2, \cdots ,M} \right\}$

(37)

狼群中人工狼的最佳位置空间为

${S^P} = \left\{ {\left( {{P_1},{P_2}, \cdots ,{P_M}} \right),{P_j} \in S,j{\rm{ = }}1,2, \cdots ,M} \right\}$

(38)

全局最优解的位置空间为

${S^g}{\rm{ = }}\left\{ {{P_g},{P_g} \in S} \right\} = S$

(39)

根据QWPEA算法的流程图^[6]可知，QWPEA算法的解算过程遵循着反复迭代，逐渐求精的过程，该过程中包括目标函数适应度值的评价、 ${p_{{\rm{best}}}}$ 位置和 ${g_{{\rm{best}}}}$ 位置的选择，以及人工狼的位置更新，从而使狼群达到更优状态。因此，可用随机映射运算过程来抽象表示QWPEA算法的流程。

设 $\left( {\varOmega ,A,P} \right)$ 是狼群搜索的概率空间，可以给出CQWPEA搜索算子的定义，见定义5。

定义5　CQWPEA算法的搜索算子T是通过逐步迭代方式对个体狼的当前位置进行迭代搜索，以获得个体狼的最好位置的过程，该过程是从人工狼当前位置的元胞状态空间以及全局位置的元胞状态空间随机映射到个体狼最好位置状态空间，其映射形式为

$T:\varOmega \times {S^X} \times {S^P} \times {S^{\rm{g}}} \to {S^P}$

(40)

CQWPEA算法在每次迭代解算过程中产生一次映射 ${T_{{\rm{CQWPEA}}}}$ 。设 $X\left( t\right)$ 和 $P\left( t \right)$ 分别为第 $t$ 次迭代过程中产生的当前位置的种群和个体最好位置种群， $X\left( {{{t + 1}}} \right)$ 、 $P\left( {t + 1} \right)$ 、 ${P_g}\left( {t + 1} \right)$ 分别为第 $t + 1$ 次迭代产生的人工狼群位置、个体狼位置以及全局最好位置，则

$P\left( {t + 1} \right) = T\left( {\omega ,X\left( t \right),P\left( t \right),{P_g}\left( t \right)} \right)$

(41)

式中： $t = 0,1, \cdots ,T - 1$ ； $T$ 为最大游走次数或迭代次数。

实验表明，CQWPEA算法中每一代全局最好解位置的适应度值序列是一个递增序列，即

$f\left( {{P_{g,t - 1}}} \right) \leqslant f\left( {{P_{g,t}}} \right) \leqslant f\left( {{P_{g,t + 1}}} \right)$

(42)

式中： ${P_{g,t - 1}} \in P\left( {t - 1} \right)$ 、 ${P_{g,t}} \in P\left( t \right)$ 、 ${P_{g,t + 1}} \in P\left( {t + 1} \right)$ 分别表示第 $t - 1$ 、 $t$ 、 $t + 1$ 代的全局最好解位置。

在CQWPEA算法中，解算优化问题时，通常只需关注搜索过程中狼群攻击获得的最好解，不妨将迭代狼群体用全局最好位置来代替。由此对CQWPEA算法的映射过程进行重新定义，其形式为

${P_{g,t + 1}} = T\left( {\omega ,{P_{g,t}}} \right),\quad {P_{g,t}} \in P\left( t \right),\quad {P_{g,t + 1}} \in P\left( {t + 1} \right)$

(43)

在CQWPEA算法中，解算优化问题的过程可视为元胞演化空间之间的映射。以下采用随机映射的方法证明和分析CQWPEA算法的收敛性。

定义6　定义度量 $d:S \times S \to R$ ，其中 $d$ 的表达式为

$\begin{aligned} d\left( {{P_{g,i}},{P_{g,j}}} \right) = \left| {c - f\left( {{P_{g,i}}} \right) - \left( {c - f\left( {{P_{g,j}}} \right)} \right)} \right| = \left| {f\left( {{P_{g,i}}} \right) - f\left( {{P_{g,j}}} \right)} \right|\end{aligned} $

(44)

式中： $c \to \infty $ ； ${P_{g,i}},{P_{g,j}} \in S\!{\text{；}}\!\!\!\! \left( {S,d} \right)$ 为完备可分的度量空间。

证明　首先证明 $\left( {S,d} \right)$ 是度量空间。设 $S \ne\text{Ø} $ ， $d \in S \times S$ 的实值函数。对于 ${P_{g,i}}{\text{、}}\!\!{P_{g,j}}{\text{、}}\!\!{P_{g,k}} \in S$ ，对应一个实数 $d\left( {{P_{g,i}},{P_{g,j}}} \right) \in S$ 满足：

1) $d\left( {{P_{g,i}},{P_{g,j}}} \right) \! \geqslant \! 0$ ，当且仅当 ${P_{g,i}} \!=\! {P_{g,j}}$ 时， $d( {P_{g,i}} $ ， ${P_{g,j}})= 0$ ，满足非负性；

2) $d\left( {{P_{g,i}},{P_{g,j}}} \right) \!\!=\!\! \left| {c \!-\! f\left( {{P_{g,i}}} \right) \!-\! \left( {c \!-\! f\left( {{P_{g,j}}} \right)} \right)} \right| \!\!=\!\! \left| {c \!-\! f\left( {{P_{g,j}}} \right) - } \right.$ $\left. {\left( {c - f\left( {{P_{g,i}}} \right)} \right)} \right|$ ，满足对称性；

3) $\left( {{P_{g,i}},{P_{g,j}}} \right) \!\!=\!\! \left| {(c \!-\! f\left( {{P_{g,i}}} \right) \!-\! \left( {c \!-\! f\left( {{P_{g,j}}} \right)} \right)} \right| \!\!=\!\! \left| {c \!-\! f\left( {{P_{g,i}}} \right) \!- } \right.$ $\left. {\left( {c - f\left( {{P_{g,k}}} \right)} \right.} \right) \,\,+\,\, \left( {\left. {c - f\left( {{P_{g,k}}} \right)} \right)} \right. - \left( {c - f\left( {{P_{g,j}}} \right)} \right) \,\,\leqslant\,\, {c - f\left( {{P_{g,i}}} \right)} - $ $\left. {\left( {\left. {c - f\left( {{P_{g,k}}} \right)} \right)} \right.} \right|+\left| {\left( {\left. {c - f\left( {{P_{g,k}}} \right)} \right) - \left( {c - f\left( {{P_{g,j}}} \right)} \right)} \right.} \right|$ ，满足三角不等式，因此 $\left( {S,d} \right)$ 为度量空间。

其次证明 $\left( {S,d} \right)$ 为完备度量空间。设 $S$ 是有限的二进制编码位串数，对当前狼群中最好个体狼位置的柯西序列 $\left\{ {{P_{g,i}},{P_{g,i}} \in S} \right\}$ ，以及 $\forall \varepsilon {{>}} 0$ ， $\exists N$ ，当自然数 $n{{>}} N$ 时， $d\left( {{P_{g,n}},{P_{g,m}}} \right){{<}} \varepsilon $ ，当 $n \to \infty $ 时， ${P_{g,n}} \to {P_g}$ 。因此 $\left( {S,d} \right)$ 是完备的度量空间。

最后证明 $\left( {S,d} \right)$ 是可分的。设 $G \subseteq S$ ，因 $S$ 为有限元集合，所以 $G$ 为可数子集。又因为 $G$ 闭包于 $S$ ，所以 $G$ 在 $S$ 中稠密，由此得到 $\left( {S,d} \right)$ 是可分的论证。故 $\left( {S,d} \right)$ 是完备可分的度量空间，证毕。

定义7　随机搜索算子 $T:\varOmega \times S \to S$ 称为随机压缩算子，如果 $\exists K\left( \omega \right)< 1$ 的非负实值随机变量，则

$d(\{ \omega ,d(T(\omega ,{P_{g,i}}),T(\omega ,{P_{g,i + 1}}))K(\omega )d({P_{g,i}},{P_{g,i + 1}})\} ) =1$

${P_{g,i}},\;\; {P_{g,i + 1}} \in S$

定理1　CQWPEA算法的迭代过程形成的映射 ${T_{{\rm{CQWPEA}}}}$ 是随机压缩算子。

证明　依据CQWPEA原理，每迭代一次均可产生比上一次更优的个体狼和目标猎物资源，所以存在一个非负实值随机变量 $K\left( \omega \right) \in \left[ {0,1} \right)$ ，使得

$\begin{array}{*{20}{c}}{d\left( {{T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i - 1}}} \right),{T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i}}} \right)} \right) = }{d\left( {{P_{g,i}},{P_{g,i + 1}}} \right)} =\\ \left| {\left( {c - f\left( {{P_{g,i}}} \right)} \right) - \left( {c - f\left( {{P_{g,i + 1}}} \right)} \right)} \right| \leqslant K\left( \omega \right)|\left( {c - f\left( {{P_{g,i - 1}}} \right)} \right) - \\\begin{array}{c}\left. \left( {c - f\left( {{P_{g,i}}} \right)} \right) \right| = K\left( \omega \right)d\left( {{P_{g,i - 1}},{P_{g,i}}} \right)\end{array}\\\begin{array}{c}{\varOmega _0} = \left\{ {\omega :d} {\left( {{T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i - 1}}} \right),{T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i - 1}}} \right)} \right) \leqslant } \right.\\\left. {K\left( \omega \right)d\left( {{P_{g,i - 1}},{P_{g,i}}} \right)} \right\} \leqslant \varOmega \\p\left( {{\varOmega _0}} \right) = 1\end{array}\end{array}$

由此可知，CQWPEA算法迭代过程中形成的映射 ${T_{{\rm{CQWPEA}}}}:\varOmega \times {S^X} \times {S^P} \times {S^g} \to {S^P}$ 是一个随机压缩算子。

定理2　(随机压缩映射定理)设随机搜索算子 $T:\varOmega \times S \to S$ 满足所有的 $\omega \in S$ ， $T\left( \omega \right)$ 均为压缩算子，即 $\exists {\varOmega _0} \in \varOmega ,p\left( {{\varOmega _0}} \right) = 1$ ，对 $\forall \omega \in {\varOmega _0}$ ，则 $d\left( {T\left( {\omega ,{P_{g,i}}} \right),} \right.$ $\left. {T\left( {\omega ,{P_{g,i - 1}}} \right)} \right) \leqslant K\left( \omega \right)d\left( {{P_{g,i}},{P_{g,i + 1}}} \right)$ ，则 ${P_{g,i}},{P_{g,i - 1}},{P_{g,i + 1}}\in S, $ $0 \leqslant K\left( \omega \right){\text{<}} 1$ ，则 $T\left( \omega \right)$ 有唯一随机不动点 $r\left( \omega \right)$ ，即 $T\left( {\omega ,r\left( \omega \right)} \right) = r\left( \omega \right)$ 。

证明　首先利用巴拿赫压不动点定理，对 $\forall \omega \in {\varOmega _0}$ ， $\exists h\left( \omega \right) \in S$ 作为 $T\left( \omega \right)$ 的唯一不动点，对 ${P_{g,i}} \in S$ ，令 $r\left( \omega \right) = \left\{ {\begin{array}{*{20}{c}}\!\!\!\!\!\!\!\!{h\left( \omega \right),\;\;\omega \in {\varOmega _0}}\\\!\!\!\!\!{{P_{g,i}},\;\omega \in \varOmega - {\varOmega _0}}\end{array}} \right.$ 为 $T\left( \omega \right)$ 的唯一不动点。

然后证明 $r\left( \omega \right)$ 的可测性。对 $\forall {P_{g, 0}} \in S$ ，令 ${P_{g,1}}\left( \omega \right) = $ $ {T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,0}}} \right)$ ， ${P_{g,i + 1}}\left( \omega \right) = {T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i}}} \right),i = 1,2, \cdots, $ 因为 ${P_{g,1}}\left( \omega \right) \! \to \! {P_{g,0}}$ ， ${T_{{\rm{CQWPEA}}}}\left( {\omega ,{P_{g,i}}\left( \omega \right)} \right) \! \to \! {T_{{\rm{CQWPEA}}}}\left( {\omega ,}\right.$ $\left.{P_{g,0}} \right),{P_{g,i}} \in S$ ，即 ${T_{{\rm{CQWPEA}}}}\left( \omega \right)$ 连续。依据符合定理， $\left\{ {\left. {{P_{g,i}}} \right\}} \right.$ 为一个随机变量序列，再根据巴拿赫压不动点定理可知， ${P_{g,i}}\left( \omega \right) \to r\left( \omega \right)$ ，根据极限随机变量定理的定义， $r\left( \omega \right)$ 作为一个随机变量，因此 $r\left( \omega \right)$ 作为 ${T_{{\rm{CQWPEA}}}}\left( {\rm{\omega }} \right)$ 的随机不动点，证毕。

4 实验仿真与结果分析 4.1 测试函数

为了检验CQWPEA算法的寻优性能，选取6个标准的测试函数进行仿真实验，6个测试函数的表达式如下：

1) Sphere函数

${f_1}\left( x \right) = \sum \limits_{i = 1}^d x_i^2, \quad - 100 \leqslant {x_i} \leqslant 100$

2) Schwefel函数

${f_2}\left( x \right) = 418.982\,\,9 \times d - \sum \limits_{i = 1}^d {x_i}\cdot {\rm{sin}}\left( {{{\left| {{x_i}} \right|}^{\frac{1}{2}}}} \right),\quad - 500 \leqslant {x_i} \leqslant 500$

3) Rosenbrock函数

${f_3}\left( x \right) = \sum \limits_{i = 1}^d \left[ {100{{\left( {{x_{i + 1}} - x_i^2} \right)}^2} + {{\left( {{x_i} - 1} \right)}^2}} \right],\quad - 30 \leqslant {x_i} \leqslant 30$

4) Rastrigrin函数

${f_4}\left( x \right) = \sum \limits_{i = 1}^d \left( {x_i^2 - 10\cos \left( {2 {\text{π}}{x_i}} \right) + 10} \right),\quad - 5.12 \leqslant {x_i} \leqslant 5.12$

5) Ackley函数

$\begin{array}{c}{f_5}\left( x \right) = - 20\exp \left( { - \displaystyle\frac{1}{5}\sqrt {\displaystyle\frac{1}{d}} \displaystyle\sum\limits_{i = 1}^d {x_i^2} } \right) - \\\exp\left( {\displaystyle\frac{1}{d}\displaystyle\sum\limits_{i = 1}^d {\cos } \left( {2{\text{π}} {x_i}} \right)} \right) + 20 + e,\quad - 32 \leqslant {x_i} \leqslant 32\end{array}$

6)Griewangk函数

${f_6}\left( x \right) = \frac{1}{{4\,\,000}} \sum \limits_{i = 1}^d x_i^2 - \prod \limits_{i = 1}^d \cos \left( {\frac{{{x_i}}}{{\sqrt i }}} \right) + 1, - 100 \leqslant {x_i} \leqslant 100$

在上述6个标准测试函数中， ${f_1}\left( x \right)$ 、 ${f_2}\left( x \right)$ 和 ${f_3}\left( x \right)$ 为单峰函数， ${f_4}\left( x \right)$ 、 ${f_5}\left( x \right)$ 和 ${f_6}\left( x \right)$ 为多峰函数，函数的维数均设置为30，6个标准测试函数的全局最优解均为0。

4.2 仿真结果分析

采用CQWPEA算法对6个标准测试函数进行解算，并将其结果与WPEA、QWPEA算法的结果进行比较。其中相同的参数设置为：狼群规模均为500，最大迭代次数为500次，收敛精度设置为0.000 01。具体到每个不同算法的参数，在WPEA算法和QWPEA算法中，判定因子 $\omega = 500$ ，步长因子 $S = 1\;000$ ，更新因子 $\beta = 6$ ，最大游走次数 ${T_{{\rm{max}}}} = 20$ ，探狼比例因子 $\delta = 4$ ，滑模交叉 $\mu = 0.2$ ， $\sigma = 0.3$ ， $I = 8$ , ${k_{{\rm{max}}}} = 500$ 。在CQWPEA算法的控制参数 $\gamma = 0.6$ ，量子旋转角 $\Delta \theta = 0.05$ ，实验仿真环境：Windows7系统，3 GB内存，4 GHz CPU，算法基于MATLAB2015a。每种算法的终止条件均为满足算法的寻优目标或达到最大迭代次数，计算结果见表1所示。各取每个算例20次的实验数据，记录其最优值、平均值、最差值；并将CQWPEA算法的结果与WPEA和QWPEA算法进行比较，分别记录其平均迭代次数、最大迭代次数、收敛率以及20次独立运行消耗的总时间。为了增加算法的可信度，WPEA和QWPEA算法的参数直接来源于参考文献，优化比较结果如表2所示。表2中的“—”表示对应的寻优成功次数指标无法获得统计结果。

从表1的结果可知，在满足固定收敛精度下，本文提出的CQWPEA算法分别在维度为10、20和30的基础上进行测试，发现除了Schwefel函数、Rosenbrock函数和Ackley函数外，其他3种函数经过20次实验均能一致性收敛到问题的全局最优解0。针对函数 ${f_1}\left( x \right)$ ，CQWPEA算法和QWPEA算法均可获得最优解，而WPEA算法的寻优能力较差；针对函数 ${f_2}\left( x \right)$ ，3种算法均无法获得最优解，但几乎可达到近似最优解；针对函数 ${f_3}\left( x \right)$ ，3种算法虽然无法获得最优解，但CQWPEA算法要比其他2种算法获得的近似最优解更为接近最优解值0；针对函数 ${f_4}\left( x \right)$ ，CQWPEA算法的寻优能力最强，WPEA算法的寻优能力要比QWPEA算法强，这主要是因为设置算法参数的不同而造成的；针对函数 ${f_5}\left( x \right)$ ，虽然3种算法均没有获得最优解值，但从总体上来看，CQWPEA算法获得的最优解几乎接近全局最优解，其寻优能力较强，而QWPEA算法和WPEA算法获得的最优解距离全局最优解相差甚远；针对函数 ${f_6}\left( x \right)$ ，CQWPEA算法可获得全局最优解，WPEA算法的寻优能力要比QWPEA算法强。

由上述分析结果可以得出，从总体上来看，本文提出的求解离散优化问题的元胞量子狼群演化算法在寻优能力均要优于其他狼群演化算法和量子狼群演化算法，但从部分函数测试的结果可知，本文算法对于部分函数也会存在无法获得全局最优解问题，这主要是因为算法的初始参数设置的随机性、局部寻优结果差、元胞演化规则对量子旋转角的调整速度慢、量子相位角的选择不精确等原因造成的。

由表2的结果可知，在不同的维数和相同的优化步数下，从收敛率和消耗时间上来看，对于6种不同的标准测试函数，CQWPEA算法收敛率均可到达100%，且消耗时间明显比WPEA算法和QWPEA算法少；但对于不同的函数，3个算法的性能还存在一定的差异。对于f₁(x)函数、f₄(x)函数、f₅(x)函数和f₆(x)函数，WPEA算法的寻优结果不理想，主要是因为当维数大于3时，这4个典型的凹函数呈现多峰特征，具有大量的局部极值点，因此找到全局最优解较为困难。对于f₃(x)函数、f₄(x)函数和f₆(x)函数，QWPEA算法的寻优结果的收敛率为0，其搜索到的最优解与目标函数的最优解的偏差较大，这是因为这3个函数是复杂的非线性多峰函数，寻优过程中会使算法陷入局部收敛；对于f₂(x)函数和f₃(x)函数，QWPEA算法的收敛率也几乎为0，其搜索到的最优解偏差也较大。

由上述的比较结果知，与WPEA算法和QWPEA算法相比，无论从收敛精度还是收敛稳定性方面，CQWPEA算法的寻优性能明显优于其他2种算法。

另外，从算法收敛(达到收敛精度)时间方面，WPEA算法对6个标准测试函数20次实验的收敛消耗总时间分别为31.55、91.34、77.39、33.74和31.59 s，而QWPEA算法对6个标准测试函数20次实验的收敛消耗总时间分别为3.69、3.24、2.62、3.20、3.10和3.25 s，CQWPEA算法对6个标准测试函数20次实验的收敛消耗总时间分别为0.46、0.82、0.52、0.72、0.84和0.55 s。从收敛消耗总时间来看，与WPEA算法和QWPEA算法相比，CQWPEA算法的收敛速度明显加快。从图6中可清晰地看出，CQWPEA算法要比WPEA算法和QWPEA算法具有较快的收敛速度。

5 结束语

1) 基于元胞自动机和量子狼群演化算法的原理，提出一种求解离散优化问题的元胞量子狼群演化算法，该算法采用双策略方法，实现量子人工狼群初始位置的生成。

2) 针对狼群中个体狼的位置与猎物资源的关系问题，采用二进制编码方式和元胞自动机中的演化规则，分别对狼群中个体狼与猎物间的距离进行精确描述和量子旋转角的选取、调整，实现狼群个体与猎物资源位置的精确定位和增强狼群的全局搜索空间能力。

3) 元胞量子狼群演化算法是对解决离散空间优化问题的初步探索，该算法具有寻优精度高、收敛速度快以及较强的鲁棒性，将CQWPEA算法进行改进以加强算法的寻优能力，并用于处理复杂约束优化问题是进一步研究的方向。