\section{Background}
\input{tables/cocomo}
\subsection{Models}\label{subsec:models}
In this section we will present the USC software engineering models that were used in this work and which influence the fitness funtion used.
\subsubsection{Effort - COCOMO II}
The COCOMO II model~\cite{boehm00b} is and evolution of the original COCOMO 81 model~\cite{boehm81} which was published by Barry Boehm. Bboth of these models have the same form refered to in \eq{cogen}, where \textit{$c_{i}$} is the sum of the cost drivers and \textit{A} is domain specific. 

{\begin{equation}\label{eq:cogen}
Effort = A*(c_{i})(Size)^{Exponent}
\end{equation}}

The difference is in what \textit{Size} and \textit{Exponent} represent. In COCOMO 81, \textit{Size} is dependent on deliverable source lines of code (DSI), while for COCOMO II it represents source lines of code (SLOC), fuction points (FP) and object points. In addition, the \textit{Exponent} in COCOMO 81 is actually a fixed constant that is selected as a function of development mode, which only exists in COCOMO 81, while in COCOMO II it is dependent on scale factors, which were introduced in COCOMO II. This is evident in \eq{coc2}. Other differences, as well as a guide to converting from COCOMO 81 to COCOMO II, is further elaborated on my D.J. Reifer and B. Boehm~\cite[reifer99]. For this thesis, we will be exclusively using COCOMO II.

\begin{figure}
{\scriptsize
\begin{center}
\begin{tabular}{crrrrrrr}
    &  &  vl&    l&    n&    h&   vh&   xh\\\hline
\multicolumn{8}{l}{{\em Scale factors:}}\\
flex&    & 5.07& 4.05& 3.04& 2.03& 1.01&  \\
pmat&    & 7.80& 6.24& 4.68& 3.12& 1.56&\\
prec&    & 6.20& 4.96& 3.72& 2.48& 1.24&   \\
resl&    & 7.07& 5.65& 4.24& 2.83& 1.41& \\
team&    & 5.48& 4.38& 3.29& 2.19& 1.01&  \\\hline
\multicolumn{8}{l}{{\em Effort multipliers:}}\\
acap&    & 1.42& 1.19& 1.00& 0.85& 0.71 & \\   
aexp&    & 1.22& 1.10& 1.00& 0.88& 0.81&    \\ 
cplx&    & 0.73& 0.87& 1.00& 1.17& 1.34& 1.74\\
data&    &     & 0.90& 1.00& 1.14& 1.28&     \\
docu&    & 0.81& 0.91& 1.00& 1.11& 1.23&     \\
ltex&    & 1.20& 1.09& 1.00& 0.91& 0.84&     \\
pcap&    & 1.34& 1.15& 1.00& 0.88& 0.76&     \\
pcon&    & 1.29& 1.12& 1.00& 0.90& 0.81&     \\
plex&    & 1.19& 1.09& 1.00& 0.91& 0.85&     \\
pvol&    &     & 0.87& 1.00& 1.15& 1.30&     \\
rely&    & 0.82& 0.92& 1.00& 1.10& 1.26&     \\
ruse&    &     &0.95& 1.00& 1.07& 1.15& 1.24\\
sced&    & 1.43& 1.14& 1.00& 1.00& 1.00&\\
site&    & 1.22& 1.09& 1.00& 0.93& 0.86& 0.80\\
stor&    &     &     & 1.00& 1.05& 1.17& 1.46\\
time&    &     &     & 1.00& 1.11& 1.29& 1.63\\
tool&    & 1.17& 1.09& 1.00& 0.90& 0.78&    
\end{tabular}
\end{center}}
\caption{Co-efficient values according to the precalibrated COCOMO II.2000 model.}\label{fig:inside}
\end{figure}

The COCOMO effort predictors estimates  development effort in terms of person months where one month is 152
hours (and includes development and management hours). 
In COCOMO, the  {\em scale factors} $SF_i$ of \ref{fig:cparems}
effect effort exponentially (on KSLOC, i.e. Thousand Source Lines of Code)
while {\em effort multipliers} $EM_j$
effect effort linearly:

{\small\begin{equation}\label{eq:coc2}
PM=a*\left(KSLOC^{\left(b+0.01*\sum_{i=1}^{5}SF_i\right)}\right)*\left(\prod_{j=1}^{17}EM_j\right)
\end{equation}}
where KSLOC is estimated
directly or computed from a function point analysis;
 $SF_i$ and $EM_j$ are the {\em scale factors};
{\em effort multipliers} of \ref{fig:cparems};
and
$a$ and $b$ are  domain-specific parameters. In our NASA data,
these ranges\begin{equation}\label{eq:ab}
\left( 3.72 \le a \le 9.18 \right) \wedge \left(0.88 \le b \le 1.09\right) 
\end{equation} 
With the effort multipliers, off-nominal ranges (i.e. \{vl=1, l=2, h=4, vh=5, xh=6\}) change the prediction by some amount.
In the special case of the nominal range (i.e. \{n=3\}), that amount is one; i.e. the nominal
range make no change to the prediction.
Hence, these  ranges  can be modeled as a straight line $y=mx+b$
passing through the point $\{x,y\}$=$\{3,1\}$. Such a line has a y-intercept
of $b=1 - 3m$. Substituting this value of $b$ into $y=mx+b$ yields:
\begin{equation}\label{eq:lineem}\small
\begin{array}{l}
\forall x \in \{1..6\}\; EM_i=m_a(x-3) + 1
\end{array}
\end{equation}
where  $m_a$ denotes the effect of effort multiplier $a$ on {\em effort}.

The effort multipliers form
into two sets:
\begin{enumerate}
\item
The {\em positive effort EM} features, with slopes $m^+_a$, that are proportional to effort. 
These features are:
cplx,
data,
docu,
pvol,
rely,
ruse,
stor, and
time.
\item
The
{\em negative effort EM} features, with slopes $m^-_{a}$,
are inversely proportional to effort.
These features are 
acap,
apex,
ltex,
pcap,
pcon,
plex,
sced ,
site,
tool.
\end{enumerate}
Based on prior work~\cite{boehm00a}, we can describe
the
space of known tunings for COCOMO effort multipliers to be 
\begin{equation}\label{eq:mem}\small
\left(0.073 \le m^+_a \le 0.21\right) \wedge
\left(-0.178 \le m^-_a \le -0.078\right)
\end{equation}
Similarly, using experience from 161 projects~\cite{boehm00a},
we can say that the space of known tunings for the COCOMO scale factors 
(prec, flex, resl,team, pmat)
are:
\begin{equation}\label{eq:linesf}\small
 \forall x \in \{1..6\}\; SF_i=m_b(x - 6) \wedge \left(
-1.56	\le m_b \le -1.014\right)
\end{equation}
where  $m_b$ denotes the effect of scale factor $b$ on {\em effort}.

Note that the above ranges for the slopes were obtained by finding the average slope for each COCOMO attribute for both effort multipliers and scale factors over the range of values of that attribute.

\subsubsection{Schedule }
The COCOMO schedule predictor estimates  development time in terms of elapsed calendar months.
This model is largely based on the COCOMO effort in that it uses
that attributes, there values, and the calibrated coefficients (i.e, $a$ and $b$).
The following are the equations for calculating months:

{\small\begin{equation}\label{eq:mon}
\begin{array}{c}
F=d+0.2*\left(0.01*(\sum_{i=1}^{5}SF_i)\right)\\
TDEV=\left[c*(PM_{NS})^{F}\right]*SCED\%\div100
\end{array}
\end{equation}}
where $PM_{NS}$ is the effort calculated without the inclusion of SCED, 
$SF_i$ are the {\em scale factors} of \ref{fig:cparems},
$c$ and $d$ are  domain-specific parameters that can be calibrated,
and $SCED\%$ is the percentage of schedule relative to the nominal 
schedule. 

\ref{fig:sced} shows the value of this parameter based on 
SCED.$TDEV$ is the development time in months calculated by this model,
and $F$ is referred to as the scaling exponent for schedule.

\begin{figure}[!h]
{\scriptsize
\begin{center}
\begin{tabular}{c|c}
SCED&SCED\%\\\hline
1&75\\
2&85\\
3&100\\
4&130\\
5&160\\
\end{tabular}
\end{center}
} \caption{The values of SCED\%}\label{fig:sced}
\end{figure}

\subsubsection{Defects - Coqualmo} 
The Coqualmo model is used to estimate the amount if defects/KSLOC within a software project.
COQUALMO has two core models, used three ways:
\begin{itemize}
\item
 The {\em defect introduction} model is similar to
\ref{eq:coc2}; i.e. settings to \ref{fig:cparems}'s effort multipliers and scale factors
map to predictions about number of defects.
\item
The {\em defect removal} model represents how various tasks (peer review, execution-based
testing, and automatic analysis) decrease the introduction of defects.
\item
The above two models are repeated three times 
for
defects introduction \&  removal for
requirements, design, or coding.
\end{itemize}

\input{coqualmo}

COQUALMO follows the same convention as COCOMO for the effort multipliers; i.e.
nominal values ($n=3$) add nothing to the predicted number of defects. As
above, COQUALMO is:
\begin{equation}\label{eq:linedefintro}\small
\begin{array}{l}
 \forall x \in \{1..6\}\; EM_i=m_c(x-3) + 1
