基于动态集合进化算法的弱变异测试用例集生成

为解决基于集合进化算法（SEA）的弱变异测试用例集生成过程中个体规模固定和执行开销大的问题,提出一种基于动态集合进化算法（DSEA）的弱变异测试用例集生成方法。以测试用例集为个体,生成覆盖所有变异分支的弱变异测试用例集。在进化过程中,集合精简算子根据最优个体的最小子集及其未覆盖变异分支数量计算所需测试用例集的最小规模,并基于该最小规模调整种群中所有个体的规模,以生成最小规模的弱变异测试用例集,同时设计了适用于评估以测试用例集为个体的适应度函数。实验结果表明,动态集合进化算法指导弱变异测试用例集生成,获得的测试用例集规模比个体初始规模平均约简了50.15%,执行时间比集合进化的弱变异测试用例集生成最多降低了74.58%。因此,动态集合进化算法为最小规模的弱变异测试用例集生成和提升算法速度提供了一种解决方案。     

一种求解集合覆盖问题的启发式算法

集合覆盖问题是运筹学研究中的一个基本的组合优化问题,它通常描述成如下的一个覆盖问题:从一个m行、n列的0-1矩阵(aij)m×n中选出若干列盖住所有的行,使得付出的代价最小.集合覆盖问题被广泛应用到航空人员行程安排、电路设计、运输的车辆路线安排等领域.对这一问题,国内外学者提出了诸如遗传算法、模拟退火算法、蚁群算法、人工神经网络算法等求解算法.本文以贪心算法为基础,利用人类的智慧和经验,提出了一种求解集合覆盖问题的启发式算法.算法的主要思想为:从某个解出发,随机移除一定比例的列,再用贪心策略加入若干列.用本文提出的算法,对Beasley提出的45个测试实例进行了实算测试,所得结果和最优解的平均相对差值为0.44%,并且得到了其中33个实例的最优解,实算结果表明,本文提出的算法对求解集合覆盖问题是行之有效的.     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

覆盖表生成的可配置贪心算法优化

覆盖表生成是组合测试研究的关键问题之一,其中,贪心算法因为速度快、生成的覆盖表规模小而得到人们的青睐.人们提出了很多基于不同策略的贪心算法,其中,多数算法可以归结到一个统一的算法框架,即形成一个可配置贪心算法,从该框架又可以衍生出很多新的算法.如何科学地配置优化受多个因素影响的算法框架、有效生成覆盖表是一个新的挑战.针对具有6个决策点的贪心算法框架,设计了3条不同的实验路线,系统地探索各个决策点以及它们之间相互作用对生成覆盖表规模的不同影响,寻找最佳配置,从而可以有效地生成规模更小的覆盖表,为覆盖表生成的贪心算法的设计和优化提供理论和实践基础.     

集合覆盖问题的数据约简研究*

针对当前解决大规模集合覆盖问题的算法普遍存在着效率不高的问题,提出了一套削减数据规模的约简方法,并给出了一个能够与其他所有解决集合覆盖问题算法相结合的约简算法。用Beasley提出的45个测试用例进行试验,结果显示贪心算法和遗传算法在结合了约简算法后能够在更少的时间内得到更优的解,表明该约简方法和约简算法可以有效提高传统算法和智能算法解决大规模集合覆盖问题的效率。     

基于面上DNA计算求解最小集合覆盖问题*

利用DNA分子结构推得DNA计算机理及实现方式,提出用面上DNA计算模型求解最小集合覆盖问题,给出了具体应用和算法评价;在计算模板表面穷举了所有可能的结果,同一时间验证结果是否满足条件,实现DNA计算的强大并行性;同时在互补的寡聚核苷酸片段发生退火反应时,通过催化剂来决定是否杂交,减少人工参与、提高计算效率。最后,通过计算机仿真模拟验证了本模型的可行性。     

基于微指令覆盖的最小指令集测试算法

