\chapter{Introduction}\label{chap:intro}

Two methodologies that are becoming increasingly
popular in software engineering are model based
development and search based software engineering.
The work presented in this thesis attempts to apply
search based techniques to model based development.
We apply a new metaheuristic search technique,
Iterative Treatment Learning, ITL, to 
NASA requirements models and NASA flight models.
These two types of models represent early life
cycle stages and late stages, respectively.



\section{Search Based Software Engineering}
Software engineering is concerned with the process of 
software construction.
The software construction process is commonly 
decomposed into the following parts:
requirements, design, implementation, testing,
and maintenance.
Software engineering researchers have produced
work on all of the above life stages.
The overall goal of this body of work is
to improve the quality of software.
This might mean improving cost estimation 
for software projects, developing tools that
make implementation easier, or automatically generating
a suite of test cases that verify requirements.


Compared to the amount of research done in
applying metaheuristic search techniques
to combinatorial problems and to other engineering fields, 
the amount of work done
with metaheuristic search in software engineering is quite
small.
Beginning in the mid-1990's some
researchers in the software
engineering field have argued for the application of common
metaheuristic search techniques to classical
software engineering problems
\cite{harman-metrics,clarke-reformulating,harman01searchbased}.
This idea is accepted by this thesis as an important
breakthrough in problem formulation for the field
of software engineering.
It is also beginning to be accepted by
the software engineering field.
For example, in a review completed in 2004 Rela \cite{rela04}
found at least 123 publications in the field of
search-based software engineering that used
evolutionary algorithms 
(evolutionary algorithms will be discussed in \tion{metaheur}).
Of the 123 publications 44\% (54) were
related to testing, while only 7\% (8) were
related to early project planning.
In \tion{sbse} we discuss these two topics, 
because much of the work
presented in this thesis deals with early project planning,
such as requirements engineering (\chap{casestudies}),
and testing using model based verification (\chap{properties}).

The first step towards the application of metaheuristic
search techniques to software engineering problems
is the realization that many of these problems
are already or could easily become a type of optimization 
problem.
All that is needed is to reformulate the goal of the research as an 
{\it objective function}\footnote{Sometimes called a {\it cost}, {\it fitness}, or {\it worth} 
function in the literature}.
The objective function
is a function that evaluates the desirability of
a given candidate solution.
This function can evaluate any property of the solution
that the practitioner wishes to use, as long as the output
is numeric.
For example, the objective function could be 
path coverage or estimated project cost.
Besides development of an objective function,
a manipulatable language, as well as the operators
that manipulate that language, need to be developed.
A more complete discussion of these steps 
can be found in \tion{rethinking}.

