\section{The Fitness Function and Heuristic Modifications}
When evaluating possible solutions with SA, better solutions have lower score, referred to here as ``energy''.
The fitness function defines the energy $E$ such that $E \ge 0$ and
{\em lower} values are $better$. This fitness function is here defined as the distance to
the origin of the 4-D space composed of effort ($Ef$),  defects ($De$), threats ($Th$), and development time ($Mo$). 
For our purposes, we model :

{\small\begin{equation}\label{eq:rd}
\begin{array}{c}
RD = relydefect^{(RELY-3)}\\\\
\end{array}
\end{equation}}
{\small\begin{equation}\label{eq:energy}
\begin{array}{c}
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, all set to $1$ by default. $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 default setting for $relydefect$ is $1.8$. Initially, this seems like a magic number; however this setting was intentionally chosen such that, as \textit{rely} varies from its minimum to maximum ratings of \textit{very low}(1) to \textit{very high}(5), the \textit{RD} weight factor changes by about a factor of ten as is demonstrated below.
\begin{center}
$RD(rely=1) = 1.8^{1-3} = 0.31$

$RD(rely=5) = 1.8^{5-3} = 3.24$
\end{center}
In addition to the above, we implemented additional heuristic modifications to the models relating to the defect reduction measures in the COQUALMO model. These modifications where implemented in the form of loop-backs, which modify the \textit{rely} and the \textit{tool} model attributes in the following manner:

{\small\begin{equation}\label{eq:relylb}
\begin{array}{c}
rely = rely + (aa-3>0? aa-3 : 0)\\
	+ (ett-3>0? ett-3 : 0)\\
	+ (peer-3>0? peer-3 : 0)
\end{array}
\end{equation}}

{\small\begin{equation}\label{eq:toollb}
\begin{array}{c}
tool = tool + (aa-3>0? aa-3 : 0)\\
	+ (ett-3>0? ett-3 : 0)
\end{array}
\end{equation}}

In \eq{relylb} and \eq{toollb}, \textit{aa}, \textit{ett} and \textit{peer} are automated analysis, execution-based testing, and peer reviews as indicated by \fig{cparems}. The equations are written in C style for simplification. For example, $(aa-3>0? aa-3 : 0)$ is equivalent to the following:
\begin{verbatim}
if (aa > nominal)
     return aa-3;
else return 0;
\end{verbatim}
These loop-backs attempt to model a logical relationship that exists between the defect reduction measures and the reliability and development and testing tools used in the development of the software project. The general reasoning is that, as the rating of defect reduction measures increase, this automatically means that \textit{rely} and \textit{tool} are more highly rated. As a counter example, it doesn't make sense for \textit{tool} to be rated at \textit{very low} while at the same time \textit{aa} and \textit{ett} are rated at \textit{very high}, since this inherently indicates that development and testing tools are being heavily used by a project.

The following is an example of how this would work. Assume that \textit{tool} is set at low (2), and \textit{aa} and \textit{ett} at set at high (4). This will modify the rating of \textit{tool} in the following manner: $tool = rating(tool) + [rating(aa)-rating(nominal)] + [rating(ett)-rating(nominal)] = 2 + [4-3] + [4-3] = 4$, i.e. \textit{tool} would be set to high. Note that for the above two attributes, the values are restricted in accordance to the default model limits shown in \fig{default} as well as the limits set by the projects. This means that \textit{rely} and \textit{tool} can never exceed 5, which corresponds to a rating of \textit{very high}.

With the above fitness function applied to the search stage (i.e. the Simulated Annealing stage) in STAR, this stage constrains all the features. For this reason feature subset selection is very important to explore and trim non-essential features in order to produce succinct policies.  Before we can {\em remove} non-essential features, we must first  {\em rank} them according to their effectiveness.

\section{Ranking Method: Support-Based Bayesian Ranking with ``BORE''}\label{sec:bayrank}
%There are two ranking methods that can be used by STAR. These are {\em Bayesian ranking} and {\em Energy ranking}. The former is the main ranking method used by STAR, while the latter is included in STAR for verifying that the Bayesian ranking is valid.
BORE ~\cite{clark05} (short for ``best or rest'')
divides numeric scores seen over $K$ runs and stores the top 10\%  in $best$ and the remaining 90\% scores in the set $rest$
(the $best$ set is computed by studying the delta
of each score 
to the best score seen in any era).
It then computes the probability that a value is found in $best$
using
Bayes theorem.
The theorem uses
evidence $E$ and a prior probability $P(H)$ for
hypothesis $H\in\{best, rest\}$,
to calculate a  posteriori  probability
$P(H|E)=P(E|H) P(H)\; /\; P(E)$.

This ranking method is the default ranking method used in STAR, and is hence used in all the subsequent experiments that were conducted.
STAR ranks the feature 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 calculates 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 normalized 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 are 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.
STAR 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}

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

