三值量子遗传算法及其应用

樊富有，王瑞锦(. 宜宾学院计算机与信息工程学院 四川 宜宾 644000；. 电子科技大学信息与软件工程学院 成都 673)



三值量子遗传算法及其应用

樊富有1，王瑞锦2
(1. 宜宾学院计算机与信息工程学院 四川 宜宾 644000；2. 电子科技大学信息与软件工程学院 成都 611731)

【摘要】面向智慧城市无线视频传感网络建设的需要，提出了一种三值量子遗传算法，用于求解网络优化覆盖中的节点部署问题。算法以二维离散网格模型描述监视区，用编码描述矩阵刻画监视区域，并采用七元组模型描述有向无线视频传感器。用三值量子遗传算法搜索解空间，通过合理设计染色体编码，优化三值量子旋转门参数，使得算法的运算速度快，收敛性好。引入理想覆盖率和理想加权覆盖率两个极限值，采用相对比较法评判算法优劣。仿真实验表明，算法获得的节点部署方案能很好逼近理想极限值。

关 键 词有向感知模型; 优化覆盖算法; 三值量子遗传算法; 无线视频传感网络

Application of Three-Valued Quantum Genetic Algorithm

FAN Fu-you1and WANG Rui-jin2
(1. School of Computer and Information Engineering, Yibin University Yibin Sichuan 644000; 2. School of Infoumation and Software Engineering, University of Electronic Science and Technology of China Chengdu 611731)

Abstract According to the construction needs of the smart city wireless video sensor network, a three-valued quantum genetic algorithm is proposed for solving the deployment problem of optimized network coverage algorithm. The monitoring region is depicted by two-dimensional discrete grid model, and the discrete grid model is represented by a code description matrix. The directional wireless video sensor is described by a seven-tuples. The three-valued quantum genetic algorithm with reasonable chromosome coding and optimized three-valued quantum rotation gate parameter is used to search the solution space, which has a good convergence rate and a fast computation speed. Two limit values of ideal coverage rate and ideal weighted coverage rate are introduced to evaluate the algorithm by the way of relative comparison. The result of simulation experiments show that the node deployment solutions worked out by the algorithm can well approximate the ideal limit value.

Key words directional sensing model; optimized coverage algorithm; three-valued quantum genetic algorithm; wireless video sensor network

智慧城市概念正在全球范围内逐渐兴起，发达国家纷纷开展智慧城市建设，把无处不在的各种智能传感器通过网络连接起来形成物联网，实现对物理城市的全面感知。本文研究的视频传感器网络是智慧城市传感网络的重要组成部分。由于无线视频传感器采用电池供电，具有成本低、无须布线、安装方便等优点，已成为代替有线视频监控器的首选设备。因此，在智慧城市建设中，如何优化部署给定数量的无线视频传感器节点，实现自主协同和对监视区的优化覆盖具有重要现实意义。

传感器初期部署通常采用随机部署或针对特定用途进行有计划部署两种方式。考虑到无线视频传感器的工作特点，采用随机方式部署的视频传感网，会产生大量不合理的覆盖结构，形成感知重叠区和盲区，造成传感器利用率低，建设成本增加，覆盖效果不好等问题。因此，需要采用有计划部署策略构建智慧城市无线视频传感网络。鉴于此，如何根据城市场景自动高效地生成无线视频传感器节点部署方案成为智慧城市建设必须解决的问题。

本文通过对二值量子遗传算法及其在无线视频传感节点部署中的应用研究[1]，结合三值量子逻辑系统的优势[2-3]，设计了一种三值量子遗传算法，该算法具有搜索空间大，搜索速度快，全局寻优能力强的特点，通过它能自动生成传感节点部署方案，对提高无线视频传感网络的覆盖率，降低网络建设成本具有重要意义。

1 三值量子遗传算法

量子计算是利用量子态的量子力学特性实现的计算，包括量子叠加、量子纠缠以及量子测量导致的量子态塌缩等非经典特性。量子遗传算法是一种基于量子计算思想的智能进化算法，它利用量子信息中的某些概念表征一个状态，用量子比特的概率幅表示形式编码染色体，使得一个染色体成为多模叠加态的组合，采用量子门的更新完成种群的进化与搜索[4-7]。量子遗传算法具有搜索空间大、速度快、全局寻优能力强等优点[1,4]。

1.1 三值量子比特

1.2 三值量子遗传算法中的染色体表示及变异运算

式中，参数θ是旋转角。染色体中的基因在旋转算子的作用下，可变换为新的基因。根据三值量子遗传算法的求解需要，本文将三值量子旋转门定义为：

式中，R(θ12)、R(θ13)和R(θ23)分别定义为：

为了降低运算复杂度，将θ12，θ13和θ23取相等值，令其为θ，则将式(4)写为：

