一种实数编码量子文化算法

郭一楠¹，刘丹丹¹，程健^{1, 2}，张书国¹

(1. 中国矿业大学 信息与电气工程学院，江苏 徐州，221116；

2. 清华大学 自动化系，北京，100084)

摘要：将基于实数编码的量子进化算法引入到文化算法的种群空间，提出一种实数编码量子文化算法。该算法在种群空间采用实数编码量子算法，采用矩形区域描述基因，并利用量子态叠加和相干原理完成量子进化过程。进化个体由基于量子种群的累积概率分布函数的逆函数得到。优势进化个体隐含的优良进化信息在信度空间以知识方式提取，并进一步通过影响函数来影响种群空间的进化个体变异和量子个体宽度更新。针对标准测试函数的仿真结果表明：该算法能有效提高解精度、进化速度和初值的鲁棒性。

关键词；实数编码；量子算法；文化算法

中图分类号：TP301          文献标志码：A         文章编号：1672-7207(2011)S1-0130-07

A novel real-coded quantum-inspired cultural algorithm

GUO Yi-nan¹, LIU Dan-dan¹, CHENG Jian^{1, 2}, ZHANG Shu-guo¹

(1. College of Information and Electronic Engineering, China University of Mining and Technology,

Xuzhou 221116, China;

2. Department of Automation, Tsinghua University, Beijing 100084, China)

Abstract: A real-coded quantum-inspired cultural algorithm is proposed by introducing the real-coded quantum-inspired evolutionary algorithm into the population space of cultural algorithm. In the real-coded mode, rectangle region is adapted to represent gene. Superposition and interference operators in quantum computation mechanics are used to accelerate the evolution process. Evolutionary individuals are obtained via the cumulative probability distribution function and inverse function. The implicit knowledge is extracted from better evolutionary individuals, and then influences the mutation of evolutionary individuals and the update of quantum individual in population space. The simulation results on standard test functions indicate that the novel algorithm improves the solution quality, the speed of convergence and the robustness of initial value.

Key words: real-coded; quantum-inspired algorithm; cultural algorithm

量子算法(Quantum evolution algorithm, QEA)是近年来由量子力学发展而来的一种基于量子叠加性、纠缠性和量子相干性来实现并行计算的一种算法^[1]。量子算法与进化算法相结合，弥补了传统进化算法的不足，形成各种用于解决不同问题的量子进化算    法^[2-3]。但多数量子进化算法都是基于量子比特编码方式，这就决定了其在旋转角查找及编码解码过程中消耗更多的计算资源，并使解精度受到影响，因此，不适合多参数优化和高精度计算的要求。为有效解决通过量子比特编码得到的二进制编码的精度和效率的冲突，许多学者相继提出各种改善方法。文献[4-5]提出了基于实数编码的量子算法，虽省去了繁琐的编码解码过程，但仍需进行旋转角查找，消耗了计算机资源，而且以该种实数编码为基础的量子进化算法不适用于解决组合优化问题。文献[6-7]提出了一种量子实数编码方式。该编码方式减少了计算机内存资源，提高了算法精度，但在种群叠加过程中并未考虑到个体适应度变化情况，而且量子个体矩形宽度定义范围过大，影响个体叠加效果。基于此编码方式，文献[8]采用四类文化算子来影响矩形脉冲的宽度变化，但没有考虑到进化开始时限制其宽度，从而影响种群个体叠加。文献[9]在该实数编码的基础上考虑了适应度叠加，同时结合自学习算子改善算法，但仍没有充分利用隐含在较优秀个体中的各类知识，即缺乏知识的指导。文化算法^[10]采用双层进化模型，由实现个体进化的种群空间和实现知识更新的信度空间构成。种群空间采用各类进化算子实现进化操作，并选取较优个体作为样本提供给信度空间。信度空间根据获得的样本提取进化过程中隐含的有价值信息，并将其以知识的形式加以描述和保存，并被用于引导种群空间个体的进化。在该模型中，引入量子实数编码算法，本文提出了一种实数编码量子文化算法(Real-coded quantum- inspired cultural algorithm, RQCA)。该算法利用量子态叠加、相干特性、实数编码和知识引导的优点，构造了一种新的量子个体。每个个体可以表达多个态的叠加，实数编码直接反映在个体中，省去繁琐的编码解码过程和旋转角查找。种群空间采用基于实数编码的量子进化算法，信度空间通过提取量子种群产生的进化种群优秀个体的知识，来影响种群空间中进化种群的进化和量子种群的更新。