\end{array}
\end{equation}
where  $m_c$ denotes the effect of $c$ on {\em defect introduction}.

The effort multipliers and  scale factors form two sets:
\begin{enumerate}
\item The {\em positive defect} features, with slopes $m^+_c$, that are proportional
to the estimated introduced defects. These features are 
flex,
data,
ruse,
cplx,
time,
stor, and 
pvol.
\item The {\em negative defect} features, with slopes $m^-_c$, that are inversely proportional
to the estimated introduced defects. These features are 
acap,
pcap,
pcon,
apex,
plex,
ltex,
tool,
site,
sced,
 prec,
resl,
team,
pmat,
rely, and
docu.
\end{enumerate}
The space of tunings for  defect introducing features are:
\begin{equation}\label{eq:coq}\small
\begin{array}{c}
requirements\left\{
\begin{array}{c}
0 \le m^+_c \le 0.112\\
-0.183 \le m^-_c \le -0.035
\end{array}
\right. \\
~\\
design \left\{
\begin{array}{c}
0 \le m^+_c \le 0.14\\
-0.208 \le m^-_c \le -0.048
\end{array}
\right. \\
~\\
coding \left\{
\begin{array}{c}
0 \le m^+_c \le  0.140\\
-0.19 \le m^-_c \le -0.053
\end{array}
\right.
\end{array}
\end{equation}

\noindent
The space of tunings for  defect removal features are:
\begin{equation}\label{eq:linedefrem}\small
\begin{array}{rl}
\forall x \in \{1..6\} &SF_i=m_d(x - 1)\\
requirements: 	& 0.08 	\le m_d \le 0.14 \\
design: 		& 0.1 	\le m_d \le 0.156 \\
coding: 		& 0.11 	\le m_d \le 0.176 \\
\end{array}
\end{equation}
where  $m_d$ denotes the effect of  $d$ on {\em defect removal}.

\subsubsection{Threat}\label{sec:threat}

The THREAT model
returns a heuristic estimate of the threat of a
schedule over run in the project. 
This estimation model is dependent upon
the COCOMO effort multipliers

Internally, THREAT contains dozens of tables of the
form of \ref{fig:madeg}. Each such table  adds some ``threat'' value
to the overall project risk when multiplied by
the effort multiplier values of the corresponding COCOMO attributes.
 There are six major categories: schedule, product, personnel, process, platform and reuse.
After the threat for each category is calculated, the sum is
normalized to produce the final threat rating.

\begin{figure}[!t]
{\scriptsize
\begin{center}
\begin{tabular}{|p{0.8in}|c|c|c|c|c|}\cline{2-6}
\multicolumn{1}{c|}{} &rely=&rely=&rely=&rely=&rely=\\
\multicolumn{1}{c|}{}& very & low &nominal & high & very\\
\multicolumn{1}{c|}{}&  low&  & &  &  high\\\hline sced= very
low& 0 & 0 & 0  &1  &2\\\hline sced= low     & 0 &0  & 0 &
0&1\\\hline sced= nominal& 0 & 0 & 0  &0  &0\\\hline sced= high&
0& 0 & 0  & 0 &0\\\hline sced= very high& 0 & 0 & 0  &0 &0\\\hline
\end{tabular}
\end{center}
} \caption{An example risk table}\label{fig:madeg}
\end{figure}

\ref{fig:madeg} can be represented as
an exponentially decaying function that peaks in one corner of the risk table
at a value of two.
All the tables peak at either a value of two  or four.
Since this model is heuristic in nature, the exact height of the peak is
not certain.
When we perform Monte Carlo simulations over THREAT, we vary the height of
the peak by 
a random factor $0.5 \le x \le 1$ if the peak is four, and $0.5 \le x \le 1.5$ if the peak is two.


\begin{figure}
\begin{ccode}
Total_threat =		
(Schedule_threat + Product_threat + Personnel_threat + Process_threat + Platform_threat + Reuse_threat)/3.73 

Schedule_threat=
Sced_Rely_threat + Sced_Time_threat + Sced_Pvol_threat + Sced_Tool_threat + Sced_Acap_threat + Sced_Aexp_threat + 
Sced_Pcap_threat + Sced_Plex_threat + Sced_Ltex_threat + Sced_Pmat_threat

Product_threat =
Rely_Acap_threat + Rely_Pcap_threat + Cplx_Acap_threat + Cplx_Pcap_threat + Cplx_Tool_threat + Rely_Pmat_threat + 
Sced_Cplx_threat + Sced_Rely_threat + Sced_Time_threat + Ruse_Aexp_threat + Ruse_Ltex_threat

Personnel_threat =
Pmat_Acap_threat + Stor_Acap_threat + Time_Acap_threat + Tool_Acap_threat + Tool_Pcap_threat + Ruse_Aexp_threat + 
Ruse_Ltex_threat + Pmat_Pcap_threat + Stor_Pcap_threat + Time_Pcap_threat + Ltex_Pcap_threat + Pvol_Plex_threat + 
Sced_Acap_threat + Sced_Aexp_threat + Sced_Pcap_threat + Sced_Plex_threat + Sced_Ltex_threat + Rely_Acap_threat + 
Rely_Pcap_threat + Cplx_Acap_threat + Cplx_Pcap_threat + Team_Aexp_threat

Process_threat =
Tool_Pmat_threat + Time_Tool_threat + Tool_Pmat_threat + Team_Aexp_threat + Team_Sced_threat + Team_Site_threat + 
Sced_Tool_threat + Sced_Pmat_threat + Cplx_Tool_threat + Pmat_Acap_threat + Tool_Acap_threat + Tool_Pcap_threat + 
Pmat_Pcap_threat

Platform_threat =
Sced_Time_threat + Sced_Pvol_threat + Stor_Acap_threat + Time_Acap_threat + Stor_Pcap_threat + Pvol_Plex_threat + 
Time_Tool_threat

Reuse_threat =
Ruse_Aexp_threat + Ruse_Ltex_threat
\end{ccode}
\caption{THREAT: the calculations.}\label{fig:srm}
\end{figure}


\begin{figure*}
\begin{center}
{\scriptsize
\begin{tabular}{l|rrrrrrr}
&& vl&  l&  n&  h& vh& xh\\\hline
&rely\\
sced&        vl&  &  &  &  1&  2&\\ 
     &    l&  &  &  &  &  1& \\\hline
&cplx\\
sced&          vl&  &  &  &  1&  2&  4\\
&         l&  &  &  &  &  1&  2\\
&         n&  &  &  &  &  &  1\\\hline
&time\\
sced&        vl& & &  &  1&  2&  4\\
 &        l& & &  &  &  1&  2\\
  &       n& & &  &  &  &  1\\\hline
&pvol\\
sced&        vl&  &  &  &  1&  2& \\
&         l&  &  &  &  &  1& \\\hline
&tool\\
sced&        vl&  2&  1&  &  &  & \\
 &        l&  1&  &  &  &  & \\\hline
&pexp\\
sced&        vl&  4&  2&  1&  &  & \\
&         l&  2&  1&  &  &  & \\
&         n&  1&  &  &  &  & \\\hline
&pcap\\
sced&        vl&  4&  2&  1&  &  & \\
  &       l&  2&  1&  &  &  & \\
   &      n&  1&  &  &  &  & \\\hline
&aexp\\
sced&        vl&  4&  2&  1&  &  & \\
     &    l&  2&  1&  &  &  & \\
      &   n&  1&  &  &  &  & \\\hline
&acap\\
sced&        vl&  4&  2&  1&  &  & \\
  &       l&  2&  1&  &  &  & \\
  &       n&  1&  &  &  &  & \\\hline
&ltex\\
sced&        vl&  2&  1&  &  &  & \\
     &    l&  1&  &  &  &  & \\\hline
&pmat\\
sced&        vl&  2&  1&  &  &  & \\
 &        l&  1&  &  &  &  & \\
\multicolumn{3}{c}{}\\
\multicolumn{3}{c}{}\\
\end{tabular}~~~~~~~~~~~~~~~~~~~~~~~~
\begin{tabular}{l|rrrrrrr}
          && vl&  l& n\\\hline
&acap\\
rely&         n&  1&  &   \\
&         h&  2&  1& \\
 &       vh&  4&  2&  1 \\\hline
&pcap\\
rely&         n&  1&  & \\
     &    h&  2&  1& \\
      &  vh&  4&  2&  1 \\\hline
&acap\\
cplx&         h&  1&  & \\
&        vh&  2&  1& \\
 &       xh&  4&  2&  1 \\\hline
&pcap\\
cplx&         h&  1&  & \\
     &   vh&  2&  1& \\
      &  xh&  4&  2&  1 \\\hline
&tool\\
cplx&         h&  1&  & \\
     &   vh&  2&  1& \\
      &  xh&  4&  2&  1 \\\hline
&pmat\\
rely&         n&  1&  &   \\
     &    h&  2&  1&    \\
      &  vh&  4&  2&  1  \\\hline
&acap\\
pmat&        vl&  2&  1& \\
     &    l&  1&  & \\\hline
&acap\\
stor&         h&  1&  & \\
   &     vh&  2&  1& \\
   &     xh&  4&  2&  1 \\\hline
&acap\\
time&         h&  1&  & \\
    &    vh&  2&  1& \\
    &    xh&  4&  2&  1 \\\hline
&acap\\
tool&        vl&  2&  1& \\
    &     l&  1&  & \\\hline
&pcap\\
tool&        vl&  2&  1& \\
     &    l&  1&  & \\
\end{tabular}~~~~~~~~~~~~~~~~~~~~~~~~
\begin{tabular}{l|rrrr}
&& vl&  l&  n \\\hline
&aexp\\
ruse&         h&  1&  & \\
     &   vh&  2&  1& \\
      &  xh&  4&  2&  1 \\\hline
&ltex\\
ruse&         h&  1&  & \\
     &   vh&  2&  1& \\
      &  xh&  4&  2&  1\\\hline
&pcap\\
pmat&        vl&  2&  1& \\
     &    l&  1&  & \\\hline
&pcap\\
stor&         h&  1&  & \\
 &       vh&  2&  1& \\
  &      xh&  4&  2&  1 \\\hline
&pcap\\
time&         h&  1&  & \\
     &   vh&  2&  1& \\
      &  xh&  4&  2&  1 \\\hline
&pcap\\
ltex&        vl&  4&  2&  1 \\
     &    l&  2&  1& \\
        & n&  1&  & \\\hline
&pexp\\
 pvol&        h&  1&  & \\
      &  vh&  2&  1& \\\hline
&pmat\\
 tool&       vl&  2&  1&    \\
      &   l&  1&  &    \\\hline
&tool\\
 time&       vh&  1&  & \\
      &  xh&  2&  1& \\\hline
&aexp\\
 team&       vl&  2&  1&   \\
      &   l&  1&  &    \\\hline
&sced\\
team&        vl&  2&  1&    \\
     &         l&  1&  &    \\\hline
&site\\
team&        vl&  2&  1&    \\
     &        l&  1&  &   
\end{tabular}}
\end{center}
\caption[THREAT: the details.]{THREAT: the details. For example, 
looking at the top-left matrix,
the {\tt Sced\_Rely\_risk} is highest when the reliability
is very high but the schedule pressure is very tight.}\label{fig:madachy}
\end{figure*}



\input{figures/default}

\subsection{Ranking Methods}
\textbf{There are two ranking methods that can be used by STAR2. These are {\em Bayesian ranking} and {\em Energy ranking}. The former is the main ranking method used by STAR2, while the latter is included in STAR2 for verifying that the Bayesian ranking is valid.}

\subsubsection{Support-Based Bayesian Ranking}\label{sec:bayrank}

STAR2 ranks the features ranges
seen in $K$ runs of a simulated annealer by dividing the $K$ runs into:
\begin{itemize}
\item {\em Best:} those associated with the  BEST\% solutions
(i.e. those with the BEST\% {\em least} energy); 
\item And the {\em rest} (i.e. the other 100-BEST\% of solutions).
\end{itemize}
It then computes the probability that a range is found in $best$.
using Bayes' Theorem.
Informally,
the
theorem says $next=old*new$ i.e. what we'll believe {\em next}
comes
from how {\em new} evidence effects {\em old} beliefs.  More
formally:\begin{equation}\label{eq:n}\small
P(H|E)=P(E|H) P(H)\; /\; P(E)\end{equation}
i.e. using
evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$.
The theorem calculate a  posteriori  probability
$P(H|E)$. 
Simple  Bayes classifiers are often called ``naive'' since they assume
independence of each feature. While this assumption
 simplifies the implementation  
(frequency
counts are required only for each feature),
 it is possible
that
correlated events are missed by this ``naive'' approach.
Domingos and Pazzini show theoretically
that the independence assumption is a problem in a vanishingly small percent
of cases~\cite{domingos97optimality}. This explains the repeated
empirical result that, on average, seemingly naive Bayes classifiers perform as well
as other seemingly more sophisticated schemes (e.g. see Table~1 in~\cite{domingos97optimality}).


When applying the theorem, {\em likelihoods}
are computed from observed
frequencies, then normalize to create
probabilities (this normalization cancels out $P(E)$ in \ref{eq:n}, so it need not be computed).
For example, after $K=10,000$ runs divided into  1,000 lowest 10\% {\em best} solutions and 9,000
{\em rest}, the  range $rely=vh$ might appears 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:

{\scriptsize
\begin{eqnarray}\nonumber
E&=& (reply=vh)\\\nonumber
P(best)&=&1000/10000 = 0.1\\\nonumber
P(rest)&=&9000/10000 = 0.9\\\nonumber
freq(E|best)&=&10/1000 = 0.01\\\nonumber
freq(E|rest)&=&5/9000 = 0.00056\\\nonumber
like(best|E)&=&freq(E|best) \cdot P(best)=0.001\\\nonumber
like(rest|E)&=&freq(E|rest) \cdot P(rest)= 0.000504\\\label{eq:ten}
P(best|E)&=& \frac{like(best|E)}{like(best|E) + like(rest|E)}=0.66
\end{eqnarray}}
Previously~\cite{clark05}
we have found that  \ref{eq:ten} 
is a poor ranking heuristic
since it is distracted by low frequency evidence.
For example, note how
the probability of $E$ belonging to the best class
is moderately high even though its support is very low; i.e. $P(best|E)=0.66$ but
$freq(E|best) = 0.01$. 

To avoid such unreliable low frequency evidence, we augment \ref{eq:ten}
with a support term.
Support should $increase$ as the frequency of a range $increases$,  i.e. 
$like(x|best)$ is a valid support measure.
STAR2 hence ranks ranges via
\begin{equation}\label{eq:ps}\small
P(best|E) * support(best|E) = \frac{like(x|best)^2}{like(x|best) + like(x|rest)}
\end{equation}

\subsubsection{Score-Based Energy Ranking}\label{sec:enrank}

While the main ranking algorithm used by STAR2 is the Bayesian method 
explained above, another very basic and intuitive baseline method was 
implemented to test Bayesian ranking. This method is Score-Based Energy
Ranking. Basically this ranking scheme uses the means of the results 
from the Simulated Annealing simulations to assess and rank COCOMO II 
attribute-value combinations. The mean results are based the scores 
generated by the Energy Function of the SA algorithm. These scores are 
basically the distance from the origin to a point in three dimensional 
space whose coordinates are the normalized Effort, Defects, and Threat scores from our models. Energy Ranking works as follows:

\begin{itemize}
\item[1.] {\em DATA COLLECTION:}
This is done while the SA algorithm is 
running whenever the algorithm generates a new candidate best result.
 The attribute-value combinations that are used for that candidate are 
detected, and data concerning the score is stored for each of these used attribute-value combinations.
\newline
\item[2.] {\em MEAN SCORE CALCULATION:}
After the SA goes through its K 
runs, the mean scores for all the attribute-value combinations are calculated. 
After this step, the attribute-value combinations are ready to be ranked.
\end{itemize}


While Energy Ranking seems to be simple enough, is has one main 
potential weakness: outliers in simulations could taint the score of
an otherwise good attribute-value combination, causing its rank to 
decrease compared to seemingly worse combinations. This issue is not
present in Bayesian Ranking since it is dependent on frequency and support rather than scores.

\subsection{The STAR Algorithm}To apply \ref{eq:ps}, STAR2 runs in six phases.
In terms of standard machine 
learning theory, step 1 generates a training set; steps 2,3,4 do some generalization;
and step 5 tests the learned theory on data not seen during training.

\begin{description}
\item[1. {\em SAMPLE:}]
To sample the ranges from the models,
STAR2 runs the simulated annealer  $K_1$ times.
\item[2. {\em DISCRETIZE:}]
The data seen in the $K_1$ samples is then discretized into $D=10$ bins.
Discretization converts a continuous range into a histogram
with $n$ break points $b_1\ldots b_n$ where $\left(\forall i < j : b_i \le b_j\right)$. 
After discretization,
many observations can fall into the same range
between $b_i$ and $b_{i+1}$
at frequency counts $c_i$. This study used equal width discretization; i.e. 
\[\forall i,j:
\left(b_i - b_{i-1}\right) = 
\left(b_j - b_{j-1}\right)\]
\item[3. {\em CLASSIFY:}]
The ranges are then classified
into those seen in BEST\% {\em best} or {\em rest}.
\item[4.
{\em RANK:}]
The ranges are then ranked in increasing order either using Support-Based Bayesian Ranking \ref{sec:bayrank}  or Score-Based Energy Ranking \ref{sec:enrank}.
\item[5.
{\em PRUNE:}]
STAR2 then runs $K_2$ experiments with the models where the top ranked ranges
$1..X$ ranges are pre-set and the
remaining ranges can be selected at random.
In terms of the business case for automated software engineering tools,
this step is crucial since it would rank new ASE tools alongside 
other methods. 
\item[6.
{\em REPORT:}]
STAR2 returns the $1..X$ ranges that  produce the least effort, defects, and threats.
\end{description}

To run our experiments, we had to apply our engineering judgment to set the parameters. The following are the default values:
\[K_1=10,000, K_2=1,000, D=10, BEST=10\%\]

%Initially, we planned experiments that varied these parameters,
%as well as trying other discretization policies.
%However, our initial results were so promising (see below) that we are not currently motivated
%to explore 
%other parameter settings (such an exploration is planned for future work).

Note that for Energy Ranking, the algorithm is slightly different. Energy ranking does not require the disretizing and the classifying steps 



\section{Related Work}
\subsection{Search Based Software Engineering}
%Here I will exapand what previous work in serach based software engineering has achieved and/or attempted. this includes techniques used as well as the aspects of software engineering and the softwre projects addressed.

The contribution of this thesis falls within the area of search based software engineering~\cite{clark03,harman01}. This is a diverse area of study, and also a young one, that has attempted to deal with many different phases of the software development life cycle. These vary from  software testing to requirements engineering, among others. This thesis, as the title suggests, deals with software process control. Search based software engineering (SBSE) is done by using a combination of a chosen search technique, combined with a fitness function that evaluates the results.

\subsubsection{Applications of SBSE}
SBSE is being studied for use in tackling many software engineering issues, some of which will be mentioned here and briefly described.

\paragraph{Project Planning and Cost Estimation}

In~\cite{aguilar01}, software project simulators, such as the likes of Stella, vensim, ithink and Posersim, are used to generate a serach space of possible decisions along with the outcome of using such decisions. This search space is passed to an evoutionary algorithm similar in concept to a genetic algorithm. By evaluating decisions using a fitness function based on how well the rule classifies project examples, this algorithm is able to generate a hierarchy of decision rules. They are able to demonstrate how applying these rules improves the management of the software project. Note that the model used for this system is project specific rather than an industry standard software engineering model.

In~\cite{antoniol04}, a scheme is developed for proejct management and allocating work loads to teams. The goal of this scheme is to determine the optimal flow of "work packages" (WP) and at the same time determine the optimal team organization given a predetermined staff allocation. This being an NP-Hard task, the authors elect to use search based techniques, genetic algorithms (GA) specifically. Note that each fo those issues has a dedicated GA for solving it, and that the fitness function is based on queuing theory~\cite{gross85}. Their system alternates back and forth between the two problems till equilibrium is achieved, after which the final output of development time is compared to a supplied deadline. If the deadline isn't met, rethinking staffing is recommended. In addition to this, simulation for different project senarios (involving reworking and/or abandonning parts of the project) is also undertaken. The estimation model is not specified. An Empirical study was conducted on a massive Y2K maintenance intervention conducted on a large financial software system from a European financial organization. Using this study they were able to demonstrate the ability of their scheme of being able to find an optimal or near-optimal solution, and hence reduce development time. A followup study was conducted~\cite{antoniol06} where hill climbing and simulated annealing were also used, and the results from all three algorithms were compared. GA was found to more efficient in finding the best solution; however, is was also found that the simpler methods (hill climbing, simulated annealing) also eventually catch up to GA given additional iterations.

In~\cite{kirsopp03}, case-based reasoning is used for predicting project effort. The mothod used for this, "Angel", is described as being close to k-nearest neighbor, and was used on the "Finnish" dataset. This dataset is comprised of 407 cases, each described by 90 features. It should be noted that these features aren't COCOMO features, rather they are specific to that particular dataset. It should also be noted that the COCOMO model, and standard models ingeneral, are critisized as being too specific to the dataset that they are derived from. In this study, feature subset selection is used in order to determine the most significat features to use in predicting the effort. In order to do that, three searh based methods were used: Random Search (RS), Hill Climbing (HC), and Forward Sequential Selection (FSS). While they all reduce the error rates compared to using all the features, HC and FSS produced the best results, with FSS edging out HC due to its quicker performance and more stable results.

\paragraph{Software testing}

In~\cite{baresel04}, the authors are using evolutionary testing that's based on genetic algorithms to generate test data for software projects. The main point of the paper is exploring a testability transformation~\cite{harman04(2)} algorithm that allows the evolutionary testing system used to handle code with loop-assigned flags. The system used was the Daimler Chrysler Evolutionary Testing System~\cite{wegener01} running on top of the Matlab Genetic and Evolutionary toolbox~\cite{pohlheim}. The empirical studies were conducted on several code bases, one of which was a the code for a car navigation system.

In~\cite{briand05}, a genetic algorithm based system is utilized in order to determine test cases where a given real-time system is apt to failure, effectively stress testing such systems. Failure here is defined as not being able to complete a time critical task within the time limits set for that task to be completed. The testing system prototype is called the Real-Time Test Tool (RTTT), and is based on using GAlib, a C++ genetic algorithm framework, and a POSIX compiant scheduler that emulates single processor execution. RTTT was used tin a case study on a generic avionics platform that was a joint effort between the software engineering institute , the Naval weapons center and IBM's federal sector division. In this senario and others, RTTT was found to be able to automatically generate test cases that were able to stress real-time systems. Note that a single GA execution run under this system took a mean time of 46.5 minutes.

In~\cite{li07}, regression testing and test case prioritization are the tasks being tackled. Test case prioritization is conducted due to the lack of enough resources to run all the regression test cases available for a project, and in order to improve the effectiveness of the regression tests being used. The main purpose of the paper is to compare several algorithms in there ability to generate prioritized test cases. The algorithms compared were greedy, additional-greedy, 2-optimal, hill climbing, and genetic algorithms. The first three are greedy algorithms that might settle for a local minimum solution. Three fitness functions were utilized and involved a percent measure of coverage of certain code aspects. After conducting empirical studies on code bases of varying sizes and with varying avalability of test suites, it was found that plain greedy search performed the worst, while all the other algorithms performed very closely to each other.

\paragraph{Automated maintenance}

The authors of~\cite{mitchell06} use a tool called ``Bunch'' in order to generate abstract high level representations of software. It does so by clustering module dependency graphs (MDG) using a serach algortithm that is integrated within Bunch to examine a small subset of all possible clustering outcomes. The algorithm used within Bunch is hill climbing, with the option of using simulated annealing to avoid getting stuck in local optima. Note that the MDG's are produced by other language specific tools, making Bunch language independent. However, due to the nature of the algorithms used, the clustering results aren't always identical, and it isn't always clear why MDG's are clustered the way they are, sometimes requiring user intervention to clear things up a bit. Case studies are demonstrated on the dot graphing tool, the korn shell and a proprietary AT\&T filesystem, showing how it is possible using the tool to generate a high level abstration of the software. This is ultimately meant to facilitate software maintanence on software engineers by giving them an overview of the software that is simpler to understand.

Automated refactoring of code is eplored in~\cite{okeeffe06}. This refactoring is aimed at simplifying software maintenance by increasing flexibility, reusability and understadability according to the Object-Oriented Design Quality Assesment (QMOOD)~\cite{bansiya02}. A system called {\em CODe-Imp} was developed which uses the Java program model (JPM) to assess legal refactoring that is to be applied to the abstract sytax tree (AST) of java 1.4 based programs. Possible types of refactoring include moving fields and methods between the classes according to the hierarchy, and modifying the class hierarchy by inserting or removing intermediate classes. There were three search mothods used by this system: First-Ascent Hill Climbing (HC1), Steepest-Ascent Hill climbing (HC2), and Simulated Annealing (SA). In empirical testing, it was found that all three search methods generated quality improvements, with slighty different results. HC1 was the least computationally intensive, HC2had the most consistent results between runs, and SA producing the greatest improvement in some cases. In addition, use of the reusability fitness function produced insatisfactory results.

\paragraph{Other Applications}
Several other applications of SBSE exist, amog those are the following:
\bi
\item
\textbf{Requirements Engineering: }The Multi-objective next release problem (MONRP) is tackled for the first time in~\cite{zhang07}. This is an extension from the next release problem~\cite{bagnall01}, where instead of having a single release requirement or several requirements that are considered independent, there are multiple requirements that might conflict with each other. This is an NP-hard problem with a set of possible solutions that are along a Pareto front. This front needs to be defined so that a decision maker is able to pick an acceptable approximate Pareto optimal solution. The search algorithms used in this study were Random Search, used as the baseline sanity check, and three other algorithms based on genetic algorithms (GA). These were Single-Objective GA, Pareto GA, and Non-dominated Sorting GA II (NSGA-II)~\cite{deb02}. In the empirical study, all the GA's performed better than Random Search, and within the smaller problem instances showed little difference between there results. However, in the larger problem instances that have more requirements, NSGA-II outperformed the others in being able to trace the Pareto front, and further widened the gap between it and Random Search, while Single-Objective GA was better able to find the extreme ranges of the Pareto front. So, it was demonstrated that solving MONRP is feasible. 
\item
\textbf{Compiler Optimization: }Cohen et al.~\cite{cohen06} attempts to improve garbage collection for multi-threaded applications by clustering threads and creating sub-heaps for each cluster of threads, while maintaining a shared heap among all the thread clusters. The premise is that this will aid in parallelizing garbage collection, while at the sametime allowng this method to scale better than providing a heap for every individual thread for very highly threaded programs. The clustering system used is based on hill climbing, and uses thread dependency graphs to cluster the threads together. The empirical study was conducted on a peer-to-peer file sharing distributed application based on the .Net platform. By clustering the threads, the size of the shared heap was reduced by up to 30\%, thus contributing parallelizing garbage collection and increasing its efficiency.
\item
\textbf{Quality Assessment: }In~\cite{bouktif06(2)}, an approach is proposed to enhance predictive accuracy of software quality by reusing expertise from a several experts, and combining them to form and expert with the optimal predictive accuracy. This approach is modeled as an optimization problem in a large solution space, making it suitable for meta-heuristic search algorithms such as simulated annealing (SA) and genetic algorithms (GA). Both of those algorithms are used in the studies conducted in this paper, with empirical studies conducted on the JAVA API classes. Note that the specific aspect of software quality that is explored is object oriented software stability, where the quality metrics used to define this are dependent on the attributes of the software code base. The experts are modeled as Bayes Classifiers. Each expert is broken up into ``expertise chunks'' by limiting the input space. These chunks are then combined and modified to increase the final predictive accuracy. The search algorithm is resposible for chosing the chuncks, where the fitness function used is the predictive accuracy. The resulting combined expert was shown to be better than any individual expert in terms of predictive accuracy. This showed that even bad experts have good expertise to contribute, where a correlation was shown between the accuracy and the amount of experts used to form the final expert. It was also shown through this study that SA performed comparably to GA, while being slightly quicker.
\ei

\subsubsection{Fitness Functions}


\subsubsection{Search Algorithms}
There are a variety of metahuristic serach algorithms that are used in SBSE. Some of these are widely used and considered baseline algorithms, while others are custom made algorithms that rely on domain knowledge to optimize their performance.

\paragraph{Local Search}

\paragraph{Hill Climbing}

\paragraph{Genetic Algorithms}


\paragraph{Simulated Annealing}\label{par:sa}
Simulated Annealing belongs to the family of Monte Carlo algorithms.
{\em Monte Carlo} algorithms randomly sample the space
of possible controllable model states. 
A  {\em Metropolis} Monte Carlo algorithm~\cite{metropolis53}
creates new states
by  small mutations to some
{\em current} state. 
If a new state is ``better'' (as assessed via an
{\em energy function}),  it becomes the new {\em current}
state used  for future
mutations.  Otherwise, a Boltzmann acceptance
criteria is used to probabilistically   decide to
assess the new state: the worse the new state, the less
likely that it becomes the new current state.
The algorithm is silent on the mutation mechanism. For our experiments,
we freeze $\frac{2}{3}$ of the features and
randomly  select ranges for the rest.

In 1983, Kirkpatrick et.el.~\cite{kirkpatrick83} 
proposed a modification that was
inspired
by a procedure used to make the strongest possible glass. Initially,
glass is heated to allow atoms to move freely. The temperature
is then slowly lowered such that the atoms can find the stablest
configuration with lowest energy. 
A {\em simulated annealing} (SA) algorithm adds
a ``temperature'' variable to the Boltzmann accept criteria
such that, at high temperatures, it is more likely that the
algorithm will jump to a  new worst current state.
This allows the algorithm to jump out of local minima while
sampling the space of options. As the temperature cools,
such jumps become less likely and the algorithm reverts
to a simple hill climber.

With SA, better solutions have lower ``energy''
so the fitness function $E$ is defined such that $E \ge 0$ and
{\em lower} values are
$better$. 
For our purposes, we model effort ($Ef$) as the distance to
the origin of the 4-D space with defects ($De$), threats ($Th$), and schedule ($Mo$):
\begin{equation}\small\label{eq:eng}
\begin{array}{c}
RD = relydefect^{(RELY-3)}\\\\
E=\frac{\left(\sqrt{(\overline{Ef}*\alpha)^2 + (\overline{De}*(\beta+RD))^2 + (\overline{Th}*\gamma)^2 + (\overline{Mo}*\delta)^2}\right)}{\sqrt{\alpha^2 + (\beta+RD)^2 + \gamma^2 + \delta^2}}\\
\end{array}
\end{equation}
Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, our energy ranges $0 \le E \le 1$ and
{\em lower} energies are {\em better}. $\alpha$, $\beta$, $\gamma$, and $\delta$ 
are the weighting factors for the different models. $relydefect$ is a constant
that defines a relationship between RELY and the defect model: as RELY increases,
the weighting of the defect model increases as well.

The acceptance criteria $P$ for a new state is defined using
the current temperature $T$, 
the energy of the current solution ($e$),
and the energy of the new mutation ($en$):
\begin{equation}\small
P(e,en,T) = e^{(e -en)/T}
\end{equation}
$T$ is defined to $decrease$ as the simulator loops through $k= 1\ldots kmax$ iterations.
We use
$T = e^{-100*k/kmax}$.

\input{figures/misc/sa}

\begin{figure}
\begin{center}
\includegraphics[width=2.5in]{figures/misc/jpl1.pdf}
%eps/JPL.pdf}
\end{center}
\caption{Processing a JPL requirements model. }\label{fig:jpl}
\end{figure}
Two advantages of SA are their {\em implementation simplicity} and their {\em ability to handle
non-linear models}:
\begin{itemize}
\item {\em Implementation simplicity:}
\ref{fig:sa} illustrates the simplicity of the algorithm. Memory is only required
for one current solution ($s$), one new solution ($sn$) and one best solution ($sb$) that stores
the best solution seen at any time in the simulation.
\item
{\em Non-linear models:}
 Previously~\cite{fea02a,me03i}, we have applied SA to non-linear JPL requirements models
where minimizing the cost of project mitigations can decrease the number of requirements
achieved by that project. Hence, decreasing {\em both} the cost and achieved requirements
is a non-linear problem that must trade between minimizing cost and increasing
requirements coverage.
The top-left line  of \ref{fig:jpl} divides the behavior of the JPL requirements models
before  and after  simulated annealing. 
As shown below the line, 
initial Monte Carlo sampling of the possible mitigations lead to a large range
of costs and benefits. Simulated annealing found a set of mitigations
that lead to the small cloud of solutions above the line. Compared to the initial samples, these
new solutions had decreased cost, increased benefit (number of requirements covered), and decreased variance (shrank
the space of solutions). 
\end{itemize}
Two disadvantages of SA algorithms are their {\em incompleteness} and the {\em
complexity}
of their solutions:
\begin{itemize}
\item 
{\em Incompleteness:} In our domain, we have some evidence that the incomplete nature of the heuristic SA
search is not a major problem.
\ref{fig:saeg} shows a sample run of our SA tool running on our prediction models
for $K=10,000$ simulations. 
As $k$ increases for $1{\ldots}10,000$, it becomes less and less
likely that a better $best$ has been missed. Hence, we run our simulations
for ten times the period it takes for $best$ to stabilize (at $k\approx 1000$). 
\begin{figure}
\begin{center}
\includegraphics[width=2.7in]{figures/misc/saeg1.pdf}
\end{center}
\caption{Dots \& lines are
SA output from current \& best solution (respectively)  after $k$ simulations.
}\label{fig:saeg}
\end{figure}
\item
{\em Solution complexity:}
Simulated annealers offer constraints to all controllable features. 
Often this
is an over-constrained solution since, 
in many domains, a repeated empirical result is a {\em feature subset selection}
effect; i.e. models that constrain M variables perform just as well, or better,
than models that constrain N variables ($M\ll N$)~\cite{kohavi97,hall03}.
For example, Kohavi~\cite{kohavi97}
studied some machine learners to find  that using just 19\% of the available features
{\em increased} prediction accuracy by just 2.14\% (on average).
For another example,
when feature subset selection was applied to the JPL requirements model of \ref{fig:jpl}, we found that
up to $\frac{2}{3}$-rds of the features can be left unconstrained,
without effecting the conclusions~\cite{fea02a}. 
\end{itemize}

\begin{figure}[!t]
\scriptsize
\begin{center}
\begin{tabular}{|l|r|r|r|p{0.95cm}|}\cline{2-4}
\multicolumn{1}{c}{}     & \multicolumn{3}{|c|}{av.  number of features} \\\hline    
dataset         &before &after &$\frac{after}{before}\%$ &accuracy change\\\hline    
breast cancer &10  &2.9 &29\% &+0.14\%   \\\hline    
cleve           &13  &2.6 &2\%  &+5.89\%   \\\hline 
   crx             &15  &2.9 &19\% &+4.49\%   \\\hline  
  DNA             &180 &11  &6\% &+3.63\% \\\hline    
horse-colic     &22  &2.8 &13\% &+1.63\%   \\\hline
 Pima            &8   &1   &13\% &+0.79\%   \\\hline   
 sick-euthyroid &25  &4   &16\% &+0.38\%   \\\hline    
soybean         &35  &12.7 &36\% &+0.15\%  \\\hline\hline    
average         &38.5&4.99 &19\% &+2.14\% \\\hline
\end{tabular}
\end{center}
\caption{Feature subset selection results from~\cite{kohavi97}}\label{fig:fssr}
\end{figure}

In terms of  the goal of this paper, exploring feature subset selection
is very important.  Before we can {\em remove} non-essential features,
we must first  {\em rank} them according to their effectiveness.
As we shall see, this ranking will be insightful to the task of
assessing the relative value of new
 ASE
tools and other methods
for reducing effort/ defects/ threats /months.


\paragraph{Other Custom Algorithms}


\subsection{Other Tools}
\subsubsection{SCAT}
SCAT is an acronym for Software Cost Analysis Tool.  It is an Excel-based version of the University of Southern California’s Constructive Cost Model II (COCOMO II). SCAT is dependent on a preclibrated COCOMO II model, as it is unable to perform local calibration. SCAT is also an adaptation to COCOMO II that allows the use of a range of inputs (Low, Most Likely, High) to capture uncertainty and generate probability distributions through the use of Monte Carlo techniques.  Therefore, unlike the USC version of COCOMO, which produces a single point estimate, SCAT produces distributional estimates in the form of cumulative distribution functions (also known as “S-curves”).

The purpose of this tool is to provide software cost estimates using a Monte Carlo simulation in combination with COCOMO II cost drivers and algorithms. SCAT is the current tool used within JPL, and is therefore considered to be the baseline in our case studies.

\subsubsection{2CEE}

2CEE is a COCOMO II based software effort estimation tool. 2CEE is the brainchild of collaboration between NASA’s Jet Propulsion Laboratory (JPL) and West Virginia University (WVU). It is designed to explore the uncertainty in the model and in the estimate, to allow estimates early in the lifecycle by representing new projects as ranges of values, and to provide numerous calibration options including stratification and feature selection.  By automating many tasks for the user it provides gains in cost analyst efficiency.

2CEE uses historical project data for COCOMO II model calibration and estimation of COCOMO II effort for new projects. Furthermore, the estimates are generated through a Monte Carlo simulation, with the ability to run an n-fold cross validation on available data.

\subsection{Local Calibration(LC)}
This section describes local calibration (LC),
the standard regression procedure used by the COCOMO
community. LC is used in conjunction with local data to calibrate the COCOMO II model, as well as the other COCOMO based models.

LC assumes that a  matrix $D_{i,j}$ 
holds:
\bi
\item
The natural log of the
$LOC$ (lines of code) estimates;
\item
The natural log of  the actual efforts
for each project $j$;
\item
The  natural logarithm of the cost drivers (the scale factors
and effort multipliers) at locations $1\le i \le 15$ (for COCOMO 81)
or $1 \le i \le 22$ (for COCOMO-II).
\ei
With those assumptions, Boehm~\cite{boehm81} shows that
for COCOMO 81,
the following calculation yields estimates
for ``$a$'' and ``$b$'' that minimize the sum of the squares of residual
errors:
\begin{equation}\label{eq:ab}{\scriptsize
\left.
\begin{array}{rcl}
EAF_i& =& \sum_j^N D_{i,j}\\
a_0  & =& t \\\
a_1  & =& \sum_i^t KLOC_i\\
a_2  & =& \sum_i^t (KLOC_i)^2\\
d_0  & =& \sum_i^t \left(actual_i - EAF_i\right)\\
d_1  & =& \sum_i^t \left((actual_i - EAF_i)*KLOC_i\right)\\
b  & =& (a_0d_1 - a_1d_0)/(a_0a_2 - a_1^2)\\
a_3    & =& (a_2d_0 - a_1d_1)/(a_0a_2 - a_1^2)\\
a    & =& e^{a_3}
\end{array}\right\}}
\end{equation}
In the case of COCOMO-I~\cite{boehm81} these $a,b$ values are used in the following equation to generate
effort estimates. In this equation, $EM_i$ are the effort multipliers from \fig{emsf2}:
\[\scriptsize effort = a \cdot KSLOC ^ b \cdot \prod^{15}_i EM_i\]
What is not widely appreciated is the size of
the
variance in the $(a,b)$ values.
The left-hand-side of
\fig{dan}  shows the COCOMO-I $(a,b)$ values learned by   Baker~\cite{baker07}
after, 300 times, extracting 10 projects at random from COCOMO data sets,
then applying \eq{ab} to the remaining data.  
The data sets used in this study contained 93 projects, so LC was applied
to  $\frac{93-10}{93}=89\%$ of the data.
A pre-experimental intuition was that we were using enough of the data to yield stable $(a,b)$ values. As can be clearly seen by the wide
variance on the $(a,b)$ values in \fig{dan},
this was not the case.
\begin{figure}[!h]
\begin{center}
\includegraphics[width=2.4in]{misc/nasa93_300.pdf}\includegraphics[width=2.4in]{misc/comparesReport_lc.pdf}
\end{center}
\caption{Results of
applying
LC numerous times to 90\%
of the NASA93 data sets (available from \protect\url{http://promisedata.org/data}).
Left-hand-side shows computed $(a,b)$ values. Right-hand-side shows MREs generated
in 20 repeats
over the NASA93 data set.
}\label{fig:dan}
\end{figure}

The right-hand-side of
\fig{dan} shows the magnitude of the relative error (or $MRE$)
values 
seen in Baker's study (MRE is a standard measure in the effort estimation field
as follows:
$MRE=\frac{abs(actual - predicted)}{actual}$). 
In the sequel, we will refer to Baker's results as MRE1. 

Some of the MRE1 errors
are very large (up to nearly 500\%)
suggesting that LC was incomplete or that the variance in the $(a,b)$ calculations  have significant impact on the estimation.
Note that this right-hand-side figure  is not without precedent in the estimation literature:
it is a well-established result that  initial development effort estimates may be incorrect
by a factor of four~\cite{boehm81} or even more~\cite{kemerer87}.


Elsewhere we have been partially successful in
reducing estimation variance
of \fig{dan}
using feature subset selection (FSS)~\cite{chen05,me06d}
or more data collection.
Unfortunately,
FSS reduces but does not eliminate the $a,b$ variance. Also, further
data collection is possible, but only at great organizational expense. 
Since we failed to generate precise tunings that yield exact estimates, we considered
a change  in our research goals. 


\subsection{XOMO and TAR3}

XOMO ~\cite{me05e} is the work that preceeded STAR. It was designed as a framework for Monte-Carlo simulations made to run on USC software related models \ref{subsec:models}. The search technique that is used by this framework is a data miner called TAR3 (and evolution of TAR2\cite{me03c}). TAR3 can be described as a treatment learner, returning concise rules or "treatments" that have the largest effect on the output of the fitness function used. Having small rules is useful for software process control since this reduces the managerial interventions on a software project, while at the same time ensuring that such interventions will have high utility for the project.

TAR3 inputs a set of training examples $E$. Each example maps a set of attribute ranges  to some class symbol; i.e.  $\{R_i,R_j,... \rightarrow C\}$ The class symbols $C_1, C_2..$ are stamped with some utility score that ranks the classes; i.e. $\{U_1 < U_2 < .. < U_C\}$. With $E$, these classes occur at frequencies
$F_1\%,F_2\%, ..., F_C\%$.
A ``treatment'' 
$T$ of size $X$ is a conjunction of attribute ranges  $\{R_1 \wedge R_ 2 ... \wedge R_X\}$.
Some subset of $e \subseteq E$ are consistent with the treatment.
In that subset, the classes occur at  frequencies
$f_1\%,f_2\%, ... f_C\%$.
TAR3 seeks the
seek smallest $T$ which most changes the weighted sum of the utilities times frequencies
of the classes. Formally, this is called the $lift$ of a treatment:
\[lift=\frac{\sum_C U_Cf_C}{\sum_C U_CF_C}\]

\begin{figure}[!t]
 {\em
\begin{center}
\begin{tabular}{rcccl}
outlook & temp($^o$F) &  humidity & windy? & class
\\\hline
sunny&  85&     86&     false&  none\\
sunny&     80&     90&     true&   none\\
sunny&     72&     95&     false&  none\\
rain&  65&     70&     true&         none\\
rain&        71&     96&     true&   none\\\hline
      rain&         70&     96&     false&      some\\
      rain&      68&     80&     false&      some\\
      rain&      75&     80&     false&  some\\\hline
      sunny&    69&     70&     false&  lots \\
      sunny&    75&     70&     true&   lots\\
      overcast&  83&     88&     false&  lots\\
      overcast&  64&     65&     true&   lots\\
      overcast&  72&     90&     true&   lots\\
     overcast&  81&     75&     false&  lots\\\hline
\end{tabular}\end{center}}
\caption{TAR3: Playing golf.}\label{fig:golfdata}
\end{figure}

%\begin{figure*}
%\begin{center}
%{\footnotesize
%\begin{tabular}{l|p{2in}|l@{~}p{1.5in}|l@{~}p{1.8in}}
%input:
% &{\footnotesize
%\begin{alltt}
%SELECT class
%FROM golf
%\end{alltt}} &&
%{\footnotesize
%\begin{alltt}
%SELECT class
%FROM golf
%WHERE
%outlook = 'overcast'
%\end{alltt}} &&
%{\footnotesize
%\begin{alltt}
%SELECT class
%FROM golf
%WHERE
%humidity >= 90
%\end{alltt}}\\\hline
%%&&&\\
%output: &{\footnotesize
%\begin{alltt}
%none none none none none 
%some some some lots lots 
%lots lots lots lots
%\end{alltt}}&&
%{\footnotesize
%\begin{alltt}
%lots lots lots lots\end{alltt}} && {\footnotesize
%\begin{alltt}
%none none none some lots
%\end{alltt}}\\\hline
%&&&&&\\
%distributions:&~~~~~~\begin{barenv} \setstyle{\sffamily} \setwidth{8}
%     \setstretch{5}
%  \setyaxis{0}{6}{2}
%\sethspace{1} \setnumberpos{down} \bar{5}{1}
% \bar{3}{4}
% \bar{6}{8}
%\end{barenv}&&~~~~~~
%\begin{barenv}
%\setstyle{\sffamily} \setwidth{8}
% \setstretch{5}
%  \setyaxis{0}{6}{2}
%\sethspace{1} \setnumberpos{down} \bar{0}{1} \bar{0}{4} \bar{4}{8}
%\end{barenv}&&~~~~~~
%\begin{barenv}
%\setstyle{\sffamily} \setwidth{8}
% \setstretch{5}
%  \setyaxis{0}{6}{2}
%\sethspace{1} \setnumberpos{down} \bar{3}{1} \bar{1}{4} \bar{1}{8}
%\end{barenv}~\\\\
%\end{tabular}}
%
%legend: \protect\legend1{none} \protect\legend4{some}
%\protect\legend8{lots}
%
%\end{center}
%
%~\\
%
% \caption[TAR3:
%Class distributions]{TAR3: Class distributions selected by different conditions in \protect\fig{golfdata}.  }
%\label{fig:golft}
%\end{figure*}


For example, consider the log of golf
playing behavior seen in \ref{fig:golfdata}. In that log, we only play
{\em lots} of golf in $\frac{6}{5+3+6}= 43\%$ of cases. To improve
our game, we might search for conditions that increases our
golfing frequency. Two such conditions are shown in the {\tt
WHERE} test of the select statements  in \fig{golft}. In the case
of {\tt outlook= overcast}, we play {\em lots} of golf all the
time. In the case of {\tt humidity $\le$ 90}, we only play {\em
lots} of golf in 20\% of cases.  So one way to play lots of golf
would be to select a vacation location where it was always
overcast. While on holidays, one thing to watch for is the
humidity: if it rises over 90\%, then our frequent golf games are
threatened.


The tests in the {\tt WHERE} clause of the select statements in
\fig{golft} is a treatment. Classes in treatment learning
get a score $U_C$
and the learner uses this to assess the class
frequencies resulting from {\em applying a treatment} (i.e. using
them in a {\tt WHERE} clause). In normal operation, a treatment learner
does {\em
controller learning} that finds a treatment which selects for
better classes and reject worse classes  By reversing the scoring
function, treatment learning can also select for the worse classes
and reject the better classes. This mode is called {\em monitor
learning} since it finds the thing we should most watch for. In
the golf example, {\em outlook = 'overcast'} was the controller
and $humidity \ge 90$ was the monitor.

Formally, treatment learning is a weighted-class minimal
contrast-set association rule learner.  The treatments are associations that occur
with preferred classes. These treatments serve to contrast undesirable situations with
desirable situation where more of the outcomes are favorable. Treatment learning
is different to other contrast set learners like
STUCCO~\cite{bay99} since those other learners don't focus on minimal theories.

Conceptually, a treatment learner explores all possible subsets of the attribute
ranges looking for good treatments. Such a search is impractical
in practice so the art of treatment learning is quickly pruning unpromising attribute
ranges. This study uses the
TAR3 treatment learner~\cite{ying02} that uses  stochastic search
to find its treatments. 

\subsection{Iterative TAR3}
Sometimes, one round of TAR3 is not enough.
{\em Iterative TAR3} runs by conducting multiple Monte Carlo
simulations over the ranges of any uncertain variables. For example,
there are 28 variables in the XOMO models:
\bi
\item
Ksloc;
\item
5 scale factors;
\item
17 effort multipliers;
\item
2 calibration parameters (``{\tt a,b}'');
\item
3 defect removal activities (automated analysis, peer reviews,
execution testing and  tools).  
\ei 
In the case studies below, only a partial description of some of these variables are available.
Hence, learning is a process of sampling from the known constraints, finding the best
treatment, then revising the constraints.
 After, say,
1000 Monte Carlo runs, 
BORE classifies the outputs as (say) either the
333 $best$ or 667 $rest$.  The treatment learner studies the
results and notes which input ranges select for $best$.
The ranges found by the learner then become restraints for 
future
simulations. The whole cycle looks like this:

{\footnotesize
\[\begin{array}{c}
restraints_i \rightarrow simulation_i \rightarrow learn \rightarrow \\
\rightarrow restraints_{i+i} \rightarrow simulation_{i+1}
\end{array}\]}
\begin{figure*}
\centering {\small
\begin{tabular}{c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}|c@{~}c@{~}c@{~}c@{~}c@{~}c}
\begin{sideways}=execution testing and tools\end{sideways}&\begin{sideways}flex\end{sideways}&\begin{sideways}stor\end{sideways}&\begin{sideways}aexp\end{sideways}&\begin{sideways}docu\end{sideways}&\begin{sideways}site\end{sideways}&\begin{sideways}plex\end{sideways}&\begin{sideways}cplx\end{sideways}&\begin{sideways}ltex\end{sideways}&\begin{sideways}peer reviews\end{sideways}&\begin{sideways}\$ksloc\end{sideways}&\begin{sideways}rely\end{sideways}&\begin{sideways}data\end{sideways}&\begin{sideways}ruse\end{sideways}&\begin{sideways}acap\end{sideways}&\begin{sideways}?\$A\end{sideways}&\begin{sideways}sced\end{sideways}&\begin{sideways}automated analysis\end{sideways}&\begin{sideways}pcon\end{sideways}&\begin{sideways}?\$B\end{sideways}&\begin{sideways}pcap\end{sideways}&\begin{sideways}tool\end{sideways}&\begin{sideways}time\end{sideways}&\begin{sideways}prec\end{sideways}&\begin{sideways}pvol\end{sideways}&\begin{sideways}resl\end{sideways}&\begin{sideways}team\end{sideways}&\begin{sideways}pmat\end{sideways}&\begin{sideways}$<$\$risk\end{sideways}&\begin{sideways}$<$\$effort\end{sideways}&\begin{sideways}$<$\$defects\end{sideways}\\\hline
1&3&3&4&4&6&4&4&5&6&116&5&4&4&4&3.10408&3&6&3&0.915776&3&5&3&4&3&4&3&5&0.68&345.87&1.67\\
1&3&3&4&4&6&4&4&5&6&78&5&4&4&4&2.80696&3&6&3&0.92094&3&5&3&3&3&4&3&4&0.68&238.43&2.00\\
1&3&3&4&4&6&4&4&5&6&118&5&4&4&4&2.51974&3&6&3&1.09107&3&5&3&5&3&4&3&5&0.68&621.76&1.55\\
1&3&3&4&4&6&4&4&5&6&118&5&4&4&4&2.808&3&6&3&1.09649&3&5&3&3&3&4&3&4&0.68&862.15&2.00\\
1&3&3&4&3&6&4&4&5&6&118&5&4&4&4&3.23396&3&6&3&1.04294&3&5&3&5&3&4&3&4&0.68&615.55&1.88\\
1&3&3&4&3&6&4&4&5&6&90&5&4&4&4&2.59488&3&6&3&1.01176&3&5&3&3&3&4&3&4&0.68&348.81&2.16\\
1&3&3&4&3&6&4&4&5&6&94&5&4&4&4&2.54054&3&6&3&0.9104&3&5&3&3&3&4&3&4&0.68&226.74&2.16\\
1&3&3&4&4&6&4&4&5&6&97&5&4&4&4&2.38838&3&6&3&1.02511&3&5&3&5&3&4&3&5&0.68&343.77&1.55\\
1&3&3&4&4&6&4&4&5&6&125&5&4&4&4&2.33558&3&6&3&1.02301&3&5&3&3&3&4&3&4&0.68&540.69&2.00\\
...
\end{tabular}
}
\caption{XOMO output.}\label{fig:xout}
\end{figure*}

\begin{figure*}
\centering {\small
\begin{tabular}{c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}c@{~}|c@{~}}
\begin{sideways}=execution testing and tools\end{sideways}&\begin{sideways}flex\end{sideways}&\begin{sideways}stor\end{sideways}&\begin{sideways}aexp\end{sideways}&\begin{sideways}docu\end{sideways}&\begin{sideways}site\end{sideways}&\begin{sideways}plex\end{sideways}&\begin{sideways}cplx\end{sideways}&\begin{sideways}ltex\end{sideways}&\begin{sideways}peer reviews\end{sideways}&\begin{sideways}\$ksloc\end{sideways}&\begin{sideways}rely\end{sideways}&\begin{sideways}data\end{sideways}&\begin{sideways}ruse\end{sideways}&\begin{sideways}acap\end{sideways}&\begin{sideways}?\$A\end{sideways}&\begin{sideways}sced\end{sideways}&\begin{sideways}automated analysis\end{sideways}&\begin{sideways}pcon\end{sideways}&\begin{sideways}?\$B\end{sideways}&\begin{sideways}pcap\end{sideways}&\begin{sideways}tool\end{sideways}&\begin{sideways}time\end{sideways}&\begin{sideways}prec\end{sideways}&\begin{sideways}pvol\end{sideways}&\begin{sideways}resl\end{sideways}&\begin{sideways}team\end{sideways}&\begin{sideways}pmat\end{sideways}&\begin{sideways}best or rest?\end{sideways}\\\hline
1&3&3&4&4&6&4&4&5&6&77&5&4&4&4&3.16394&3&6&3&0.900243&3&5&3&5&3&4&3&5&\_1\\
1&3&3&4&3&6&4&4&5&6&75&5&4&4&4&2.98155&3&6&3&1.09603&3&5&3&3&3&4&3&4&\_0\\
1&3&3&4&3&6&4&4&5&6&84&5&4&4&4&2.4412&3&6&3&1.01243&3&5&3&3&3&4&3&4&\_0\\
1&3&3&4&3&6&4&4&5&6&102&5&4&4&4&3.1926&3&6&3&0.971668&3&5&3&3&3&4&3&4&\_0\\
1&3&3&4&3&6&4&4&5&6&117&5&4&4&4&2.33322&3&6&3&0.934947&3&5&3&4&3&4&3&4&\_0\\
1&3&3&4&4&6&4&4&5&6&115&5&4&4&4&2.95164&3&6&3&0.990819&3&5&3&5&3&4&3&5&\_1\\
1&3&3&4&3&6&4&4&5&6&122&5&4&4&4&2.51071&3&6&3&0.957017&3&5&3&5&3&4&3&5&\_1\\
1&3&3&4&4&6&4&4&5&6&117&5&4&4&4&3.01523&3&6&3&0.961085&3&5&3&4&3&4&3&4&\_0\\
1&3&3&4&3&6&4&4&5&6&112&5&4&4&4&2.48963&3&6&3&1.07945&3&5&3&4&3&4&3&4&\_0\\
1&3&3&4&3&6&4&4&5&6&117&5&4&4&4&2.77276&3&6&3&1.00916&3&5&3&4&3&4&3&5&\_0\\
...
\end{tabular}
}
\caption[BORE output]{BORE output. In the last column, \_0 denotes ``rest'' and \_1 denotes ``best''.}\label{fig:bore}
\end{figure*}