Incremental decision making  is an important property of STAR.
Observe how, in 
\fig{flighttactical},
50\% of the score reduction
arises from around 15\% of the decisions.
If a manager cannot implement all STAR's recommendations and a 50\% reduction
is adequate,
she might elect to  use just these top 15\% decisions.
That is, STAR not only makes $R$ recommendations, it also reports on the value of
just applying just some subset of $r \subseteq R$.

\begin{description}
\item[1. {\em SAMPLE:}]
To sample the ranges from the models,
STAR runs the simulated annealer  $K_1$ times. Note that here, we sample across the ranges of all the attributes. While most of the time we sample randomly across the range, we also have a heuristic optimization called extreme sampling. This form of sampling works in the following manner: for x\% (x is set to 5 by default), STAR samples only the extremums of the attributes. SEESAW, presented in \subsub{otheralgo}, was inspired by the effectiveness of this optimization, and implements it 100\% of the time.
\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 using Support-Based Bayesian Ranking \tion{bayrank}.
\item[5.
{\em PRUNE:}]
Also called the back select stage. STAR 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:}]
STAR returns the $1..X$ settings that optimize the best for the fitness function being used according to the weights applied to effort, defects, development time, and threats. These settings are determined by iterating back from the minimum point achieved towards the first point that is statistically similar to the minimum point. This statistical difference is tested via a standard t-test.
\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 

STAR is very much a multi-purpose tool that not only has inspired others tools, but was also used in order to explore many problems in the software engineering world. Such problems include the following: 

\bi
\item the importance of automated software engineering (ASE) tools
\item the ability to estimate effort without the presence of model calibration data
\item the efficacy of drastic change versus improving certain aspects of a project with in the projects preset limits
\item addressing the better-faster-cheaper, ``pick any two", problem and its implications
\item the future of software engineering and exploring what policies are going to be needed
\ei

Using STAR we will attempt to address these problems and discuss some of the solutions that STAR suggests. 

\section{Standard NASA Case Studies and Policies}\label{sec:nasaprojpol}
STAR was tested on the four NASA case studies of~\fig{cases}:
\bi
\item OSP: The Orbital Space Plane GNC prototype (a 1990s NASA system).
OSP was an early prototype for OSP2.
\item OSP2: the guidance and navigation control system of a current NASA launch vehicle, under development.
\item FLIGHT/GROUND: these two are project templates used for nasa projects.
\ei
In \fig{cases},  {\em values} are {\em fixed} while {\em ranges} represent a space of options.
\input{figures/cases}
The following observation can be made concerning the above projects:
OSP2
constrains most of its features to fixed values while
OSP allows more variation in feature ranges. Flight and Ground are more like project templates that, for the most part, enforce restrictions on the ranges of the project. OSP and OSP2 and both considered ``Flight" projects.

\input{tables/strattact}

In addition to the above, the policies need to be defined. The last two columns of \fig{strattact} 
show the results of  Delphi panel session at JPL where the COCOMO variables
were classified into those $tactical$ variables
that can be changed within the space of one project,
and those $strategic$ variables
that required higher-level institutional change (and so may take
longer to change). This effectively defines 2 policies: $strategic$ and $tactical$. For example, the panel declared that $pmat$ (process maturity)
is hard to change within the space of a single JPL project. Specifying the use of one policy or the other restricts the attributes explored in the back select ``prune'' part of the STAR algorithm, and hence restricts the policies that can be used. These two analysis policies are used in the following sections for different experiments. When the policy is not specified, this inherently means that the experiment is using default analysis, i.e. all the attributes are being explored during the pruning phase.

