Forecasting and Evaluating the Efficiency of Test Generation Algorithms by Genetic Algorithm

To generate a test set for a given circuit (including both combinational and sequential circuits), choice of an algorithm within a number of existing test generation algorithms to apply is bound to vary from circuit to circuit. In this paper, the genetic algorithms are used to construct the models of existing test generation algorithms in making such choice more easily. Therefore, we may forecast the testability parameters of a circuit before using the real test generation algorithm. The results also can be used to evaluate the efficiency of the existing test generation algorithms. Experimental results are given to convince the readers of the truth and the usefulness of this approach.

Target-Fault-Oriented Test Generation of Sequential CircuitsUsing Genetic Algorithm

This paper deals with the target-fault-oriented test generation of sequential circuits using genetic algorithms. We adopted the concept of multiple phases and proposed four sub-procedures which consist of activation, propagation and justification phases. The paper focuses on the design of genetic operators and construction of fitness functions which are based on the structure information of circuits. Using ISCAS89 benchmarks, the experiment results of GA were given.

MC/DC Test Data Generation Algorithm Based on Whale Genetic Algorithm

The automatic generation of test data is a key step in realizing automated testing.Most automated testing tools for unit testing only provide test case execution drivers and cannot generate test data that meets coverage requirements.This paper presents an improved Whale Genetic Algorithm for generating test data re-quired for unit testing MC/DC coverage.The proposed algorithm introduces an elite retention strategy to avoid the genetic algorithm from falling into iterative degradation.At the same time,the mutation threshold of the whale algorithm is introduced to balance the global exploration and local search capabilities of the genetic al-gorithm.The threshold is dynamically adjusted according to the diversity and evolution stage of current popu-lation,which positively guides the evolution of the population.Finally,an improved crossover strategy is pro-posed to accelerate the convergence of the algorithm.The improved whale genetic algorithm is compared with genetic algorithm,whale algorithm and particle swarm algorithm on two benchmark programs.The results show that the proposed algorithm is faster for test data generation than comparison methods and can provide better coverage with fewer evaluations,and has great advantages in generating test data.

Generating of Test Data by Harmony Search Against Genetic Algorithms

Many search-based algorithms have been successfully applied in sev-eral software engineering activities.Genetic algorithms(GAs)are the most used in the scientific domains by scholars to solve software testing problems.They imi-tate the theory of natural selection and evolution.The harmony search algorithm(HSA)is one of the most recent search algorithms in the last years.It imitates the behavior of a musician tofind the best harmony.Scholars have estimated the simi-larities and the differences between genetic algorithms and the harmony search algorithm in diverse research domains.The test data generation process represents a critical task in software validation.Unfortunately,there is no work comparing the performance of genetic algorithms and the harmony search algorithm in the test data generation process.This paper studies the similarities and the differences between genetic algorithms and the harmony search algorithm based on the ability and speed offinding the required test data.The current research performs an empirical comparison of the HSA and the GAs,and then the significance of the results is estimated using the t-Test.The study investigates the efficiency of the harmony search algorithm and the genetic algorithms according to(1)the time performance,(2)the significance of the generated test data,and(3)the adequacy of the generated test data to satisfy a given testing criterion.The results showed that the harmony search algorithm is significantly faster than the genetic algo-rithms because the t-Test showed that the p-value of the time values is 0.026<α(αis the significance level=0.05 at 95%confidence level).In contrast,there is no significant difference between the two algorithms in generating the adequate test data because the t-Test showed that the p-value of thefitness values is 0.25>α.

Test Case Generation from UML-Diagrams Using Genetic Algorithm

Software testing has been attracting a lot of attention for effective software development.In model driven approach,Unified Modelling Language(UML)is a conceptual modelling approach for obligations and other features of the system in a model-driven methodology.Specialized tools interpret these models into other software artifacts such as code,test data and documentation.The generation of test cases permits the appropriate test data to be determined that have the aptitude to ascertain the requirements.This paper focuses on optimizing the test data obtained from UML activity and state chart diagrams by using Basic Genetic Algorithm(BGA).For generating the test cases,both diagrams were converted into their corresponding intermediate graphical forms namely,Activity Diagram Graph(ADG)and State Chart Diagram Graph(SCDG).Then both graphs will be combined to form a single graph called,Activity State Chart Diagram Graph(ASCDG).Both graphs were then joined to create a single graph known as the Activity State Chart Diagram Graph(ASCDG).Next,the ASCDG will be optimized using BGA to generate the test data.A case study involving a withdrawal from the automated teller machine(ATM)of a bank was employed to demonstrate the approach.The approach successfully identified defects in various ATM functions such as messaging and operation.

Minimal-Length Interoperability Test Sequences Generation via Genetic Algorithm

