Efficiency of mutation operators and selective mutation strategies: an empirical study

This paper investigates the mutation scores achieved by individual operators of the Mothra mutation system and their associated costs in order to determine the most efficient operators. The cost of mutation analysis includes both test set generation and equivalent mutant detection. The score and cost information is then used as a heuristic for choosing a subset of the operators for use in efficient selective mutation testing. Experiments were performed using a sample of 11 programs and a number of test sets for each program. The results show that the use of efficient operators can provide significant efficiency gains for selective mutation if the acceptable mutation score is not very close to one. When mutation scores very close to one are required, a randomly selected proportion of the mutants provides a more efficient strategy than a subset of efficient operators. Copyright © 1999 John Wiley & Sons, Ltd.     

Multi-objective framework for cost-effective OTN switch placement using NSGA-II with embedded domain knowledge

The continuous growth of traffic coming from a plethora of bandwidth-hungry applications will drive network operators to further pursue strategies to cost-efficiently plan and dimension their transport networks. In view of this trend, this paper presents an evolutionary multi-objective design framework for routing a set of services in an optical transport network such that the key resources impacting capital expenditures (CapEx) – line interfaces and optical transport network (OTN) switches – are minimized. Particularly, the multi-objective problem is customized to select the most cost-effective network nodes to place OTN switches, while at the same time keeping the number of line interfaces required to a minimum. To solve the multi-objective design problem, different strategies were considered to produce the Pareto front of non-dominated solutions, using the Non-dominated Sorting Genetic Algorithm (NSGA-II). These strategies differ on how mutation and crossover solutions are generated: randomly or exploiting prior knowledge. The solution quality obtained with both strategies after a fixed number of generations is compared. The results indicate that embedding expert knowledge within the genetic algorithm leads to better convergence results. Moreover, the knowledge-based implementation of the genetic algorithm presents on average a 59% increase in the hyper volume rate when compared to the purely random evolutionary algorithm for the same number of generations.     

基于策略自适应的多目标差分进化算法及其应用

为提高多目标差分进化算法求解多目标优化问题的能力,提出一种基于策略自适应的多目标差分进化算法（multi-objective differential evolution algorithm based on self-adaptive strategy,MODE-SS）。该算法采用超体积（hyper-volume,HV）对变异策略进行性能评价,并实现变异策略的自动选择;使用动态调整的二项式交叉策略和模拟二进制交叉（simulated binary crossover,SBX）策略实现全局搜索与局部搜索的平衡。通过与其他六种多目标进化算法在10个测试函数上的性能比较,结果表明MODE-SS算法的整体性能要好于其他所比较算法。最后,将MODE-SS算法用于求解海铁联运能耗优化问题,所得结果能够为决策者提供多种可行方案。     

一种基于多策略差分进化的分解多目标进化算法

为了提高多目标优化问题非支配解集合的分布性和收敛性,根据不同差分进化策略的特点,基于切比雪夫分解机制,提出一种基于多策略差分进化的分解多目标进化算法(MOEA/D-WMSDE).该算法首先采用切比雪夫分解机制,将多目标优化问题转化为一系列单目标优化子问题;然后引入小波基函数和正态分布实现差分进化算法的参数控制,探究一种...     

A parallel multi-objective algorithm for two-dimensional bin packing with rotations and load balancing

Bin packing problems are NP-hard combinatorial optimization problems of fundamental importance in several fields, including computer science, engineering, economics, management, manufacturing, transportation, and logistics. In particular, the non-guillotine version of the single-objective two-dimensional bin packing problem with rotations is a highly complex scheduling problem that consists in packing a set of items into the minimum number of bins, where items can be rotated 90° and are characterized by having different heights and widths. Recently, some authors have proposed multi-objective formulations that also consider additional objectives, such as the balancing the bin load in order to increase its stability. The load imbalance minimization, which depends on the distribution of the items packed in them, is a critical point in many real applications. This paper analyzes how to solve two-dimensional bin packing problems with rotations and load balancing using parallel and multi-objective memetic algorithms that apply a set of search operators specifically designed to solve this problem. Results obtained using a set of test problems show the good performance of parallel and multi-objective memetic algorithms in comparison with other methods found in the literature.     