1  基于实数编码的量子文化算法

量子文化算法采用文化算法的双层进化机制。种群空间采用实数编码量子算法，定期把由种群空间量子种群转化获得的进化种群优势个体传递给信度空间；信度空间提取优势进化个体知识，并进一步通过影响函数来引导种群空间进化个体的进化操作，进而影响量子种群更新。量子种群间隔一定进化代数会自动更新，产生新的种群，避免寻优陷入局部最优。这里，量子个体是指采用基于矩形区域实现实数编码的个体，其构成量子种群；进化个体是指由一系列实数向量构成的个体，可实现个体适应度计算，进化个体构成进化种群。由于进化个体是基于量子个体的概率函数产生的，量子个体和进化个体具有相同的基因个数。

量子文化算法的具体步骤如下。

Step1：在决策空间内生成种群规模为p的初始量子种群Q(0)；初始化信度空间。

Step2：量子种群Q(t)转化生成同样种群规模的进化种群P(t)；基于进化个体实现个体适应度评价操作。

Step3：通过接受函数提取优势进化个体作为样本，更新信度空间各类知识。

Step4：通过影响函数利用各类知识引导进化个体的变异操作，生成p个子代个体。

Step5：结合子代进化个体和父代进化个体构成规模为2p的进化子代种群，并进行个体的适应度评价；采用联赛选择得到下一代进化种群P(t+1)。

Step6：基于进化种群P(t+1)更新量子种群Q(t+1)；

Step7：判断是否满足算法终止条件，如果满足则输出最优个体；否则跳转到step2。

可见，算法的核心在于：适合于量子算法的知识描述及其对量子进化过程的影响方式。

2  信度空间知识描述及更新

信度空间是一个用来存储个体经验的知识库，个体可以在信度空间中间接地学到其他个体获得的社会经验。种群空间和信度空间相互联系、相互影响。本文信度空间选用状况知识和规范知识这2类知识。信度空间实现对进化个体知识的描述和提取，并通过影响函数作用于种群空间，从而实现对进化个体的进化引导。同时，信度空间存储的知识也会在更新函数的作用下不断更新，从而加速进化收敛。

2.1  规范知识

规范知识K₁用于描述问题的可行解空间，记为。其中：L(t)={l₁(t), l₂(t), …, l_m(t)}；U(t)={u₁(t), u₂(t), …, u_m(t)}； ；；m是变量维数；u_i和l_i分别表示第i维变量的上限和下限；和分别表示对应于变量上、下限的适应度。记为变量j的可调整区间宽度。

规范知识更新体现为可行搜索空间的变化。随着进化深入，搜索范围应集中涵盖在优势区域。因此，当存在较优个体超出当前搜索范围时，更新标准知识。以最小值优化问题为例，第j维变量的上/下限更新过程及其适应度更新过程为：

  (1)

 (2)

   (3)

 (4)

标准知识约束了搜索范围，用于判断子代个体的可行性，保证进化在较优势区域进行。

2.2  状况知识

状况知识K₃用于记录进化过程中的较优个体，记为。式中：s为状况知识容量；为样本库中第i个较优个体，f(x_i)为x_i的适应度。

状况知识中记录的较优个体按照个体适应度降序排列，即满足f(x_i-1)＞f(x_i), i≤s。种群空间每代进化完成后，接受函数选取较优个体提交给信度空间，知识更新函数从中选出最优个体，用于更新状况知识。设x^Best(t)是种群空间第t代最优个体，其更新过程描述为：

  (5)

可见：状况知识是进化过程中具有优势引导作用个体轨线的反映。

3  知识引导的量子算法

量子文化算法中，种群空间采用量子实数编码，由量子个体构成的量子种群和进化个体构成的进化种群组成。前者实现量子进化操作，后者利用信度空间知识改善进化性能。

