Starting in the mid-1990's various researchers working
in the field of software engineering started
looking at how the field of optimization might
be applied to their field.
Many other engineering disciplines incorporated
optimization techniques into their standard toolboxes
long ago.
These include mechanical engineering \cite{polyfailure92,sebag98parametric},
chemical engineering \cite{birge92,karrsharma93},
medical and biomedical engineering \cite{poli95genetic,sanchez95,weiss01engineered},
civil engineering \cite{bentley96,babovic98,feng97,jenkins92}, and
electronic engineering \cite{bennet99,on98evolutionary,miyamoto93}.
In contrast to the multitude of areas outside software engineering, 
researchers in the field of software engineering are just starting
to realize the applicability of search based optimization
to their problem domain.
This section will first describe how to view
software engineering problems as search problems (\tion{rethinking}).
The key insight in search based software engineering is
that many standard software engineering problems are 
not amenable to analytic solutions since 
the mathematics of the problem does not permit symbolic analysis
nor complete methods since the size of the search space is too large to 
make such a search feasible.
The rest of the section will review some of the research done 
in software engineering that has applied optimization techniques
(\tion{testing} - \tion{reqAnalysis}).


\subsection{Rethinking Software Engineering as Numeric Optimization}\label{sect:rethinking}
As described in \cite{harman01searchbased,clarke-reformulating}
there are three key elements to rethinking a software engineering
problem as a search problem. \\
\be
{The problem has to be described in a manipulatable language.
The metaheuristic technique used must be able to generate new
proposed solutions automatically using this language.}
{An objective function
%\footnote{The terms {\it fitness}/{\it worth}/{\it cost} 
%functions are often used interchangable.}
must be developed.
This function needs to map proposed solutions to a single numeric output.
This output then is either minimized or maximized (i.e. optimized)
by the metaheuristic technique being employed.}
\item Transformation operators that work on
proposed solutions also need to be developed.
This might mean defining a neighborhood function that generates
solutions ``close'' to another solution based on some criteria.
Or it might mean taking a single proposed solution and changing
some aspects to generate a new proposed solution.
%\footnote{Recall that mutate is often used in the field of evolutionary 
%algorithms but in this sense it is taken to be the general term for any 
%operator that changes one proposed solution to another, regardless
%of search technique being used}
\ee
If these conditions are not met, using a metaheuristic
search technique may not be possible or may not be necessary.

\paragraph{Representation}
Solutions to the problem need to be encoded in such a way
that the various operators
of the search technique being used can operate on them.
Therefore, the
first issue that must be addressed when applying a search
technique is to find a suitable representation for 
candidate solutions.

The problem of representation can be more complex than might be
first assumed, because the most natural encoding may
not be the best scheme for the search technique being used.
For instance, consider the bit encoding of an integer, as might
be required when using a genetic algorithm.
It is possible to represent integers as ``pure'' binary numbers.
One would be represented as $0001$, two as $0010$, 
three as $0011$, and so on.
According to the rules of arithmetic, seven can be transformed into
eight through only one application of the successor function.
But in pure binary seven, $0111$, must have four bits flipped
to be transformed into eight, $1000$.
Since the mutation operator in a genetic algorithm
works on the bit representation, seven is no longer only one
operation away from eight.
For this reason {\it gray} encoding is preferred.
With gray encoding seven would be $0100$ and eight would
be $1100$\footnote{Other gray encodings are possible, but this 
is the must popular.}.
Now seven and eight are only one mutation apart.
It has been reported that gray encoding outperforms
binary encoding \cite{whitley99free,jones96structural}.

\cite{tracey00,wegener01} have also pointed out that
both binary and gray encoding of real or integer numbers
that have a restricted range can lead to the mutation
and crossover operators that create out of bounds
values.  This means that after each mutation
or crossover event the chromosome has to be inspected
and, if necessary, repaired.
Or if this possibility is ignored the semantics of a language
with restricted range types (\eg Ada) can be violated.
They suggest using real-valued encoding to avoid this problem.
\cite{eshleman93} also argues for using real-valued
encodings with evolutionary techniques.

Picking an encoding scheme must clearly include not
only an understanding of the search technique but
domain knowledge as well.

\paragraph{Objective function}
The next problem is developing an objective function.
Software engineers are used to collecting
software metrics, so those metrics are a ready supply
of objective functions.
For example, path or branch coverage for
test case generation can be used as objective functions.
There are a few new issues that should be addressed
before these metrics, which were developed for other purposes,
can be used as objective functions.
\cite{harman-metrics} lays out four requirements for
a metric function to be used as an objective function,
each of which will be discussed in more detail below. \\
\be
{the input space of the metric function shouldn't be 
small enough to allow an exhaustive search}
{the function should have no known optimal solutions}
\item the function must be computationally efficient
\item the function should be approximately continuous
\ee