A novel interoperability test sequences optimization scheme is proposed in which the genetic algorithm （GA） is used to obtain the minimal-length interoperability test sequences. During our work, the basic interoperability test sequences are generated based on the minimal-complete-coverage criterion, which removes the redundancy from conformance test sequences. Then interoperability sequences minimization problem can be considered as an instance of the set covering problem, and the GA is applied to remove redundancy in interoperability transitions. The results show that compared to conventional algorithm, the proposed algorithm is more practical to avoid the state space explosion problem, for it can reduce the length of the test sequences and maintain the same transition coverage.

Optimal Test Points Selection Based on Multi-Objective Genetic Algorithm

A new approach to select anoptimal set of test points is proposed. The described method uses fault-wise table and multi-objective genetic algorithm to find the optimal set of test points. First, the fault-wise table is constructed whose entries are measurements associated with faults and test points. The selection of optimal test points is transformed to the selection of the columns that isolate the rows of the table. Then, four objectives are described according to practical test requirements. The multi-objective genetic algorithm is explained. Finally, the presented approach is illustrated by a practical example. The results indicate that the proposed method can efficiently and accurately find the optimal set of test points and is practical for large scale systems.

A Parallel Genetic Algorithm Based on Spark for Pairwise Test Suite Generation

Pairwise testing is an effective test generation technique that requires all pairs of parameter values to be by at least one test case. It has been proven that generating minimum test suite is an NP-complete problem covered Genetic algorithms have been used for pairwise test suite generation by researchers. However, it is always a time-consuming process, which leads to significant limitations and obstacles for practical use of genetic algorithms towards large-scale test problems. Parallelism will be an effective way to not only enhance the computation performance but also improve the quality of the solutions. In this paper, we use Spark, a fast and general parallel computing platform, to parallelize the genetic algorithm to tackle the problem. We propose a two-phase parallelization algorithm including fitness evaluation parallelization and genetic operation parallelization. Experimental results show that our algorithm outperforms the sequential genetic algorithm and competes with other approaches in both test suite size and computational performance. As a result, our algorithm is a promising improvement of the genetic algorithm for pairwise test suite generation.

Forecasting the Efficiency of Test Generation Algorithms for Combinational Circuits

In this era of VLSI circuits, testability is truly a very crucial issue.To generate a test set for a given circuit, choice of an algorithm from a number ofexisting test generation algorithms to apply is bound to vary from circuit to circuit.In this paper, the Genetic Algorithm is used in order to construct an accurate modelfor some existing test generation algorithms that are being used everywhere in theworld. Some objective quantitative measures are used as an effective tool in makingsuch choice. Such measures are so important to the analysis of algorithms that theybecome one of the subjects of this work.

System level test selection based on combinatorial dependency matrix

Test selection is to select the test set with the least total cost or the least total number from the alternative test set on the premise of meeting the required testability indicators.The existing models and methods are not suitable for system level test selection.The first problem is the lack of detailed data of the units’fault set and the test set,which makes it impossible to establish a traditional dependency matrix for the system level.The second problem is that the system level fault detection rate and the fault isolation rate(referred to as"two rates")are not enough to describe the fault diagnostic ability of the system level tests.An innovative dependency matrix(called combinatorial dependency matrix)composed of three submatrices is presented.The first problem is solved by simplifying the submatrix between the units’fault and the test,and the second problem is solved by establishing the system level fault detection rate,the fault isolation rate and the integrated fault detection rate(referred to as"three rates")based on the new matrix.The mathematical model of the system level test selection problem is constructed,and the binary genetic algorithm is applied to solve the problem,which achieves the goal of system level test selection.

基于遗传算法的故障样本优化选取方法

为降低测试性验证试验费用,提出基于遗传算法的故障样本优化选取方法。方法通过故障—测试关联分析和故障—故障等价分析,确定初始故障样本集中各元素对应的等价集,并对初始故障样本集进行扩展,在此基础上,建立了故障样本选取优化求解模型。在不降低样本注入数量和测试特性的条件下,以试验费用最小为优化目标,给出了基于改进遗传算法的样本优化选取方法。算例应用结果表明,该方法设计的故障样本选取方法能有效降低测试性验证试验费用。

基于自适应免疫遗传算法的测试优化选择方法研究

针对某型挖掘机制动系统,通过对该系统结构以及故障模式影响分析的基础上,进行了系统测试点布置,并建立了故障测试关系矩阵,利用自适应免疫遗传算法对该系统测试选择优化问题进行求解,得到一组最优测试集,实例应用表明,该方法对求解测试点优化选择问题的有效性。

基于目标语句占优关系的软件可测试性转化

标记变量问题是基于搜索的软件测试数据生成的关键问题之一.本文提出一种基于目标语句占优关系的软件可测试性转化理论与方法,思想是:对于涉及标记变量问题的目标语句,如果存在另一目标语句(集),使得该目标语句(集)占优原有目标语句,则用新的目标语句(集)代替原有目标语句生成测试数据,从而消除标记变量的不利影响.将本文方法应用于典型被测程序,实验结果表明,该方法可以有效解决标记变量问题,从而提高测试数据的生成效率.

基于小生境遗传算法的SoC测试存取机制优化

