Search Based Software Engineering: Techniques, Taxonomy, Tutorial - Empirical Software Engineering and Verification - page 25

Algorithm. A well known MOEA by Deb et al. [24], NSGA-II, was used for the
case study. Pareto optimality is used in the process of selecting individuals. This
leads to the problem of selecting one individual out of a non-dominated pair.
NSGA-II uses the concept of crowding distancetomakethisdecision;crowding
distance measures how far away an individual is from the rest of the population.
NSGA-II tries to achieve a wider Pareto frontier by selecting individuals that are
far from the others. NSGA-II is based on elitism; it performs the non-dominated
sorting in each generation in order to preserve the individuals on the current
Pareto frontier into the next generation.
The widely used single-objective approximation for set cover problem is greedy
algorithm. The only way to deal with the chosen three objectives is to take the
weighted sum of each coverage metric per time, i.e.:

Results. Figure 13 shows the results for the three objective test suite minimi-
sation for a test suite of a program called space , which is taken from Software
Infrastructure Repository (SIR). The 3D plots display the solutions produced
by the weighted-sum additional greedy algorithm (depicted by + symbols con-
nected with a line), and the reference Pareto front (depicted by

symbols).
The reference Pareto front contains all non-dominated solutions from the com-
bined results of weighted-sum greedy approach and NSGA-II approach. While
the weighted-sum greedy approach produces solutions that are not dominated,
it can be seen that NSGA-II produces a much richer set of solutions that explore
wider area of the trade-off surface.

×

Fig. 13. A plot of 3-dimensional Pareto-front from multi-objective test suite minimisa-
tion for program space from European Space Agency, taken from Yoo and Harman [106]

8.2 Case Study: Requirements Analysis

Selecting a set of software requirements for the release of the next version of a
software system is a demanding decision procedure. The problem of choosing the