【机器学习】求解离散优化问题的元胞量子狼群演化算法

第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201705007 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180426.1120.004html 求解离散优化问题的元胞量子狼群演化算法 马龙，卢才武，顾清华 (西安建筑科技大学管理学院，陕西西安710055) 摘要：针对离散空间优化问题，提出了求解离散优化问题的元胞量子狼群演化算法，首先，为了提高算法的全 局收敛速度，采用双策略量子位初始化方法和滑模交叉方法，分别生成量子狼群初始位置和产生头狼，实现种 群多样性：其次，为了描述头狼与猎物间的距离以及增强狼群的遍历范围，采用二进制编码方式和元胞自动机 中的演化规则，分别实现狼群中个体狼与猎物距离的精确描述和量子旋转角的选取调整：然后，为了证明该算 法的收敛性能，采用泛函分析方法，实现了算法全局收敛性能的验证：最后，通过6个标准测试函数的仿真实 验，并与狼群算法以及量子狼群算法的优化结果进行比较。实验结果表明，该算法具有较快的收敛速度和较好 的全局寻优能力。 关键词：离散优化：量子狼群算法：元胞自动机：双策略方法：滑模交叉：二进制编码：泛函分析：狼群算法：量子 旋转角 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2018)05-0716-12 中文引用格式：马龙，卢才武，顾清华.求解离散优化问题的元胞量子狼群演化算法J川.智能系统学报，2018,13(5)： 716-727. 英文引用格式：MA Long,LUCaiwu,,GU Qinghua..Cellular and quantum-behaved wolf pack evolutionary algorithm for solving discrete optimization problems J.CAAI transactions on intelligent systems,2018,13(5):716-727. Cellular and quantum-behaved wolf pack evolutionary algorithm for solving discrete optimization problems MA Long,LU Caiwu,GU Qinghua (School of Management,Xi'an University of Architecture and Technology,Xi'an 710055,China) Abstract:To solve optimization problems in discrete space,a cellular quantum-inspired wolf pack evolutionary al- gorithm is proposed for solving discrete optimization problems.First,to speed up the global convergence of the al- gorithm,when generating the diversity of population,the method fully utilizes the double strategy quantum bit initializa- tion method and the sliding mode crossover method to help generate the initial position and candidate wolf,respectively. Then,to accurately describe the distance between the wolf and the prey as well as enhance the traverse range of wolf pack,the methods of the binary encoding and evolution rules of the cellular automata are used to realize precise descrip- tion and the selection of the quantum rotation angle,respectively.Then to prove the convergence performance of the al- gorithm,the method fully utilizes the functional analysis to verify the global convergence.Finally,simulation experi- ment on six benchmark functions was carried out,and the comparison between the wolf pack algorithm and quantum-in- spired wolf pack evolutionary algorithm was provided.The results show that the proposed approach has better conver- gence speed and great global convergence optimization ability. Keywords:discrete optimization;quantum-inspired wolf pack algorithm;cellular automata;double strategy method; sliding mode crossover;binary encoding;functional analysis;wolf pack algorithm;quantum rotation angle 在人工智能计算和系统工程等领域中，许多 收稿日期：2017-05-08.网络出版日期：2018-04-26 基金项目：国家自然科学基金项目(51774228,51404182)：陕西 离散空间优化问题常具有解的多样性、动态性以 省自然科学基金项目(2017JM5043):陕西省教育厅 专项科研计划项目(17K0425). 及目标函数收敛速度慢等特点。为了在有限的空 通信作者：顾清华.E-mail:qinghuagu@(126.com. 间环境下快速搜寻到优化问题的最优解，学者们

DOI: 10.11992/tis.201705007 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180426.1120.004.html 求解离散优化问题的元胞量子狼群演化算法 马龙，卢才武，顾清华 （西安建筑科技大学 管理学院，陕西 西安 710055） 摘 要：针对离散空间优化问题，提出了求解离散优化问题的元胞量子狼群演化算法，首先，为了提高算法的全 局收敛速度，采用双策略量子位初始化方法和滑模交叉方法，分别生成量子狼群初始位置和产生头狼，实现种 群多样性；其次，为了描述头狼与猎物间的距离以及增强狼群的遍历范围，采用二进制编码方式和元胞自动机 中的演化规则，分别实现狼群中个体狼与猎物距离的精确描述和量子旋转角的选取调整；然后，为了证明该算 法的收敛性能，采用泛函分析方法，实现了算法全局收敛性能的验证；最后，通过 6 个标准测试函数的仿真实 验，并与狼群算法以及量子狼群算法的优化结果进行比较。实验结果表明，该算法具有较快的收敛速度和较好 的全局寻优能力。 关键词：离散优化；量子狼群算法；元胞自动机；双策略方法；滑模交叉；二进制编码；泛函分析；狼群算法；量子 旋转角 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2018)05−0716−12 中文引用格式：马龙, 卢才武, 顾清华. 求解离散优化问题的元胞量子狼群演化算法[J]. 智能系统学报, 2018, 13(5): 716–727. 英文引用格式：MA Long, LU Caiwu, GU Qinghua. Cellular and quantum-behaved wolf pack evolutionary algorithm for solving discrete optimization problems[J]. CAAI transactions on intelligent systems, 2018, 13(5): 716–727. Cellular and quantum-behaved wolf pack evolutionary algorithm for solving discrete optimization problems MA Long，LU Caiwu，GU Qinghua (School of Management, Xi’an University of Architecture and Technology, Xi’an 710055, China) Abstract: To solve optimization problems in discrete space, a cellular quantum-inspired wolf pack evolutionary al￾gorithm is proposed for solving discrete optimization problems. First, to speed up the global convergence of the al￾gorithm, when generating the diversity of population, the method fully utilizes the double strategy quantum bit initializa￾tion method and the sliding mode crossover method to help generate the initial position and candidate wolf, respectively. Then, to accurately describe the distance between the wolf and the prey as well as enhance the traverse range of wolf pack, the methods of the binary encoding and evolution rules of the cellular automata are used to realize precise descrip￾tion and the selection of the quantum rotation angle, respectively. Then to prove the convergence performance of the al￾gorithm, the method fully utilizes the functional analysis to verify the global convergence. Finally, simulation experi￾ment on six benchmark functions was carried out, and the comparison between the wolf pack algorithm and quantum-in￾spired wolf pack evolutionary algorithm was provided. The results show that the proposed approach has better conver￾gence speed and great global convergence optimization ability. Keywords: discrete optimization; quantum-inspired wolf pack algorithm; cellular automata; double strategy method; sliding mode crossover; binary encoding; functional analysis; wolf pack algorithm; quantum rotation angle 在人工智能计算和系统工程等领域中，许多 离散空间优化问题常具有解的多样性、动态性以 及目标函数收敛速度慢等特点。为了在有限的空 间环境下快速搜寻到优化问题的最优解，学者们 收稿日期：2017−05−08. 网络出版日期：2018−04−26. 基金项目：国家自然科学基金项目 (51774228，51404182)；陕西 省自然科学基金项目 (2017JM5043)；陕西省教育厅 专项科研计划项目 (17JK0425). 通信作者：顾清华. E-mail：qinghuagu@126.com. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018

