Information Technology Reference
In-Depth Information
module clustering [77] that better results can be obtained for using a multi ob-
jective optimisation on a single objective problem. This happens because the
other objectives may help the search to find routes to the global optima in
the single objective space. Therefore, searching for solutions that satisfy multi-
ple objectives may, perhaps counter-intuitively, help to solve a single objective
problem. If you find that one of your fitness characterisation has an unattrac-
tive search landscape, yet it provides useful guidance in some cases, you might
consider incorporating additional fitness functions.
Use Secondary Fitness: For problems in which there are too many plateaux,
you may consider the use of a secondary fitness function, to be used to distin-
guish candidate solutions that lie on a plateaux according to the primary fitness
function. This has been used in the SBSE problem of search based transforma-
tion. In transformation, the goal is to find a new version of the program that is
better (according to some metric) by searching the space of transformations of
the original program (or the transformations sequences that can be applied to
it). This is a very well studied area of SBSE [21, 29, 30, 52, 75, 85], dating back to
the work of Ryan and Williams [83, 104] on auto-parallelisation transformations.
One of the problems for this SBSE problem, is that there are many trans-
formations the application of which fails to affect the primary fitness function.
For example, suppose we seek to shrink the size of a program by either remov-
ing redundant computation or by slicing [44]. In this situation, there are many
transformations that will not reduce the size of the program to which they are
applied. All such transformations will lie on a plateau of fitness with regard to
their effect on code reduction for some specific program. However, we can dis-
tinguish among such transformations. Those that are not applicable are worse
than those that are applicable. Those that are applicable, but have no effect at
all are worse than those that alter the code without reducing its size. In the
early stages of the search those transformations that have a larger effect on the
syntax may also be preferred. This suggests a secondary fitness that can be used
to guide a search to the edges of a plateaux in the search space induced by the
primary fitness function. This has been employed to improve the performance of
search based slicing [30].
Landscape Analysis: In the more general optimisation literature, the issue
of landscape analysis and algorithmic characterisation is well studied [103]. For
example, there has been work on the analysis of plateaux in search landscapes
[91]. There has also been much work on SBSE landscape analysis and algorithm
characterisation. Early work in this area for the project estimate feature selection
[57] and modularisation [67] has been championed in the SBSE literature [36]
as exemplary of the kinds of analyse that can be achieved, empirically, using
a simple (but effective) multiple restart simple hill climbing approach. There
has also been recent theoretical analysis of SBSE algorithm performance [61]
and theoretical and empirical analyses of search based testing for structural test
data generation [7, 49, 50].
Search WWH ::




Custom Search