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

better. Random search never covered 18F, and requires 5 times as much effort
(test data evaluations) in order to cover 19T.

8.4 Case Study: Cost Estimation for Project Planning

Software effort estimation is an important activity performed in the planning
phase of a software project. Its importance can be easily realised by the fact that
the effort estimation will drive the planning of basically all remaining activities in
the software development. Given such significance, many approaches have been
proposed in the attempt to find effective techniques for software estimation.
Nevertheless, as a result of the high complexity of this activity, the search for
ecient and effective estimation models is still underway. An interesting example
on the application of a search based approach - genetic programming, in this case
- to tackle the software estimation problem can be found in [25].
In this application, the software estimation problem is modeled as a search
problem, considering as search space the set of cost predictive functions which
will have their predictive capability evaluated based on some particular measure.
A search algorithm would then seek functions which maximise this evaluation
measure.
Therefore, the Software Cost Estimation problem can be defined, as in [25],
as follows:

Definition 4. Software Cost Estimation Problem

Given: Well-formed equations, which can be used to produce cost predictions.

Problem: Find the equation with best predictive capability, calculated by mea-

sures such as mean squared error or correlation coecient.

Representation. For this problem, solutions are represented as trees, express-
ing well-formed equations. In each tree, terminal nodes represent constants or
variables, and each non-terminal node stores a simple function, from a pre-
determined set of available functions that can be used in the composition of
an equation. The available functions proposed in the original paper were: plus,
minus, multiplication, division, square, square root, natural logarithm and ex-
ponential.
Fitness Function. As pointed out by Dolado [25], classical measures used to
evaluate the fitting of equations to some data can be use as fitness functions
for this software estimation problem. In the paper, the following measures were
considered: mean squared error , which quantifies the error of the considered
function being used as estimator, and the correlation coecient , which measures
the variation between the predicted and the actual values.

Algorithm. Genetic programming (GP), as a variation of the well-known ge-
netic algorithm (GA), can be used to manipulate complex individuals, expressed
by data structures representing trees, source codes, design projects, or any other