第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·717· 已对多种智能算法进行融合并展开了广泛的研究 问题，受二进制编码量子粒子群演化算法的启 和应用。 示，在量子狼群演化算法中引入二进制编码，融 狼群演化算法(wolf pack evolutionary al- 合元胞自动机演化规则，提出了求解离散优化问 gorithm,WPEA)作为模拟自然界群狼分工协作捕 题的元胞量子行为狼群演化算法。为分析方便， 猎的启发式智能优化算法，1970年美国著名专家 首先对元胞自动机原理、二进制量子狼群演化算 Mech在其著作中对狼群的行为特征进行了详细 法中的狼群行为规则、头狼产生规则、狼群更新 的描述；20l4年Mirjalili等P将该算法与金字塔模 和变异等演化方程进行描述。 型进行结合，提出了一种具有等级森严的狼群捕 1.1元胞自动机原理 猎层次模型，该算法在解决实数空间问题的应用 元胞自动机通过利用大量元胞的并行演化规 效果明显。此后针对离散空间优化问题，文献[3] 则来模拟复杂结构和过程，成为探索复杂系统的 针对分类特征子集的优化问题，提出了二进制狼 有效工具四。CA协同更新元胞空间中的所有元 群演化算法；文献[4-5]提出了一种改进的二进制 胞，协同更新的规则：下一个时刻元胞的状态是 狼群演化算法，扩展了狼群演化算法的应用范 由自身和邻居在前一时刻的状态来决定的。元胞 围；Srikanth等在深入分析狼群演化算法的基础 状态集、邻居、元胞空间以及局部演化规则作为 上，针对组合调度优化问题，提出了二进制量子 CA的基本组成要素，其邻接类型主要有两种，即 狼群演化算法(quantum wolf pack evolutionary al-- Von.Neumann型和Moore型，如图1所示。 gorithm,QWPEA)。QWPEA算法相对于WPEA 算法具有原理简单、参数设置少、收敛速度快、较 强的全局搜索能力等特点，在测试函数和实际工 (i,) () 程应用中取得了突出的效果1。但这些应用都 是以固定的搜索空间和种群个体位置的静态更新 为基础进行优化求解，对于离散空间中局部和全 (a)Von.Neumann型 (b)Moore型 局的并行演化以及狼群中的个体狼的量子位置旋 图1CA的邻居类型 转角的动态选取和调整问题，QWPEA算法并没 Fig.1 The neighbor types of CA 有一个有效的解决方法。 元胞自动机的动态演化规则以元胞的动态时 元胞自动机(cellar automation,CA)最早由冯 间状态变化集合为基础，其可表示为 诺伊曼在1966年提出)，CA是一种根据简单的 F:S→S (1) 并行演化规则和协同更新方法，采用元胞来模拟 式中：S表示元胞状态的有限集合；Z表示取整数 复杂的离散系统动力学方法o,CA具有时空动态 集的一维空间；t表示时间值。 性、状态离散性和同步性等基本特征。 元胞的局部演化函数∫对于元胞的动态演化 为了解决有限的离散空间内狼群演化算法的 规则具有决定性作用，在取整数的一维空间中， 收敛速度慢、搜索能力弱以及易于陷入局部最优 元胞与其邻居可用S2+来表示，元胞的局部演化 等问题，提出了一种求解离散优化问题的元胞量 函数f可表示为 子狼群演化算法(cellar quantum-behaved wolf pack f:S21→S4i (2) evolutionary algorithm,CQWPEA),该算法主要采 元胞局部演化函数都是在有限的元胞状态 用二进制编码方式和元胞自动机中的演化规则， 集上输人和输出的，将局部演化函数与元胞空间 分别实现量子狼群中的个体狼位置与猎物之间的 内的每个元胞进行组合优化，这样就形成了一个 距离以及量子旋转角的选取和调整，并给出了头 全局演化规则： 狼与猎物资源位置的编码方式，同时给出了探狼 F(ci4)=fC,cr,…,Ci,…,Ctr (3) 和猛狼局部搜索算子的编码方式，分析了编码规 式中：c表示在位置处的元胞，r表示邻居半径。 则。另外，采用泛函分析方法对该算法的收敛性 CA由一个标准的四元组构成，其形式为 进行了证明，最后通过6个测试函数验证了 A=(Hp:S,M,f) (4) CQWPEA算法的有效性和合理性。 式中：A为一个CA;H和D为一个元胞空间和维度 1量子狼群演化算法 数；S为元胞的离散状态有限集；M为所有元胞 (邻域和中心元胞)的组合，其可表示为 为了使量子狼群算法适应离散搜索空间寻优 N=(S1,S2,…,Sn) (5)

已对多种智能算法进行融合并展开了广泛的研究 和应用。 狼群演化算法 (wolf pack evolutionary al￾gorithm，WPEA) 作为模拟自然界群狼分工协作捕 猎的启发式智能优化算法，1970 年美国著名专家 Mech[1]在其著作中对狼群的行为特征进行了详细 的描述；2014 年 Mirjalili 等 [2]将该算法与金字塔模 型进行结合，提出了一种具有等级森严的狼群捕 猎层次模型，该算法在解决实数空间问题的应用 效果明显。此后针对离散空间优化问题，文献[3] 针对分类特征子集的优化问题，提出了二进制狼 群演化算法；文献[4-5]提出了一种改进的二进制 狼群演化算法，扩展了狼群演化算法的应用范 围；Srikanth 等 [6]在深入分析狼群演化算法的基础 上，针对组合调度优化问题，提出了二进制量子 狼群演化算法 (quantum wolf pack evolutionary al￾gorithm，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 元胞自动机原理 i 元胞自动机通过利用大量元胞的并行演化规 则来模拟复杂结构和过程，成为探索复杂系统的 有效工具[12]。CA 协同更新元胞空间中的所有元 胞，协同更新的规则：下一个时刻元胞 的状态是 由自身和邻居在前一时刻的状态来决定的。元胞 状态集、邻居、元胞空间以及局部演化规则作为 CA 的基本组成要素，其邻接类型主要有两种，即 Von.Neumann 型和 Moore 型，如图 1 所示。 (i, j) (i, j) (a) Von.Neumann 型 (b) Moore 型 图 1 CA 的邻居类型 Fig. 1 The neighbor types of CA 元胞自动机的动态演化规则以元胞的动态时 间状态变化集合为基础，其可表示为 F : S Z t → S Z t+1 (1) S Z t 式中： 表示元胞状态的有限集合； 表示取整数 集的一维空间； 表示时间值。 f S 2r+1 f 元胞的局部演化函数 对于元胞的动态演化 规则具有决定性作用，在取整数的一维空间中， 元胞与其邻居可用 来表示，元胞的局部演化 函数 可表示为 f : S 2r+1 t → S t+1 (2) 元胞局部演化函数 f 都是在有限的元胞状态 集上输入和输出的，将局部演化函数与元胞空间 内的每个元胞进行组合优化，这样就形成了一个 全局演化规则： F(c i t+1 ) = f(c i−r t , c i−r+1 t ,··· , c i t ,··· , c i+r t ) (3) c i t 式中： 表示在位置 i 处的元胞，r表示邻居半径。 CA 由一个标准的四元组构成，其形式为 A = (HD,S, M, f) (4) A H D S M 式中： 为一个 CA； 和 为一个元胞空间和维度 数 ； 为元胞的离散状态有限集； 为所有元胞 (邻域和中心元胞) 的组合，其可表示为 N = (S 1,S 2,··· ,S n) (5) 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·717·

·718· 智能系统学报 第13卷 式中：n表示一个元胞空间内的元胞邻居数；S:是 序，选取个适应度值高的个体狼构成初始狼群。 一个取值为1~n的整数集；f表示局部演化函数在 1.2.3头狼产生规则 S"→S的映射过程；确定元胞空间中的所有元胞 在初始解空间中，将最接近猎物资源（或最优 位置采用z4整数矩阵。 目标函数)的个体狼视为头狼，头狼直接进人迭 1.2量子狼群算法 代过程。算法运行中，通过比较每匹人工狼的量 1.2.1量子狼群编码 子位状态5，获得当前狼群迭代过程中的最优个 在量子狼群演化算法中，人工狼编码是以一 体狼作为头狼，最终求解得到头狼的位置和最佳 组量子位和二进制表示，每个量子位的状态可用 适应度。第个位上的量子位状态可表示为 式表(6)示： 0 random.1] )=alO)+B1)》 (6) (10) 1, 式中α与B表示量子位对应状态的概率幅。 random[0,1]s 人工狼当前位置的编码可通过量子位的概率 式中：(5,52，…，s)表示量子状态位对应于人工狼 幅表示，考虑到狼群初始化时编码的随机性，假 的二进制表示形式；random[0,1]表示在0,1]之间的 设采用量子方式编码的个体为P,则编码方式为 随机数，j=1,2,…,d。 在传统的进化算法中，与狼群算法的“优胜劣 (7) 汰生存”规则和遗传算法的“轮盘赌”规则不同的 式中：表示量子态被观测为1O)态概率，为量 是，本文设计了一种基于滑模原理的交叉量子位 子态被观测为1)态概率，满足a+B,=1;i= 遗传演化方法，用于将选择之后产生的候选头狼 1,2.d:d为编码位数。 集合Z中的个体头狼按优秀程度降序排序，然后 由此可知，量子狼群可表示为Q(q)=(,92,…,9), 从染色体右端低量子位开始与头狼染色体按照滑 其中，g表示进化代数，n表示个体狼数量： 模方式交叉，式(11)和式(12)表示交叉参数ω，呈 i=1,2,…,)表示第g代狼群中第i只狼，即 高斯分布，随着候选个体头狼逐渐陷入局部解， (8) 如图2所示，交叉点滑模按照式(13)向左移动， a 用于分别与新一代头狼迭代，产生更优秀后代头狼。 最后通过对Q()进行量子测量，获得一组确 定的解p(g)=(,x,…,x,其中xi=1,2,…,n)为 o0山可致 010o11 一匹狼通过量子测量到确定状态的二进制序列， 100100口头狼染001000 色体 若该二进制序串的位数为d,那么x可以表示为 。滑动 、滑动 1011 10111001 x=(,点，…，)。 oDo0袋 1.2.2双策略的初始量子位生成过程 o中o0· 11000100 在初始化狼群演化过程中，狼群中每匹狼位 置的所有量子位对应态的概率幅可采用Logist- 图2候选头狼染色体量子位滑模交叉方法 Fig.2 The sliding mode crossover of quantum bits of can- iC混沌映射产生，其产生的基本过程为： didate lead wolf 1)设狼群规模为m,个体狼位置编码的长度为d; 交叉权值分布函数为 2)随机产生d个混沌变量初始值xi=1,2,…,: (e)=、1 exp _(e-2 j=1,2.…,d (11) V2π0 22 3)对式(9)采用迭代计算获得相应的混沌变 式中：Z=(Z,Z,…,Z),jeL表示第匹候选头 量序列xk=1,2,…,mj=1,2,…,d,用这n个混沌 狼染色体量子位从最优至次优串排列； 变量来初始化狼群： i=1,2,,Wj=1,2,…,d。 +1=(1-x,k=0,1,…,n (9) 交叉权值为 式中：4为混沌因子，0≤μ≤4：k为迭代次数。当 μ=4,0≤x≤1时，Logistic完全处于混沌状态。 fo (ei)dei,iel 4)采用2种策略将式(8)中的aa、B分别初始 (12) 化为cos2x)、sin(2x)和g、V1-(),由此获得 2n个全部个体； =1 5)计算全部2个个体的适应度值并进行排 式中/表示当前候选头狼数量

n S i 1 ∼ n f S n → S Z d 式中： 表示一个元胞空间内的元胞邻居数； 是 一个取值为 的整数集； 表示局部演化函数在 的映射过程；确定元胞空间中的所有元胞 位置采用 整数矩阵。 1.2 量子狼群算法 1.2.1 量子狼群编码 在量子狼群演化算法中，人工狼编码是以一 组量子位和二进制表示，每个量子位的状态可用 式表（6）示： |µ⟩ = α|0⟩+β|1⟩ (6) 式中α与 β 表示量子位对应状态的概率幅。 pi 人工狼当前位置的编码可通过量子位的概率 幅表示，考虑到狼群初始化时编码的随机性，假 设采用量子方式编码的个体为 ，则编码方式为 p = [ α1 α2 ··· αd β1 β2 ··· βd ] (7) |α| 2 |0⟩ |β| 2 |1⟩ |αi | 2 +|βi | 2 = 1 1,2,d;d 式中： 表示量子态被观测为 态概率， 为量 子态被观测为 态概率，满足 ； i = 为编码位数。 Q(q) = (q g 1 ,q g 2 ,··· ,q g n) g n q g i (i = 1,2,··· ,n) g i 由此可知，量子狼群可表示为 , 其中， 表示进化代数， 表示个体狼数量； 表示第 代狼群中第 只狼，即 q g i = [ α g i1 α g i2 ··· α g id β g i1 β g i2 ··· β g id ] (8) Q(q) p(g) = (x g 1 , x g 2 ,··· , x g n) x g i (i = 1,2,··· ,n) d x g i x g i = (x g i1 , x g i2 ,··· , x g id) 最后通过对 进行量子测量，获得一组确 定的解 ，其中 为 一匹狼通过量子测量到确定状态的二进制序列， 若该二进制序串的位数为 ，那么 可以表示为 。 1.2.2 双策略的初始量子位生成过程 在初始化狼群演化过程中，狼群中每匹狼位 置的所有量子位对应态的概率幅可采用 Logist￾ic 混沌映射产生，其产生的基本过程为： 1) 设狼群规模为n，个体狼位置编码的长度为 d ； d x j i (i = 1,2,··· ,n j = 1,2,··· ,d) 2) 随机产生 个混沌变量初始值 ； ; x j k (k = 1,2,··· ,n; j = 1,2,··· ,d) n 3) 对式 (9) 采用迭代计算获得相应的混沌变 量序列 ，用这 个混沌 变量来初始化狼群： x j k+1 = µx j k (1− x j k ), k = 0,1,··· ,n (9) 0 ⩽ µ ⩽ 4 µ=4 0 ⩽ x j k ⩽ 1 式中：μ 为混沌因子， ；k 为迭代次数。当 ， 时，Logistic 完全处于混沌状态。 α g id β g id cos(2x j k π) sin(2x j k π) x j i √ 1−(x j k ) 2 2 n 4) 采用 2 种策略将式 (8) 中的 、 分别初始 化为 、 和 、 ，由此获得 个全部个体； 2 5) 计算全部 n个个体的适应度值并进行排 序，选取n个适应度值高的个体狼构成初始狼群。 1.2.3 头狼产生规则 sj j 在初始解空间中，将最接近猎物资源 (或最优 目标函数) 的个体狼视为头狼，头狼直接进入迭 代过程。算法运行中，通过比较每匹人工狼的量 子位状态 ，获得当前狼群迭代过程中的最优个 体狼作为头狼，最终求解得到头狼的位置和最佳 适应度。第 个位上的量子位状态可表示为 sj =    0, random[0,1] >   αj    2 1, random[0,1] ⩽   αj    2 (10) (s1,s2,··· ,sj) random[0,1] [0,1] j = 1,2,··· ,d 式中： 表示量子状态位对应于人工狼 的二进制表示形式； 表示在 之间的 随机数， 。 Z od ωi 在传统的进化算法中，与狼群算法的“优胜劣 汰生存”规则和遗传算法的“轮盘赌”规则不同的 是，本文设计了一种基于滑模原理的交叉量子位 遗传演化方法，用于将选择之后产生的候选头狼 集合 中的个体头狼按优秀程度降序排序，然后 从染色体右端低量子位开始与头狼染色体按照滑 模方式交叉，式 (11) 和式 (12) 表示交叉参数 呈 高斯分布，随着候选个体头狼逐渐陷入局部解， 如图 2 所示，交叉点滑模按照式 (13) 向左移动， 用于分别与新一代头狼迭代，产生更优秀后代头狼。 滑动 滑动 头狼染 色体 交叉 0 1 1 0 1 11 0 1 1 1 0 0 0 01 1 0 0 1 1 0 10 1 1 1 0 0 0 01 0 1 1 1 0 1 11 1 1 0 0 0 0 01 1 0 1 1 1 0 01 1 1 0 0 0 0 10 Zi od 头狼染 色体 交叉 Zi+1 od 图 2 候选头狼染色体量子位滑模交叉方法 Fig. 2 The sliding mode crossover of quantum bits of can￾didate lead wolf 交叉权值分布函数为 fgs ( ei) = 1 √ 2πσ exp[ − ( ei −µ) 2 2σ2 ] (11) Z od i = (Z od i,1 ,Z od i,2 ,··· ,Z od i, j ), j ∈ L i j i = 1,2,··· ,N; j = 1,2, ··· ,d 式中： 表示第 匹候选头 狼染色体量子位 从最优至次优串排列； 。 交叉权值为    ωi = i+1 I ∫ σ i I σ fgs ( ei) dei , i ∈ I ∑I i=1 ωi = 1 (12) 式中 I 表示当前候选头狼数量。 ·718· 智 能 系 统 学 报 第 13 卷