\subsection{Conflict Analysis with S-Cost}
\label{hohin}
Hoh In and Boehm \ref{} describe a system called S-Cost. The purpose of this system to semi-automate the process of finding conflicts in cost - quality requirements of software systems. This system also works to facilitate the process of resolving those conflicts by presenting stakeholders in the software project with several strategies for the purpose of finding a proper compromise for all parties. In this section, we will present this system, describing briefly how it operates and explaining the strategies that it presents to stakeholders.

\subsubsection{The problem}
Quality in software products was being attributed to service oriented customer satisfaction, which caused some qualities to be neglected (e.g. maintainability) and placed too much emphasis on usability. To remedy this, this was expanded to include the evaluation for not only the customer, but also the all the other stakeholders in a software product. This allowed considering cost, maintainability, interoperability and other software qualities as parts of what describe software quality. However, this also introduced the problem of coordinating all the stakeholders needs, causing cost-quality conflicts to emerge. This is exasperated by the complex dependencies that software cost has with the software quality attributes, as well as the large resolution space that is available to find solutions to these cost-quality conflicts. S-Cost was introduced as a semi-automated system in order to assist the stakeholders in visualizing and resolving conflicts by applying certain strategies to different modules of the software product.

\subsubsection{S-Cost}
S-Cost combines two separate systems to provide its semi-automated risk resolution capabilities: USC-CSE WinWin system and the Qarcc tool. WinWin is based on a spiral model that aims at resolving conflicts between stakeholder needs, otherwise called as "win conditions", and making everyone a "winner". This system is manually manipulated, making ti hard on stakeholders in larger products to identify the conflicts in their win conditions. Qarcc is a knowledge-based tool that identifies conflicts in software quality requirements, by using predefined stakeholder/quality-attribute relationships, and notifies stakeholders of these possible conflicts. Neither of these systems has the ability to get the effect of conflict resolution on development costs. S-Cost adds this ability, combining both systems to be able to find win-win solutions to quality conflicts, all while using COCOMO (COnstructive COst MOdel) to indicate cost estimates. This allows S-Cost to help resolve cost-quality conflicts as well as quality conflicts between different stakeholders. S-Cost is able to give suggestions (or strategies) for the stakeholder to apply to resolve cost conflicts, while keeping keeping affected stakeholders of the implications of these resolutions. Visualization and negotiation aids are provided as well by S-Cost.