\subparagraph{Input space size and known optimal solutions}
Items 1 and 2 have bearing on the question of whether
a search would beneficial.
If the input space of the objective function is small
enough to permit exhaustive search, then there is 
nothing to gain by using a incomplete search 
algorithm.
Exactly how big is too big will depend on the hardware
available and the computational costs of the objective function.
For example, mission critical tasks
might have the budget to allow the use of long periods
of time on large amounts of hardware to tackle very
large search spaces.
Many of the case studies presented in chapter \ref{chap:casestudies}
have $2^{55}$ ($10^{17}$) or more possible input vectors, so it is
unlikely that any amount of hardware or budget would
allow a reasonable chance to do a complete search.
The objective function must also have no known optimal solution
for there to be any gain to using a metaheuristic search.
For example, if a 3-SAT proposition has a single 
unsatisfiable clause (which can be found in linear time
\cite{garey79}),
there would be no point in conducting an expensive
search for that particular proposition.
Any analytic solution should be preferred to
a solution found through search,
and any near-optimal solution found analytically would also be
preferred.  
For example, an analytically found near-optimal solution might have
a upper bound on its distance from the unknown optimal solution.
This type of information would not be found by a
metaheuristic search technique.


\subparagraph{Objective function efficiency and continuity}
Items 3 and 4 have bearing on whether an effective search 
would be practical.
While the exact number of times the objective
function is evaluated depends on the technique being used,
it will most likely be at least $10^4$ and possibly
more than $10^7$.
One of the main driving forces behind the development of ITL
is reducing the needed number of evaluations of the objective function.
As a search technique moves around the input space
it must have some hint that it is moving in an undesirable
or desirable direction.
For that reason, the more continuous the objective function, 
the more efficiently we can expect the search to progress.
If there exist many near-optimal solutions at points of
high discontinuity, the probability that any search
technique will find them approaches the probability that
a random search would find them, as the discontinuity
of the objective function increases.
We encountered this problem in the studies
presented in \chap{properties} and \chap{others}.

The next three sections will discuss the application of search-based software
engineering to the fields of testing (\tion{testing}),
cost estimation (\tion{costEstimation}), and
requirements analysis (\tion{reqAnalysis}).
These fields are reviewed because cost estimation
and requirements analysis are early life cycle activities,
similar to the study presented in \chap{casestudies},
and testing is a late life cycle activity,
similar to the studies presented in \chap{properties}).


\subsection{Testing}\label{sect:testing}
One of the first areas in software engineering to use
optimization techniques was test case generation.
Test case generation has a few properties that make it
uniquely suited for search-based optimization.
First, there are many metrics that have already been developed
by the testing community that serve as ready-made
candidates for objective functions.
There are static measures like the McCabe complexity values \cite{mccabe76},
and dynamic measures like path or branch coverage.
Second, the input space to even the most trivial
programs is far too large for any exhaustive search.
Third, static program analysis is difficult for most
real world programs.  It is a well known result
that it is not computationally possible to 
decide even the simplest program 
properties\footnote{For example, the halting property} for 
any Turing-complete language.
Fourth, manual construction of test data is quite expensive.
Testing often accounts for up to 50\% of the cost
for typical software projects \cite{beizer90}.
For these reasons there has been much
work on applying search techniques to the problem of automatic
test case generation.


An early work using search based techniques on automatic
test case generation is \cite{ellis92}.
Since then there have been improvements to
the original work 
\cite{jones96structural,mcgraw97generating,korel96}
by removing
the need for a human tester to select a path and by
changing the way the objective function is calculated for
conditional branches.
For example, control dependence graph analysis has been
included in the objective function \cite{pargas99testdata}.
If the search is trying
to execute branch {\it c}, which is dominated by branch
{\it b}, which in turn is dominated by branch {\it a},
the objective function reflects how many of the branches
{\it a, b,} or {\it c} are executed.
However, this type of function suffers because the
objective function has a large plateau in the areas
of the input space that don't execute branch {\it a}.
The objective function doesn't provide any distance guidance
as to how to execute any particular branch.
Even with this disadvantage \cite{pargas99testdata} still reported
significant speed ups when compared to a purely
random search.
Later other researchers, \cite{tracey00,tracey02},
added a distance metric to
the objective function to remove some of the discontinuity
of the function.  