着重讨论了如何利用微处理器中的自测试设计来缩短功能测试序列的长度,首先,依据指令的表示模型,将指令测试分成微指令序列和微指令执行两个测试层次,提出了一个基于微指令覆盖的最小指令集测试算法,只需检测指令集的子集就能达到指令测试的目的。然后,通过定义指令的测试代价和测试效率,提出了一个可以有效地选择最小测试指令集的方法,最后,将算法应用于ＮＲＳ４０００微处理器的功能测试,仅为传统的全指令集测试序列的３     

无线传感器网络中基于虚拟力的覆盖算法

在无线传感器网络的很多应用场景中,大量的传感器节点被任意播撒在被监测区域内,形成很多覆盖空洞,对无线传感网络的感知、监测和数据采集能力造成很大影响。为了解决无线传感器网络中的覆盖问题,提出了一种基于虚拟引力的覆盖算法。首先,根据虚拟引力产生的约束条件和引力大小,一种扩大网络覆盖范围的算法被提出,算法分析证明这种算法能够减少覆盖空洞;第二,提出了维持邻居节点连通性的方法;第三,提出一种覆盖感兴趣区域的算法。仿真结果表明,这种算法既能提高网络的覆盖能力,又能减少传感器节点的移动距离。     

集合多覆盖问题的乘性权重更新分析

集合多覆盖问题的简单贪心算法的近似比是lnn＋1。本文提出简单贪心算法的一个变形,宽度优先贪心算法,并且证明其有近似比（lnn）／r＋lnlnn＋O（1）,其中r是覆盖要求。这个结果比由随机取整方法得到的近似比O（（lnn）/r＋√（lnn）＋1为优。宽度优先贪心算法的设计可以归入Arora等最近提出的乘性权重更新方法的框架。关键词集合多覆盖,宽度优先贪心算法,乘性权重更新方法     

Ad Hoc网络区域最小覆盖方法研究

覆盖控制作为无线传感器网络中的一个基本问题,反映了网络所能提供的“感知”服务质量,可以使无线传感器网络的空间资源得到优化分配,进而更好地完成环境感知、信息获取和有效传输的任务.如何计算同时满足“覆盖要求”（工作节点必须能够完全覆盖目标区域）和“连通性要求”（工作节点组成的通信网络必须是连通的）的最小节点集合,是一个NP难问题.本文设计了一种基于目标区域Voronoi划分的改进集中式近似算法,用于计算完全覆盖目标区域所需要的近似最小节点集.     

Tight Results on Minimum Entropy Set Cover

In the minimum entropy set cover problem, one is given a collection of k sets which collectively cover an n-element ground set. A feasible solution of the problem is a partition of the ground set into parts such that each part is included in some of the k given sets. Such a partition defines a probability distribution, obtained by dividing each part size by n. The goal is to find a feasible solution minimizing the (binary) entropy of the corresponding distribution. Halperin and Karp have recently proved that the greedy algorithm always returns a solution whose cost is at most the optimum plus a constant. We improve their result by showing that the greedy algorithm approximates the minimum entropy set cover problem within an additive error of 1 nat =log ₂ e bits ≃1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem. G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).     

关于最小测试集的线性规划松弛近似

目前最小测试集的最佳近似比是贪心算法的2 ln n＋o（1）.这个近似比能否改进是一个公开的问题.本文讨论了最小测试集的基于线性规划松弛的近似比证明方法的能力问题.我们证明最小测试集的整性间隙至少为0.72 ln n,而且最小测试集整性间隙的系数可以与最小集合覆盖的整性间隙的系数一样大.另外,我们说明加权最小测试集的贪心算法的近似比不能通过对偶拟合方法改进超过一个常数.     

基于堆的最小连通支配集高效近似算法

提出一种解决连通网络图上连通支配集(CDS)问题的贪心近似算法。利用堆结构逐步选出支配节点,将支配节点加入由之前已确定节点组成的树中,完成网络图中支配树的构造。通过计算堆操作次数,分析算法在平均情况下的时间复杂度。在随机网络模型上的模拟实验结果表明,与已有算法相比,该算法可以得到点数更少的连通支配集。     