在旋转算子的作用下，染色体中的第j个基因可变换为新的基因，即：

由于旋转角的幅值会对收敛速度产生影响，如果幅值过大，会导致早熟；如果过小，会使收敛速度变慢，影响求解速度。经过对三值量子遗传算法旋转门的深入对比研究，在总结大量实验数据的基础上，建议旋转角θ的取值区间定为[] 0.02π,0.05π。此外，文献[6]提出了一种对传统量子旋转门的改进算法，该算法有助于跳出求解过程中产生的局部最优解，避免出现早熟现象。本文借鉴这一思想，定义适合于三值量子遗传算法的量子修正门H3ε，用于对变异基因进行修正，有：

修正规则定义如下：

其中，0<ε≤ 1，不同的ε值对算法的收敛性影响很大。当ε=0时，H3ε门成为普通的三值量子旋转门；当ε过大时，个体的收敛趋势将会消失。本文的ε取值区间定为[0.01,0.02]。

为保证搜索过程中种群的多样性，避免早熟收敛，增大搜索到最优值的机会，可引入变异算子来改变染色体基因的位置。本文算法采用三值量子非门完成这一功能。三值量子非门定义为：

在量子非门作用下，染色体各基因的分量概率幅作如下变化：

1.3 三值量子遗传算法的基本步骤

以1.1节和1.2节所定义的量子比特、种群、染色体、基因、旋转算子、修正算子和变异算子等概念为基础，将三值量子遗传算法的基本步骤定义如下：

1) 初始化三值量子遗传算法中的各项参数。2) 随机产生初始种群。

3) 测量种群中的所有个体，获得到一组解，评估所得解的适应度，记录下其中的最优个体作为下一代的演化目标值。

4) 判断算法终止条件是否满足。如果满足，则程序结束，保留结果并退出；否则继续。

5) 根据当前的演化目标值，运用旋转算子和修正算子对种群个体进行更新，获得子代种群。

6) 用变异算子对染色体进行变异更新。

7) 将父代种群中的最优解与当前的目标值作比较，取适应度较高的个体作为下一次的演化目标值，回到步骤4)。

2 无线视频网络覆盖问题数学模型

应用于智慧城市的无线视频传感网络因其功能和属性的特殊性，所涉及的监视区场景和传感器节点均各有其特点。为设计出满足需要的优化覆盖算法，首先需要构造出能满足理论计算和工程实践需要的网络覆盖数学模型[1,8]。本节给出监视区场景描述模型、传感器节点属性模型和视频传感网覆盖模型。

2.1 监视区场景描述

在实际工程应用中的无线视频传感网，所覆盖的监视区环境复杂，情况差异大。工程实践中需要根据监视区场景的实际情况，合理地部署传感器节点，减少感知重叠区和盲区，提高传感网络的有效覆盖率。

为实现传感器网络节点部署和优化覆盖控制，需对监视区构造出对应数学模型。综合考虑视频传感器的视距、视角、监视区的大小和监视精度等因素，确定以1 m为量化单位将监视区平面进行离散化处理，形成二维网格。对网格化的视频监视区进行离散采样编码，重点监视区编码为2，障碍物所在区域编码为1，空旷区域编码为0。采用矩阵存储编码值，矩阵的行列索引值代表该采样点在监视区中的相对坐标，称这样的矩阵为监视区描述矩阵，有：

该数学模型结构简单，易于实现，存取方便，并能进行分块操作，为算法设计带来诸多便利。反之给定一个描述矩阵，也很容易绘制出监视区的平面图，能方便进行数据的后期输出处理。

从式(12)可以看出，监视区描述矩阵City描述了一个长、宽分别为10 m的正方形区域。在该区域中，有两个障碍物，障碍物形状在1 m精度下分别表示一个矩形和一个圆形。监视区中还存在一个需重点监视的直角边长为3 m的等腰直角三角形区域。

2.2 视频传感器节点描述

视频传感网节点的成像器件大多是矩形的，其有效感知范围类似于一个四棱锥，应为其建立一种有向感知模型[9]。通常情况下，视频传感器镜头与水平面有一个夹角，为方便建模，将传感器与水平方向的夹角和传感器视距进行合并处理，将传感器的有效感知范围投影在水平面上进行建模，用七元组来描述视频传感器节点[1,10]。

图1　视频传感器七元组模型

为简化运算，方便工程应用需要，节点参数iα在本文的网络优化覆盖算法中未作考虑，但在特征提取和模式识别研究中需要作为重要参数加以考虑。

2.3 无线视频传感网的覆盖描述模型

根据图1节点的参数含义和式(13)的定义，每个节点的最大覆盖面积相同。记节点vi的覆盖面积为则将节点vi的覆盖区记为则有：