Mutating database queries

A set of mutation operators for SQL queries that retrieve information from a database is developed and tested against a set of queries drawn from the NIST SQL Conformance Test Suite. The mutation operators cover a wide spectrum of SQL features, including the handling of null values. Additional experiments are performed to explore whether the cost of executing mutants can be reduced using selective mutation or the test suite size can be reduced by using an appropriate ordering of the mutants. The SQL mutation approach can be helpful in assessing the adequacy of database test cases and their development, and as a tool for systematically injecting faults in order to compare different database testing techniques.     

Design of an adaptive mutation operator in an electrical load management case study

An adequately designed and parameterized set of operators is crucial for an efficient behaviour of Genetic Algorithms (GAs). Several strategies have been adopted in order to better adapt parameters to the problem under resolution and to increase the algorithm's performance. One of these approaches consists in using operators presenting a dynamic behaviour, that is displaying a different qualitative behaviour in different stages of the evolutionary process. In this work a comparative analysis of the effects of using an adaptive mutation operator is presented in the operational framework of a multi-objective GA for the design and selection of electrical load management strategies. It is shown that the use of a time/space varying mutation operator depending on the values achieved for each objective function increases the performance of the algorithm.     

Using Mutation Analysis for Assessing and Comparing Testing Coverage Criteria

The empirical assessment of test techniques plays an important role in software testing research. One common practice is to seed faults in subject software, either manually or by using a program that generates all possible mutants based on a set of mutation operators. The latter allows the systematic, repeatable seeding of large numbers of faults, thus facilitating the statistical analysis of fault detection effectiveness of test suites; however, we do not know whether empirical results obtained this way lead to valid, representative conclusions. Focusing on four common control and data flow criteria (block, decision, C-use, and P-use), this paper investigates this important issue based on a middle size industrial program with a comprehensive pool of test cases and known faults. Based on the data available thus far, the results are very consistent across the investigated criteria as they show that the use of mutation operators is yielding trustworthy results: generated mutants can be used to predict the detection effectiveness of real faults. Applying such a mutation analysis, we then investigate the relative cost and effectiveness of the above-mentioned criteria by revisiting fundamental questions regarding the relationships between fault detection, test suite size, and control/data flow coverage. Although such questions have been partially investigated in previous studies, we can use a large number of mutants, which helps decrease the impact of random variation in our analysis and allows us to use a different analysis approach. Our results are then; compared with published studies, plausible reasons for the differences are provided, and the research leads us to suggest a way to tune the mutation analysis process to possible differences in fault detection probabilities in a specific environment     

Evolutionary programming using a mixed mutation strategy

Different mutation operators have been proposed in evolutionary programming, but for each operator there are some types of optimization problems that cannot be solved efficiently. A mixed strategy, integrating several mutation operators into a single algorithm, can overcome this problem. Inspired by evolutionary game theory, this paper presents a mixed strategy evolutionary programming algorithm that employs the Gaussian, Cauchy, Lévy, and single-point mutation operators. The novel algorithm is tested on a set of 22 benchmark problems. The results show that the mixed strategy performs equally well or better than the best of the four pure strategies does, for all of the benchmark problems.     

基于代数式规范的变异测试方法的设计与实现

软件测试是软件工程中保证软件产品质量的重要组成部分.变异测试是一种衡量测试用例集完备性的测试策略,也被用于生成完备的测试用例集.为了提出一种基于代数式规范的新的变异测试方法,为此设计了12类针对代数式规范的变异操作符,对5个代数式规范进行了实验,并进行了结果分析.结果表明基于代数式规范的变异测试方法相比基于代码的传统变异测试方法,生成更少的变异体,也大幅度提升了变异测试的效率.     

Assessment of C++ object‐oriented mutation operators: A selective mutation approach

