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