下载文档原格式
基于QPSO 算法的软件测试数据自动生成李文瑞，张伟，任洪丽摘要：针对目前进化算法生成测试数据方法存在算法复杂、参数设置不易、易陷入局部最优解等缺陷，提出了一种应用于软件测试中的基于量子粒子群算法(QPSO)的测试数据自动生成算法。
该算法是在PSO 算法基础上引入量子理论的思想。
解决了PSO 算法搜索空间有限，容易陷入局部最优解的问题。
通过具体实验证明，该方法是有效可行的，其效率也明显高于GA 算法和PSO 算法。
关键字：软件测试；测试数据生成；粒子群算法；量子粒子群算法0 引言软件测试是软件开发过程中必须完成的重要活动之一，而测试数据的自动生成是软件测试的最关键的问题，可以有效的提高软件测试的效率。
软件测试数据自动生成通常包括功能测试数据自动生成和结构测试数据自动生成，目前通过进化算法生成测试数据方面的研究取得的很大的进展。
文献[1]将遗传算法（GA ）应用于面向对象软件的单元测试中，文献[2]提出“分支函数叠加法”来构造适应值函数。
文献[3]对遗传算法在软件测试用例生成的性能进行研究，并提出了两种提高遗传算法生成测试用例效率的方法。
文献[4]将把量子理论应用于PSO 算法中从而提出一种改进的粒子群优化算法。
文献[7]在传统的遗传算法中注入免疫算子，提出了基于免疫遗传算法生成软件测试数据的方法。
文献[8]提出一种基于PSO 算法的软件测试数据生成方法。
但是遗传算法及其改进算法都存在算法复杂、参数设置不易等问题，PSO 算法具有搜索空间有限、容易陷入局部最优解的缺陷。
本文提出一种基于QPSO 的软件测试数据生成方法，并通过实验验证，其效率明显优于遗传算法和粒子群算法，解决了PSO 算法容易陷入局部最优解的缺陷。
1 基本概念1.1 粒子群算法设X i = ( x i1 , x i2 ,…, x in ) 为粒子i 的当前位置；V i = ( v i1 ,v i2 ,…, v in ) 为粒子i 的当前飞行速度；P i = ( p i1 , p i2 , …, p in ) 为粒子i 所经历过的具有最好适应值的位置。
基于量子进化算法的时序电路测试生成
李智;范源远;许川佩
【期刊名称】《微计算机信息》
【年(卷),期】2007(0)35
【摘要】本文介绍将量子进化算法应用在时序电路测试生成的研究结果.结合时序电路的特点,本文将量子计算中的量子位和叠加态的概念引入传统的测试生成算法中,建立了时序电路的量子进化算法测试生成模型.在国际标准电路上的验证结果表明,与同类算法相比,该算法模型可获得较高的故障覆盖率和较小的测试矢量集.【总页数】3页(P290-291,310)
【作者】李智;范源远;许川佩
【作者单位】541004,桂林,桂林电子科技大学电子工程学院;541004,桂林,桂林电子科技大学电子工程学院;541004,桂林,桂林电子科技大学电子工程学院
【正文语种】中文
【中图分类】TP274;TN407
【相关文献】
1.基于FSM的时序电路测试生成探析 [J], 王红霞;叶晓慧;何光进
2.基于仿真的时序电路测试生成方法研究 [J], 郭希维;苏群星;谷宏强
3.基于蚁群算法的时序电路测试生成研究 [J], 汪小亮;姚旺生
4.基于混合蛙跳算法的时序电路测试生成 [J], 朱爱军;李智;许川佩
5.基于分解等价的时序电路测试生成算法 [J], 韩之刚; 赵莹; 赵航; 关连伟
因版权原因，仅展示原文概要，查看原文内容请购买。
![量子进化算法原理_智能控制简明教程_[共3页]](https://img.taocdn.com/s1/m/08db93cac281e53a5902ff67.png)
第6章 计算智能 163（5）随着迭代次数的增加，适应度函数变化即函数()10sin(5)7cos(4)f x x x x =++取得最大值的过程如图6.7所示。
图6.7 粒子群算法的适应度函数曲线变化通过上述粒子群优化计算，最终获得式6.35目标函数的最优解为7.8569x =，()24.8554f x =。
6.3 量子进化算法6.3.1 量子进化算法量子进化算法建立在量子态矢量表达基础上，将量子比特的概率矢量表示应用于染色体的编码，使得一条量子染色体可以表达多个态的叠加，并利用各种量子门实现染色体的更新操作，从而实现目标求解。
2000年，Kuk-Hyun Han 将量子态矢量表达引入染色体编码中，通过量子门旋转实现染色体更新，提出了遗传量子算法（Genetic Quantum Algorithm ，GQA ），并通过对背包问题的优化计算，取得了比常规遗传算法更好的效果。
针对GQA 的不足，Han 在2002年通过改进量子门旋转角度策略和引入移民策略，提出了量子进化算法（Quantum Evolutionary Algorithm ，QEA ）。
由于量子进化算法具有多样性特征，在参数优化计算的过程中可以获得更好的结果，目前已经应用到数值优化、组合优化、图形图像处理、电路设计、通信、多目标优化等领域。
6.3.2 量子进化算法原理量子进化算法采用量子位编码来表示染色体，通过量子门更新种群完成进化搜索。
与传统进化算法相比，它具有种群规模小、收敛速度较快、全局寻优能力强的特点。
下面介绍量子进化算法的原理。
1．QEA 算法基本操作（1）量子染色体编码在量子计算中，采用量子位表示最小的信息单元，一个量子位可以处于“1”态、“0”态。
LOGIC对扰动不敏感（2）Register寄存器为存放二进制数据的器件，通常由Latch 构成。
一般地，寄存器为边沿触发。
（3）flip-flops（触发器）任何由交叉耦合的门形成的双稳电路Register 时序参数D Q Clk T Clk D tsu Q tc-q thold注意：数据的上升和下降时间不同时，延时将不同。
2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 11 页Latch 时序参数Latch 的时序（ Timing ）参数还要考虑tD 2 D Q DQtD-qQClk tC 2Clk tC 2QQ寄存器（Register）2004－12－1锁存器（Latch）第 8 章 (1) 第 12 页清华大学微电子所 《数字大规模集成电路》 周润德Latch 时序参数D Q Clk正电平 Latch 时钟负边沿T Clk D tc-q PWm thold td-q tsuQ注意：数据的上升和下降时间不同时，延时将不同。
2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 13 页最高时钟频率φ FF’s LOGIC tp,comb最高时钟频率需要满足：tclk-Q + tplogic+ tsetup < = T但同时需要满足:其中tplogic = tp,comb (max) tcd:污染延时（contamination delay） = 最小延时（minimum delay）第 8 章 (1) 第 14 页tcdreg + tcdlogic > thold =2004－12－1其中清华大学微电子所 《数字大规模集成电路》 周润德研究不同时刻 （t1, t2）FF1φ (t1) LOGIC t p,combφ (t2)CLKt1tsu D tholdFF1 输入数据 应保持稳定t tsuF F2t2holdtFF2 输入数据 应保持稳定tclk-q QFF1 输出数据 经组合逻辑到达 t 已达稳定 寄存器输入端tclk-Qtp,comb (max）tsetup因此要求：tclk-Q + tp,comb (max) + tsetup < =T2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 15 页研究同一时刻 （t1）t1 时FF1φ (t1) LOGIC FF1 t p,combt1 时FF2输入数据（2）φ (t1)输入数据（1）tclk-q QFF1 输出数据 已达稳定经组合逻辑已 到达FF2 输入端破坏了本应保 持的数据（2）tt1tcdregtcdlogicholdsuD输入数据（2）应保持稳定至 t1F F2t因此要求 :2004－12－1= tcd: 污染延时（contamination delay） = 最小延时（minimum delay）清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 16 页tcdreg + tcdlogic > thold写入（触发）静态 Latch 的方法：以时钟作为隔离信号, 它区分了“透明” （transparent ）和“不透明” （opaque）状态CLKCLKQ CLKD CLKDD弱反相器CLKMUX 实现弱反相器实现（强制写入）（控制门可仅用NMOS实现）2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德第 8 章 (1) 第 17 页Latch 的具体实现基于Mux 的 Latch负（电平） latch (CLK= 0 时透明) 正（电平） latch (CLK= 1 时透明)1 D CLK 0Q D CLK0 1QQ = Clk ⋅ Q + Clk ⋅ In2004－12－1Q = Clk ⋅ Q + Clk ⋅ In第 8 章 (1) 第 18 页清华大学微电子所 《数字大规模集成电路》 周润德基于（传输门实现的） Mux 的 LatchCLKQ CLK DCLK（1）尺寸设计容易 （2）晶体管数目多（时钟负载因而功耗大）2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 19 页基于（传输管实现）Mux 的 LatchCLK QM QM CLK CLK（仅NMOS 实现）CLK仅NMOS 实现不重叠时钟 （Non-overlapping clocks）（1）仅NMOS 实现，电路简单，减少了时钟负载 （2）有电压阈值损失（影响噪声容限和性能，可能引起静态功耗）2004－12－1清华大学微电子所 《数字大规模集成电路》 周润德 第 8 章 (1) 第 20 页Q单元形式的Latch采用串联电压开关逻辑（CVSL）QNon-overlap时间过长，存储在动态节点上的电荷会泄漏掉（故称伪静态）低电压静态Latch双边沿触发寄存器RS Latch?动态Latch 和Register（1）比静态Latch和Register 简单（2）基于在寄生电容上存储电荷，由于漏电需要周期刷新（或经常更新数据）（3）不破坏的读信息：因此需要输入高阻抗的器件传输门构成的动态边沿触发寄存器（只需8 个晶体管，节省功耗和提高性能，甚至可只用NMOS 实现）动态节点正电平灵敏正沿触发＝＝正沿负沿t DC > Wt SUt SUt DC >t SU=t DQ=t DQ。
量子纠缠与量子电路的制备与操作步骤解析量子计算作为新一代计算技术的前沿领域，正在迅速发展，并显示出超越传统计算机的潜力。
其中，量子纠缠和量子电路是两个关键的概念。
量子纠缠是指在量子力学中，两个或多个量子系统之间存在一种特殊的关系，使它们的状态无法独立地描述。
而量子电路是用量子比特搭建的一种电路，用来处理和操作量子信息。
在本文中，我们将对量子纠缠和量子电路的制备与操作步骤进行详细解析。
一、量子纠缠的制备量子纠缠的制备过程通常可以通过以下步骤实现：1. 制备纠缠态：首先，需要选择两个或多个量子比特作为待纠缠的系统。
目前，常用的量子比特包括原子、离子和超导体。
然后，利用特定的量子门操作将这些量子比特纠缠在一起，使它们的状态相互依赖。
例如，可以使用CNOT门或Hadamard门等常见的量子门操作来制备纠缠态。
2. 纠缠质量的判断：纠缠质量是指纠缠态的纯度程度。
在实际制备纠缠态中，由于环境的噪声和干扰等因素，纠缠态往往会受到一定的退相干影响。
因此，需要采用一些方法来评估纠缠态的纯度程度。
例如，可以通过测量两个量子比特之间的关联度或密度矩阵的特征值等指标来判断纠缠质量。
3. 纠缠态的存储和传输：在制备好纠缠态后，需要将其存储或传输到其他的物理系统中。
这可以通过一些物理手段来实现，例如，可以将纠缠态传输到另一个量子比特或传输到远距离的量子通信线路中。
二、量子电路的制备量子电路的制备通常包括以下几个步骤：1. 选取量子比特：首先，需要选择用来搭建量子电路的量子比特。
常用的量子比特有超导量子比特、离子量子比特、原子量子比特等。
选择量子比特时，需要考虑其稳定性、易操作性和可控性等因素。
2. 量子比特的初始化：每一个量子计算任务的开始，都需要进行量子比特的初始化，即将量子比特的状态置为目标状态。
常用的初始化方法包括将量子比特置于基态或将之放置在超导系统的合适激发态。
3. 量子门操作：量子门操作是量子电路中的关键步骤，用于创造量子比特之间的纠缠和进行量子信息处理。
量子计算机-课件(精)contents •量子计算机基础知识•量子计算机硬件架构•量子算法•量子计算机编程语言•量子计算机应用场景•量子计算机发展现状与未来趋势目录01量子计算机基础知识1量子计算机的定义与特点23量子计算机是一种基于量子力学原理进行信息处理的计算机。
量子计算机具有高度并行性、量子态叠加和纠缠等特性。
量子计算机能够解决传统计算机无法处理的复杂问题。
03量子计算机通过量子门操作对量子比特进行操作，实现量子计算。
量子计算机的基本原理01量子比特（qubit）是量子计算机的基本单元，可以处于0和1的叠加态。
02量子比特之间的相互作用可以实现并行计算。
量子计算机在处理大规模信息时具有高度并行性和计算效率优势。
量子计算机在化学、材料科学、人工智能等领域具有广泛的应用前景。
量子计算机目前仍处于发展初期，尚未完全成熟和普及化。
量子计算机在加密和密码破解方面具有天然优势。
量子计算机与传统计算机的比较02量子计算机硬件架构1量子计算机的硬件组成23量子计算机的基本信息处理单元，相当于经典计算机中的二进制位。
量子比特（qubit）量子比特之间的相互作用和控制，相当于经典计算机中的逻辑门。
量子门（quantum g…量子比特之间的关联和纠缠状态，是量子计算机实现并行计算的关键。
量子纠缠（quantum …超导量子计算机概述超导量子计算机是利用超导材料和电路实现量子比特的量子计算机。
超导量子比特的实现利用约瑟夫森结、通量、相位等实现超导量子比特。
超导量子计算机的优点工艺成熟、可扩展性强、易于集成等。
离子阱量子计算机概述离子阱量子计算机是利用离子的能级和电荷相互作用实现量子比特的量子计算机。
离子阱量子比特的实现利用激光束、微波场、电场等实现对离子的控制和操作。
离子阱量子计算机的优点相干时间长、易于隔离、可拓展性强等。
010203概述光子量子计算机是利用光子实现量子比特的量子计算机。
光子量子比特的实现利用光子偏振、路径、角动量等自由度实现光子量子比特。
本项目为国家自然科学基金（编号：60266001）资助项目；广西自然科学基金项目（桂科字0542051）。
基于量子进化算法的时序电路测试生成李智 范源远 许川佩（桂林电子科技大学电子工程学院 桂林 541004）摘要:本文介绍将量子进化算法应用在时序电路测试生成的研究结果。
结合时序电路的特点，本文将量子计算中的量子位和叠加态的概念引入传统的测试生成算法中，建立了时序电路的量子进化算法测试生成模型。
在国际标准电路上的验证结果表明，与同类算法相比，该算法模型可获得较高的故障覆盖率和较小的测试矢量集。
关键词：量子进化算法 自动测试生成 时序电路中图分类号: TP274 ; TN407 文献标识码: ATest Pattern Generation Based on Quantum EvolutionaryAlgorithm for Sequential CircuitsLi Zhi Fan Yuanyuan Xu Chuanpei(School of Electronic Engineering, Guilin University of Electronic Technology, Guilin, 541004, China)ABSTRACT: This paper presented some results obtained by applying quantum evolutionaryalgorithm in sequential circuits test pattern generation （ATPG ）. In the paper, concepts like qubit and superposition of quantum computation were introduced to conventional evolution algorithm, to build a quantum-inspired evolution algorithm model for ATPG . Experiments on ISCAS benchmark shows, compared to other similar algorithm, the proposed algorithm can achieve higher fault coverage and more compact test sets.KEYWORDS: quantum-inspired evolution algorithm, ATPG , sequential circuit量子进化算法是一种结合了量子计算概念和思想的进化算法，它借鉴了量子计算中的复合位和叠加态等思想，采用了量子态的编码形式和交叉变异的方法，收敛速度显著提高，具有很好的搜索和数据挖掘能力。
Kuk－Hyun Han，Jong—Hwan Kim [1] 和杨淑媛，焦李成[2]在这方面做了深入的研究，为解决组合优化问题提供了有力的工具。
量子进化算法应用在许多领域中都取得了良好的效果，已有的应用领域包括电网优化，图像边缘检测等等。
根据文献[2]的研究，量子进化算法与其他同类算法相比，找到最优解所需的迭代次数大大减小，迭代所需的时间增加有限，求解性能的提高是显著的。
本文采用了基于模拟的测试生成算法，结合量子进化算法的优点，通过故障模拟器，只做前向处理，避免了回溯的复杂性，有利于实现快速高效的测试生成。
1 量子进化算法1.1 量子计算量子计算理论来源于量子力学理论的基本概念。
经典计算机的存储单元是比特,它只有两种状态,要么为0 ,要么为1；而量子计算最基本的存储单元是量子比特,它是一个二维Hilbert 空间的量子体系,这个空间有两个基,分别记为| 0〉和| 1〉。
与经典计算机中的比特不同的是,量子比特的状态可以为任意的归一化态:α| 0〉+β| 1〉，其中α和β为满足归一化条件221αβ+=的任意复数。
由此可以看出，一个量子比特所包含的信息要比经典比特多。
量子比特的状态由测量确定，一旦测量完成，系统就坍缩到所测量量子比特的一个基上，一个量子比特就变成了经典比特，所有其它信息都丢失了。
一个量子比特α| 0〉+β| 1〉坍缩到一个基| 0〉的概率为2α,坍缩到| 1〉的概率相应的为2β。
量子算法相对于经典算法而言,它最本质的特征就是充分利用了量子态的叠加性和相干性，以及量子比特之间的纠缠性,它是量子力学直接与算法理论结合的产物。
量子算法与经典算法最主要的区别就是它具有量子并行性。
1.2 量子进化算法把量子计算和进化计算结合起来的研究工作始于上世纪90年代后期，Ajit Narayanan 和Mark Moore [3]率先提出了量子驱动的进化算法，用来求解简单的9个城市的tsp 问题，平均的迭代次数明显少于传统的进化算法。
与经典进化算法的编码方法不同，量子进化算法采用量子位编码，使用一对复数定义一个量子比特位，⎜ψ〉＝α⎜0〉＋β⎜1〉；量子进化算法的一个个体的染色体就由多个这样的量子位组成（1）。
一个含有m 个量子比特位的染色体可以描述为:112112m m m m ααααββββ−−⎡⎤⎢⎥⎣⎦L （1） 其中221i i αβ+=（i ＝1，2，···m ）。
这条染色体经过量子测量就变成了一个经典的二进制串(“01…001”)。
一条或多条染色体和构成量子进化算法的一个个体，多个个体组成了一个量子群体Q(t)，把Q(t)的染色体经测量产生的二进制串作为经典群体P(t)。
在量子计算中，信息处理的过程是通过量子态的酉变换过程来实现的。
量子进化算法中的更新算子是算法的关键，它取代了经典进化算法中的交叉和变异过程，而采用量子旋转门作用于量子位，量子旋转门中的旋转角度由量子位的个体的观测值与当前最优解来确定。
量子旋转门是量子变换门的一种，通过量子旋转门来进化种群，可以在变异中加入最优个体的信息来引导进化，从而加快算法的收敛。
对于二值编码问题，我们可以设计下面这种量子变异算子来加快进化求解的速度。
令cos sin sin cos U θθθθ−⎡⎤=⎢⎥⎣⎦（2） U 表示量子旋转门,旋转变异的角度i θ的大小和方向可由文献[1]中表1得到。
量子进化算法(QEA)的具体步骤可简要描述为： ①量子进化算法初始化为第0代: t = 0； ②初始化种群Q(t) ；③由Q(t)通过量子测量生成P(t)；④评价群体P(t)的适应度,选出最优个体best并保存； ⑤用量子变异算子U (2)更新Q(t)，产生新的种群Q(t＋1)；⑥停机条件判断:当条件不满足时,转到③;否则输出当前最优个体,算法结束。
2 自动测试生成的量子进化算法模型2.1 算法描述自动测试生成的目的是寻找一组测试矢量，将其加到被测故障电路的主输入(PI)上时，能够使主输出(PO)不同于无故障时的电路输出。
这组测试矢量通常用二进制字符(“0”，“1”)组成的二进制字符串来表示。
本文所提到的故障指的是固定型故障。
在量子进化算法模型中把这些测试矢量定义为，群体Q(t)经量子测量产生的一组二进制串P(t)，t 表示群体Q 是第t 代。
根据时序电路的特点，前面时帧输入的矢量，会影响以后时帧的输出。
为了产生更好的矢量集，Q(t)的一个个体含有多条染色体，经过量子测量后可产生一组测试矢量，通过迭代，可选择较好的利用了这一特点的测试矢量组。
多个这样的个体形成一个种群Q，把这一种群作为测试矢量生成器，通过种群的演化，寻找其中最优的个体作为测试矢量集。
算法实现的过程描述如下：第一步，根据电路的特点确定种群Q 中染色体的长度（由PI 的长度确定），和种群Q 中的个体数NUM；并初始化第0代群体的染色体。
将一个有m 个主输入(PI) 的被测电路对应的染色体初始化为状态（1），其中取第0代群体的任意的染色体概率幅αβ==，以使第0代群体产生的测试矢量每一位取“0”和取“1”的概率相等，确保初始化矢量的随机性。
第二步，测量每个个体的染色体，把得到的测试矢量集施加到故障模拟器中进行故障诊断。
由Q(t)生成P(t)的具体方法是: 产生一个随机数a ∈[0 ,1 ]，若它大于概率幅α的平方，取值1，否则，取值0。
记录每个个体的故障诊断的结果，通过这些结果评价每个个体的适应度，找出群体中的适应度最优的测试向量组best，由best 和每个个体产生的测试向量根据文献[1]中表1来确定量子变异算子参数i θ。
第三步，对整个群体的染色体应用量子变异算子U (2)，，使群体中每个个体的染色体向best 靠近i θ∆，从而产生下一代群体Q(t+1)。
第四步，进行停机条件判断。
如果个体的适应度已经连续Ter 次未增加，或者超过了最大的迭代次数MAX，或故障列表中的所有故障已经检测完毕，则终止迭代；否则，返回第二步继续迭代。
2.2 参数的选取基于量子进化算法的测试生成，主要包含以下几个参数： 1.每个个体的染色体的条数L，这与待测电路的结构相关；2.种群的个体数NUM，最大迭代次数MAX，和旋转角度i θ是此算法的主要运行参数。
3.停机条件Ter，与待测电路的复杂程度有关。
电路中易测故障对测试向量比较敏感，而难测故障需要较长的矢量进行激活和传播。
因此，在测试生成的过程中L 设为可变化的，测试向量组中的矢量个数L 的最小值设为1，最大值设为PI 到PO 之间触发器的最大数目。
经过多次试验，当L 个染色体不能检测到故障时，就将染色体的个数L 增加一个，这样设置既减少了测试矢量，又有利于测到更多的故障。
群体的个体数NUM 与被测电路的PI 的长度有关，输入门数越多，测试的群体大小也相应增加，NUM 还与被测电路的复杂程度有关。
群体大小NUM＝PI 门数＋触发器的数目/20，对输入少而门数多的复杂电路，群体大小还随着向量组的大小L 的增加而增加，NUM＝PI 门数＋触发器的数目/20＋L×2。
足够数量的迭代次数保证了算法不会漏掉最优解，但迭代次数太多，也会造成CPU 时间的浪费。
迭代次数与电路的复杂程度有关，本文将最大迭代次数MAX 设为待测电路门数的三分之一，但最小的迭代次数不会少于50次。
设置停机条件Ter 的目的，是在适应度连续多次停止增加的情况下，停止迭代以避免CPU 时间的浪费，本文把Ter 设为12次。
在量子进化算法的迭代过程中，i θ∆的选取起了很大的作用，i θ∆越大染色体变化的也就越快，但同时也会使迭代对某一结果的趋向变得不稳定。
较大的i θ∆在迭代初期可使群体更快的趋向最优解，但在迭代的后期就可能使群体跳过最优解，而i θ∆过小也会使群体易于陷入局部最优解。