第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,则探狼向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) randomfitj 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·

·720· 智能系统学报 第13卷 工狼（猛狼和探狼）在d维空间中智能步长数。 演化算法的搜索空间，人工狼的位置为 假设在第d个变量的取值范围为maxa,minu小， X,={x1,x2,…,xmli∈{1,2，…，N;j∈1,2，…，m}(22)） 则从狼群算法中抽象出的3种智能行为所涉及的 式中：N表示人工狼总数，m表示编码长度；表示 游走步长step、奔袭步长step和猎杀步长step之 人工狼的第X,个位置的第j个编码位置，通过反置 间的关系为 赋值操作且只能取0、1；头狼p和猎物资源q之间 step=2.step=step/2 =maxa,min/S (21) 的曼哈顿距离可表示为 式中：S表示步长因子，S值越小人工探狼搜索越 L(p.q)= ，p,q∈{1,2，…，W (23) 精细。 2元胞量子狼群演化算法 定义2 移动算子，设人工狼的位置为X,= {,x2,…,x,…,xm;M表示非空的反置编码位 在CQWPEA算法中，人工狼（头狼、探狼和 即表达了人工狼的位置；r是非空的反置编码位 猛狼)的位置表示为一组0、1构成的二进制编码 数，即游走步长；运动算子0(X,M,r)表示在人工狼 向量，首先通过使用概率统计方法对个体狼与猎 的位置X中，从M个编码位中随机选择，个编码位 物之间的最优平均位置值进行编码，并记录编码 并对其进行反置操作。 位中出现的0、1次数，实现局部搜索算子编码位 定义3设集合C=(c1,c,…,c,…,cn,C∈{0,1， 的计算；然后，采用元胞自动机选取和调整人工 c的排列组合构成元胞空间，其具体形式为 狼群位置的量子位旋转角，增强元胞量子狼群演 L={CellX=(c1,c2,…,c…,cn)lc,e{0,1》 (24) 化算法的搜索空间，加快算法的收敛速度。 式中CelLY表示由c所组合的元胞。 COWPEA的设计思路是，将散布在猎场空间 定义4扩展Moore邻居类型 中的量子狼群中的探狼朝着猎物遗留的气味浓度 Nmoore (Cell Yldiff (celly-cell X)<r,cellx,cellY eL) (25) 强和环境信息方向进行嗅探，一旦发现猎物，探 式中：任意两个c、c+1的排序组合的差异度为 狼需要判断自身与头狼距离猎物资源的位置，如 diff(celY-cellX)≤r,r为差异度，本文取r=2。 果探狼与猎物的量子位置旋转角比头狼与猎物的 在二进制编码的元胞量子狼群演化算法中 量子位置旋转角大，则探狼代替头狼发起嚎叫召 为了精确表达头狼和猎物资源之间的距离，根据 唤行为，否则向头狼报告猎物的位置信息；猛狼 定义1，假设头狼和猎物的位置为(X1,X2),它们分 收到嚎叫召唤信号后，猛狼迅速向头狼所在位置 别有两个决策变量(X1,X12)、(X21,X22),采用6位二 或猎物所在位置靠拢，同时对猎场的周围环境进 进制编码对每个决策变量进行表示，如图3所示。 行探测，量子狼群进化算法中的人工狼之间以嚎 X 叫信息实现相互通信，并通过元胞机中的局部演 110101100010 化规则不断调整人工狼的位置旋转角度，更好地 X X 调节人工狼群的搜索范围和定位猎物的位置，随 010110110111 着局部搜索过程的不断推进，人工狼群向着全局 图3头狼与猎物位置的二进制编码 最优解逼近，最终通过计算头狼与猎物的平均最 Fig.3 Location of the lead wolf and prey with binary en- 优位置来实现目标函数的优化求解。 coding 2.1个体狼位置的二进制编码 在CQWPEA算法中，定义头狼与猎物（目标 在二进制编码的元胞量子狼群演化算法中！ 函数)含有决策变量的个数即为元胞空间的维 为了精确描述狼群中头狼与猎物资源之间的距离 数；例如，X表示狼群中第i匹头狼的d个决策变 关系，将元胞空间作为量子狼群演化算法的搜索 量，X、X的二进制编码长度分别用l和l表示，则 空间，将距离猎物资源最近的头狼所在位置p看 (26) 作猎物资源（目标函数）的位置，使用量子狼群进 1=2k。d=12,D 化算法中的探狼、猛狼搜索到的局部最优解和猎 根据量子狼群演化算法，通过修改算法中的 杀攻击后的全局最优解分别作为元胞空间内一个 头狼和猎物之间的平均最优位置me的值，生成 元胞，并采用扩展Moore邻居类型，采用数学语 CQWPEA中的me,并用二进制位串表示种群中 言对元胞量子狼群演化算法进行形式化描述。 全部最优个体狼位置，通过概率统计方法向，记录 定义1设以N×m维欧式空间作为量子狼群 二进制编码位中0、1出现的概率次数，如果0出

工狼 i (猛狼和探狼) 在 d 维空间中智能步长数。 d [maxd,mind] stepd s stepd b stepd i 假设在第 个变量的取值范围为 ， 则从狼群算法中抽象出的 3 种智能行为所涉及的 游走步长 、奔袭步长 和猎杀步长 之 间的关系为 stepd s = 2 ·stepd i = stepd b /2 =|maxd,mind|/S (21) 式中： S 表示步长因子， S 值越小人工探狼搜索越 精细。 2 元胞量子狼群演化算法 在 CQWPEA 算法中，人工狼 (头狼、探狼和 猛狼) 的位置表示为一组 0、1 构成的二进制编码 向量，首先通过使用概率统计方法对个体狼与猎 物之间的最优平均位置值进行编码，并记录编码 位中出现的 0、1 次数，实现局部搜索算子编码位 的计算；然后，采用元胞自动机选取和调整人工 狼群位置的量子位旋转角，增强元胞量子狼群演 化算法的搜索空间，加快算法的收敛速度。 CQWPEA 的设计思路是，将散布在猎场空间 中的量子狼群中的探狼朝着猎物遗留的气味浓度 强和环境信息方向进行嗅探，一旦发现猎物，探 狼需要判断自身与头狼距离猎物资源的位置，如 果探狼与猎物的量子位置旋转角比头狼与猎物的 量子位置旋转角大，则探狼代替头狼发起嚎叫召 唤行为，否则向头狼报告猎物的位置信息；猛狼 收到嚎叫召唤信号后，猛狼迅速向头狼所在位置 或猎物所在位置靠拢，同时对猎场的周围环境进 行探测，量子狼群进化算法中的人工狼之间以嚎 叫信息实现相互通信，并通过元胞机中的局部演 化规则不断调整人工狼的位置旋转角度，更好地 调节人工狼群的搜索范围和定位猎物的位置，随 着局部搜索过程的不断推进，人工狼群向着全局 最优解逼近，最终通过计算头狼与猎物的平均最 优位置来实现目标函数的优化求解。 2.1 个体狼位置的二进制编码 pd 在二进制编码的元胞量子狼群演化算法中， 为了精确描述狼群中头狼与猎物资源之间的距离 关系，将元胞空间作为量子狼群演化算法的搜索 空间，将距离猎物资源最近的头狼所在位置 看 作猎物资源 (目标函数) 的位置，使用量子狼群进 化算法中的探狼、猛狼搜索到的局部最优解和猎 杀攻击后的全局最优解分别作为元胞空间内一个 元胞，并采用扩展 Moore 邻居类型，采用数学语 言对元胞量子狼群演化算法进行形式化描述。 定义 1 设以 N ×m维欧式空间作为量子狼群 演化算法的搜索空间，人工狼的位置为 Xi = {xi1, xi2,··· , xim|i ∈ {1,2,··· ,N; j ∈ 1,2,··· ,m}} (22) N m xi j Xi j p q 式中： 表示人工狼总数， 表示编码长度； 表示 人工狼的第 个位置的第 个编码位置，通过反置 赋值操作且只能取 0、1；头狼 和猎物资源 之间 的曼哈顿距离可表示为 L(p,q) = ∑m j=1   xp j − xq j   , p,q ∈ {1,2,··· ,N} (23) i Xi = {xi1, xi2,··· , xi j,··· , xim} M r θ (Xi , M,r) i Xi M r 定义 2 移动算子[5] ，设人工狼 的位置为 ； 表示非空的反置编码位， 即表达了人工狼的位置； 是非空的反置编码位 数，即游走步长；运动算子 表示在人工狼 的位置 中，从 个编码位中随机选择 个编码位 并对其进行反置操作。 C = (c1, c2,··· , ci ,··· , cn), ci ∈ {0,1} ci 定义 3 设集合 ， 的排列组合构成元胞空间，其具体形式为 L = {CellX = (c1, c2,··· , ci ,··· , cn)|ci ∈ {0,1}} (24) 式中 CellX 表示由ci所组合的元胞。 定义 4 [7] 扩展 Moore 邻居类型 Nmoore = {Cell Y|diff ( cellY −cell X) ⩽ r, cellX, cellY ∈ L} (25) ci、ci+1 diff (cellY −cellX) ⩽ r r r = 2 式中：任意两个 的排序组合的差异度为 ， 为差异度，本文取 。 (X1,X2) (X11,X12) (X21,X22) 在二进制编码的元胞量子狼群演化算法中， 为了精确表达头狼和猎物资源之间的距离，根据 定义 1，假设头狼和猎物的位置为 ，它们分 别有两个决策变量 、 ，采用 6 位二 进制编码对每个决策变量进行表示，如图 3 所示。 X11 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 X1 X12 X21 X2 X22 图 3 头狼与猎物位置的二进制编码 Fig. 3 Location of the lead wolf and prey with binary en￾coding Xid i d Xi、Xid l ld 在 CQWPEA 算法中，定义头狼与猎物 (目标 函数) 含有决策变量的个数即为元胞空间的维 数；例如， 表示狼群中第 匹头狼的 个决策变 量， 的二进制编码长度分别用 和 表示，则 l = ∑d i=1 li , d = 1,2,··· ,D (26) mbest mbest 根据量子狼群演化算法，通过修改算法中的 头狼和猎物之间的平均最优位置 的值，生成 CQWPEA 中的 ，并用二进制位串表示种群中 全部最优个体狼位置，通过概率统计方法[6] ，记录 二进制编码位中 0、1 出现的概率次数，如果 0 出 ·720· 智 能 系 统 学 报 第 13 卷

第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·

·722· 智能系统学报 第13卷 △6={0，±△8，±2△0,3A (36) SP={P1,P2,…,Pw,P∈S,j=1,2,…,M (38) 由式(36)可知，本文算法中的量子旋转角扩 全局最优解的位置空间为 大了3倍，呈现双向性，避免了混沌序列的迭代计 S=(P,PES]=S (39) 算和多次比较的查表操作，节省了运算时间。 根据QWPEA算法的流程图可知，QWPEA 2.3 COWPEA算法的步骤 算法的解算过程遵循着反复迭代，逐渐求精的过 1)初始化参数，根据1.2.2节的双策略对量子 程，该过程中包括目标函数适应度值的评价、 狼群的初始量子位进行初始化，并采用二进制序 Pt位置和gen位置的选择，以及人工狼的位置更 串的形式初始化狼群中的个体狼位置，使p= 新，从而使狼群达到更优状态。因此，可用随机 ,计算初始狼群个体的适应度值，同时对算法的 映射运算过程来抽象表示QWPEA算法的流程。 基本参数进行初始化操作。 设(2，A,P)是狼群搜索的概率空间，可以给出 2)根据met函数计算人工狼与猎物资源之间 CQWPEA搜索算子的定义，见定义5。 的平均最优位置值meto 定义5 CQWPEA算法的搜索算子T是通过 3)根据方程式(29)、(30)计算局部搜索算子 逐步迭代方式对个体狼的当前位置进行迭代搜 Pd,Pa的值。 索，以获得个体狼的最好位置的过程，该过程是 4)根据初始狼群的适应度函数值计算种群中 从人工狼当前位置的元胞状态空间以及全局位置 每个个体狼位置值，并与上一次迭代的局部最优 的元胞状态空间随机映射到个体狼最好位置状态 值进行比较，如果适应度值t(X)<f(pr),则用 空间，其映射形式为 P=X更新局部最优位置；反之，则不更新；转 T:QxSxXSPxS8→S (40) 入步骤5)。 CQWPEA算法在每次迭代解算过程中产生 5)量子人工狼按照式(31)(36)进行元胞邻 一次映射TCQWPEA。设X()和P(①分别为第f次迭代 域搜索，并计算狼群体中新的适应度值。将狼群 过程中产生的当前位置的种群和个体最好位置种 的全局最优位置值gea与上一次的全局最优位置 群，X(t+1)、P(t+1)、P(t+1)分别为第t+1次迭代 值gewr-进行比较，如果f(geua)<f(gew-),则替换 产生的人工狼群位置、个体狼位置以及全局最好 原最优位置值，反之，不更新。另外在量子旋转 位置，则 角中，如果△0=0，对狼群的量子编码位进行交 P(t+1)=T(ω，X(t),P(),Pg() (41) 叉，交换量子位概率幅a与B。 式中：t=0,1,…,T-1:T为最大游走次数或迭代次数。 6)按头狼产生规则和猎物气息元胞邻居空间 实验表明，CQWPEA算法中每一代全局最好 的演化规则对头狼位置p进行更新，邻域搜索 解位置的适应度值序列是一个递增序列，即 (42) 同4)。 f(P-i)≤f(Pg)≤f(P+i) T)将局部搜索算子Pd、Pa的值转换为全局最 式中：P-1∈P(t-1)、Pu∈P(0、P41∈P(t+1)分别 优位置值。 表示第t-1、t、t+1代的全局最好解位置。 8)判断是否满足迭代次数kx要求，如果满 在CQWPEA算法中，解算优化问题时，通常 只需关注搜索过程中狼群攻击获得的最好解，不 足，则输出头狼的位置p,即所求解问题的最优 解，否则转人2)。 妨将迭代狼群体用全局最好位置来代替。由此 9)输出目前的最优解集和最优值。 对CQWPEA算法的映射过程进行重新定义，其形 式为 3 CQWPEA算法的收敛性分析 Px1=T(ω，Pg),P∈P(),P41∈Pt+1)(43) 在CQWPEA算法中，解算优化问题的过程可 本节将用泛函分析方法31对CQWPEA算法 视为元胞演化空间之间的映射。以下采用随机映 的收敛性进行分析证明。令二进制编码字符集 射的方法证明和分析CQWPEA算法的收敛性。 k=0,1,采用长度为D的二进制位串表示头狼位 定义6定义度量d:S×S一R,其中d的表达 置编码，编码空间S={0,1P,S1=2P。假设狼群规 式为 模为M,狼群单钱位置集合为X,头狼最佳位置集 d(Pxi.Pj)=c-f(P)-(c-f(Pj))=f(Px)-f(Pj) 合为P,则狼群的当前位置空间可表示为 (44) Sx={X1,X2,…,Xw),X∈S,j=1,2,…,M(37) 式中：c→o;P,PjeS;(S,d)为完备可分的度量 狼群中人工狼的最佳位置空间为 空间

∆θ g+1 i j = {0, ±∆θ, ±2∆θ, 3∆θ} (36) 由式 (36) 可知，本文算法中的量子旋转角扩 大了 3 倍，呈现双向性，避免了混沌序列的迭代计 算和多次比较的查表操作，节省了运算时间。 2.3 CQWPEA 算法的步骤 x k id pbest = x k id 1) 初始化参数，根据 1.2.2 节的双策略对量子 狼群的初始量子位进行初始化，并采用二进制序 串的形式初始化狼群中的个体狼位置 ，使 ，计算初始狼群个体的适应度值，同时对算法的 基本参数进行初始化操作。 mbest mbest 2) 根据 函数计算人工狼与猎物资源之间 的平均最优位置值 。 pid, pjd 3) 根据方程式 (29)、(30) 计算局部搜索算子 的值。 fit(Xi) <f (pbesti) pbesti = Xi 4) 根据初始狼群的适应度函数值计算种群中 每个个体狼位置值，并与上一次迭代的局部最优 值进行比较，如果适应度值 ，则用 更新局部最优位置；反之，则不更新；转 入步骤 5) 。 gbestid gbesti−1 f (gbestid)<f (gbesti−1) ∆θ = 0 α β 5) 量子人工狼按照式 (31)~(36) 进行元胞邻 域搜索，并计算狼群体中新的适应度值。将狼群 的全局最优位置值 与上一次的全局最优位置 值 进行比较，如果 ，则替换 原最优位置值，反之，不更新。另外在量子旋转 角中，如果 ，对狼群的量子编码位进行交 叉，交换量子位概率幅 与 。 pd 6) 按头狼产生规则和猎物气息元胞邻居空间 的演化规则对头狼位置 进行更新，邻域搜索 同 4)。 7) 将局部搜索算子 pid、pjd 的值转换为全局最 优位置值。 kmax pd 8) 判断是否满足迭代次数 要求，如果满 足，则输出头狼的位置 ，即所求解问题的最优 解，否则转入 2)。 9) 输出目前的最优解集和最优值。 3 CQWPEA 算法的收敛性分析 k={0,1} D S = {0,1} D ,|S | = 2 D M X P 本节将用泛函分析方法[13-14]对 CQWPEA 算法 的收敛性进行分析证明。令二进制编码字符集 ，采用长度为 的二进制位串表示头狼位 置编码，编码空间 。假设狼群规 模为 ，狼群单钱位置集合为 ，头狼最佳位置集 合为 ，则狼群的当前位置空间可表示为 S X = { (X1 ,X2 ,··· ,XM),Xj ∈ S, j = 1,2,··· , M } (37) 狼群中人工狼的最佳位置空间为 S P = { (P1 ,P2 ,··· ,PM),Pj ∈ S, j=1,2,··· , M } (38) 全局最优解的位置空间为 S g= { Pg,Pg ∈ S } = S (39) pbest gbest 根据 QWPEA 算法的流程图[6]可知，QWPEA 算法的解算过程遵循着反复迭代，逐渐求精的过 程，该过程中包括目标函数适应度值的评价、 位置和 位置的选择，以及人工狼的位置更 新，从而使狼群达到更优状态。因此，可用随机 映射运算过程来抽象表示 QWPEA 算法的流程。 设 (Ω,A,P) 是狼群搜索的概率空间，可以给出 CQWPEA 搜索算子的定义，见定义 5。 定义 5 CQWPEA 算法的搜索算子 T 是通过 逐步迭代方式对个体狼的当前位置进行迭代搜 索，以获得个体狼的最好位置的过程，该过程是 从人工狼当前位置的元胞状态空间以及全局位置 的元胞状态空间随机映射到个体狼最好位置状态 空间，其映射形式为 T : Ω×S X ×S P ×S g → S P (40) TCQWPEA X (t) P(t) t X (t+1) P(t+1) Pg (t+1) t+1 CQWPEA 算法在每次迭代解算过程中产生 一次映射 。设 和 分别为第 次迭代 过程中产生的当前位置的种群和个体最好位置种 群 ， 、 、 分别为第 次迭代 产生的人工狼群位置、个体狼位置以及全局最好 位置，则 P(t+1) = T ( ω,X (t),P(t),Pg (t) ) (41) 式中： t = 0,1,··· ,T −1 ； T 为最大游走次数或迭代次数。 实验表明，CQWPEA 算法中每一代全局最好 解位置的适应度值序列是一个递增序列，即 f ( Pg,t−1 ) ⩽ f ( Pg,t ) ⩽ f ( Pg,t+1 ) (42) Pg,t−1 ∈ P(t−1) Pg,t ∈ P(t) Pg,t+1 ∈ P(t+1) t−1 t t+1 式中： 、 、 分别 表示第 、 、 代的全局最好解位置。 在 CQWPEA 算法中，解算优化问题时，通常 只需关注搜索过程中狼群攻击获得的最好解，不 妨将迭代狼群体用全局最好位置来代替。由此 对 CQWPEA 算法的映射过程进行重新定义，其形 式为 Pg,t+1 = T ( ω,Pg,t ) , Pg,t ∈ P(t), Pg,t+1 ∈ P(t+1) (43) 在 CQWPEA 算法中，解算优化问题的过程可 视为元胞演化空间之间的映射。以下采用随机映 射的方法证明和分析 CQWPEA 算法的收敛性。 定义 6 定义度量 d : S ×S → R ，其中 d 的表达 式为 d ( Pg,i ,Pg, j ) =   c− f ( Pg,i ) − ( c− f ( Pg, j ))   =    f ( Pg,i ) − f ( Pg, j )    (44) c → ∞ Pg,i 式中： ； ,Pg, j ∈ S；(S,d) 为完备可分的度量 空间。 ·722· 智 能 系 统 学 报 第 13 卷