基于最小支配集组簇的MF路由协议

为了进一步提高容延迟移动传感器网络中的数据投递率、降低平均延迟和能量消耗,提出一种改进的Message Ferry(MF)路由协议MF-MDS。该协议采用最小支配集对网络中的普通节点进行组簇。在NS-2上进行的仿真实验证明MF-MDS在投递率和平均延迟上明显优于传统的MF协议。     

基于分享度的最小连通支配集求解算法

以节点分享度作为选择分配点的优先级,提出一种最小连通支配集(CDS)求解算法.从根节点开始,将具有局部最大分享度的节点作为支配点,选择连接点与已确定的支配点连通,逐步构造网络的支配树,分析支配树的直径,计算支配树的平均跳数距离(AHD),从而评价网络的通信成本.实验结果表明,与CDS-BD-C2算法相比,该算法得到的CDS规模较小,且支配树的AHD平均减少12％.     

基于GSO算法的最小连通支配集问题求解

经典的最小连通支配集(MCDS)计算是NP难问题。为此,提出一种利用萤火虫优化算法求解该难题的新方法。把网络中的每个节点当作一个萤火虫个体,以节点度为基础构成荧光素,通过概率选择和荧光素调节机制,使个体被吸引向邻接的高亮度个体,从而由所选出的个体组成网络的支配集。经连接和修剪处理后,得到MCDS的近似解。在无线传感器网络模型的单位圆盘图上进行模拟实验,结果表明,该算法得到的连通支配集规模较小,更接近集中式算法的结果。     

基于高阶最小生成树脑网络的多特征融合分类方法

现有的基于脑疾病的分类方法的研究使用的都是传统的低阶功能连接网络。低阶功能连接网络可能会忽略复杂的大脑区域之间动态的相互作用的模式。高阶功能连接网络能够反映网络中包含的丰富的动态时间信息,但原有的高阶功能连接网络使用聚类的方法降低了数据维度,使得构建的网络无法进行有效的神经学解释;其次,高阶功能连接网络由于规模较大,在利用复杂网络或图理论计算一些拓扑指标时消耗较大。基于此,提出了一种高阶最小生成树网络的构建方法,然后计算了传统的可量化网络指标(度和离心率)并结合频繁子图挖掘技术来挖掘具有判别能力的子网络,最后采用多核支持向量机进行分类。实验结果表明所提方法的分类精确度高达97.54%,获得了很好的分类性能。     

基于混沌遗传算法的测试用例自动生成研究

测试用例自动生成是提高软件测试效率的重要手段.针对传统遗传算法的测试用例自动生成方法存在早熟收敛、迭代后期种群多样性降低等问题,提出了一种基于混沌遗传算法的测试用例自动生成模型,运用反向学习策略初始化种群,结合层接近度改进个体适应度的评价方法,并利用混沌序列优化遗传算法的交叉、变异操作.实验结果表明,与已有测试用例自动...     

基于ATML的可移植TPS开发技术研究

针对当前自动测试系统存在的互操作性差、TPS可移植性难问题,研究了基于ATML标准的可移植TPS开发技术.设计了兼容ATML标准的可移植TPS开发方法,分析了ATML模型结构,形成了AT-ML模型与现有TPS软件平台之间的对接表,并开发了ATML兼容工具,从而实现了基于ATML的可移植TPS开发技术,解决了TPS移植问题,为实现具有通用性、开放性、互操作性的ATS软件及武器装备全寿命周期测试信息共享奠定了基础.     

求解最小连通r-跳k-支配集的启发式算法

针对最小连通r-跳k-支配集的求解问题,提出一种基于节点度贪心策略的启发式算法。把网络节点集合作为初始解,从中选出度数最小的节点,通过判断节点的连通性决定是否将该节点从当前可行解中删除,由此逐步缩小连通支配集的规模,直至处理完所有节点。在单位圆盘图上进行算法复杂性分析和模拟实验,结果表明,相比同类算法,该算法得到的连通r-跳k-支配点集更少,且性能稳定。