Early work using EA techniques to generate test
data using a {\em Z} specification 
(see \cite{zede92} for a full discussion of the {\em Z} specification)
can be found in \cite{jones95}.
They used the canonical triangle classification problem
and developed a {\em Z} specification for that program.
The specification consisted of predicate statement
in disjunctive normal form.
Each disjunct was considered a path through the program.
The objective function measured how close an input set came
to satisfying one of the disjuncts.
Success was reported for covering all nominal cases.
More recent work on using specification driven
test data generation has been done in \cite{tracey98flaw,tracey02}.


\cite{wegener99} investigated the objective landscape
for timing behavior.  
They found that GAs outperformed SAs and
they explained this difference
by looking at the topology of the objective landscape.
Recall that GAs perform global searches, since each individual
in the population is initialized to a different location
and cross-over events can generate individuals
in radically different locations than their parents.
The objective landscape had discontinuities wherever
different paths through the control flow graph were taken.
If the different paths had significantly different execution times,
this creates a discontinuity at that location in the
objective landscape.
The landscape also had many plateaus.
If different input values led to the same exact path being
executed, their execution times were usually very close.
These discontinuities and plateaus were less likely 
to deteriorate the performance of a global search
algorithm like a GA.

Simulated Annealing (SA) is also a popular metaheuristic
technique in automatic test data generation.
For instance, \cite{tracey98automated,tracey98unifying}
investigate using SAs to find the worst case execution time and
maximizing structural coverage.
\cite{tracey98flaw} uses pre/post conditions written in
disjunctive normal form.
The objective function was a distance metric that measures
how close a given input comes during execution to violating
the pre/post conditions.
%This technique can also be used to try to find assertions 
%violation with langauges that support assertions.


Note the importance the objective function plays in all
the work described in this section.
The contributions of these publications are not new
search techniques or even modifications to
existing techniques, but rather new ways
to formulate the objective function to allow the search
to proceed more efficiently.
Also note that symbolic analysis of the source code
is necessary for the distance measures of branch points.
The case studies presented by this thesis
(\chap{properties} and \chap{others})
highlight the importance of a objective
function that follows the advice laid out
in \tion{rethinking}.


For a broader survey of search based automatic test case generation
see \cite{mcminn04searchbased}.


\subsection{Cost Estimation}\label{sect:costEstimation}
While a high quality estimate of a project's cost
would be very useful to software planners,
software cost estimations can be notoriously inaccurate.
For example, \cite{boraso96software} reports that 60\%
of large projects significantly overrun their 
estimates and 15\% of software projects are never
completed due to gross misestimation of development
effort.
A very popular technique for software cost estimation
is the COCOMO \cite{boehm81} linear regression 
method\footnote{Citeseer reports over 2000 citations to this work.}.
The rest of this section will describe some efforts
to improve software cost estimation
by applying search-based techniques.


In \cite{aguilarevolutionary} a sequential covering
evolutionary algorithm was used to generate management
rules to reduce the likelihood of effort and time overruns.
This technique is a ``divide-and-conquer'' technique
as rules are adjusted according to data points not
already covered.  Once a data point is covered
by the rule it is removed from the pool of 
remaining points.  
The data points used in this study came from a dynamic
model that had 12 numeric and ordinal inputs with restricted ranges.
The two outputs of this model were development effort (developer-days) 
and development time (days to complete).
The objective function combined the error for a rule, the
support for the rule\footnote{The absolute number of correct classifications},
and the coverage of the input space by the rule.

Although the technique can be generalized to any
number of target classes, in this study the
data points were split into two classes, GOOD and BAD.
Those points that had both a development effort and time
below a nominal value were labeled GOOD, all other points
were labeled BAD.
The nominal values for development effort and time were
generated in the following fashion.
An initial estimate of development effort and time 
was generated assigning values
to the various inputs based on discussions with the
project manager.
The outputs of this initial run of the dynamic model
were used as the nominal values.  
After finding the nominal values for time and effort,
the simulator was then run randomly choosing inputs.
The results of these runs were entered into a database.
The database then became the source of the data points
used by their sequential covering algorithm.
They present several rules generated by their algorithm
that the dynamic model predicts would have led to a
6\% reduction in effort and a 9\% reduction in time.

