AuthorsD. Pradhan, S. Wang, S. Ali, T. Yue and M. Liaaen
TitleCBGA-ES+: A Cluster-Based Genetic Algorithm with Non-Dominated Elitist Selection for Supporting Multi-Objective Test Optimization
AfilliationSoftware Engineering
Project(s)The Certus Centre (SFI), Department of Engineering Complex Software Systems
StatusPublished
Publication TypeJournal Article
Year of Publication2018
JournalIEEE Transactions on Software Engineering
PublisherIEEE
Abstract

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%, respectively. Regarding the running time of the algorithm, CBGA-ES+ was faster than CBGA-ES for all the experiments. 

Citation Key26214