\subsubsection{The strategies}
\begin{figure}[!b]
\footnotesize
\begin{tabular}{c@{~}p{.4\linewidth}p{.5\linewidth}}
&{\bf Drastic change} & {\bf Possible undesirable impact}\\\hline
1&Improve personnel & Firing and re-hiring personnel leading to wide-spread union unrest.\\\hline
2&Improve tools, techniques, or  
development platform & Changing operating systems, IDEs, coding languages\\\hline
3&Improve precedentness / \newline development flexibility &
Changing the goals
of the project and the development method.\\\hline
4&Increase architectural \newline analysis /  risk resolution &
Far more elaborate early life cycle analysis.\\\hline
5&Relax schedule  & Delivering the system later.\\\hline
6&Improve process maturity & May be expensive in the short term.\\\hline
7&Reduce 
functionality & Delivering less than expected.\\\hline
8&Improve the team & Requires effort on team building.\\\hline

9&Reduce quality 
& Less user approval, smaller market.
\end{tabular}
\caption{Nine drastic changes from~\cite{boehm99}.}\label{fig:dchange}
\end{figure}

There are several strategies that S-Cost presents to the stakeholder, giving the stakeholder the option of choosing the degree to which to apply it to the different modules of the software product. Each strategy influences a subset of the COCOMO (in this case COCOMO II) software cost attributes, and each has its own pros and cons that are presented to the stakeholder. These strategies are the following:

