%\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
\documentclass{sig-alternate}
\usepackage{graphicx}
\usepackage{wrapfig,url}
\usepackage{rotating}
\newcounter{over}
\newcounter{max}
\newcommand{\fred}[2]{\setcounter{over}{#2}\addtocounter{over}{#1}}
\newcommand{\boxplot}[5]{%
\scalebox{0.5}{\textcolor{white}{\setcounter{max}{#4}\addtocounter{max}{#5}\fred{#4}{-#2}}%
\begin{picture}(100,10)%
\put(0,0){\line(0,1){16}}%
\put(100,0){\line(0,1){16}}%
\put(#2,4){\line(1,0){\theover}}%
\put(#3,4){\circle*{4}}%
\put(50,0){\line(0,1){16}}%
\end{picture}}
} 
\usepackage{eso-pic}
\usepackage{color}
\usepackage{type1cm}
%\makeatletter
%  \AddToShipoutPicture{%
%    \setlength{\@tempdimb}{.5\paperwidth}%
%    \setlength{\@tempdimc}{.5\paperheight}%
%    \setlength{\unitlength}{1pt}%
%      \makebox(600,900){\rotatebox{45}{\textcolor[gray]{0.80}{\fontsize{5cm}{5cm}\selectfont{Draft v5}}}}}
%\makeatother
%
\newenvironment{smallitem}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{itemize}
   \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{itemize}}
\newenvironment{smallenum}
 {\setlength{\topsep}{0pt}
  \setlength{\partopsep}{0pt}
  \setlength{\parskip}{0pt}
  \begin{enumerate}
  \setlength{\leftmargin}{.2in}
  \setlength{\parsep}{0pt}
  \setlength{\parskip}{0pt}
  \setlength{\itemsep}{0pt}}
 {\end{enumerate}}

 \newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
 \newcommand{\bi}{\begin{smallitem}}
\newcommand{\ei}{\end{smallitem}}
 \newcommand{\be}{\begin{smallenum}}
\newcommand{\ee}{\end{smallenum}}
\newcommand{\fig}[1]{Figure~\ref{fig:#1}}
\newcommand{\eq}[1]{Equation~\ref{eq:#1}}
\newcommand{\tion}[1]{\S\ref{sec:#1}}

%\usepackage{times}
\usepackage{alltt}
\usepackage{url}
% IEEE Computer Society needs nocompress option
% requires cite.sty v4.0 or later (November 2003)
\usepackage{cite}
% normal IEEE
 % \usepackage{cite}

% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\pdfpagewidth=8.5in
\pdfpageheight=11in
\begin{document}

\conferenceinfo{PROMISE'10} {September 12--13, 2010, Timisoara, Romania} 

\CopyrightYear{2010}

\crdata{978-1-60558-036-4/08/05}


\title{A Baseline Method For Search-Based Software Engineering}

\numberofauthors{1}
%
\author{
\alignauthor Gregory Gay
\\
	\affaddr{University of Minnesota}\\ 
	\affaddr{Minneapolis, MN}\\
       \email{greg@greggay.com}
}
\date{19 May, 2010}

\maketitle
\begin{abstract}
{\bf Background:} Search-based Software Engineering (SBSE) uses a variety of techniques such as evolutionary algorithms or meta-heuristic searches but lacks a standard baseline method.\newline 
{\bf Aims}: The KEYS2 algorithm meets the criteria of a baseline. It is fast, stable, easy to understand, and presents results that are competitive with standard techniques.\newline
{\bf Method:} KEYS2 operates on the theory that a small subset of variables control the majority of the search space. It uses a greedy search and a Bayesian ranking heuristic to fix the values of these variables, which rapidly forces the search towards stable high-scoring areas.\newline  
{\bf Results:} KEYS2 is faster than standard techniques, presents competitive results (assessed with a rank-sum test), and offers stable solutions.\newline
{\bf Conclusions:} KEYS2 is a valid candidate to serve as a baseline technique for SBSE research.
\end{abstract}
\category{I.2.8}{Problem Solving, Control Methods, and Search}{Heuristic methods}
\category{D.2.8}{Requirements/Specifications}{Tools}
\keywords{search-based software engineering, requirements optimization, meta-heuristic search}

\newpage

\section{Introduction}

Despite decades of research, testing, trials, and deliberation from both industry and academia, 
many fundamental questions of the software engineering field remain unanswered. Given the scope 
of many of these issues (for example, the entire space of programs developed in JAVA) or 
the required balancing between competing factors (i.e. the amount of money spent versus
the completion of goals), many of these questions are {\em unanswerable}.  
These are the areas where search-based software engineering (SBSE) has typically excelled. 

Search-based software engineering is the practice of reformulating typical software engineering issues as search problems, and applying meta-heuristic methods to find solutions. For any problem
that represents a set of competing - yet equally important - factors,
there will be no single perfect solution. Instead, there are likely to be several 
{\em near-optimal} solutions. In this implied space of trade-offs, meta-heuristic search 
techniques are ideal for sifting through a number of potential solutions for those that contain
an ideal balancing of factors. 

Although the concept of applying search to software engineering problems has existed for decades,
the term SBSE was coined and the field was formalized in 2001~\cite{harman01}. Since then, the SBSE 
research community has expanded rapidly. SBSE research has been applied successfully to requirements engineering~\cite{bagnall01,ruhe09,zhang07b}, 
project cost estimation ~\cite{kirsopp02,dolado01,burgess01}, testing ~\cite{baresel02,emer02,rhys09}, 
software maintenance ~\cite{harman02,mitchell02}, transformation~\cite{harman04b,fatiregun04,baresel04} and software evolution ~\cite{belle02} (among others).

SBSE practitioners  apply a variety of techniques, among them: genetic and evolutionary algorithms ~\cite{barricelli54,hol75},
hill-climbers ~\cite{metropolis53,kirkpatrick83,mcminn04},
tabu search~\cite{glover89,glover90},
particle swarm optimization~\cite{kennedy95,eberhart95},
and ant colony optimization~\cite{dorigo97}. 
Yet, there exists no agreed-upon baseline technique. A number of these approaches are common - simulated
annealing and genetic algorithms are heavily favored - and a "random search" is often used as a sanity 
measure, but there is no standard method to use as 
a basis for comparison when new methods are introduced.

In 1993, Robert Holte introduced the 1R classification algorithm~\cite{holte93}. In 
comparison to many of the prevalent techniques used at the time, such as the entropy-based 
C4.5 classifier, 1R was incredibly simple. The learning method treated each attribute of a data set as 
a continuous range (rather than as discrete intervals) and ranked them according to the error rate. 
Although Holte did not set out with the intention of defining a baseline for the data mining 
research field, there are several factors that perfectly positioned 1R for such a title:
\newline
\bi
\item {\em Simplicity}: 1R is easy to understand, using error rate as a judgment heuristic. 
\item {\em Competitive Results}: 1R produces results that are, on average, within 5\% of C4.5's on the same
data sets~\cite{holte93}.
\item {\em Fast Runtimes}: 1R is faster than more complex techniques. 
\item {\em Stable Results}: The results produced by 1R are consistent for the same data set over multiple trials.
\ei
A baseline technique for any field {\em must} have some level of simplicity. The algorithm must be easy to comprehend and 
easy to 
implement. 
A researcher's time and effort must
go into the technique meant to surpass the baseline, not the baseline itself.   
However, it is not enough to be simple - "dumb" ideas will yield poor results. 
For a algorithm to stand as a valid baseline, it must meet all
four of these factors; the heuristic must be easy-to-understand, fast, stable, {\em and} produce results that are competitive 
with state-of-the-art techniques. 

The PROMISE conference series
(and, ultimately, the entire academic world) seeks "repeatable, improvable, maybe even refutable, 
software engineering experiments."\footnote{Quoted from \url{http://promisedata.org/?page_id=2}}
It is not enough that some techniques, such as simulated annealing or random testing, 
reach near-ubiquity. 
The existence of a valid baseline gives a common basis of comparison, 
facilitating the repeatability 
and improvement of a wide variety of software engineering experiments.
Just as the data mining field has benefited from the use of 1R as a baseline~\cite{Witten05},
the SBSE research field would benefit as well. 

In this research, I propose the KEYS2 algorithm~\cite{gay10} as a candidate baseline technique for 
SBSE problems. KEYS2 is based on a straightforward theory - if the behavior of a model is 
controlled by a small number of {\em key} variables, then ideal solutions can be quickly found by
isolating those variables and exploring the range of their values. 
In a case study centered around the optimization of early life-cycle requirements models, KEYS2 
is demonstrated to fit all four of the factors required from a baseline technique and to have certain
advantages over other potential baseline methods, such as random search:
\bi
\item KEYS2 is based on a simple theory; that is, the exploitation of a small set of important variables.
\item KEYS2 produces results that are of higher quality than a simulated annealer and are 
competitive with a genetic algorithm (as assessed by a Mann-Whitney rank-sum test with a 95\% 
confidence interval). 
\item KEYS2 is faster than standard SBSE techniques, executing almost four times faster than
the genetic algorithm on the most complex models. 
\item KEYS2 produces stable results, and has the ability to produce partial solutions.
\ei

This work builds on previous optimization research with the KEYS algorithm. 
\bi
\item The original KEYS algorithm is presented in ~\cite{jalali08}.
\item KEYS2 is presented and both it and KEYS2 are benchmarked against a variety of search techniques, including Simulated Annealing, in  ~\cite{gay10}.
\item The contributions of this paper include a new genetic algorithm designed to optimize DDP models, new benchmarking experiments, and an explicit focus on a SBSE research context. 
\ei

\section{Search-Based Software Eng.}\label{sec:sbse}

Many of the problems inherent to the software engineering field deal in the {\em balancing} of
competing factors. Consider these scenarios:
\bi
\item Do you want to finish a project with money left in the budget, or is it more important to deliver a robust feature set? 
\item If the programmers are not meeting deadlines, you could replace them with a new team. 
Would the additional man-hours required for training and catch-up be worth the possible benefits?
\item If a longer design cycle would result in a shorter programming period, will too many defects slip by unnoticed?   
\ei

In many of these cases, there is no {\em perfect} solution. In fact, there could be dozens of "good"
solutions. 
Instead of finding some theoretical catch-all answer, software engineering problems 
are typically concerned with near-optimal solutions. That is, 
the subset of solutions that fall within a certain 
tolerance threshold. While it may be impossible or impractical to attempt to find the single {\em best} solution, it is certainly
possible to compare two candidate solutions. This comparison forms the basis of search-based
software engineering. 

Search-based software engineering is a research field concerned with the reformulation 
of standard software engineering problems as search problems, and the application of heuristic techniques to solve
said problems. 
Because of this implied trade-off space, meta-heuristic search-based methods are ideal for producing
a set of near-optimal candidate solutions. 

According to Clark and Harman~\cite{harman04,harman01}, there are four key properties that must be met before 
attempting to apply a SBSE solution:
\bi
\item {\em A Large Search Space}: If there are only a small number of options to optimize, there is no need for a meta-heuristic approach. 
This is rarely the case, as software engineering typically deals in incredibly large search spaces (for instance, the Eclipse project contains over two million lines of code and 7500 classes).  
\item {\em Low Computational Complexity}: If the first property is met, SBSE algorithms must sample a non-trivial population.
Therefore, the computational complexity of any evaluation method or fitness function
has a major impact on the execution time of the search algorithm. 
\item {\em Approximate Continuity}: Any search-based optimization must rely on an objective function for guidance. Some level of
continuity will ensure that such guidance is accurate. 
\item {\em No Known Optimal Solutions}: If an optimal solution to a problem is already known, then there is no need to apply search techniques. 
\ei 

The first and last properties are absolutely necessary for any search-based software engineering solution to succeed. The second and third
{\em should} be met, but if they are not, it may still be possible to formulate the problem as a search-based one~\cite{baresel04,harman04b}.

\subsection{Simulated Annealing}\label{sec:sa}

Simulated annealing (SA)~\cite{metropolis53,kirkpatrick83} is a sophisticated hill-climbing search 
algorithm. Hill-climbing searches survey the immediate neighborhood and 
"climb" to higher-scoring states, continuing until they reach a peak (that is, an optimal area in the search space).
Hill-climbers are prone to becoming stuck in local maxima, returning a sub-optimal solution.
To avoid this, simulated annealing utilizes a technique from its namesake. Annealing is a metallurgy technique where a material is 
heated, then cooled. The heat causes the atoms in the material to 
wander randomly through different energy states and the cooling process increases the chances of finding a state with a lower energy than the starting position.
When assessing each neighbor, SA will jump to a sub-optimal neighbor at a probability determined by the current {\em temperature}. When that temperature is high, SA will jump around the search space wildly. As it cools, the algorithm will stabilize into what is, ideally, an optimal area of the search space.

Simulated annealing and hill-climbers are widely used in SBSE research for several reasons. 
They are simple to understand, easy to implement, and are typically very fast~\cite{mcminn04}. 
However, they have several known flaws. While the temperature function helps to prevent the search from
becoming stuck in local maxima, it does not completely mitigate this problem. In fact, past research
has shown that the additional
randomness in this search often leads to an unacceptable level of variance in the 
results~\cite{gay10,gay10b}.
Thus, one must take caution when choosing a cooling strategy - cool too quickly, and it is likely that the annealer will return a sub-optimal solution. 

This research uses a version of simulated annealing tuned specifically for the DDP models (discussed
in Section \ref{sec:ddp}). 
During each round, SA ``picks'' a neighboring set of mitigations. To calculate the configuration of this neighboring solution, a function traverses the mitigation settings of the current state and randomly flips those settings (at a 5\% chance). 
If the neighbor has a better score, SA will move to it and set it as the current state. If no score improvement is seen, the algorithm will decide whether or not to move based on the following probability function:
\begin{equation}\label{eq:ps1}
prob(moving) = e^{((score-neighborscore) * \frac{time}{temp})}
\end{equation}
\begin{equation}\label{eq:ps}
temp = \frac{(maxtime-time)}{maxtime}
\end{equation}
If the value of the {\tt prob} function is greater than some randomly generated number, SA will move to that state regardless of its score. The algorithm will continue to operate until the number of tries is exhausted (i.e. the temperature drops to zero) or a score meets the threshold requirement. 

\subsection{Genetic Algorithms}

Inspired by early experiments with the computational simulation of evolution~\cite{barricelli54,hol75},
genetic algorithms (and the broader field of evolutionary algorithms) have become one of the most 
famous meta-heuristics used in the search-based software engineering
literature. Influenced by Darwin's Theory of Evolution, genetic algorithms take a group of 
candidate solutions and mutate them over several generations - filtering out bad "genes" and promoting good ones. 
Genetic algorithms rely on four major attributes: 
population, selection, mutation, and crossover. 

During each generation (that is, each step of the algorithm), 
a population of solutions is considered.
Each member of the population is made up of a
set of binary switches.
These switches are collectively known as the chromosomes, the genetic makeup, of a particular solution state.
Typically, a potential solution must be carefully translated to this binary representation. 
However, as the models in this research are naturally represented as a set of binary variables, no special encoding of the 
model states is necessary. This has an additional benefit of reducing the required setup and 
execution time. The GA can make
use of the same fitness function that the simulated annealer and KEYS2 use. 

Because the initial population is unlikely to have the "best" solution, some form of diversity must 
be induced into the population.
This diversity is established by forming children using the crossover and mutation operations.
During each generation, several "good" solutions (as scored by a predetermined fitness function) are 
chosen by
the selection mechanism to generate new children for the next generation. The values of the binary settings in these children are determined by the crossover mechanism, which combines chromosome settings from each parent and inserts them into the offspring with 
probability $P_{crossover}$.
A mutation mechanism takes high-quality members of the current population and moves them over to the 
next generation while instilling small changes in their chromosomes. 
Mutation is necessary to prevent the algorithm from being trapped in local maxima. 
To avoid the loss of good solutions, a certain number of the best results
will be copied
to the next generation without any sort of modification.
This process is repeated with a new population each round until a certain threshold 
(commonly related to the  performance score, number of generations, or a set time period) has passed. 

To summarize, a 
standard genetic algorithm 
follows this framework:
\bi
\item Evaluate each member of the population.
\item Create a new populations using these scores along with the crossover and mutation mechanisms.
\item Discard the old population and repeat the process.
\item Stop if $time > maxtime$ (in number of generations or some real-time threshold).
\ei

The genetic algorithm used in this research creates a population of size 100 each round, and 
selects all population members that score within 10\% of the top-scoring member (as determined by the
objective function defined in Section \ref{sec:ddp}) to "reproduce." The chosen {\em parents} populate 
40\% of the next population (15\% through crossover, 20\% through mutation, and 5\% are carried over 
unchanged). The remaining 60\% of the population are randomly generated. These percentage values were 
chosen at the overall best values after an exhaustive search across five models, incrementing each 
factor by 5\% each round. Each setting can be overridden by the user. This genetic algorithm 
stops after the number of past generations is equal to the number of variables in the model being optimized.  

\subsection{KEYS2}\label{sec:keys}

The core premise of KEYS2 is that standard SBSE techniques perform over-elaborate searches.
Suppose 
that the behavior of a large system is
determined by a small number of {\em key} variables. 
If so, then stable near-optimal solutions can be quickly found by finding these {\em keys} and then 
exploring the range of their values.

Within a model, there are chains of {\em reasons} linking select inputs to the desired goals.
Some of the links clash with others. However, some of those clashes are not dependent on other clashes. 
In the following chains of reasoning 
the clashes are $\{e, \neg e\}$, 
$\{g, \neg g\}$ 
\& $\{j,\neg j\}$;
the independent clashes 
are
$\{e \neg e\}$, 
\& $\{g \neg g\}$, 
\[\begin{array}{r@{}l@{}l}
&a \longrightarrow b \longrightarrow c \longrightarrow d \longrightarrow e\\
input_1 \longrightarrow  &f \longrightarrow g \longrightarrow h \longrightarrow i \longrightarrow j & \longrightarrow goal\\
input_2 \longrightarrow  &k \rightarrow \neg g \longrightarrow l \longrightarrow m \rightarrow \neg j & \longrightarrow goal\\
%&n \longrightarrow o \longrightarrow p \longrightarrow q \longrightarrow
\neg e
\end{array}
\]
In order to optimize decision making about this model, we must first decide about these independent 
clashes (these are the {\em keys}).
Returning to the above reasoning chains,
any of $\{a, b, ..q\}$ are subject to discussion.
However, most of this model is completely irrelevant to the task of
$input_i\vdash~goal$. For example, 
the $\{e, \neg e\}$ clash is
irrelevant to the decision making process
as no reason uses $e$ or $\neg e$. 
In the context of reaching $goal$ from 
$input_i$, the only important discussions are
the clashes $\{g,\neg g,j,\neg j\}$.
Further, since $\{j, \neg
j\}$ are dependent on $\{g,\neg g\}$, then the core decision
must be about variable $g$ with two disputed values: true and
false. 

Fixing the value of these keys reduces the number of reachable states within the model. 
This is called the $clumping$ effect. Only a small fraction of the possible states are actually reachable.
The effects of clumping can be quite dramatic.
Without knowledge of these keys,  the above example model has $2^{20}$ 
possible states.
However, in the context of 
$input_i\vdash~goal$,
that massive collection of states clumps to the following two configurations: 
$\{input_1,f,g,h,i,j,goal\}$ or
$\{input_2,k,\neg g,l,m,\neg j,goal\}$.

The KEYS algorithm finds these key variables using a greedy search and a Bayesian ranking heuristic (called BORE). 
If a model contains keys then, by definition, those variables must appear in all solutions
to that model. If model outputs are scored by some objective function, then the key variables are 
those with ranges that occur with very different frequencies
in the high and the low scoring model configurations.
Therefore, we need not waste time searching for the keys - rather, we just need to keep frequency counts 
on how often ranges appear in $best$ or $rest$ outputs.

The greedy
search explores a space of $M$ 
mitigations over the course of $N$ eras.  
Initially, the entire set of mitigations is set randomly. 
During each era, one more
mitigation is set to $M_i=X_j$, $X_j \in \{true,false\}$. 
In the original version of KEYS~\cite{jalali08}, the greedy search fixed the value of one variable per era.
KEYS2, fixes an increasing number of variables as the search progresses. That is, KEYS2 fixes one variable in
the first era, two in the second era, three in the third era, and so on

In KEYS2, each era $e$ generates
a set $<input,score>$ as follows:
\be
\item[1:]
$MaxTries$ times repeat:
\bi
\item
$Selected[1{\ldots}(e-1)]$ are settings from previous eras.
\item
	$Guessed$ are randomly selected values for unfixed mitigations.  
\item
	$Input = selected \cup guessed$.
\item
Call {\tt model} to compute $score=ddp(input)$;
\ei
\item[2:] The $MaxTries$ $score$s are divided into $\beta$\% ``best'' 
and remainder become ``rest''. 
\item[3:]
The $input$ mitigation values are then scored using BORE
(described below).
\item[4:]
The top ranked mitigations are fixed and stored in $selected[e]$.\ee
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure KEYS
2. while FIXED_MITIGATIONS != TOTAL_MITIGATIONS
3.    for I:=1 to 100
4.       SELECTED[1...(I-1)] = best decisions up to this step
5.       GUESSED = random settings to the remaining mitigations
6.       INPUT = SELECTED + GUESSED
7.       SCORES= SCORE(INPUT)
8.    end for   
9.    for J:=1 to NUM_MITIGATIONS_TO_SET 
10.      TOP_MITIGATION = BORE(SCORES)       
11.      SELECTED[FIXED_MITIGATIONS++] = TOP_MITIGATION 
12.   end for  
13. end while          
14. return SELECTED \end{verbatim} }
~\hrule~
\caption{Pseudocode for KEYS}
\label{fig:KEYS}
\end{figure}

The search moves to era $e+1$ and repeats steps 1,2,3,4.
This process stops 
when every mitigation has a fixed value.  
The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment.
Past research has shown that, for DDP model optimization, these should be set to 
$MaxTries=100$ and $\beta=10$~\cite{jalali08}.
For full details, see \fig{KEYS}. 

KEYS ranks mitigations using a support-based
Bayesian ranking measure called BORE.
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)$.
When applying the theorem, {\em likelihoods}
are computed from observed
frequencies. These likelihoods (called "like" below for space consideration) are then normalized to calculate probabilities. 
This normalization cancels out $P(E)$ in Bayes' theorem.
For example, after $K=10,000$ runs are divided into  1,000 {\em best} solutions and 9,000
{\em rest}, the  value \mbox{$mitigation31=false$} might appear 10 times in the $best$ solutions, but only
5 times in the $rest$. Hence:\newline
\begin{minipage}{1.0\linewidth}
{\scriptsize
\begin{eqnarray}\nonumber
E&=& (mitigation31=false)\\\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}}
\end{minipage}\newline
Previously~\cite{clark05},
it has been found that Bayes' theorem
is a poor ranking heuristic
since it is easily 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 the problem of unreliable low frequency evidence, \eq{ten} is augmented
with a support term.
Support should $increase$ as the frequency of a value $increases$,  i.e. 
$like(best|E)$ is a valid support measure.
 Hence, step 3 of the greedy search ranks values  via
\begin{equation}\label{eq:ps3}
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}


\section{Case Study: The Defect Detection and Prevention Model}\label{sec:ddp}

The
Defect Detection and Prevention (DDP) requirements modeling tool~\cite{corn01,feather08}. 
is used to interactively document the 
early life-cycle
 meetings conducted by "Team X" at 
NASA's Jet Propulsion Laboratory (JPL). 

At Team X meetings, groups of up to 30 experts from various fields (propulsion, engineering,
communication, navigation, science, etc) meet for short periods of time to produce
a design document. This document may commit the current project to certain design choices. For example,
the experts might choose solar power rather than nuclear power, or they might decide to use some particular style of guidance software. 
All subsequent work on the project is guided by the initial design decisions made in these mission concept documents. 

\begin{figure}[!t]
{\footnotesize
\begin{tabular}{p{\linewidth}}\hline
\be
\item Requirement goals:
\bi
\item
Spacecraft ground-based testing \& flight problem monitoring
\item
 Spacecraft experiments with on-board Intelligent Systems Health Management (ISHM)
\ei
\item Risks:
	\bi
	\item Obstacles to spacecraft ground-based testing \& flight problem monitoring
			\bi
			\item
			Customer has no, or insufficient, money available for my use
			\item
			Difficulty of building the models and design tools
			\ei
	\item ISHM Experiment is a failure (without necessarily causing flight failure)
	\item Usability, User/Recipient-system interfaces undefined
	\item V\&V (certification path) untried and the scope is unknown
	\item Obstacles to spacecraft experiments with on-board ISHM
	\bi
	\item Bug tracking / fixes / configuration management issues, managing revisions and upgrades (multi-center tech. development issue)
	\item Concern about my technology interfering with in-flight mission
	\ei
	\ei
\item Mitigations:
	\bi
	\item  Mission-specific actions
		\bi
		\item Spacecraft ground-based testing \& flight problem monitoring
		\item  Become a team member on the operations team
		\item Use Bugzilla and CVS
		\ei
	\item  Spacecraft experiments with on-board ISHM
		\bi
		\item Become a team member on the operations team
		\item Utilize ISHM expert's experience and guidance with certification of his technology
		\ei
	\ei
\ee\\\hline
\end{tabular}}
\caption{Sample DDP requirements, risks, and mitigations.}\label{fig:ddpegeg}
\end{figure}

The DDP model allows for the representation of the goals, risks, and
risk-removing mitigations that belong to a specific project.  
During  a Team X meeting,
users of DDP explore the combinations of mitigations that will cost the least amount of money
while still allowing for the completion of a large number of requirements.  
For example, here is a trivial DDP model
where  {\tt mitigation1} costs \$10,000 to apply and each requirement is of equal
value (100). Note that the mitigation can remove 90\% of the risk. Also, unless mitigated,
the risk will disable 10\% to 99\% of requirements one and two:
\begin{equation}\label{eq:mod1}
\overbrace{mitigation1}^{\$10,000} \underbrace{\rightarrow}_{0.9} risk1 \rightarrow
\left< \begin{array}{c} \overbrace{\rightarrow}^{0.1} (requirement1=100) \\ 
\underbrace{\rightarrow}_{0.99} (requirement2=100) \end{array} \right.\end{equation}
The other numbers show the impact of mitigations on risks, and the impact of risks
on requirements. DDP propagates a series of influences over two matrices: 
one for {\em mitigations*risks} and another for
{\em risks*requirements}.

DDP uses the following ontology:
\bi
\item \textit{Requirements} (free text) describe the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) of each requirement, reflecting
their relative importance; 
\item \textit{Risks} (free text) are
events that damage the completion of requirements; 
\item \textit{Mitigations}: (free
text) are actions that reduce risks; 
\item \textit{Costs}: (numbers) reflect the cost associated with activating a mitigation;
\item \textit{Mappings}: directed, weighted edges between
requirements, mitigations, and risks that capture the quantitative relationships among them. 
\item \textit{Part-of relations}:
structure the collections of requirements, risks and mitigations; 
\ei

To improve runtimes, a compiler stores a flattened form of the DDP requirements tree in a 
function usable by any program written in the C language. 
In the compiled form, all computations are  performed once 
and added as a constant to each reference of the requirement.
The topology of the mitigation network is represented as terms in equations within the {\tt model} function,
which is called each time that a configuration of the entire model needs to be scored by a fitness function. 
As the models grow more complex, so do these equations. The largest 
real-world model used in this research, which contains 99 mitigations, generates 1427 lines of code.
\fig{ddpModels} contains details on five publicly-available DDP models.  

\begin{figure}[!t]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|c|c|} \hline
Model&LOC&Objectives&Risks&Mitigations\\ \hline
model1.c&  55  &3         &2    &2          \\ \hline
model2.c& 272   &1         &30   &31         \\ \hline
model3.c& 72   &3         &2    &3         \\ \hline
model4.c& 1241   &50        &31   &58         \\ \hline
model5.c&1427    &32        &70   &99         \\ \hline
\end{tabular}
\end{center}
\caption{Details of Five DDP Models. }
\label{fig:ddpModels}
\end{figure}

When the {\tt model} function is called, two values are returned (the total cost of the selected 
mitigations and the number of reachable requirements attained). 
These two values are input into the following objective function in order to calculate a fitness score 
for the current configuration of the model.
This objective function normalizes the cost and attainment values 
into a single score that represents the Euclidean distance to a {\em sweet spot} of 
maximum requirement attainment and minimum cost: 
\begin{equation}\label{eq:score}
score = \sqrt{\overline{cost}^2 + (\overline{attainment}-1)^2}
\end{equation}

Here, $\overline{x}$ is a normalized value 
$0 \le \frac{x - min(x)}{max(x) - min(x)} \le 1$. 
Hence, scores ranges $0 \le score \le \sqrt{2}$ and
{\em lower} scores are {\em better}.

DDP is a valid choice for early life-cycle requirements optimization for 
three reasons:
\bi
\item One potential drawback with ultra-lightweight models is that they are excessively lightweight and contain no useful
information. DDP models are demonstrably useful for NASA, and clear project 
improvements (such as savings in power and mass) have been seen from DDP sessions at JPL. 
Cost savings of \$100,000 have been seen in multiple sessions, and in at least two sessions, they have exceeded \$1 million~\cite{feather08}. 
\item Numerous real-world requirements models have been written in this format,
and many projects are likely to use these models in the future~\cite{feather08b}. The DDP tool can be used to document not just final decisions, but also to review the rationale that led to those decisions.
Hence, it remains in use at JPL not only for its original purpose (group decision support),
but also as a design rationale tool to document decisions. 
\item The DDP tool is representative of other requirements modeling tools in widespread use. 
DDP is a set of directed influences expressed in a rigid hierarchy and controlled by a set of equations. 
At this level of abstraction, DDP
is just another form of QOC~\cite{shum94}  or a variant of Mylopoulos' soft goal graphs~\cite{mylo99}.
\ei

Like any interesting search-based software engineering problem, DDP models represent a space of 
competing factors. In this case, the trade-off is between the budget of a project and 
the attainment of goals. 
Using the four properties of SBSE problems (as discussed in Section \ref{sec:sbse}), it can 
be shown that the optimization of DDP models is a valid application area for SBSE techniques.
\bi
\item Typical DDP models present a massive search space, encompassing hundreds to thousands of possible combinations of mitigation settings. 
One collection of model settings must comment on dozens of individual 
mitigations. In one known model, there are over $2^{99}$ \newline 
(${mitigation\:values}^{number\:of\:mitigations}$) possible combinations. 
\item With such a large number of combinations in the search space, any candidate
solution must execute in a short time (to meet the second condition of a SBSE problems). 
As will be shown in Section \ref{sec:runtimes}, standard SBSE techniques execute in 
one second or less, implying a low computational complexity in the model assessment method.
Furthermore, past research~\cite{gay10} has demonstrated that the proposed baseline method, KEYS2, 
operates in low-order polynomial time ($O(N^2)$).
\item While DDP models do not represent a continuous search space (any model with 
{\em true/false} statements is, by definition, not continuous), this is not a problem. The objective function used to score a DDP configuration represents an approximately continuous trade-off between project costs and feature attainment. Therefore, it provides the 
necessary guidance needed to meet the third condition.  
\item Finally, DDP models have no known optimal solution. In fact, any solution is dependent on the specific features of the project being modeled. 
As such, a search method {\em must} be employed in order to calculate some set of {\em near-optimal solutions}. 
\ei

By meeting all four of these conditions, 
the optimization of these early life-cycle DDP models is a valid avenue for search-base software 
engineering research.

\section{Experiments \& Results}

\begin{figure*}[!t]\centering
\begin{center}\scriptsize
\begin{tabular}{c@{}c@{}c@{}c@{~}c}
&~~~~~&Model 2&Model 4 &Model 5 \\
&~~~~~& (31 mitigations)& (58 mitigations)&(99 mitigations)\\ \hline
\begin{sideways}Simulated\end{sideways}&\begin{sideways}Annealing\end{sideways} & \includegraphics[width=4.25cm]{WithLabel/2/SA.pdf} & \includegraphics[width=4cm]{WithLabel/4/SA.pdf} & \includegraphics[width=4cm]{WithLabel/5/SA.pdf} \\\hline 
\begin{sideways}Genetic\end{sideways}&\begin{sideways}Algorithm\end{sideways} &\includegraphics[width=4.25cm]{WithLabel/2/model2_nob.pdf} & \includegraphics[width=4cm]{WithLabel/4/model4_nob.pdf} & \includegraphics[width=4cm]{WithLabel/5/model5_nob.pdf} \\ \hline
\begin{sideways}~~~~~KEYS2\end{sideways}& & \includegraphics[width=4.25cm]{WithLabel/2/model2_keys2.pdf} & \includegraphics[width=4cm]{WithLabel/4/model4_keys2.pdf} & \includegraphics[width=4cm]{WithLabel/5/model5_keys2.pdf} \\
\end{tabular}
\caption{Results of each algorithm for each model (1000 trials per algorithm/model pairing).
The y-axis shows
cost (in thousands) and  the x-axis shows attainment. 
Better solutions fall towards the bottom right of each plot (low costs and high attainment) 
and are clumped tightly together (low variance).
\label{fig:finalModelResults}
}
\end{center}
\end{figure*}


While the "simplicity" of the KEYS2 algorithm is arguably subjective, the
other three requirements of a baseline algorithm can be assessed qualitatively. 
In order to demonstrate that KEYS2 is a valid candidate
for a baseline technique, it must be experimentally shown to be:
\bi
\item Results that are competitive with those of state-of-the-art techniques.
\item As fast as competing algorithms.
\item A low level of variance in its results.
\ei

In the following experiments, three algorithms (KEYS2, a simulated annealer, and a genetic 
algorithm) will be used to optimize three of the five publicly-available DDP models\footnote{
These models are available from the PROMISE repository at \url{http://promisedata.org/?cat=133}}.
Note that:
\bi
\item Models one and three are trivially small. They were used to debug source code, but have been excluded from the following experiments.
\item Model 4 was previously discussed in detail~\cite{me03n}. Model 5 was optimized in ~\cite{fea02a}.
\item All five models were optimized by the original KEYS algorithm in ~\cite{jalali08}. However, that paper presented no comparison results.
\item KEYS2 was benchmarked against a variety of algorithms, including simulated annealing, on models 2,4, and 5 in ~\cite{gay10}. However, 
no results were reused. All results presented in this paper are from new trials.
\ei

\subsection{Result Quality}\label{sec:quality}

By definition, the purpose of a baseline is to provide a {\em starting goal}. It should set some kind of bar that a newly-developed
technique must pass before it can be considered for real-world use. 
However, while the goal of any experiment will be to "beat" the baseline score, that does not mean that a baseline should
be some sort of "straw man." A baseline technique might not yield results that surpass the state-of-the-art, but it should at
least be {\em competitive} with them. 

In order to assess the overall result quality, each algorithm was executed 1000 times per model. These results
are plotted in Figure \ref{fig:finalModelResults}. In each graph, the x-axis represents the "attainment" (the number 
of project objectives that were successfully completed in the final configuration of the model). The y-axis
is the cost, in thousands, of the mitigations employed by that model configuration. 
Better results are those that appear in the bottom-right corner. These are the configurations resulting in a low cost and high attainment 
of goals. 
It follows that the worst results are in the top-left, the area of high cost and low attainment. 

A visual inspection gives a very clear idea of the result quality. The simulated annealing 
method can instantly be eliminated from the comparison. Its results, for every model, fall all over
the graph. Very few of its conclusions result in an ideal balance of the cost and attainment. Even if some of its results 
are ideal, the massive level of variance eliminates it from the competition. 
Both KEYS2 and the genetic algorithm fare better, with the vast majority of their results concentrated
in the ideal low cost, high attainment area. 

To confirm this visual analysis, the distribution of values for each algorithm and each model were compared
using a non-parametric rank-sum test (Mann-Whitney) with a 95\% confidence interval. Separate tests were completed
for cost and attainment for each of the three models. The wins, ties, and losses were aggregated and are listed in Figure \ref{fig:wlt}.

\begin{figure}[!h]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|r|} \hline
Algorithm&Ties&Wins&Losses&Score (wins-losses)\\ \hline
Genetic Algorithm& 0 & 7 & 5 & 2 \\ \hline
KEYS2& 0 & 7 &5 & 2\\ \hline
Simulated Annealing& 0 & 4 & 8 & -4 \\ \hline
\end{tabular}
\end{center}
\caption{Win-loss-tie results from a Mann-Whitney rank-sum test with a 95\% confidence interval. }
\label{fig:wlt}
\end{figure}

As expected, the wide range of results for simulated annealing hurt its overall result quality. The algorithm
lost twice as often as it won in comparison tests. KEYS2 and the genetic algorithm yielded the exact same number of 
wins and losses. While they never tied, the fact that they traded wins and losses at such equal parity shows that KEYS2
is extremely competitive with the most commonly used SBSE techniques. 

\subsection{Runtimes}\label{sec:runtimes}

For both researchers and industrial practitioners, time is limited and expensive. 
By asking any of these individuals to run a baseline algorithm for comparison purposes, we
are implicitly asking them to spend more time considering a problem. Therefore, it is crucial
that any baseline technique be fast, even real-time if possible. 

In order to compare execution times, each algorithm was executed for each model 100 times. 
The total time for these 100 trials was recorded using the Unix {\tt time} command, and the 
"real time" value was divided by 100 in order to calculate the average execution time. 

All three algorithms were executed under the same operating conditions on the same machine - a 
Dell XPS workstation with a 2.40 GHz Intel Core2 Duo CPU and 2 GB of memory running the Ubuntu
8.04 operating system.  

\begin{figure}[!h]
\small
\begin{center}
\begin{tabular}{|c|r|r|r|} \hline
Algorithm&Model 2&Model 4&Model 5\\ \hline
simulated annealing&0.40967&0.94350&0.64050\\ \hline
genetic algorithm&0.00976&0.04625&0.09948\\ \hline
KEYS2&0.00430&0.01407&0.02695\\ \hline
\end{tabular}
\end{center}
\caption{Average runtimes for each algorithm on each model, in seconds, averaged over 100 runs.}
\label{fig:runtimes}
\end{figure}

The results of this experiment can be seen in Figure \ref{fig:runtimes}. The simulated annealer
clearly experiences some difficulty in optimizing these models. It takes orders of magnitude more
time to complete a single run than other algorithms. 

The remaining two algorithms are incredibly fast, both returning results in under a tenth of a 
second on average. A closer look shows that KEYS2 is still much faster than the genetic algorithm,
completing each trial between 2.27 to 3.69 times faster than its competitor.  

\subsection{Stability}\label{sec:stability}

The results shown in Section \ref{sec:quality} give some idea of the variance in the performance of 
each of the compared techniques. From a visual inspection of Figure \ref{fig:finalModelResults}, it is clear that the annealer's
final values are unpredictable. Very few of its results fall in the ideal bottom-right corner (where the project leads pay a little
to achieve a lot). The final score values of both the genetic algorithm and KEYS2 fall in a much smaller cluster.  
To gain a clearer view of the result variance of each algorithm, we will examine
the range of values output by each algorithm for the largest model (model 5 from Section \ref{sec:ddp}). 

\begin{figure}[!h]
\scriptsize
\begin{center}
\begin{tabular}{c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}c}
\multicolumn{1}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{2-6}
&min& & med & &max\\\cline{2-6}
&0& 25\%& 50\% & 75\%&100\%\\\cline{1-6}
SA&163000&239025&248525&709025&1079000&\boxplot{11.2}{11.2}{17.1}{48.8}{25.8}\\ 
GA&162369&205525&215197&227525&312052&\boxplot{11.2}{11.2}{14.8}{15.6}{78.5}\\
KEYS2&154025&198025&211525&224525&305525&\boxplot{10.6}{10.6}{14.5}{15.4}{79.0}\\
\end{tabular}
\end{center}
\caption{Quartile charts of the final "cost" results, taken from 1000 executions 
of each algorithm on model 5. Lines represent the full range of values, with the dot
representing the median.
}\label{fig:costquart}
\end{figure}

\begin{figure}[!h]
\scriptsize
\begin{center}
\begin{tabular}{c@{~}|c@{~}|c@{~}|c@{~}|c@{~}|c@{~}c}
\multicolumn{1}{c}{~}&\multicolumn{5}{c}{quartiles}\\\cline{2-6}
&min& & med & &max\\\cline{2-6}
&0& 25\%& 50\% & 75\%&100\%\\\cline{1-6}
SA&46.3&201.1&207.4&217.0&255.2&\boxplot{17.4}{17.4}{78.1}{81.7}{4.0}\\ 
GA&226.4&239.5&241.3&242.4&249.9&\boxplot{85.2}{85.2}{90.8}{91.2}{6.0}\\
KEYS2&227.3&236.2&237.9&239.4&252.0&\boxplot{85.5}{85.5}{89.5}{90.1}{5.2}\\
\end{tabular}
\end{center}
\caption{Quartile charts of the final "attainment" results, taken from 1000 executions 
of each algorithm on model 5. Lines represent the full range of values, with the dot representing
the median.
}\label{fig:attainquart}
\end{figure}

Figures \ref{fig:costquart} and \ref{fig:attainquart} show quartile breakdowns of the value
distributions for the cost and attainment results on model 5. Simulated annealing reaches median values that 
are weaker than, but not too far from, the other two algorithms. However, the full range of its 
results is much wider than that of KEYS2 or the genetic algorithm. Simulated annealing demonstrates an unacceptable
level of variance. KEYS2 and the GA yield similar results. The GA has a slightly tighter range 
of results with a spread (75th quartile - 25th) of 22000 to 26500 for cost and 2.9 to 3.2 on 
attainment. 

From this, it can be concluded that KEYS2 demonstrates the consistency required of a baseline method. 
However, its very design provides one additional degree of stability. 
Recall that each round, KEYS2 seeks out the most important variable and fixes its value. Thus,
by providing a linear ranking of model variables, KEYS2 could be stopped at any point during
its execution. Unlike the other two algorithms, KEYS2 can provide partial results. Because it generates 100 random configurations 
at each stage of execution, the variance of those partial decisions can be measured.  

\begin{figure}[!h]
\begin{center}
\includegraphics[width=3in]{model5.pdf}
\end{center}
\caption{Median and spread of internal decisions made by KEYS2 during one trial. X-axis shows the number
of rounds passed.  ``Median'' shows the 50th percentile of the measured
value seen in the 100 random configurations made during each round. ``Spread'' shows the difference between the 75th  and 50th percentile. }
\label{fig:in5}
\end{figure}

Figure \ref{fig:in5} demonstrates the internal stability during one execution of KEYS2 on model 5.
At any stage, the spread (i.e. the variance) of KEYS internal decisions can be measured. It
can clearly be seen that KEYS2 rapidly plateaus towards stable, high-scoring results for both the cost and attainment of goals. 
The ability to generate partial {\em or} complete solutions, both with a low degree of variance, 
lend credence to the use of KEYS2 as an experimental baseline. 

\section{Discussion \& Conclusions}

Despite the extensive body of research that has been invested in the 
search-based software engineering field over the past few years,
there is still no agreed-upon basis for comparison between the disparate research tracts. 
With all of the different improvements to and implementations of the {\em "standard"} techniques, it 
has become difficult
to achieve the PROMISE community's goal of "repeatable, improvable, maybe even refutable, software engineering experiments."

For the further expansion of the body of knowledge, it is necessary for the SBSE field to adopt some sort of baseline technique. 
Just as data mining research has benefited from Holte's 1R algorithm~\cite{holte93}, the SBSE community would benefit from a 
common baseline. Such a technique would allow comparisons between seemingly incomparable algorithms, would more easily allow for the 
repetition and improvement of existing experiments, and would give a performance goal to be beaten by newly-developed methods. 

However, not just any algorithm can be chosen as a baseline. A baseline technique must meet several criteria:
\bi
\item {\em Simplicity}: The method must be easily understood and easily implemented. If not, researchers will waste crucial
time and brainpower that would be better spent on their own ideas. 
\item {\em Competitive Results}: Although a baseline is meant to be "beaten," is should not be a straw man. It must
yield results within the same neighborhood as the state-of-the-art. 
\item {\em Fast Runtimes}: By asking a researcher to execute a baseline algorithm, you are implicitly asking them to devote 
more time to their experiments. Thus, an ideal baseline technique should execute in an almost unnoticeable amount of time. 
\item {\em Stable Results}: A baseline technique must be reliable and trustworthy. It must return results that fall within
a small range of fitness values.
\ei 
It is not enough for a technique to meet one or two of these criteria. A fast algorithm is pointless if its results are seemingly random. Likewise,
a simple method is not useful if its results are poor. A baseline algorithm should be fast, reliable, competitive, and be straight-forward
to implement. 

Out of the commonly-used approaches in the SBSE field, 
random search is likely the closest to an agreed-upon baseline.
Random search is used by may researchers as a "sanity check," a de facto bar to beat with their algorithm of choice
~\cite{harman10}. 
However, random search is a weak approach. Its very nature
implies that it will eventually violate either the second or third of the previously-specified properties of a baseline. 
Although it {\em may} find an ideal solution in a short amount of time, 
there is no way to ensure that it {\em always} will. Because
it picks inputs at random, there will be a massive amount of variance in its final 
results (for a similar effect, see the simulated annealing results in
Sections \ref{sec:quality} and \ref{sec:stability}). There is some  empirical 
evidence that, given enough time, random testing will deliver predictable results~\cite{ciupa09}. However, 
such a time threshold will violate the second guideline, that any baseline execute quickly.  
Many researchers seem to have little confidence in random search, treating it as a straw man. As Harman notes, 
"It is something of a 'sanity check'; in any optimization problem worthy of study, the chosen technique should be able to convincingly outperform random search.~\cite{harman10}"
The use of random search is an ongoing debate in the SBSE community~\cite{arcuri10}. I would suggest, despite the popularity of random search, a stronger baseline algorithm 
should be chosen.  

The KEYS2 algorithm~\cite{jalali08,gay10} meets all of these criteria. 
It is based on a straightforward theory, that a small number of important variables control the vast majority of the search space. 
A search that rapidly isolates these variables and fixes their values will quickly plateau 
towards stable, optimal solutions. 
In a case study centered around the DDP early life-cycle requirements models~\cite{corn01,feather08}, KEYS2 was demonstrated to 
fulfill the other three requirements.
\bi
\item In Section \ref{sec:quality}, it is shown that KEYS2 and a genetic algorithm are statistically identical in terms of quality.
They yielded the same number of wins and losses in a series of rank-sum tests. 
\item Section \ref{sec:runtimes} shows that KEYS2 executes three or more times faster than other SBSE techniques. 
\item Finally, Section \ref{sec:stability} demonstrates that KEYS2 yields stable results. KEYS2 can also output partial results, and
the variance and spread of these can be examined as well.
\ei
Thus, KEYS2 is a candidate to serve as a baseline technique for the SBSE field. 

I am not presumptuous enough to insist that KEYS2 be the absolute baseline or even that it is the best candidate. 
However, it is crucially important to debate this topic. 
Even amongst "standard" techniques like simulated annealing, there are thousands of slightly different implementations and tweaks. Direct
comparisons are almost impossible. For the goal of open research to become 
possible, a simple (yet competitive) technique should
be adopted and made available to the research community. Such a baseline is necessary for the growth of this research field, and the PROMISE
community is in an ideal position to promote its use. 


\bibliographystyle{plain}
\bibliography{refs}

\appendix
\section*{Acquiring the Algorithms}

In the spirit of the PROMISE conference series, all of the algorithm implementations  and data used in this research are
available for public use. 

All five DDP models are available from the PROMISE repository at \url{http://www.promisedata.org/?cat=133}.

KEYS2 can be downloaded from \url{http://www.unbox.org/wisp/var/greg/keys/2.6}. The genetic algorithm can be found at 
\url{http://www.unbox.org/wisp/var/greg/genefreeze} and the simulated annealing is located at
\url{http://www.unbox.org/wisp/tags/ddpExperiment}. 

\end{document}