Mutation testing is an effective but costly testing technique. Several studies have observed that some mutants can be redundant and therefore removed without affecting its effectiveness. Similarly, some mutants may be more effective than others in guiding the tester on the creation of high‐quality test cases. On the basis of these findings, we present an assessment of C++ class mutation operators by classifying them into 2 rankings: the first ranking sorts the operators on the basis of their degree of redundancy and the second regarding the quality of the tests they help to design. Both rankings are used in a selective mutation study analysing the trade‐off between the reduction achieved and the effectiveness when using a subset of mutants. Experimental results consistently show that leveraging the operators at the top of the 2 rankings, which are different, lead to a significant reduction in the number of mutants with a minimum loss of effectiveness.     

基于隐马尔可夫链的自适应MODE及应用

不同的控制参数设定和生成策略（交叉和变异）都会对多目标差分进化算法的性能产生显著影响。为实现其控制参数和变异策略的实时自适应调整,提出一种基于隐马尔可夫链的自适应多目标差分进化算法。该算法利用隐马尔可夫模型对种群信息进行分析并得到最优序列,通过最优序列与实际状态序列的对比得出变异缩放因子[F]与交叉概率[CR]的最大似然估计值,从而实现控制参数的自适应调整;同时,通过隐马尔可夫模型得到一组策略链来辅助多目标差分进化算法来选择合适的变异策略。通过与其他9种多目标进化算法在16个测试函数上的对比研究,结果表明所提算法的整体性能优于其他比较算法。最后,将该算法用于求解海铁联运能耗优化问题,所得结果能够为决策者提供多种可行方案。     

Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems

The offline 2D bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem in which objects with various width and length sizes are packed into minimized number of 2D bins. Various versions of this well-known industrial engineering problem can be faced frequently. Several heuristics have been proposed for the solution of 2DBPP but it has not been possible to find the exact solutions for large problem instances. Next fit, first fit, best fit, unified tabu search, genetic and memetic algorithms are some of the state-of-the-art methods successfully applied to this important problem. In this study, we propose a set of novel hyper-heuristic algorithms that select/combine the state-of-the-art heuristics and local search techniques for minimizing the number of 2D bins. The proposed algorithms introduce new crossover and mutation operators for the selection of the heuristics. Through the results of exhaustive experiments on a set of offline 2DBPP benchmark problem instances, we conclude that the proposed algorithms are robust with their ability to obtain high percentage of the optimal solutions.     

Mutation based test case generation via a path selection strategy

ContextGenerally, mutation analysis has been identified as a powerful testing method. Researchers have shown that its use as a testing criterion exercises quite thoroughly the system under test while it achieves to reveal more faults than standard structural testing criteria. Despite its potential, mutation fails to be adopted in a widespread practical use and its popularity falls significantly short when compared with other structural methods. This can be attributed to the lack of thorough studies dealing with the practical problems introduced by mutation and the assessment of the effort needed when applying it. Such an incident, masks the real cost involved preventing the development of easy and effective to use strategies to circumvent this problem.ObjectiveIn this paper, a path selection strategy for selecting test cases able to effectively kill mutants when performing weak mutation testing is presented and analysed.MethodThe testing effort is highly correlated with the number of attempts the tester makes in order to generate adequate test cases. Therefore, a significant influence on the efficiency associated with a test case generation strategy greatly depends on the number of candidate paths selected in order to achieve a predefined coverage goal. The effort can thus be related to the number of infeasible paths encountered during the test case generation process.ResultsAn experiment, investigating well over 55 million of program paths is conducted based on a strategy that alleviates the effects of infeasible paths. Strategy details, along with a prototype implementation are reported and analysed through the experimental results obtained by its employment to a set of program units.ConclusionThe results obtained suggest that the strategy used can play an important role in making the mutation testing method more appealing and practical.     

基于改进多目标优化算法的分布式数据中心负载调度