3.1  量子个体实数编码

量子态矢量表达是量子算法的实现基础。目前，量子个体常采用二进制和实数2种编码方式。面向连续优化问题，二进制编码存在离散化误差，且计算精度低，所需信息存储空间大。因此，本文采用量子实数编码。

量子实数编码方式采用一个矩形区域来表示基因，矩形区域由中心位置和宽度来唯一确定，并以个体相对势能作为其高度^[9]。该基于概率密度的实数编码方式不同于一般的实数编码。它通过模拟量子态叠加、相干原理，构造了一种新的量子个体，种群的叠加直接反映在个体上，既充分利用了量子算法的并行性，加快求解速度，又利用了传统实数编码的优点，避免了量子比特编码的冗余。设量子种群由n个量子个体构成。每个个体包含m个基因：

; i=1, 2, …, n  (6)

其中：c_ij和w_ij分别为第i个量子个体第j个基因所对应的矩形区域中心和宽度。可见：1个量子个体表示的矩形区域包含了以c_ij为中心、以w_ij为宽度的区间内的所有值，它记录优化问题的1个解。矩形区域的高度通过个体适应度来表示^[9]：

                (7)

其中：h_i和f(q_i)分别表示第i个量子个体的矩形高度和其适应度。可见，量子种群满足。此处，为了计算量子个体的适应度，定义临时进化个体。临时进化个体的基因变量值以量子个体表示的矩形区域内观察的某个单点值表示，在此用矩形中心表示。临时进化个体的适应度就是量子个体的适应度。

3.2  量子种群叠加及进化个体生成

通过对量子个体之间的叠加获得相应的概率密度函数。设PDF_j为第j个等位基因的叠加状态，满足：

             (8)

针对量子种群，其叠加过程如图1所示。量子种群叠加后，其所有量子个体都处于纠缠状态，即量子个体之间相互影响，任何量子个体的改变都会使处于叠加状态的系统发生改变^[9]。叠加后的量子个体可以表示决策变量在不同取值区间的取值概率。通过该叠加过程可以增大较优个体被观测的概率，使量子种群向最优解迁移。

在量子叠加后的矩形区域内随机选取某个点作为进化个体基因位。根据所获得的量子种群概率分布函数，求取累积概率分布函数及其逆函数。通过选择随机数r，在逆函数曲线上找出相对应的点，重复该步骤，直至量子个体所有基因位找到相对应的实数点为止，此时即生成1个用实数向量表示的进化个体。设r是[0,1]区间内满足正态分布的随机数，如图2所示，采用不同r，可以生成相应的进化个体，记为x_ij。

              (9)

             (10)

显然，进化个体中等位基因在具有较高概率分布的区域存在解的可能性更大，并且进化个体与量子个体具有相同数量的基因位数。值得注意的是：为保证逆函数存在，要求CDF必须严格单调递增。为满足该条件，必须保证个体适应度满足f(q _i)＞0。

图1  2个量子个体叠加过程

Fig.1  Splicing process between two quantum individuals

图2  进化个体生成机制

Fig.2  Transform method of evolutionary individual

3.3  知识引导的进化个体变异操作

传统变异操作是一种随机扰动，没有有效利用进化过程中的信息，因而收敛速度较慢。为加快收敛速度，本文采用信度空间的两类知识来引导种群空间的变异操作，使种群向着优良方向进化。规范知识用于调整变量变化步长，使用形势知识调整其变化方向。设和分别为变异前、后第i个进化个体的第j个变量值，则知识引导的进化个体变异操作为：

    (11)

其中：N(0,1)为服从标准正态的随机数；e_i为形势知识记录的优秀个体；λ为步长收缩因子。显然，当进化个体处于较好区间时，仅对个体进行微小变异，在其他情况下则使父代进化个体尽可能向信度空间规范知识所限定的最可能得到最优值的区间迁移。可见：通过知识的引导作用，进化个体能快速的向优秀个体靠拢，从而加快进化收敛速度。

3.4  知识引导的量子个体更新