由于监视区中可能存在障碍物，记障碍物所在区域为B，则：

如果有障碍物出现在节点vi的覆盖区内，则称节点vi有遮挡，遮挡区记为如果节点vi的覆盖区与其他节点的覆盖区发生重叠，则将重叠部分区域记为则：

节点vi的有效覆盖区记为则：

若将监视区中全体视频传感器节点的有效覆盖区域记为S′，则：

在部署视频传感器节点时，除考虑要使有效覆盖面积最大化外，还应考虑节点能否正常实现数据收发。根据式(13)，节点vi的通信半径为r，它能与其周围节点进行通信的区域记为则：

根据式(13)～式(19)的定义，在对监视区的重要程度不作区分的情况下，视频传感网络对监视区S的覆盖率记为r( S )，则：

3 优化覆盖问题数学的数学规划模型

用三值量子遗传算法对优化覆盖问题进行求解，需首先建立正确的数学规划模型。视频传感器网络对监视区的加权覆盖率为r′(S)，求解目标是使最大化。则数学规划模型为：

约束关系确保传感器节点部署在监视区内的非障碍物所在区域，使得在任意节点的通信区域内至少存在另一中继节点，以此保证无孤立节点存在。

4 无线视频网络优化覆盖算法

由于城市环境的特殊性和视频传感节点的有向性，不能采用大量随机“撒播”的方式部署无线视频传感网络。因此，无线视频网络优化覆盖算法采用第1节中提出的三值量子遗传算法对第3节给出的覆盖数学规划模型进行启发式求解，计算出节点具有最大覆盖率的部署方案，方案中描述了节点数量、各节点的位置坐标和方位角。位置坐标受监视区描述矩阵City约束，且对重点监视区作加权处理，方位角不受约束，方案能保证无孤立节点存在。优化覆盖算法的基本内容如下。

4.1 染色体编码

在种群中，一条染色体表征解空间中的一个可行解。每条染色体由n个基因序列构成，每个基因序列描述一个传感器节点的位置坐标和方位角。基因序列中的qutrit数，由表数精度和问题规模共同决定。算法分别采用10个qutrit来编码x、 y、 θ。测量时可分别得到10位的三进制0、1、2序列，但它们代表的含义不同。描述x、 y的0、1、2序列代表一个整数，表数范围为0～59 048。描述θ的0、1、2序列代表一个实数，前3个qutrit代表整数部分，表数范围为0～26，后7个qutrit代表小数部分，表数范围为0～0.999 543，整体表数范围为0～26.999 542。

4.2 适应度评估函数

适应度函数是选择和评估染色体的重要依据。为了得到式(23)中的最大值，应该采用传感器节点在监视区中的有效覆盖率作为适应度函数。但直接计算该适应度函数特别困难。考虑到第3节建立的数学模型，监视区被描述为离散网络，由描述矩阵City表示。因此，可把式(22)中各区域的面积积分计算，近似为对区域所围网格点数的求和运算，从而得到：

则式(24)中的Cg就作为本文优化覆盖算法中三值量子遗传算法的适应度函数。

4.3 优化覆盖算法步骤

1) 根据监视区环境，初始化描述矩阵City，生成障碍物集合B和重点监视区集合K。

2) 随机在非障碍物区“撒播”视频传感器节点，记录下各传感器节点的位置坐标和方位角。

3) 在约束条件限制下，采用三值量子遗传算法求解出传感器节点集的合理位置坐标和方位角，得到一组最优解。

4) 形成节点部署方案，算法结束。

5 优化覆盖效果分析

由于无线视频传感网的绝对覆盖率是和节点数量成正相关的，当节点数量超过某一数值后，绝对覆盖率可达100%，但付出的成本却会很高。因此，本文采用相对比较的方法来评判算法的优化覆盖效果，即用尽量少的节点，达到尽量大的覆盖率。为此，引入两个极限理想参数：理想覆盖率和理想加权覆盖率。

视频传感网的理想覆盖率是指在理想态下，传感网的覆盖率上限。视频传感网的理想加权覆盖率是指在理想态下，传感网的理想加权覆盖率上限。表1是50个节点和200个节点覆盖率与理想值的对比数据。

表1　节点覆盖率与理想值的对比

从表1可以看出，当节点个数为50，迭代到800次时，节点覆盖率可达到理想极限值的99.57%，加权覆盖率可达理想极限值的99.21%。这一比值已经和理想值相差无几，算法表现相当优秀。但当节点个数为200，迭代到800次时，节点覆盖率达到理想极限值的97.43%，加权覆盖率达到理想极限值的97.85%，与理想都相差2个百分点，算法表现不是特别优秀。但这并不是算法本身的问题，主要原因是节点的可视范围形状与重点监视区形状不能实现无缝无重叠覆盖，从理论上讲就无法向理想极限值靠近了。从这两组数据与极限值的对比情况来看，算法的效果已经很好了。