提出了基于小生境遗传算法的系统级芯片(SoC)测试存取机制(TAM)的优化方法.结合TAM宽度约束进行SoC中功能内核(IP)的测试壳的优化,解决测试存取机制的测试总线划分及测试总线细分等的优化问题,取得了较好的结果,并有效地减少SoC的测试时间.采用分支-联合(Fork-Joint)的方法可得到更为优化的TAM方法,对于ITC 2002基准SoC d695,比未采用分支-联合方法的TAM划分方法的测试性能最大可以提高30%,和其它方法的优化结果相比,该方法的平均效果优于其它方法1到9个百分点.

基于模拟退火离散粒子群算法的测试点优化

针对复杂系统的测试点优化问题,提出一种基于模拟退火离散粒子群(SA-BPSO)算法的测试点优化算法。该算法利用模拟退火算法的概率突跳能力,克服了基本粒子群算法易陷入局部最优解的缺陷。阐述了该算法在系统测试点优化应用中的流程及关键步骤,并且理论分析了该算法的复杂度。仿真结果表明,该算法在计算时间和测试费用方面都优于遗传算法,能够应用于复杂系统的测试点优化。

碳交易市场期货间价格波动关系与趋势预测

碳排放交易市场中不同期货价格波动及其相互影响较为复杂,价格趋势预测也在金融投资领域占有重要地位。针对碳交易市场中非线性预测问题,选取欧盟配额期货与碳排放核证减排量期货相关参数作为研究对象,运用协整关系检验确定其是否具有长期协整关系,采用Granger因果检验确定其领先滞后关系,将具有领先关系的期货参数作为部分输入变量,建立遗传算法改进的运用不同小波函数的神经网络模型,对具有滞后关系的期货价格趋势进行预测,并与改进前的BP小波神经网络模型预测结果进行对比。实验结果表明,碳排放交易市场中期货价格之间存在长期均衡协整关系,改进的模型可以有效刻画期货价格序列变化趋势,为碳排放交易提供良好的投资建议。

测试算法评估及可测性预报系统

测试算法评估及可测性预报系统使用回归分析和遗传算法 ,为测试生成算法建立可测性参数的预报模型 ,使得对于给定电路 ,不必实际运行各测试生成算法 ,就可以快速评估并预报出最适合的算法。本文整体介绍了这一系统 。

A novel strategy for automatic test data generation using soft computing technique

Software testing is one of the most crucial and analytical aspect to assure that developed software meets pre- scribed quality standards. Software development process in- vests at least 50% of the total cost in software testing process. Optimum and efficacious test data design of software is an important and challenging activity due to the nonlinear struc- ture of software. Moreover, test case type and scope deter- mines the quality of test data. To address this issue, software testing tools should employ intelligence based soft comput- ing techniques like particle swarm optimization （PSO） and genetic algorithm （GA） to generate smart and efficient test data automatically. This paper presents a hybrid PSO and GA based heuristic for automatic generation of test suites. In this paper, we described the design and implementation of the proposed strategy and evaluated our model by performing ex- periments with ten container classes from the Java standard library. We analyzed our algorithm statistically with test ad- equacy criterion as branch coverage. The performance ade- quacy criterion is taken as percentage coverage per unit time and percentage of faults detected by the generated test data. We have compared our work with the heuristic based upon GA, PSO, existing hybrid strategies based on GA and PSO and memetic algorithm. The results showed that the test case generation is efficient in our work.

基于多信号流图模型的导弹系统级测试性设计研究

针对导弹长时间贮存,一次性使用特点,开展测试性设计工作难度较大的问题,提出采用多信号流图模型对导弹系统进行测试性设计研究。根据故障模式、影响及危害性分析(FMECA)信息确定系统的故障模式,采用多信号流图模型建立导弹系统级测试性模型,根据可达性算法得到故障-测试相关性矩阵,确定系统的测试性指标。考虑到现有算法如遗传算法、二进制粒子群算法等诸多算法的缺点,提出采用混合离散二进制粒子群-遗传算法对测试进行优化选取,将22个备选测试减少至14个,大大减少测试个数。最后通过实例验证,所提算法可以满足系统测试性指标精度要求,并有效降低测试个数,减少测试费用。

使用遗传算法对时序电路进行可测性预报

随着LSI/VLSI技术的发展,许多新的测试生成算法被开发出来 对于一个给定电路,快速而准确地选择最适合它的测试生成算法是一个具有很强现实意义的问题.本文提出了使用遗传算法(GA)找出逻辑电路的特性参数与测试生成算法可测性参数之间的关系,从而建立测试生成算法可测性参数(故障覆盖率,测试码个数)的模型,并对给定电路进行参数预报的方法。作者开发了遗传算法预报系统(GAFS),并使用该系统为常用的测试生成算法建立了直观的可测性参数表达式模型.用户可通过计算直接求得各测试生成算法对电路的可测性参数,然后通过比较选出最佳的算法.预报结果显示该系统具有较强的有效性和实用性.