反映当前优势进化个体信息的知识被用于控制量子个体的更新，从而使种群向优良模式进化。量子个体更新包括量子个体的矩形区域的中心值c_ij和宽度w_ij。设e_ij表示形势知识记录的优秀进化个体基因值，c_ij表示更新后的量子个体矩形中心值，记为^[6]：

              (12)

设表示更新后量子个体的矩形宽度，则矩形宽度w_ij的更新如下：

     (13)

式中：N(0,1)为服从标准正态的随机数；为评定准则，记为

       (14)

显然，当多于1/5的进化个体性能得到提高时，缩短矩形宽度，减小搜索区域；当少于1/5的进化个体性能未得到提高，增加矩形宽度，扩大搜索区域；否则，宽度保持不变。

4  仿真结果与分析

为验证本文所提算法的合理性和有效性，采用表1中的标准测试函数，针对算法中的关键参数对进化性能的影响进行深入分析，并将其与遗传算法(Simple genetic algorithm, SGA)、量子实数编码的量子算法(Real-coded quantum-inspired evolutionary algorithm, RQEA)进行分析比较。在遗传算法中，采用精英保留+联赛选择策略、单点交叉算子和高斯变异算子。在RQEA 和RQCA的进化过程中，矩形区域的宽度控制着搜索区域，特别是初始宽度。为了达到更好的种群叠加效果，定义矩形区域宽度的初始值为。仿真分析中算法的主要参数包括：量子种群规模为10，进化种群规模为10，样本库规模为5，接受比例为0.2，交叉概率为0.6，更新频率为5，运行次数为30，进化终止代数=1 000。

表 1  测试函数

Table 1  Benchmark functions

4.1  算法性能分析

量子文化算法不同于传统的基于种群个体表示优化问题候选解的遗传算法。它利用矩形脉冲来表示1个个体，每个个体在矩形区域所在的区间内变化。因此，它能够在整个区间内快速收敛。此外，把文化算法的双层结构嵌入到由量子个体产生的进化个体中，充分利用进化知识信息来引导进化操作，进而影响量子个体的更新，可以提高收敛速度，改善算法性能。

4.1.1  种群规模n

算法中，量子个体通过叠加得到累积概率分布函数，因此，种群规模n直接影响曲线的平滑度。针对测试函数f₄，分别采用5，10，15这3种不同的种群规模，经仿真实验获得概率密度函数(PDF)曲线和累积概率分布函数(CDF)曲线，如图3所示。分析表明：种群规模越大，曲线越平滑，从而更容易找到最优解，但也会增加算法的复杂度；当种群规模越小时，曲线由一些列折线构成，使得在寻找最优解的过程中易陷入局部最优解。因此，本文选取量子种群规模为10，以兼顾曲线平滑度和算法的计算效率。

图 3  不同量子规模下PDF和CDF曲线比较

Fig.3  Comparison of PDF and CDF with different quantum population sizes

表2  不同更新频率算法性能比较

Table 2  Comparison of algorithms’ performances with different τ

表3  不同算法性能比较

Table 3  Comparison of performances with different algorithms

4.1.2  更新频率τ

种群空间的量子种群更新频率反映出知识对量子个体的影响程度。选取3组不同的更新频率进行比较，仿真运行结果如表2所示。表中：M₁表示平均最优目标值，M₂表示最优值的均方差，M₃表示最优解找到的次数，M₄表示最优解的运行次数。从表2可见：随着更新频率增大，算法的收敛精度、收敛效率和初值的鲁棒性均得到一定提高。分析表明：当更新频率较大时，知识引导的进化个体不能及时更新量子个体，容易使量子个体进化陷入局部收敛；当更新频率较小时，能够快速进化，提高解精度和速度，然而，频繁地更新会增加计算的复杂度。

4.2  与其他算法比较

为进一步测试算法性能，针对表1中测试函数，把RQCA与RQEA和SGA进行比较，运行结果的统计分析如表3所示。可见：量子文化算法在整体上具有较好的解精度和收敛代数，且对初值的鲁棒性较好。这是因为：该算法采用了基于概率密度的量子实数编码，使得一个量子个体能够表征多个态的叠加，充分利用了量子并行性和传统实数编码的优点；同时，把实数编码量子进化算法嵌入到文化算法的框架中，通过知识学习使种群朝着优秀个体的方向进化，比传统的进化算法具有更好的多样性和快速收敛性，有效避免了搜索进化过程的早熟收敛现象。