\begin{itemize}
\item\textbf{Reduce/defer Functionality: }\textit{KDSI, DATA} - Reducing the functionality of the product will reduce size, hence reducing cost and easing maintenance. This however reduces the abilities of the product which influences customer satisfaction.
\item\textbf{Reduce/defer Quality: }\textit{RELY, DOCU, TIME, CPLX} - Reducing quality will drive costs and development time down, but will increase maintenance costs especially for products that will have longer life cycles.
\item\textbf{Improve tools, techniques or platform: }\textit{TIME, STOR, PVOL, TOOL, SITE} - Improving tools and the platform will cause training and platform costs to increase, but will improve maintainability and will reduce software cost and schedule in the long run.
\item\textbf{Relax the delivery schedule constraint: }\textit{SCED} - Tightening the delivery schedule will allow development time and cost to decrease but may negatively influence product capabilities.
\item\textbf{Improve personnel capabilities: }\textit{ACAP, PCAP, PCON, AEXP, PEXP, LTEX, KSLOC/PM} - Improving capabilities of analysts and programmers and transferring more experienced ones to the project would reduce the cost of the product while improving its quality. This would mean however that other products will lose skilled personnel, negatively influncing them, and the cost per person will increase due to using more skilled personnel.
\item\textbf{Reuse software assets: }\textit{ADSI, DM, CM, IM} - Reusing software code will allow the cost of the development to decrease, however the effect on the product's quality depends solely on the quality of the software being reused. 
\item\textbf{Improve coordination via teambuilding: }\textit{TEAM} - Team building allows for removing interpersonal overhead, which drives down the schedule and the cost. This factor isn'y always controlable however.
\item\textbf{Architecture and risk resolution: }\textit{RESL} - Reducing risk resolution will allow more resources to be allocated for product development, reducing the development time and cost. This will cause a need for additional risk management overhead however.
\item\textbf{Improve process maturity level: }\textit{PMAT} - Increasing this will help with reducing the time and cost of resolving product bugs and hence improves quality. Overhead is introduced with this however due to the need to implement the Software Engineering Institute's Capability Maturity Model.
\item\textbf{Improve precedentedness and development flexibility: }\textit{PREC, FLEX} - Having increased familiarity with the product type and more flexible development would reduce costs. Such factors are uncontrollable sometimes and depend on the development environment and history.
\item\textbf{Increase budget: }\textit{Revised win condition} - If Funds are available, this could allow the product to be more competitive and may increase ROI.
\end{itemize}

