Many real-world test optimization problems (e.g., test case prioritization) are multi-objective intrinsically and can be tackled using various multi-objective search algorithms (e.g., Non-dominated Sorting Genetic Algorithm (NSGA-II)). However, existing multi-objective search algorithms have certain randomness when selecting parent solutions for producing offspring solutions. In a worse case, suboptimal parent solutions may result in offspring solutions with bad quality, and thus affect the overall quality of the solutions in the next generation. To address such a challenge, we propose CBGA-ES+, a novel cluster-based genetic algorithm with non-dominated elitist selection to reduce the randomness when selecting the parent solutions to support multi-objective test optimization. We empirically compared CBGA-ES+with random search and greedy (as baselines), four commonly used multi-objective search algorithms (i.e., Multi-objective Cellular genetic algorithm (MOCell), NSGA-II, Pareto Archived Evolution Strategy (PAES), and Strength Pareto Evolutionary Algorithm (SPEA2)), and the predecessor of CBGA-ES+(named CBGA-ES) using five multi-objective test optimization problems with eight subjects (two industrial, one real world, and five open source). The results showed that CBGA-ES+managed to significantly outperform the selected search algorithms for a majority of the experiments. Moreover, for the solutions in the same search space, CBGA-ES+managed to perform better than CBGA-ES, MOCell, NSGA-II, PAES, and SPEA2 for 2.2, 13.6, 14.5, 17.4, and 9.9 percent, respectively. Regarding the running time of the algorithm, CBGA-ES+was faster than CBGA-ES for all the experiments.

Search-Based Software Engineering (SBSE) researchers who apply multi-objective search algorithms (MOSAs) often assess the quality of solutions produced by MOSAs with one or more quality indicators (QIs). However, SBSE lacks evidence providing insights on commonly used QIs, especially about agreements among them and their relations with SBSE problems and applied MOSAs. Such evidence about QIs agreements is essential to understand relationships among QIs, identify redundant QIs, and consequently devise guidelines for SBSE researchers to select appropriate QIs for their specific contexts. To this end, we conducted an extensive empirical evaluation to provide insights on commonly used QIs in the context of SBSE, by studying agreements among QIs with and without considering differences of SBSE problems and MOSAs. In addition, by defining a systematic process based on three common ways of comparing MOSAs in SBSE, we present additional observations that were automatically produced based on the results of our empirical evaluation. These observations can be used by SBSE researchers to gain a better understanding of the commonly used QIs in SBSE, in particular, regarding their agreements. Finally, based on the results, we also provide a set of guidelines for SBSE researchers to select appropriate QIs for their particular context.

Test case prioritization (TP) prioritizes test cases into an optimal order for achieving specific criteria (e.g., higher fault detection capability) as early as possible. However, the existing TP techniques usually only produce a static test case order before the execution without taking runtime test case execution results into account. In this paper, we propose an approach for black-box dynamic TP using rule mining and multi-objective search (named as REMAP). REMAP has three key components: 1) Rule Miner, which mines execution relations among test cases from historical execution data; 2) Static Prioritizer, which defines two objectives (i.e., fault detection capability (FDC) and test case reliance score (TRS)) and applies multi-objective search to prioritize test cases statically; and 3) Dynamic Executor and Prioritizer, which executes statically-prioritized test cases and dynamically updates the test case order based on the runtime test case execution results. We empirically evaluated REMAP with random search, greedy based on FDC, greedy based on FDC and TRS, static search-based prioritization, and rule-based prioritization using two industrial and three open source case studies. Results showed that REMAP significantly outperformed the other approaches for 96% of the case studies and managed to achieve on average 18% higher Average Percentage of Faults Detected (APFD).

Multi-objective search algorithms (e.g., non-dominated sorting genetic algorithm II (NSGA-II)) have been frequently applied to address various testing problems requiring multi-objective optimization such as test case selection. However, existing multi-objective search algorithms have certain randomness when selecting parent solutions for producing offspring solutions. In the worse case, suboptimal parent solutions may result in offspring solutions with bad quality, and thus affect the overall quality of the next generation. To address such a challenge, we propose a cluster-based genetic algorithm with elitist selection (CBGA-ES) with the aim to reduce such randomness for supporting multi-objective test optimization. We empirically compared CBGA-ES with random search, greedy (as baselines) and four commonly used multi-objective search algorithms (e.g., NSGA-II) using two industrial and one real world test optimization problem, i.e., test suite minimization, test case prioritization, and test case selection. The results showed that CBGA-ES significantly outperformed the baseline algorithms (e.g., greedy), and the four selected search algorithms for all the three test optimization problems. CBGA-ES managed to outperform more than 75% of the objectives for all the four algorithms in each test optimization problem. Moreover, CBGA-ES was able to improve the quality of the solutions for an average of 32.5% for each objective as compared to the four algorithms for the three test optimization problems.

Due to limited time and resources available for execution, test case selection always remains crucial for cost-effective testing. It is even more prominent when test cases require manual steps, e.g., operating physical equipment. Thus, test case selection must consider complicated trade-offs between cost (e.g., execution time) and effectiveness (e.g., fault detection capability). Based on our industrial collaboration within the Maritime domain, we identified a real-world and multi-objective test case selection problem in the context of robustness testing, where test case execution requires human involvement in certain steps, such as turning on the power supply to a device. The high-level goal is to select test cases for execution within a given time budget, where test engineers provide weights for a set of objectives, depending on testing requirements, standards, and regulations. To address the identified test case selection problem, we defined a fitness function including one cost measure, i.e., Time Difference (TD) and three effectiveness measures, i.e., Mean Priority (MPR), Mean Probability (MPO) and Mean Consequence (MC) that were identified together with test engineers. We further empirically evaluated eight multi-objective search algorithms, which include three weight-based search algorithms (e.g., Alternating Variable Method) and five Pareto-based search algorithms (e.g., Strength Pareto Evolutionary Algorithm 2 (SPEA2)) using two weight assignment strategies (WASs). Notice that Random Search (RS) was used as a comparison baseline. We conducted two sets of empirical evaluations: 1) Using a real world case study that was developed based on our industrial collaboration; 2) Simulating the real world case study to a larger scale to assess the scalability of the search algorithms. Results show that SPEA2 with either of the WASs performed the best for both the studies. Overall, SPEA2 managed to improve on average 32.7%, 39% and 33% in terms of MPR, MPO and MC respectively as compared to RS.

Test prioritization is crucial for testing products in a product line considering limited budget in terms of available time and resources. In general, it is not practically feasible to execute all the possible test cases and so, ordering test case execution permits test engineers to discover faults earlier in the testing process. An efficient prioritization of test cases for one or more products requires a clear consideration of the tradeoff among various costs (e.g., time, required resources) and effectiveness (e.g., feature coverage) objectives. As an integral part of the future Cisco's test scheduling system for validating video conferencing products, we introduce a search-based multi-objective test prioritization technique, considering multiple cost and effectiveness measures. In particular, our multi-objective optimization setup includes the minimization of execution cost (e.g., time), and the maximization of number of prioritized test cases, feature pairwise coverage and fault detection capability. Based on cost-effectiveness measures, a novel fitness function is defined for such test prioritization problem. The fitness function is empirically evaluated together with three commonly used search algorithms (e.g., (1+1) Evolutionary algorithm (EA)) and Random Search as a comparison baseline based on the Cisco's industrial case study and 500 artificial designed problems. The results show that (1+1) EA achieves the best performance for solving the test prioritization problem and it scales up to solve the problems of varying complexity.