\section{Sanity Checks}
For the purpose of verifying that our system is valid in its estimations, we need to baseline it against the reference implementations of the models that we are using to make sure that we obtain ballpark estimates at least. For this purpose, a ``Sanity'' project was created that has all the effort multipliers set to nominal, the scale factors set to extremely high, and the defect removal tools left unset to allow STAR to be able to run. Note that these tools do not effect the COCOMO II effort (person-months), the Months (development time), or the Threat estimates. For comparisons with the reference COQUALMO model, the settings for the defect removal was set to the policy produced by STAR. \fig{sanity} presents the results of this exercise, where the last column presents the value of the percent difference between the Median result that STAR produces and the reference results. Note that the reference implementations are an online form \footnote{http://sunset.usc.edu/research/COCOMOII/expert\_cocomo/expert\_cocomo2000.html} for COCOMO II, threat and Months and a USC Center of software engineering sourced excel file for COQUALMO.

\begin{figure}
\begin{center}
\begin{tabular}{|l||c|c|c|c|c|}\hline
Model &STAR Median &STAR Spread &Refrence Model&Differece &Difference\%\\\hline\hline
COCOMO II &677.83 &159.75 &840.3 &-162.47 &-19.33\\
COQUALMO &540.39 &313.22 &417.25 &+123.14 &+29.51\\
Months &23.97 &2.52 &24.2 &-0.23 &-0.95\\
Threat &0 &0 &0 &0 &0\\\hline
\end{tabular}
\end{center}
\caption{Sanity Checks: Showing the differences in estimates produced by STAR and the reference models}\label{fig:sanity}
\end{figure}

Note that the results for STAR aren't set in stone simply because of the stochastic nature of the search that is conducted with in it, and because of the internal variation in model slopes that is conducted within the model implementations in STAR. Inspecting the results of the above experiment, we can see that the differences aren't large enough to warrant concern, keeping in mind that we aren't adhering to the calibrated models that the reference implementations are. 

\section{Stability and Performance}
In addition to the necessity of verifying that the results of STAR are within the ballpark of standardized methods, we also need to verify that we have some degree of stability. For this purpose we use two sample projects: one that is highly constrained (OSP) and one that is loosely constrained (flight). STAR was run ten times for both, and then the policy results produced were compared. Each of the projects were run through STAR ten times while using the \textit{all} strategy, where all the model features are included in the search to produce policies. \fig{flightstab} and \fig{ospstab} below presents the percentage of times that a certain policy appears: the higher the percentage, the more that is indicative of the stability of that policy.

\input{tables/stability}

As we can see, there is a high rate of stability with respect to the policies being produced by STAR for these two sample projects. Any degree of instability that is indicated is a normal occurrence given that the core algorithm used in STAR is a meta-heuristic search algorithm, and also given that we are actively varying the internal parameters of the models used. 

In addition to analyzing stability of the output of STAR in terms of the policies produced, we can also analyze the stability in terms of the model estimates produced by STAR for the projects, as well as the time performance of STAR. Note that these are times produced on a machine running Ubuntu 8.04 with a 2.2GHz Intel Core 2 Duo processor and 2GB of RAM.

\input{tables/run-stats}

In \fig{runstats}, ``MinMed'' indicates the median value of the corresponding estimate at the policy point, while ``MinSP'' indicates the spread of the corresponding estimate. Looking at \fig{runstats}, we present the medians and the spreads of both the medians and the spreads of the estimates produced at the policy points in STAR. As we can see above, the spreads of the medians are with in acceptable limits, indicating a stability in estimates produced despite us varying the  internal parameters of the models. In addition, the performance of STAR is quick thanks to fine tuning the parameters of the search. With regards to performance, we can also observe a correlation between how much a project is constrained and how long it takes to produce results. While the performance of the search part of the algorithm, indicated by ``SATime'', is almost the same for both projects, the total time is shorter for \textit{OSP}. This suggests that the ranking and backselect times are dependent on how constrained a project is. Note that in either case, STAR is achieving in under a minute what took XOMO up to 30 minutes.

\section{STAR vs. LC}
LC is a standard tuning/estimation method presented in \tion{lc}. This method is dependent on local data to generate the tunings and estimates. We seek to investigate whether STAR can generate estimates of similar quality to LC. If this is achieved, it will allow us to bypass the the data drought issue, while at the same time adding validation to using AI search for software process control. Note that the same study was done by Menzies et. al~\cite{me08c}.

%\input{star-vs-lc}
\subsection{Experiments}

\fig{cases} shows various $Projects$ expressed in term of $float$ing
and $fixed$ variables. For example, with JPL's flight systems,
the $rely$ (required reliability) can float anywhere in the upper range;
i.e. $rely\in\{3,4,5\}$. However, for flight systems, $sced$ (schedule pressure)
is tightly defined (so $sced$ is fixed to the value 3).

For this section, we will be looking at the four case studies
of \fig{cases}, plus a fifth study called ``ALL'' that
uses the entire range COCOMO attributes,
unconstrained by a particular project specification. Each study was repeated
twice- one for controlling just the strategic variables
and once for controlling just the tactical variables.
This resulted in ten experiments. The results of the experiments are presented later in \chap{ase}. for the purposes of this section, all that was needed were simulations that were run at the policy point of the particular case. The results of these simulations were used to create the STAR MRE graphs.

For each of the cases, the following procedure was repeated 20 times.
Ten examples were removed at random and Boehm's local calibration (LC) procedure~\cite[p526-529]{boehm81}  was
used to train a COCOMO model on the remaining $Project$ 
examples. LC's estimates were then compared to the estimates generated by
STAR's simulation at the policy point (i.e. floating over both the policy and the $Model$ ranges). 
\fig{deltas} show the median difference in the 
 estimates generated by LC and STAR . Note that, in all the
cases, the difference is under 35\%. This result is confirmed by the plots in \fig{starlc}, where it is evident that for all the cases, the MRE plots for star are close to the corresponding plots for LC. Also notice that, for all the plots, STAR's MRE never exceeds 100\%. This shows that the difference between STAR and LC is never excessively high, where STAR generates estimates in the ball park of LC's estimates.

\begin{figure}
\begin{center}
\includegraphics[width=1.5in]{figures/star-vs-lc/OSP-strategic.pdf}    % 21.78
\includegraphics[width=1.5in]{figures/star-vs-lc/ground-tactical.pdf}  %  22.17
\includegraphics[width=1.5in]{figures/star-vs-lc/ALL-strategic.pdf}    %  22.95
\includegraphics[width=1.5in]{figures/star-vs-lc/ALL-tactical.pdf}     %  23.14
\includegraphics[width=1.5in]{figures/star-vs-lc/ground-strategic.pdf} %  23.38
\includegraphics[width=1.5in]{figures/star-vs-lc/flight-tactical.pdf}  %  25
\includegraphics[width=1.5in]{figures/star-vs-lc/OSP2-strategic.pdf}   %  26.6
\includegraphics[width=1.5in]{figures/star-vs-lc/OSP-tactical.pdf}     % 27.71
\includegraphics[width=1.5in]{figures/star-vs-lc/flight-strategic.pdf} %  28.47
\includegraphics[width=1.5in]{figures/star-vs-lc/OSP2-tactical.pdf}    %  32.07
\end{center}
\caption[MRE plots for LC and STAR]{Plots of the MREs of the effort estimates generated by LC (fat line) and 
STAR (thin line). The ten plots are sorted in order of the median differences
(shown in \fig{deltas}). Within in each plot,
the results are sorted by the MRE of the estimated offered by LC or STAR. A log scale is used for the y-axis. 
}\label{fig:starlc}
\end{figure}

\begin{figure}[!t]
\begin{center}
\scriptsize
\begin{tabular}{l|c|rl}
case study&~control method &~~ $\delta$ \%  & \\\hline
OSP&strategic&21.78&\rule{9mm}{2mm}\\
ground&tactical&22.17&\rule{10mm}{2mm}\\
All&strategic&22.95&\rule{10mm}{2mm}\\
All&tactical&23.14&\rule{10mm}{2mm}\\
ground&strategic&23.38&\rule{10mm}{2mm}\\
flight&tactical&25&\rule{11mm}{2mm}\\
OSP2&strategic&26.6&\rule{11mm}{2mm}\\
OSP&tactical&27.71&\rule{12mm}{2mm}\\
flight&strategic&28.47&\rule{12mm}{2mm}\\
OSP2&tactical&32.07&\rule{14mm}{2mm}\\
\end{tabular}
\end{center}
\caption[Median $\delta$ between STAR and LC]{Median 
 $\delta=(estimate(STAR) - estimate(lc))$
between effort
estimates generated by conventional means (LC)
and STAR.}\label{fig:deltas}
\end{figure}


%The median $\delta$ values of \fig{deltas} are around 
%0.4; i.e. a STAR estimate of 100 months
%could really range for 60 to 140 months.
%Compared to
%the effort estimate reductions shown in the  introduction, $\delta$ 
%is quite small.
%Recall that STAR reduced effort estimates to a small part of the initial values, sometimes
%a factor of 20; i.e by  a factor that is much larger than 0.4. Clearly,
%even if STAR is wrong by $\pm 40$\%, then the overall benefits to be gained from applying
%STAR's policies are  still
%dramatically large.


\subsection{Discussion}
%Given all the randomized exploration
%STAR performs over the space of possible $Models$, this discrepancy is very small.
%and 
%those discrepancies are dwarfed 
%by the much larger  effort reductions of Figure 1.
The Above result presented by STAR  is very interesting in that, even without any calibration data, and with only a realization of the space of those tunings, STAR was able to generate estimates similar to the estimates generated by LC. Keep in mind the LC works with local tuning data, and really is expected to do better. This result introduces us to the ability and effectiveness of STAR, and search based methods, to manage uncertainty in the absence of local data.

How are we to  explain the remarkable effectiveness of STAR in
managing uncertainty?
Researchers in planning and theorem proving have
recently shown that as model complexity grows, other constraining
effects may appear such as ``master variables''; i.e. a small number
of settings that control all other
settings~\cite{crawford94,williams03}. Such master variables can
greatly reduce the search space within large models.  

 We hypothesize that software process models also contain master variables;
i.e. much 
 much of uncertainty in a model is due to the influence of a 
small subset
of model variables. If so, then after (a)~ranking variables
by their ability to constrain the output; and
(b)~applying a small number of the top-ranked variables;
then 
it should be possible to (c)~make
stable predictions
in the constrained space.