Once an objective function is formulated,
a software engineering researcher 
does not have to
develop their own optimization technique.
Rather, researchers can borrow techniques developed for
other problems that can be easily adapted to their own problem domain.
While current research on metaheuristic search techniques
may focus on complex issues such as robustness to noise,
local optimum escaping, or hybrid approaches,
software engineering researchers can use simple versions of
many metaheuristic search techniques that have be shown to
be effective, despite their simplicity.
In fact, for some languages and platforms,
all the researcher has to do is develop
their objective function in a particular
language and use a framework already 
developed\footnote{For example, see \url{http://www.cs.uwyo.edu/~wspears/freeware.html}
for William Spears's C implementation of a genetic
algorithm}.

This change in approach will facilitate
the the adding of metaheuristic search techniques
to the toolbox of all software engineering researchers.


\section{Model Based Development}

%jim stuff
Software engineers build models at every phase of the life cycle.
Some are paper-based and some are executable but all these artifacts
are \emph{models}, which are defined in \cite{mellor03} as
\begin{quote}
``elements describing something (for example, a
system, bank, phone, or train) built for some
purpose that is amenable to a particular form
of analysis, such as communication of ideas between people
and machines; completeness checking; test case generation; etc.''
\end{quote}
The benefits of modeling include
increasing productivity and reduced time-to-market for 
software products \cite{sendall03} and
the imposition of 
``structure and common vocabularies
so that artifacts are useful for their main purpose in their
particular stage in the life cycle" \cite{hailpern06}.
The current ubiquity of the term \emph{model-driven
software engineering} is both a recognition of these benefits
and an appreciation of the reality that we are not 
using these models as effectively as we may hope.  

%The utility of model-based SE is widely acknowledged.
Model based software engineering has been put into practice by many groups.
The Object Management Group \cite{omg03}, 
Microsoft \cite{greenfield04}, and Lockhead Martin
\cite{waddington03}, have all adopted model
based development as part of their software engineering
process.
%For example, the 
%Object Management Group
%(OMG) has recently adopted a \emph{model-driven architecture}
%framework with goals of ``portability, interoperability and reusability
%through architectural separation of concerns." \cite{omg03}  
%Also, Microsoft has been developing a \emph{Software Factory} concept
%that leverages models with the goal of automation of the software
%development process~\cite{greenfield04}.
%And, at Lockheed Martin, engineers have developed an 
%integrated modeling method called 
%\emph{Model Centric Software Development}
%that uses ``automated generation of partial implementation artifacts," 
%reverse engineering to integrate legacy
%assets, and model verification and checking~\cite{waddington03 }
And just as their are search based tools available to researchers,
tools to support model based development have been developed.
These include tools for
distributed agent-based simulations \cite{clancey96a}, 
discrete-event simulation \cite{law00,harrell00,kelton02},
continuous simulation (also called system dynamics) \cite{hamid91,sterman00},
state-based simulation \cite{akhavi93,harel90,martin00}, 
and rule-based simulations~\cite{mi90}. 
One can find models used in the requirements phase 
(see \tion{ddpDes} for a description of such a tool, DDP),
refactoring of designs using patterns \cite{france03}, 
software integration \cite{denno03},
model-based security \cite{jurjens06}, 
and performance assessment \cite{bals04}.


Recently, AI has been successful applied to model based software engineering.
For example, Whittle uses deductive learners to
generate lower-level UML designs (state charts)
from higher-level constructs (use case diagrams)~\cite{whittle06}.
More generally, the field of search based software engineering augments
model based development with metaheuristic techniques, 
like those discussed in \tion{introMH} and \tion{metaheur}, 
to explore a model.
Such heuristic methods are hardly complete but as remarked in
\cite{clarke03}: ``...software engineers face problems
which consist, not in finding \emph{the} solution, but rather, in
engineering an \emph{acceptable} or \emph{near optimal solution}
from a large number of alternatives."

%We therefore endorse athe thesis that models
%are currently used throughout the software development process --
% from requirements and design to testing and performance evaluation
% -- and that the use of such models will only increase.  
%We also
% recognize that, even with tool support, creation of practical and
% functional models is a resource-intensive activity, especially in
% terms of human intelligence.  Effective use of models requires
% that they be allowed to evolve through the software development
% process.  Other researchers  have recognized that ``designers must
% be able to examine various design alternatives quickly and easily
% among myriad and diverse {\em configuration possibilities}''\cite{gray06}.

\section{Metaheuristics}\label{sect:introMH}
Metaheuristic search is the catch-all phrase for
a set of high-level heuristics that are abstract enough to 
be applied to many different fields.
A central idea to all metaheuristic search techniques
is that most interesting real-world problems
are far too difficult to solve exactly.
Therefore heuristic techniques must be used
to find near-optimal solutions.
Since heuristics techniques have no performance
or convergence guarantees several different techniques
have been developed, so that if a problem
defeats one technique another may be used.

The most commonly used metaheuristic search
techniques are simulated annealing,
evolutionary algorithms, and tabu search.
These techniques will be discussed in 
\tion{metaheur}.  
This section will also discuss important ways to
characterize metaheuristic techniques, such as
mechanisms for escaping local optima and
candidate solution encoding.
These characteristics will be revisited in
\tion{itlChars} to see how they can be applied
to our new metaheuristic search technique,
Iterative Treatment Learning.
Occasionally we will review 
techniques from statistics and linear algebra that 
are used on some problems, which will be 
discussed in \tion{sbse} and as they relate to
search based software engineering.

\section{Machine Learning as a Search Heuristic}
It will be shown in this thesis that a machine learning
technique has been successfully used as search heuristic.
The machine learning technique used is treatment learning
\cite{me03c}
and the search technique we call 
{\it Iterative Treatment Learning} (ITL),
since the treatment learner is called in an iterative fashion.
ITL has some characteristics that differentiate it from other
mainstream metaheuristic search techniques.
Most metaheuristics' base heuristic have a 
statistical or geometric interpretation.
The base heuristic for ITL is treatment learning, 
which is considered a machine learning algorithm.
Another important difference is that ITL's near-optimal
solution is a {\it partial description} rather than a
{\it complete description}.
The difference between these two types 
of solutions is that partial descriptions
do not comment on all the available attributes 
and these comments are not {\it exact} value assignments,
but are value {\it range} assignments
(see \tion{solutionForm} for a more complete
discussion of partial descriptions).


Menzies {\it et. al.} introduced 
%{\it Iterative Treatment Learning}
ITL
\cite{me02c} as an alternative search
heuristic in requirements engineering.
While their work was interesting and novel,
the methodology used to demonstrate
the performance of ITL could use much improvement.
A single model was used in their study,
they did not explore design options within ITL,
and ITL was not placed in the context of metaheuristic search.

Another version of ITL called SPY has also been introduced
by Clarke \cite{clark06}.  SPY is an integrated model
development and search environment.
The search algorithm used by SPY is an ITL method
with a slightly different search strategy and a 
more efficient treatment learner.
SPY finds range restrictions to the model's inputs to
confine model output behavior to specified modes.
The original use case for SPY was that these behavior modes
would be temporal properties in models with real valued inputs.
In \cite{clark06} SPY was only applied to a small number of simple models.
In addition, there was no comparative analysis of SPY to benchmark it
against other tools or analysis methods
And like the original work on ITL, SPY was not presented in a search context.
SPY will be described in more detail in \tion{SPY}.


\section{Machine Learning}
Machine learning is any algorithmic process that generalizes
from a specific data set to a theory that can
be applied to new unseen data.
One type of machine learner is the classifier;
\tion{ml} will describe several different
classifiers, including treatment learning.
Classifiers build theories that can be used
to assign one of the target labels to unseen examples.
Contrast this with the typical use of metaheuristic search techniques.
Search techniques produce near-optimal solutions without
attempting to generalize anything learned during their search.
Even when viewing ITL as a search technique, which seeks a near-optimal
solution, its solution is in a form that captures
generalizations that can be used after the search.

\section{Problem Statement}
\textbf{Can ITL be used as a search technique for models from different stages of the software life cycle?}

To address that question the following topics
will be discussed in the rest of this thesis.

\subsection{Rethinking ITL as metaheuristic search}
ITL has previously been presented as a machine learning 
technique. 
In this thesis we argue that ITL
should be considered a metaheuristic search
technique that has novel characteristics not
common in other metaheuristic search techniques.

\subsection{Improved methodology demonstrating ITL's ability to optimize
early stage models in requirements engineering} 
The use of ITL to investigate early project requirements engineering
has been limited to a single model.  Other uses of ITL
have focused on models with a small number of independent variables
(fewer than 40).
This thesis uses three models for early project requirements engineering
that have 99, 83, and 58 independent variables, respectively.
The new methodology also includes the development of extreme
sampling, a new discretization method for ITL.


\subsection{Can SPY be used in late stage life cycles?}
Previous work with the SPY framework only used toy models
which didn't have any previous analysis.
This thesis uses the SPY framework on models that have
been used elsewhere in the literature, hence
a comparison of previous results with results generated
by SPY is possible.
We will investigate the use of SPY
on real world models from the aerospace industry
and compare the performance of SPY with a commercial
tool.
Lastly, we will investigate biomathematical models,
using SPY to restrict the output behavior modes of
these models.

\section{Previous Work on Problem Statement}
Treatment learning has been developed and tested extensively by
Menzies, Hu, Clarke, \etal \cite{me01i,me01c,me02a,ying02}.
The machine learning properties of treatment learning will no
be explored further in this thesis.
ITL has been previously developed by Menzies \etal \cite{fea01,me01d}.
That work focused on either models not presented in this thesis
or just one of the requirements models, \aerons, used in
\chap{casestudies}.
In addition, the SPY framework has developed by Clarke
and Menzies \cite{clark06}.
That work focused on the validation of the SPY framework's
methodology using small toy problems developed for
testing purposes.

\section{Contribution}
This thesis makes the following novel contributions towards
addressing the problem statement \\
\bi
{Presents ITL in a metaheuristic search context.}

{Introduces the concept of an extreme sampling discretizer, and
develops three variants of a discretizer.}

\item Three cost/benefit models, including two not previously analyzed, 
are used to

\setlength{\topsep}{-12pt}\setlength{\partopsep}{-12pt}
\begin{itemize}
\item Conduct a study of the effect of parameter settings to extreme sampling's
performance according to numerous criteria
\item Compare performance of ITL with extreme sampling discretizer 
vs.\ diagonal striping discretizer
\item Compare performance of ITL vs.\ simulated annealer
\end{itemize}
\setlength{\topsep}{+15pt}\setlength{\partopsep}{+15pt}

\item A total of five models, 
from varied domains and with a higher complexity than 
models previously studied, are analyzed by SPY to find
range restrictions that restrict the models' output
behavior to specified modes.
\ei

The rest of this thesis will be structured around
these contributions in the following manner:
ITL will be placed in the context of metaheuristic
search in \tion{metaheur} and \chap{itl},
extreme sampling and its three variants will be
discussed in \chap{itl},
the three cost/benefit models will be studied,
along with extreme sampling, in \chap{casestudies},
and the five models analyzed by SPY will be spread over
\chap{properties} and \chap{others}.


%\section{ {\it Model execution?} }
%Should I discuss our main use case here,
%which is the iterative execution of possibly slow
%models, that are being constrained by
%each iteration of ITL?



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