Similar to this thesis, \cite{alvarez-data} investigated using data mining
techniques for software effort estimation.
The work presented differs in a significant way
from the current work.  In \cite{alvarez-data} a
dynamic model is used to generate data, but
there is no feedback from the learner to
the model.  All records generated from
the model are stored to a database and then
the learner works on those records, after the
simulation has ended.
They do acknowledge that smaller rules should
be preferred, but leave that advice to the user.
In other words, their learner does not systematically
search for smaller solutions.
They also have the problem of needing to discretize
the output parameters of the model for their learner.
Their solution is for the project manager to define
a ``cutting-section''.  The cutting-section defines
the maximum allowed values for each of the three outputs
of the model (cost, development time, and quality).
If any of the those three limits is exceeded the record
is labeled ``bad'', otherwise the record is labeled
``good''.
%The algorithm used attempts to find regions in the
%input space that contain at least $\alpha$
%percentage of the same class.  This is repeated
%until either a maximum number of generations has been exceeded
%or the percent of covered instances is greater than $\beta$.
%Both $\alpha$ and $\beta$ are user-defined parameters.
Their objective function (adapted from \cite{aguilarevolutionary})
is slightly complex, taking into
account the uniformity of the region, the coverage of the region,
and the total hyper-volume\footnote{Called amplitude in the original paper}
of the region.
No attempt is made to demonstrate the superiority of the induced
rules, rather just a validation of the data mining technique.
Other modeling work with software cost estimation includes 
\cite{dolado01,finnie97,shepperd97,walkerden99}.

Extreme sampling (discussed in \tion{xsampling})
was developed independently of 
\cite{aguilarevolutionary,alvarez-data}
and follows a similar logic, but with a different motivation.
The discretization methods in 
\cite{aguilarevolutionary,alvarez-data}
are used to guide the search towards acceptable solutions, 
because business restrictions made some solutions unacceptable.
The extreme sampling discretization method was developed to 
complement the search heuristic used by ITL.
\tion{xsampling} contains a fuller
description of extreme sampling.


Other techniques not discussed in \tion{ml} and \tion{metaheur}
are used in cost estimation.
For instance in \cite{dolado2000} 
linear regression, neural nets\footnote{
Neural nets are a another machine learning technique
not discussed in this thesis, see \cite{haykin99} for
a complete description.},
and genetic programming were used to build cost estimators.
They studied 46 student projects 
developed by a total of 148 students.
All projects were accounting information
systems for hypothetical firms.  
Different groups
had different hypothetical firms with different requirements.
In addition all the projects studied were developed
in the same language. %(Informix-4GL).
They found that neural nets slightly outperformed
GP, and linear regression performed slightly worse.


%They split the code written for the projects into three
%components, menus, inputs, and reports/inquiries.

%The effort estimations for the menus components
%were very good, with all three methods performing
%equally well (pred(.25) = 100 for 5 of 6 groups).
%The effort estimations for the inputs components
%were not as accurate.  With those components the average
%pred(.25) was 38\% for linear regression.
%For this component neural nets reported a pred(.25) of
%54\%, while using a GP technique resulted in a pred(.25)
%of 51\%.
%The effort estimation for the last component, reports/inquiries,
%performed worse than the inputs component.
%45\% for LR, 58\% for NN, and 47\% for GP.

\subsection{Requirements Engineering}\label{sect:reqAnalysis}
Since all software projects have a limited set
of resources (money, staff, hardware, \etc),
project managers must balance the expenditures
of these resources to meet the specific goals
of their projects.
Additionally, it is an accepted fact that
the earlier a fault is discovered, the less
costly it will be to correct it
\cite{mcconnell04,brooks95,nakajo91,boehm81}.
For these two reasons (and others) organizations
have been spending more attention on the field
of requirements engineering (RE).
Search techniques have not been applied 
to requirements engineering as extensively as they
have been in other fields.
For instance, \cite{nuseibeh00} does not even mention
search-based techniques in its requirements engineering road map.
To pick an example from that road map, \cite{yu97}
discusses model building and their argument for 
building models early in the requirements 
phase\footnote{As opposed to late in or after the 
end of the requirements phase}.
There is no discussion of, or even citation to, the application of
search techniques to requirements engineering.

This lack of a large body of work in applying search to RE
does not reflect any inherent inapplicability
of search techniques to the problem of requirements engineering.
Researchers in requirements engineering have already developed
numeric metrics that can be easily used as objective functions.
Most of these are some combination of
projected cost of the project, 
risk inherent in the project, 
the value of the achieved requirements, 
defect injection rate,
and expected development time.
As in the field of cost estimation, 
dynamic models can be used to model the interactions
between the elements a requirements engineer is
trying to study.
For example, DDP (see \tion{ddpDes}) is a tool that facilities
the development and analysis of risk-cost models.