5  结论

基于文化进化机制和量子实数编码思想，提出了一种量子文化算法。该算法的种群空间采用实数编码量子算法，引入矩形区域来表示基因，通过个体等位基因的叠加使种群处于相干状态，并通过进化算子来增加最优解被观测到的概率。接收函数定期把由种群空间的优秀进化个体传递给信度空间，信度空间通过提取进化过程中知识，并进一步引导进化种群的搜索方向，进而影响量子种群的更新，从而使进化朝着方向搜寻最优解。仿真结果表明，该算法能够提高解的质量、进化速度和初值的鲁棒性，改善算法性能。

参考文献：

[1] 焦李成, 杜海峰, 刘芳, 等. 免疫优化计算、学习与识别[M]. 北京: 科学出版社, 2006: 140-141.
JIAO Li-cheng, DU Hai-feng, LIU Fang, et al. Immune optimization calculation, learning and recognition[M]. Beijing: Science Press, 2006: 140-141.

[2] Narayanan A, Moore M. Quantum-inspired genetic algorithm[C]//Proceedings of the International Conference on Evolutionary Computation. Piscataway, USA: IEEE Press, 1996: 61-66.

[3] Han K H, Park K H, Lee, C H, et al. Parallel quantum-inspired gentic algorithm for combinatorial optimization problems[C]// Proceedings of the IEEE Conference on Evolutionary Computation. Piscataway, USA: IEEE Press, 2001: 1442-1429.

[4] 陈辉, 张家树, 张超. 实数编码混沌量子遗传算法[J]. 控制与决策, 2005, 20(11): 1300-1303.
CHEN Hui, ZHANG Jia-shu, ZHANG Chao. Real-coded chaotic quantum-inspired genetic algorithm[J]. Control and Decision, 2005, 20(11): 1300-1303.

[5] 高辉, 徐光辉, 张锐, 等. 实数编码量子进化算法[J]. 控制与决策, 2008, 23(1): 88-90.
GAO Hui, XU Guang-hui, ZHANG Rui, et al. Real-coded quantum evolutionary algorithm[J]. Control and Decision, 2008, 23(1): 88-90.

[6] Cruz A V A, Vellasco M B R, Pacheco M A C. Quantum- inspired evolutionary algorithm for numerical optimization[C]// Vancouver, Canada: IEEE Press. 2006: 2630-2637.

[7] Cruz A V A, Barbosa C R H, Pacheco M A C, et al. Quantum- inspired evolutionary algorithms and its application to numerical optimization problems[C]//Proceedings of International Conference on Neural Information Processing. Calcutta, India: Springer, 2004: 212-217.

[8] Cruz A V A, Pacheco M A C, Vellasco M B R, et al. Cultural operators for a quantum-inspired evolutionary algorithm applied to numerical optimization problems[C]//Proceedings of International Conference on Natural and Artificial Computation. Las Palmas, Spain: Springer, 2005: 1-10.

[9] 覃朝勇, 郑建国. 一种新量子进化算法及其在函数优化中的应用[J]. 系统仿真学报, 2009, 21(10): 2862-2865.
QIN Chao-yong, ZHENG Jian-guo. Novel quantum-inspired evolutionary algorithm and its application to number optimization problems[J]. Journal of System Simulation, 2009, 21(10): 2862-2865.

[10] 郭一楠, 王辉. 文化算法研究综述[J]. 计算机工程与应用, 2009, 45(9): 41-46.
GUO Yi-nan, WANG Hui. Overview of cultural algorithm[J]. Computer Engineering and Application, 2009, 45(9): 41-46.

(编辑 陈灿华)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(60805025)；江苏省自然科学基金资助项目(BK2010183)；中国博士后基金资助项目(20090460328)；江苏省青蓝工程(2008)

通信作者：郭一楠(1975-)，女，山西太原人，博士，教授，从事智能优化算法与智能控制研究；电话：13852000540；E-mail: nanfly@126.com