在数据中心的运营中运营商需要考虑如何在利润最大化的同时降低碳排放和提升服务质量,这些目标之间的平衡是一个巨大挑战.针对该问题,建立分布式数据中心负载调度的多目标优化模型,提出一种改进拥挤距离和自适应交叉变异的非支配排序遗传算法(ICDA-NSGA-II).在NSGA-II算法的基础上,通过对拥挤距离的改进能够提高算法的开采和勘探能力,引入正态分布交叉(NDX)算子和自适应变异算子增强种群的多样性,从而保证算法能快速、准确地得到Pareto解集.为了显示改进算法的有效性,对基准测试函数进行求解,仿真结果表明,改进算法相比于典型的NSGA-II和MOEA/D具有更快的收敛速度和精度,在分布式数据中心负载调度优化中,能够快速有效地给出满足利润、碳排放和服务质量等目标的Pareto最优解.     

改进NSGA算法求解多目标柔性车间作业调度问题

在多目标柔性车间作业调度问题的研究中,求解算法与多目标处理至关重要。因此,基于非支配排序遗传算法提出了改进遗传算法求解该问题,设计了相应的矩阵编码、交叉算子,改进了非劣前沿分级方法,并提出了基于Pareto等级的自适应变异算子以及精英保留策略。实例计算表明,该算法可以利用传统遗传算法全局搜索能力的同时可以防止早熟现象的发生。改进非劣前沿分级方法可以快速得到Pareto最优解集,进一步减小了计算复杂度,而且可以根据种群的多样性改变变异概率,有利于保持种群多样性、发掘潜力个体。     

基于变异的正则表达式反例测试串生成算法

正则表达式在计算机科学的许多领域具有广泛应用. 然而, 由于正则表达式语法比较复杂, 并且允许使用大量元字符, 导致开发人员在定义和使用时容易出错. 测试是保证正则表达式语义正确性的实用和有效手段, 常用的方法是根据被测表达式生成一些字符串, 并检查它们是否符合预期. 现有的测试数据生成大多只关注正例串, 而研究表明, 实际开发中存在的错误大部分在于定义的语言比预期语言小, 这类错误只能通过反例串才能发现. 研究基于变异的正则表达式反例测试串生成. 首先通过变异向被测表达式中注入缺陷得到一组变异体, 然后在被测表达式所定义语言的补集中选取反例字符串揭示相应变异体所模拟的错误. 为了能够模拟复杂缺陷类型, 以及避免出现变异体特化而无法获得反例串的问题, 引入二阶变异机制. 同时采取冗余变异体消除、变异算子选择等优化技术对变异体进行约简, 从而控制最终生成的测试集规模. 实验结果表明, 与已有工具相比, 所提算法生成的反例测试串规模适中, 并且具有较强的揭示错误能力.     

Multi-objective optimization algorithms applied to the class integration and test order problem

In the context of object-oriented software, a common problem is the determination of test orders for the integration test of classes, known as the class integration and test order (CITO) problem. The existing approaches, based on graphs, usually generate solutions that are sub-optimal, and do not consider the different factors and measures that can affect the construction of stubs. To overcome this limitation, solutions based on genetic algorithms (GA) have presented promising results. However, the determination of a cost function, which is able to generate the best solution, is not always a trivial task, mainly for complex systems. Therefore, to better represent the CITO problem, we introduce, in this paper, a multi-objective optimization approach, to generate a set of good solutions that achieve a balanced compromise between the different measures (objectives). Three different multi-objective optimization algorithms (MOA) were implemented: Pareto ant colony, multi-objective Tabu search and non-dominated sorting GA. The approach is applied to real programs and the obtained results allow comparison with the simple GA approach and evaluation of the different MOA.     

一种基于UML状态图的规约变异测试方法

规约变异测试从软件功能的角度,对规约进行分析,从而揭示规约中存在的问题。本文提出一种基于UML状态图的变异测试方法,针对每种变异算子,分析其是否会引入冲突,进而有效避免不合理的变异操作;分析了每种变异算子产生等价变异体的条件,能够在生成变异体的同时检测并移除等价变异体,进而减少其对测试过程的影响;给出了杀掉每种变异体所需满足的条件,可在此基础上产生杀掉特定变异体所需的测试用例,从而提高测试用例集的质量。在此基础上,根据变异算子的实际功能,整合了功能相同的算子,减少了变异算子的数量,从而进一步降低了变异测试的开销。实验结果表明,本方法能够较好地提高测试用例的质量,进而提升测试的效率。