\begin{figure}[!t]
\footnotesize
\begin{tabular}{c@{~}p{.5\linewidth}p{.4\linewidth}}
&{\bf Drastic change} 
& {\bf Effects on \fig{cases}} \\\hline

1&Improve personnel 
& 
acap = 5; pcap = 5;
                    pcon = 5 \newline 
                    apex  = 5 ;
                    plex = 5 ;
                    ltex = 5 \\\hline
2&Improve tools, techniques, or  development platform 
& 
    time = 3; 
                    stor = 3\newline
                    pvol = 2;
                    tool = 5\newline
                    site = 6\\\hline
3&Improve precedentness / development flexibility 
&
prec = 5;
flex = 5
\\\hline
4&Increase architectural analysis /  risk resolution 
&resl = 5
\\\hline
5&Relax schedule  
& 
    sced = 5      
\\\hline

6&Improve process maturity 
& pmat = 5
\\\hline

7&Reduce \newline
functionality 
& 
 data = 2; 
                    kloc  * 0.5
\\\hline
8&Improve the team 
&
team = 5 
\\\hline

9&Reduce quality 
& 
  rely = 1 ;
                    docu = 1\newline
                    time = 3 ;
                    cplx = 1
\end{tabular}
\caption{Implementing drastic changes.
}\label{fig:how}
\end{figure}

\subsection{Better, Faster, Cheaper: Pick Any Two}

This was an philosophy that was pushed in NASA by Dniel Goldin, who served as the NASA Administrator from April $1^{st}$, 1992 to November $17^{th}$, 2001. It was mainly pushed to counter the funding cutbacks for NASA. This philosophy can be described by the following: better, faster, cheaper; pick any two. This indicated that for any givven project, two of these three characteristics would need to be optimized for, suggesting that optimizing for all three wasn't a viable endeavor. The net result of this was that many projects were under funded cuasing many projects to fail due to management mixups or human error.




