第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 algorithm is proposed for solving discrete optimization problems. First, to speed up the global convergence of the algorithm, when generating the diversity of population, the method fully utilizes the double strategy quantum bit initialization 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 description and the selection of the quantum rotation angle, respectively. Then to prove the convergence performance of the algorithm, the method fully utilizes the functional analysis to verify the global convergence. Finally, simulation experiment on six benchmark functions was carried out, and the comparison between the wolf pack algorithm and quantum-inspired wolf pack evolutionary algorithm was provided. The results show that the proposed approach has better convergence 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 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 元胞自动机原理 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 双策略的初始量子位生成过程 在初始化狼群演化过程中，狼群中每匹狼位 置的所有量子位对应态的概率幅可采用 Logistic 混沌映射产生，其产生的基本过程为： 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 candidate 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,则猛狼继 续快速奔袭，且与头狼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·
·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 encoding 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 卷