The input space of a typical requirements problem is very large.
Even if the input vector is boolean, 
a few dozen requirements can
not reasonably be searched exhaustively.
Some techniques have been explored,
\eg the Analytic Hierarchy Process \cite{saaty80} and 
Multi-criteria Decision Making,
that are solvable by analytic techniques.
But these techniques have some restrictions that
limit their applicability.
They have trouble dealing with dependency and ordering
properties of requirements and costs.
The use of dynamic modeling eliminates the
possibility of using one of these analytic techniques.
But dynamic models can be used to capture complex features,
such as interdependent requirements or mitigations.
The DDP tool already mentioned is capable
of handling such dependencies.

Finally it should be noted that model building can be
quite expensive (see discussion of DDP in \tion{ddpDes}), 
so developing
high-quality solutions will help maximize the return-on-investment.


\paragraph{Analytic Hierarchy Process}\label{par:ahp}
The Analytic Hierarchy Process (AHP) \cite{saaty80}
is a method that uses pairwise comparisons to
calculate the relative importance of any criterion.
If $n$ alternatives are possible, a square matrix of size $n$
is built.
Each element in the matrix is the comparative importance of the
alternative in the row to the alternative in the column.
If the alternative in the row is more important an integer
[1,9] is used, the reciprocals being used if the
column is more important than the row.
The matrix  should have 1's along the diagonal.
Various matrix operations are then performed which
lead to a relative ranking of the alternatives and
a consistency ratio.
Advocates of the AHP claim that pairwise comparisons
reduce the error common to this type of human judgment,
when compared to absolute scores \cite{lederer92}.

Since there has been little work applying search, we will discuss
some related work on requirements engineering that doesn't utilize
search based techniques.
\cite{karlsson97} developed a cost-value technique that
uses the AHP to inform managers of the most cost effective requirements.
They present two case studies from Ericsson Radio Systems,
a telecommunications manufacturer.
They had a group of project members develop the 
high level requirements for two projects (one currently in development,
the other a mature product that had already had three
major public releases).
The group then filled in the pairwise matrix, first
for the the value of each requirement, and then for
the cost of implementing those requirements.
The different requirements were then plotted,
on a cost vs value graph.
It is then very easy to see which requirements
have the lowest cost-to-value ratio and which
have the highest.
Dropping the three requirements (out of 14) with the highest
ratios still captured 94\% of the value for only
78\% of the cost in the first project; while
dropping the three requirements (out of 11) with the highest
ratios in the second project led to 95\% of the value
for only 75\% of the cost.
This is a archetypal example of requirements analysis
balancing two or more competing goals.
A simple technique like AHP can be used with these
examples in large part because the models
studied do not allow interdependencies.
It is unlikely that it is possible for a group of experts
to develop a completely orthogonal set of requirements.
Developing an orthogonal set of requirements will
get more difficult as the set of requirements grows 
larger\footnote{Due to the exponential growth of the number of
possible edges as the number of nodes increases.}.
In a later paper \cite{karlsson98evaluation} they compare
six different methods for prioritizing.  
None of the six techniques deal with the possibility
of dependencies between the requirements.


%While the previous study dealt with ranking the requirements
%according to their cost-value ratio, \cite{jung98} used the AHP
%to maximize the value acheived for a set cost ceiling.
%In that formulation the problem is essentially a 0-1 knapsack problem, 
%which known to be NP-hard in the general case \cite{garey79,martello90}.
%However the two case studies presented in \cite{karlsson97} 
%are small enough that commerically available tools can find
%the optimal solution in negligible time.
%\cite{jung98} uses a two step process to find an optimal
%solution to implementing the highest value requirements
%within a given cost ceiling.
%First, an integer programming technique is used to find
%the maximum value below the cost ceiling.
%Then, the requirements that acheive that maximum value
%for the minimum cost is found using another commerically
%available nonlinear model solver.
%Small decreases in the cost were found in both case studies.

%The topic of this thesis, ITL, has been used in previous
%work on requirements engineering.
%We will present a brief introduction to the work by 
%Menzies {\it et. al.} here and leave many of the details for
%later in this thesis.

%\cite{me01g,me02c} is one the first papers to appear that describes
%the application of ITL to a problem in requirements engineering.
%\cite{me02c} presents the results of three case studies from,
%a softgoal software architecture, a qualitative model, and
%a setellite design model.  They demonstrate how to use
%ITL to greatly reduce the uncertainty of a models output
%by restricting the ranges of allowable inputs on only
%a fraction of the inputs.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../thesis"
%%% End: 