因本文的结果与文献[11-12]的研究数据没有可比性，故未在文中与其他文献所述算法作性能比较。本文提出的与理想值作对比的做法相对客观，不受监视场景、数学模型差异的限制，可以较为真实的反映出算法的优劣。

6 结 束 语

本文以智慧城市无线视频传感网络建设为背景，提出一种基于三值量子遗传算法的网络优化覆盖算法。以二维离散网格模型表示监视区场景，用编码描述矩阵表示监视区域，用七元组描述有向视频传感器，推导得出了问题的数学规划模型。采用三值量子遗传算法搜索解空间，通过合理编码染色体，优化量子旋转门参数，使得算法的运算速度快，收敛性好。仿真实验和数据分析表明，该算法获得的方案能很好逼近理想极限值，求解出的节点部署方案，适合用于实际工程项目。

参 考 文 献

[1] 樊富有, 杨国武, 乐千桤, 等. 基于量子遗传算法的无线视频传感网络优化覆盖算法[J]. 通信学报, 2015, 36(6): 201512-1-11. FAN Fu-you, YANG Guo-wu, LE Qian-kai, et al. Optimized coverage algorithm of wireless video sensor network based on quantum genetic algorithm[J]. Journal of Communications, 2015, 36(6): 201512-1-11.

[2] FAN Fu-you, YANG Guo-wu, YANG Gang, et al. A synthesis method of quantum reversible logic circuit based on elementary qutrit quantum logic gates[J]. Journal of Circuits, Systems and Computers, 2015, 24(8): 1550121-1-20.

[3] 樊富有, 杨国武, 张艳, 等. 三值量子基本门及其对量子 Fourier变换的电路实现[J]. 计算机科学, 2015, 42(7): 57-61. FAN Fu-you, YANG Guo-wu, ZHANG Yan, et al. Three-valued quantum elementary and implementation of quantum Fourier transform[J]. Computer Science, 2015, 42(7): 57-61.

[4] HAN K H，KIM J H. Quantum-inspired evolutionary algorithm for a class of combinational optimization[J]. IEEE Transactions on Evolutionary Computing, 2002, 6(6): 580-593.

[5] HAN K H, KIM J H. On setting the parameters of quantum-inspired evolutionary algorithm for practical application[C]//Congress on Evolutionary Computation. Canberra, Australia: IEEE, 2003: 178-194.

[6] HAN K H, KIM J H. Quantum-inspired evolutionary algorithms with a new termination criterion, Hεgate, and two-phase scheme[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(2): 156-169.

[7] LI Pan-chi, LI Shi-yong. Quantum-inspired evolutionary algorithm for continuous spaces optimization based on bloch coordinates of qubits[J]. Neurocomputjng, 2008, 72(1-3): 581-591.

[8] AKYILDIZ I F, MELODIA T, CHOWDHURY K R. A survey on wireless multimedia sensor networks[J]. Computer networks, 2007, 51(4): 921-960.

[9] MA Hua-dong, LIU Yong-he. Some problems of directional sensor networks[J]. International Journal of Sensor Networks, 2007, 2(1): 44-52.

[10] FAN Gao-juan, WANG Ru-chuan, HUANG Hai-ping, et al. Coverage-guaranteed sensor node deployment strategies for wireless sensor networks[J]. Sensors, 2010, 10(3): 2064-2087.

[11] 任彦, 张思东, 张宏科. 无线传感器网络中覆盖控制理论与算法[J]. 软件学报, 2006, 17(3): 422-433. REN Yan, ZHANG Si-dong, ZHANG Hong-ke. Theories and algorithms of coverage control for wireless sensor networks[J]. Journal of Software, 2006, 17(3): 422-433.

[12] 蒋一波, 王万良, 陈伟杰, 等. 视频传感器网络中无盲区监视优化[J]. 软件学报, 2012, 23(2): 310-322. JIANG Yi-bo, WANG Wan-liang, CHEN Wei-jie, et al. Coverage optimization of occlusion-free surveillance for video sensor networks[J]. Journal of Software, 2012, 23(2): 310-322.

编 辑 漆 蓉

作者简介：樊富有(1974 − )，男，博士生，副教授，主要从事量子计算和量子可逆逻辑电路综合方面的研究.

基金项目：国家自然科学基金(61272175)；四川省科技厅项目(2012JY009)；四川省教育厅重点项目(2011ZA173)

收稿日期：2015 − 06 − 06；修回日期：2015 − 11 − 08

中图分类号TP393；TN929

文献标志码A

doi:10.3969/j.issn.1001-0548.2016.01.021