第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·723· 证明首先证明(S,d)是度量空间。设S≠O, P∈S,令r(o)= h(w),w∈2o Pg,ωe2-2o 为T(w)的唯一不 dES×S的实值函数。对于Pi、P、Pk∈S,对应 动点。 一个实数d(P,P)∈S满足： 然后证明r()的可测性。对HPo∈S,令P:(o)= 1)d(PsP)≥0，当且仅当Pu=P时，dPi, TCowPEA (@Pso),Paiti (@)TCOwPEA (@P).i=1,2.. P）=0,满足非负性； 因为P1(d)→Pg0,TCOWPEA(d,Pgu(w)→TCQWPEA(u, 2)d(Pxi.Psj)=c-f(Ps)-(c-f(Ps))=c-f(P:j)- Po),P∈S,即TCOWPEA(ω)连续。依据符合定理，{P (c-f(P)冰满足对称性； 为一个随机变量序列，再根据巴拿赫压不动点定 3)(PrP)=(c-f(P:)-(c-f(P=c-f(P)- 理可知，P(ω)→r(ω)，根据极限随机变量定理的 (c-f(Ps)+(c-f(Pg》-(c-f(Px》≤c-f(Pg)- 定义，r(U)作为一个随机变量，因此r(w)作为TCOWPEA(d) (c-f(P)川+(c-f(P)-(c-f(P)川，满足三角 的随机不动点，证毕。 不等式，因此(S,d)为度量空间。 其次证明(S,d为完备度量空间。设S是有限 4实验仿真与结果分析 的二进制编码位串数，对当前狼群中最好个体狼 4.1测试函数 位置的柯西序列P,P∈S,以及Ve>0,3N,当自 为了检验CQWPEA算法的寻优性能，选取 然数n>N时，d(Pa,Pgm)<E,当n→o时，Pn→Pgo 6个标准的测试函数进行仿真实验，6个测试函数 因此(S,d)是完备的度量空间。 的表达式如下： 最后证明(S,d)是可分的。设GSS,因S为有 l)Sphere函数 限元集合，所以G为可数子集。又因为G闭包于S, -100≤x:≤100 所以G在S中稠密，由此得到(S,d)是可分的论证。 故(S,d)是完备可分的度量空间，证毕。 o 2)Schwefel函数 定义7随机搜索算子T:2×S→S称为随机 压缩算子，如果K()<1的非负实值随机变量，则 E=418929xd-2-smu. -500≤x≤500 d(to,d(T(w,P,T(w,Pg+i)》K(ω)dPg,Pg+i)D=1 3)Rosenbrock函数 P,Pg41∈S 定理1 CQWPEA算法的迭代过程形成的映 -2oa-f+c-y -30≤：≤30 射TCOWPEA是随机压缩算子。 证明依据CQWPEA原理，每迭代一次均可 4)Rastrigrin函数 产生比上一次更优的个体狼和目标猎物资源，所 i)-∑(G-10cos2)+10 ，-5.12≤x≤5.12 以存在一个非负实值随机变量K()∈0,1)，使得 d(TCQWPEA(@,Psi-1).TcQWPEA(@,P))=d(Pi,P3.it)= 5)Ackley函数 (c-f(P》-(c-f(Ps*i)≤K(o)I(c-f(P-i)》- (c-f(Px)川=K(ω)d(Pg-1,P) =-20e52 2o=:d(TcQWPEA (@Pi-1),TCQWPEA(@,Pi-1)) K(w)d(P-,Pg}≤2 an传2me小w622 p(2o)=1 6)Griewangk函数 由此可知，CQWPEA算法迭代过程中形成的 映射TCQWPEA:2×SX×SP×S8→SP是一个随机压缩 f()= 2-im+1-1mxe1m 算子。 在上述6个标准测试函数中，无(x)、(,)和 定理2（随机压缩映射定理）设随机搜索算 6(x)为单峰函数，(x、5(x)和f6(x)为多峰函数，函 子T:2×S→S满足所有的w∈S,T(w)均为压缩算 数的维数均设置为30,6个标准测试函数的全局 子，即32∈2，p(2o)=1,对w∈2o,则d(T(w,P), 最优解均为0。 T(,P-i》≤K(o)d(P,P+),则P,P-l,Pg41∈S, 4.2仿真结果分析 0≤K()<1,则T(w)有唯一随机不动点r(),即 采用CQWPEA算法对6个标准测试函数进 T(w,r(w)=r(w)。 行解算，并将其结果与WPEA、QWPEA算法的结 证明首先利用巴拿赫压不动点定理，对 果进行比较。其中相同的参数设置为：狼群规模 u∈2o,h(o)∈S作为T(o)的唯一不动点，对 均为500，最大迭代次数为500次，收敛精度设置

(S,d) S , Ø d ∈ S ×S Pg,i、Pg, j、Pg,k ∈ S d ( Pg,i ,Pg, j ) ∈ S 证明 首先证明 是度量空间。设 ， 的实值函数。对于 ，对应 一个实数 满足： d ( Pg,i ,Pg, j ) ⩾0 Pg,i =Pg, j d(Pg,i Pg, j) = 0 1 ) ，当且仅当 时 ， ， ，满足非负性； d ( Pg,i ,Pg, j ) =   c− f ( Pg,i ) − ( c− f ( Pg, j ))  =   c− f ( Pg, j ) − ( c− f ( Pg,i ))   2) ，满足对称性； ( Pg,i ,Pg, j ) =   (c− f ( Pg,i ) − ( c− f ( Pg, j ))  =   c− f ( Pg,i ) − ( c− f ( Pg,k ) ) + ( c− f ( Pg,k )) − ( c− f ( Pg, j )) ⩽ c− f ( Pg,i ) − ( c− f ( Pg,k ))  +    ( c− f ( Pg,k ))− ( c− f ( Pg, j ))   (S,d) 3 ) ，满足三角 不等式，因此 为度量空间。 (S,d) S { Pg,i ,Pg,i ∈ S } ∀ε>0 ∃N n>N d ( Pg,n,Pg,m ) <ε n → ∞ Pg,n → Pg (S,d) 其次证明 为完备度量空间。设 是有限 的二进制编码位串数，对当前狼群中最好个体狼 位置的柯西序列 ，以及 ， ，当自 然数 时 ， ，当 时 ， 。 因此 是完备的度量空间。 (S,d) G ⊆ S S G G S G S (S,d) (S,d) 最后证明 是可分的。设 ，因 为有 限元集合，所以 为可数子集。又因为 闭包于 ， 所以 在 中稠密，由此得到 是可分的论证。 故 是完备可分的度量空间，证毕。 T : Ω×S → S ∃K(ω) < 1 定义 7 随机搜索算子 称为随机 压缩算子，如果 的非负实值随机变量，则 d({ω,d(T(ω,Pg,i),T(ω,Pg,i+1))K(ω)d(Pg,i ,Pg,i+1)}) = 1 Pg,i , Pg,i+1 ∈ S TCQWPEA 定理 1 CQWPEA 算法的迭代过程形成的映 射 是随机压缩算子。 K(ω) ∈ [0,1) 证明 依据 CQWPEA 原理，每迭代一次均可 产生比上一次更优的个体狼和目标猎物资源，所 以存在一个非负实值随机变量 ，使得 d ( TCQWPEA ( ω,Pg,i−1 ) ,TCQWPEA ( ω,Pg,i )) =d ( Pg,i ,Pg,i+1 ) =    ( c− f ( Pg,i ))− ( c− f ( Pg,i+1 ))   ⩽ K(ω)| ( c− f ( Pg,i−1 ))− ( c− f ( Pg,i ))   = K(ω)d ( Pg,i−1 ,Pg,i ) Ω0 = { ω : d ( TCQWPEA ( ω,Pg,i−1 ) ,TCQWPEA ( ω,Pg,i−1 )) ⩽ K(ω)d ( Pg,i−1 ,Pg,i )} ⩽ Ω p(Ω0) = 1 TCQWPEA : Ω×S X ×S P ×S g → S P 由此可知，CQWPEA 算法迭代过程中形成的 映射 是一个随机压缩 算子。 T : Ω×S → S ω ∈ S T (ω) ∃Ω0 ∈ Ω, p(Ω0) = 1 ∀ω ∈ Ω0 d ( T ( ω,Pg,i ) , T ( ω,Pg,i−1 )) ⩽ K(ω)d ( Pg,i ,Pg,i+1 ) Pg,i ,Pg,i−1,Pg,i+1 ∈ S, 0 ⩽ K(ω)<1 T (ω) r(ω) T (ω,r(ω)) = r(ω) 定理 2 (随机压缩映射定理) 设随机搜索算 子 满足所有的 ， 均为压缩算 子，即 ， 对 ， 则 ， 则 ， 则 有唯一随机不动点 ， 即 。 ∀ω ∈ Ω0 ∃h(ω) ∈ S T (ω) 证明 首先利用巴拿赫压不动点定理，对 ， 作 为 的唯一不动点，对 Pg,i ∈ S r(ω) = { h(ω), ω ∈ Ω0 Pg,i , ω ∈ Ω−Ω0 ， 令 为 T (ω) 的唯一不 动点。 r(ω) ∀Pg,0 ∈ S Pg,1 (ω) = TCQWPEA ( ω,Pg,0 ) Pg,i+1 (ω) = TCQWPEA ( ω,Pg,i ) ,i = 1,2,··· , Pg,1 (ω)→Pg,0 TCQWPEA ( ω,Pg,i(ω) )→TCQWPEA (ω, Pg,0 ) ,Pg,i ∈ S TCQWPEA (ω) { Pg,i } Pg,i(ω) → r(ω) r(ω) r(ω) TCQWPEA (ω) 然后证明 的可测性。对 ，令 ， 因 为 ， ，即 连续。依据符合定理， 为一个随机变量序列，再根据巴拿赫压不动点定 理可知， ，根据极限随机变量定理的 定义， 作为一个随机变量，因此 作为 的随机不动点，证毕。 4 实验仿真与结果分析 4.1 测试函数 为了检验 CQWPEA 算法的寻优性能，选取 6 个标准的测试函数进行仿真实验，6 个测试函数 的表达式如下： 1) Sphere 函数 f1 (x) = ∑d i=1 x 2 i , −100 ⩽ xi ⩽ 100 2) Schwefel 函数 f2 (x) = 418.982 9×d− ∑d i=1 xi ·sin( |xi | 1 2 ) , −500 ⩽ xi ⩽ 500 3) Rosenbrock 函数 f3 (x) = ∑d i=1 [ 100( xi+1 − x 2 i )2 +(xi −1) 2 ] , −30 ⩽ xi ⩽ 30 4) Rastrigrin 函数 f4 (x) = ∑d i=1 ( x 2 i −10 cos(2πxi)+10) , −5.12 ⩽ xi ⩽ 5.12 5) Ackley 函数 f5 (x) = −20 exp  − 1 5 √ 1 d ∑d i=1 x 2 i  − exp   1 d ∑d i=1 cos(2πxi)   +20+e, −32 ⩽ xi ⩽ 32 6)Griewangk 函数 f6 (x) = 1 4 000 ∑d i=1 x 2 i − ∏d i=1 cos( xi √ i ) +1,−100 ⩽ xi ⩽ 100 f1 (x) f2 (x) f3 (x) f4 (x) f5 (x) f6 (x) 在上述 6 个标准测试函数中， 、 和 为单峰函数， 、 和 为多峰函数，函 数的维数均设置为 30，6 个标准测试函数的全局 最优解均为 0。 4.2 仿真结果分析 采用 CQWPEA 算法对 6 个标准测试函数进 行解算，并将其结果与 WPEA、QWPEA 算法的结 果进行比较。其中相同的参数设置为：狼群规模 均为 500，最大迭代次数为 500 次，收敛精度设置 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·723·

·724· 智能系统学报 第13卷 为0.00001。具体到每个不同算法的参数，在 果见表1所示。各取每个算例20次的实验数据， WPEA算法和QWPEA算法中，判定因子w=5O0, 记录其最优值、平均值、最差值；并将 步长因子S=1000,更新因子B=6,最大游走次数 CQWPEA算法的结果与WPEA和QWPEA算法 Tms=20,探狼比例因子6=4，滑模交叉μ=0.2， 进行比较，分别记录其平均迭代次数、最大迭代 σ=0.3，I=8,km=500。在CQWPEA算法的控制 次数、收敛率以及20次独立运行消耗的总时间。 参数y=0.6,量子旋转角△0=0.05，实验仿真环境： 为了增加算法的可信度，WPEA和QWPEA算法 Windows7系统，3GB内存，4 GHz CPU,算法基 的参数直接来源于参考文献，优化比较结果如表2 于MATLAB2015a。每种算法的终止条件均为满 所示。表2中的“一”表示对应的寻优成功次数指 足算法的寻优目标或达到最大迭代次数，计算结 标无法获得统计结果。 表16个测试函数的结果比较 Table 1 Experimental results of six test functions WPEA QWPEA CQWPEA 函数维数 最优值最差值平均值 最优值 最差值 平均值 最优值 最差值 平均值 100.15072.96911.4948 0 0 0 0 0 0 f(x)200.27423.52913.1710 0 0 0 0 0 0 300.12628.84544.0091 0 0 0 0 0 0 100.02091.28740.8437 1.2730x103 2.4178×103 1.2766×1031.2728×1041.2728×101.2728×10 f)200.00361.98710.52202.5460x10 2.9102×103 2.5564×1032.5455×102.5455×102.5455×10 300.06301.84560.80633.8190×10 4.1996×103 3.8309x1033.8183×103.8183×103.8183×10 100.00350.11840.5403 20.5278 832.2900x×10 1.1538×103 9.9220x100 8.9999 7.4550x1026 5(0200.02800.32520.1373 128.1207 9.0315×10 3.0338×10 2.9390×107 8.9969 4.7820×1014 300.00780.28970.1503 165.6075 9.0168×10 3.8070×103 2.9230×1016 26.2234 6.0330x10-13 100.00300.02910.0097 9.8800 33.8274 22.3800 0 0 0 f(x)200.00550.03060.0143 72.8137 137.7914 100.2844 0 0 0 300.01300.06550.0308 144.4023 222.5470 192.9870 0 0 100.02090.05970.0337 0.0197 8.3460 1.3460 8.8820x10168.8820×10168.8820x1016 f5(0200.02470.05400.0329 0.0240 7.5541 2.0060 8.8820×10168.8820x10-168.8820x1016 300.02510.06590.0370 0.0282 5.8638 2.5985 8.8820×10168.8820×10168.8820x1016 100.00310.31330.1072 0.2779 0.4128 0.0964 0 0 0 f6(x)200.00810.48080.2656 0.2573 0.8517 0.5038 0 0 0 300.00200.32530.1639 0.3637 0.9949 0.7816 0 0 0 从表1的结果可知，在满足固定收敛精度下， 算法要比其他2种算法获得的近似最优解更为接 本文提出的CQWPEA算法分别在维度为10、 近最优解值O:针对函数fi(x,CQWPEA算法的寻 20和30的基础上进行测试，发现除了Schwefel 优能力最强，WPEA算法的寻优能力要比 函数、Rosenbrock函数和Ackley函数外，其他 QWPEA算法强，这主要是因为设置算法参数的 3种函数经过20次实验均能一致性收敛到问题 不同而造成的；针对函数5(x),虽然3种算法均没 的全局最优解0。针对函数f(x),CQWPEA算法 有获得最优解值，但从总体上来看，CQWPEA算 和QWPEA算法均可获得最优解，而WPEA算法 法获得的最优解几乎接近全局最优解，其寻优能 的寻优能力较差；针对函数5(x),3种算法均无法 力较强，而QWPEA算法和WPEA算法获得的最 获得最优解，但几乎可达到近似最优解；针对函 优解距离全局最优解相差甚远；针对函数f(x), 数5(x,3种算法虽然无法获得最优解，但CQWPEA CQWPEA算法可获得全局最优解，WPEA算法的

ω = 500 S = 1 000 β = 6 Tmax = 20 δ = 4 µ = 0.2 σ = 0.3 I = 8 kmax = 500 γ = 0.6 ∆θ = 0.05 为 0.000 01。具体到每个不同算法的参数，在 WPEA 算法和 QWPEA 算法中，判定因子 ， 步长因子 ，更新因子 ，最大游走次数 ，探狼比例因子 ，滑模交叉 ， ， , 。在 CQWPEA 算法的控制 参数 ，量子旋转角 ，实验仿真环境： Windows7 系统，3 GB 内存，4 GHz CPU，算法基 于 MATLAB2015a。每种算法的终止条件均为满 足算法的寻优目标或达到最大迭代次数，计算结 果见表 1 所示。各取每个算例 20 次的实验数据， 记录其最优值、平均值、最差值；并 将 CQWPEA 算法的结果与 WPEA 和 QWPEA 算法 进行比较，分别记录其平均迭代次数、最大迭代 次数、收敛率以及 20 次独立运行消耗的总时间。 为了增加算法的可信度，WPEA 和 QWPEA 算法 的参数直接来源于参考文献，优化比较结果如表 2 所示。表 2 中的“—”表示对应的寻优成功次数指 标无法获得统计结果。 f1 (x) f2 (x) f3 (x) 从表 1 的结果可知，在满足固定收敛精度下， 本文提出的 CQWPEA 算法分别在维度为 10、 20 和 30 的基础上进行测试，发现除了 Schwefel 函数、Rosenbrock 函数和 Ackley 函数外，其他 3 种函数经过 20 次实验均能一致性收敛到问题 的全局最优解 0。针对函数 ，CQWPEA 算法 和 QWPEA 算法均可获得最优解，而 WPEA 算法 的寻优能力较差；针对函数 ，3 种算法均无法 获得最优解，但几乎可达到近似最优解；针对函 数 ，3 种算法虽然无法获得最优解，但 CQWPEA f4 (x) f5 (x) f6 (x) 算法要比其他 2 种算法获得的近似最优解更为接 近最优解值 0；针对函数 ，CQWPEA 算法的寻 优能力最强， WPE A 算法的寻优能力要 比 QWPEA 算法强，这主要是因为设置算法参数的 不同而造成的；针对函数 ，虽然 3 种算法均没 有获得最优解值，但从总体上来看，CQWPEA 算 法获得的最优解几乎接近全局最优解，其寻优能 力较强，而 QWPEA 算法和 WPEA 算法获得的最 优解距离全局最优解相差甚远；针对函数 ， CQWPEA 算法可获得全局最优解，WPEA 算法的 表 1 6 个测试函数的结果比较 Table 1 Experimental results of six test functions 函数 维数 WPEA QWPEA CQWPEA 最优值 最差值 平均值 最优值 最差值 平均值 最优值 最差值 平均值 f1(x) 10 0.150 7 2.969 1 1.494 8 0 0 0 0 0 0 20 0.274 2 3.529 1 3.171 0 0 0 0 0 0 0 30 0.126 2 8.845 4 4.009 1 0 0 0 0 0 0 f2(x) 10 0.020 9 1.287 4 0.843 7 1.273 0×10–3 2.417 8×10–3 1.276 6×10–3 1.272 8×10–4 1.272 8×10–4 1.272 8×10–4 20 0.003 6 1.987 1 0.522 0 2.546 0×10–3 2.910 2×10–3 2.556 4×10–3 2.545 5×10–4 2.545 5×10–4 2.545 5×10–4 30 0.063 0 1.845 6 0.806 3 3.819 0×10–3 4.199 6×10–3 3.830 9×10–3 3.818 3×10–4 3.818 3×10–4 3.818 3×10–4 f3(x) 10 0.003 5 0.118 4 0.540 3 20.527 8 832.290 0×104 1.153 8×103 9.922 0×10–30 8.999 9 7.455 0×10–26 20 0.028 0 0.325 2 0.137 3 128.120 7 9.031 5×104 3.033 8×103 2.939 0×10–17 8.996 9 4.782 0×10–14 30 0.007 8 0.289 7 0.150 3 165.607 5 9.016 8×104 3.807 0×103 2.923 0×10–16 26.223 4 6.033 0×10–13 f4(x) 10 0.003 0 0.029 1 0.009 7 9.880 0 33.827 4 22.380 0 0 0 0 20 0.005 5 0.030 6 0.014 3 72.813 7 137.791 4 100.284 4 0 0 0 30 0.013 0 0.065 5 0.030 8 144.402 3 222.547 0 192.987 0 0 0 0 f5(x) 10 0.020 9 0.059 7 0.033 7 0.019 7 8.346 0 1.346 0 8.882 0×10–16 8.882 0×10–16 8.882 0×10–16 20 0.024 7 0.054 0 0.032 9 0.024 0 7.554 1 2.006 0 8.882 0×10–16 8.882 0×10–16 8.882 0×10–16 30 0.025 1 0.065 9 0.037 0 0.028 2 5.863 8 2.598 5 8.882 0×10–16 8.882 0×10–16 8.882 0×10–16 f6(x) 10 0.003 1 0.313 3 0.107 2 0.277 9 0.412 8 0.096 4 0 0 0 20 0.008 1 0.480 8 0.265 6 0.257 3 0.851 7 0.503 8 0 0 0 30 0.002 0 0.325 3 0.163 9 0.363 7 0.994 9 0.781 6 0 0 0 ·724· 智 能 系 统 学 报 第 13 卷

第5期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·725· 寻优能力要比QWPEA算法强。 知，本文算法对于部分函数也会存在无法获得全 由上述分析结果可以得出，从总体上来看，本 局最优解问题，这主要是因为算法的初始参数设 文提出的求解离散优化问题的元胞量子狼群演化 置的随机性、局部寻优结果差、元胞演化规则对 算法在寻优能力均要优于其他狼群演化算法和量 量子旋转角的调整速度慢、量子相位角的选择不 子狼群演化算法，但从部分函数测试的结果可 精确等原因造成的。 表2迭代次数比较 Table 2 Comparison of iterations 函数维数 算法 优化步数 平均迭代次数 最大迭代次数 收敛率% 消耗总时间s WPEA 500 31.545960 f(x) % OWPEA 500 13.40 10 100 3.692419 COWPEA 500 17.95 100 0.460025 WPEA 500 909 501 25 91.341201 f(x) 10 OWPEA 500 28.5 80 3.238189 COWPEA 500 7.20 100 0.822512 WPEA 500 950.20 502 10 77.387860 f(x) 10 QWPEA 500 一 0 2.615991 CQWPEA 500 300.85 249 100 0.511912 WPEA 500 0 f(x) % QWPEA 500 0 5.197518 COWPEA 500 18.75 16 100 0.724987 WPEA 500 0 33.743127 f5(x) 30 QWPEA 500 907.35 66 10 3.103910 CQWPEA 500 27.60 21 100 0.842867 WPEA 500 0 31.591887 f6(x) 30 QWPEA 500 0 3.250854 COWPEA 500 21.40 10 100 0.545058 由表2的结果可知，在不同的维数和相同的 由上述的比较结果知，与WPEA算法和QWPEA 优化步数下，从收敛率和消耗时间上来看，对于 算法相比，无论从收敛精度还是收敛稳定性方 6种不同的标准测试函数，CQWPEA算法收敛率 面，CQWPEA算法的寻优性能明显优于其他2种 均可到达100%，且消耗时间明显比WPEA算法 算法。 和QWPEA算法少；但对于不同的函数，3个算法的 另外，从算法收敛（达到收敛精度）时间方 性能还存在一定的差异。对于(x)函数、(x)函 面，WPEA算法对6个标准测试函数20次实验的 数、fx)函数和fx)函数，WPEA算法的寻优结果 收敛消耗总时间分别为31.55、91.34、77.39、33.74 不理想，主要是因为当维数大于3时，这4个典型的 和31.59s,而QWPEA算法对6个标准测试函数 凹函数呈现多峰特征，具有大量的局部极值点， 20次实验的收敛消耗总时间分别为3.69、3.24、 因此找到全局最优解较为困难。对于(x)函数、 2.62、3.20、3.10和3.25s,CQWPEA算法对6个标 fx)函数和fx)函数，QWPEA算法的寻优结果的 准测试函数20次实验的收敛消耗总时间分别为 收敛率为0，其搜索到的最优解与目标函数的最 0.46、0.82、0.52、0.72、0.84和0.55s。从收敛消耗 优解的偏差较大，这是因为这3个函数是复杂的非 总时间来看，与WPEA算法和QWPEA算法相 线性多峰函数，寻优过程中会使算法陷入局部收 比，CQWPEA算法的收敛速度明显加快。从图6 敛；对于(x)函数和f5x)函数，QWPEA算法的收 中可清晰地看出，CQWPEA算法要比WPEA算法 敛率也几乎为0，其搜索到的最优解偏差也较大。 和QWPEA算法具有较快的收敛速度

寻优能力要比 QWPEA 算法强。 由上述分析结果可以得出，从总体上来看，本 文提出的求解离散优化问题的元胞量子狼群演化 算法在寻优能力均要优于其他狼群演化算法和量 子狼群演化算法，但从部分函数测试的结果可 知，本文算法对于部分函数也会存在无法获得全 局最优解问题，这主要是因为算法的初始参数设 置的随机性、局部寻优结果差、元胞演化规则对 量子旋转角的调整速度慢、量子相位角的选择不 精确等原因造成的。 由表 2 的结果可知，在不同的维数和相同的 优化步数下，从收敛率和消耗时间上来看，对于 6 种不同的标准测试函数，CQWPEA 算法收敛率 均可到达 100%，且消耗时间明显比 WPEA 算法 和 QWPEA 算法少；但对于不同的函数，3 个算法的 性能还存在一定的差异。对于 f1 (x) 函数、f4 (x) 函 数、f5 (x) 函数和 f6 (x) 函数，WPEA 算法的寻优结果 不理想，主要是因为当维数大于 3 时，这 4 个典型的 凹函数呈现多峰特征，具有大量的局部极值点， 因此找到全局最优解较为困难。对于 f3 (x) 函数、 f4 (x) 函数和 f6 (x) 函数，QWPEA 算法的寻优结果的 收敛率为 0，其搜索到的最优解与目标函数的最 优解的偏差较大，这是因为这 3 个函数是复杂的非 线性多峰函数，寻优过程中会使算法陷入局部收 敛；对于 f2 (x) 函数和 f3 (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 算法具有较快的收敛速度。 表 2 迭代次数比较 Table 2 Comparison of iterations 函数 维数 算法 优化步数 平均迭代次数 最大迭代次数 收敛率/% 消耗总时间/s f1(x) 30 WPEA 500 — — 0 31.545 960 QWPEA 500 13.40 10 100 3.692 419 CQWPEA 500 17.95 12 100 0.460 025 f2(x) 10 WPEA 500 909 501 25 91.341 201 QWPEA 500 28.5 11 80 3.238 189 CQWPEA 500 7.20 2 100 0.822 512 f3(x) 10 WPEA 500 950.20 502 10 77.387 860 QWPEA 500 — — 0 2.615 991 CQWPEA 500 300.85 249 100 0.511 912 f4(x) 30 WPEA 500 — — 0 — QWPEA 500 — — 0 5.197 518 CQWPEA 500 18.75 16 100 0.724 987 f5(x) 30 WPEA 500 — — 0 33.743 127 QWPEA 500 907.35 66 10 3.103 910 CQWPEA 500 27.60 21 100 0.842 867 f6(x) 30 WPEA 500 — — 0 31.591 887 QWPEA 500 — — 0 3.250 854 CQWPEA 500 21.40 10 100 0.545 058 第 5 期 马龙，等：求解离散优化问题的元胞量子狼群演化算法 ·725·