Empirical Study of Different Algorithms for Search Based Slicing
Yigang Zhang, Mark Harman · 2006
Slicing has been widely applied in many fields of software engineering, such as debugging, testing, software maintenance and restructuring. Several meta-heuristic search algorithms have been discussed and applied in many areas and been proved to work effectively. Hence, the concept of formulating slicing to search-based applications under the framework of SBSE is arose. This report introduces an approach to locate dependent structures in a program by exploring all the combinations of possible program slices. The paper formulates this problem as a search based software engineering problem. To evaluate the approach, the paper introduces an instance of a search based slicing problem concerned with locating sets of slices that decompose a program into a set of covering slices that minimize inter-slice overlap. The paper reports on algorithm performance and efficiency for implementations of genetic algorithms, random search, hill climbing, simulated annealing and greedy algorithm applied to a set of six C programs. Afterward, a multi-objective genetic algorithm, Niched Pareto Genetic Algorithm, is also introduced into this application. Results from this application show the distribution of the individuals and the tradeoff Pareto front are very positive.