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

Choose the Right Algorithm for the Search Space: Choosing the right
algorithm for the problem is as fundamental to search as choosing the right tool
for the job is in any engineering endeavour. The field of optimisation is well
known for its many versions of the 'no free lunch theorem' [102]. There is plenty
of evidence [3, 48, 78] to indicate that SBSE problems are as wide and varied
as those found in the general optimisation literature. It is, therefore, foolhardy
to believe that one search based optimisation technique will be superior for all
possible problems that one might encounter.
The most popular algorithms (by far) that have been used hitherto in SBSE
work are variations on the theme of population-based evolutionary algorithm
[48]. This is not the result of evidence that evolutionary algorithms are superior
to other algorithms. Quite the contrary in fact: There is evidence to suggest
that, for some problems, such as structure test data generation (a very widely
studied problem), simpler local search algorithms may be better [49], and that
some form of hybridisation that seeks to achieve the best of both local and global
search [50] may be the best performing approach so far known.

11.4 The Final Fitness I Obtained Is Simply Too Poor: The

Solutions Are Just not Good Enough

Usually, even with a relatively 'out of the box' choice of fitness function and
search based optimisation technique, the results obtained will be better than
those obtained using a purely random search. However, you may still feel that
the results are not as good as you would like, or, if you have as specific threshold
fitness value in mind, you may find that your algorithm fails to achieve this
threshold, even when you allow it considerable computation resources. In this
situation, you should not give up and assume that 'SBSE does not work' (it is just
possible that it may not, but it is certainly too soon to be sure!). It may be that
your algorithm is performing poorly because of some of the parameter choices
or because it is the wrong algorithm for this particular problem. Even should
all else fail, you may be able to extract useful information from the suboptimal
results you have obtained.

Avoid Premature Convergence: Premature convergence on a local optima
often turns out to underlie the observation that an SBSE algorithm fails to pro-
duce 'good enough' results. This can happen because, for example, too much
elitism has been incorporated into an evolutionary approach, or because some
domain knowledge has been injected in a way that strongly biases solutions to-
wards only one part of the search space. In general, it may be helpful to think
of your search process as a compromise between exploration and exploitation (a
common distinction in the more general optimisation literature). If you fail to
explore suciently, then premature convergence will result. If you fail to exploit
suciently, then you may have a broad spread of solutions across the search
space, none of which is of particularly high quality. It is a good overarching
principle to seek to favour exploration in the earlier stages of the search pro-
cess and exploitation subsequently. This principle is captured, elegantly, by the