%\documentclass[onecolumn,draftcls,journal,compsoc]{IEEEtran}
%\documentclass[technote]{IEEEtran}
\documentclass{sig-alternate}
\usepackage{graphicx}
\usepackage{wrapfig,url,times}
\newcommand{\boxplot}[5]{
	\begin{picture}(100,10)
		\put(0,0){\line(0,1){8}}
		\put(100,0){\line(0,1){8}}
		\put(#1,4){\line(1,0){#2}}
		\put(#3,4){\circle*{6}}
		\put(#4,4){\line(1,0){#5}}
		\put(50,0){\line(0,1){8}}
	\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'09,} {May 18--19, 2009, Vancouver, Canada} 

\CopyrightYear{2009}

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


%\CopyrightYear{2008} % Allows default copyright year (200X) to be over-ridden - IF NEED BE.
%\crdata{0-12345-67-8/90/01}  % Allows default copyright data (0-89791-88-6/97/05) to be over-ridden - IF NEED BE.

\title{
Review of Search-Based Methods
%\titlenote{Submitted to the PROMISE 2008 workshop on repeatable SE experiments.
%%A draft version of this paper may be downloaded fro
%\url{http://menzies.us/pdf/08keys.pdf}
%}
}

\numberofauthors{1}
%
\author{
%% 1st. author
\alignauthor Gregory Gay
\\~\\
       \affaddr{Dept of CS\& EE, West Virginia University, Morgantown, WV, USA}\\
       \email{gregoryg@csee.wvu.edu}
}
%
\date{6 February 2009}

\maketitle
\begin{abstract}

\end{abstract}
%\category{i.5}{learning}{machine learning}
%\category{d.2.8}{software engineering}{product metrics}
%\terms{algorithms,experimentation, measurement}
%\keywords{[TBD]}

\section{Introduction}

Software models are, without a doubt, becoming an increasingly important factor in the world of 
Software Engineering. It is easy to see why this is the case. 
The use of models imposes structure and a common vocabulary ~\cite{hailpern06}. 
Models allow developers to see a problem more clearly, which in turn reduces 
time-to-market and increases productivity ~\cite{sendall03}. 
It is for this reason that firms as diverse as Microsoft ~\cite{greenfield04} 
and Lockheed Martin  have accepted model-based SE as the norm. 

One model of particular interest is the Defect Detection and Prevention (DDP) model ~\cite{corn01,feather08}
proposed and used by NASA's Jet Propulsion Lab. In the simplest terms, DDP allows a team of experts to
find the least costly project options that most increase the chance to meet more goals. By visually displaying 
the connections between the objectives and risks, these software researchers can find important combinations 
of options that might have been missed. 

Search-based Software Engineering ~\cite{harman07} is another area that has been recieving a growing amount of attention.  
SBSE applies classical Artificial Intelligence techniques like Simulated Annealing, bredth-first search, and genetic algorithms to 
these models. These metaheuristic techniques allow researchers to find the ideal combination of attributes to optimize the output
of a model. Many of these techniques have been applied to DDP models in the past ~\cite{gay08}, and this essay will present a brief survey of them
as well as other algorithms. 

\section{User Feedback using Rocchio}

In order to fix a problem in a software system, a user must find the exact method containing that issue. 
When a system is large and complex, such as Eclipse (around 75,000 methods), this can be an incredibly daunting task. 
Certain information retrieval techniques can be applied to shorten the search task. 
One such method is to return results sorted by their similarity to a query supplied by the user.

If the query is well-written and descriptive, this can shorten the time to find a method dramatically. 
However, the success of this method is highly dependent on the strength of the initial query. 
The Rocchio relevance feedback method ~\cite{rocchio} can be used to modify that query based on key words found in 
documents deemed relevant to the current task.

\begin{figure}
\begin{tabular}{p{.95\linewidth}}\hline
\small
The original query $Q$ = "A A B" \newline
$\alpha$=1, $\beta$=0.50, $\chi$=0.15 \newline

The set of relevant documents $R_{q}$ = $D_1$, $D_2$ \newline
$D_1$ = "A B C C" \newline
$D_2$ = "A A A" \newline

New document $D_3$ = <A B B> has been judged as irrelevant. \newline

The new query $Q_{n}$ = <2 1 0> + (0.50 * <4 1 2>)/2 - (0.15 * <1 2 0>)/1 \newline
$Q_{n}$ = <2.85 0.95 0.5> = "A A A B C"
\\\hline
\end{tabular}
\caption{An example of query expansion using Rocchio}
\end{figure}


Each round, a user is presented with the method with the highest similarity score to their query.
Normally, the user would try to determine if that method was the one they were searching for and
move on to the next round if it was not. 
While using Rocchio, one additional step is added to each round. The user is asked to judge the current method
as relevant, irrelevant, or neutral to the current task. 
Given a set of documents $D_{q}$ encompassed by query $Q$, you can separate the documents into two distinct subsets of relevant ($R_{q}$) and
irrelevant ($I_{q}$) documents. 
The original query can be transformed by adding important terms from $R_{q}$ and removing terms from $I_{q}$.

\begin{equation}\label{eq:rochio}
{Q_n = \alpha Q + \frac{\beta}{|R_q|} \sum_{d{\in}R_q} d - \frac{\chi}{|I_q|} \sum_{d{\in}I_q} d 
}\end{equation}

That is to say, each round a term is added (term frequency {\em divided by} the number of relevant documents
{\em multiplied} by a weighting parameter $\beta$) times to the previous query 
and then a number are removed by that same formula, considered for the irrelevant set. 
The Rocchio technique is recursive. Each round, a new query is generated based on the query generated in the previous round.

The three constants ($\alpha$, $\beta$, and $\chi$) are provided so that a level of {\em importance} can be specified by the user.
According to Dekhtyar et al /cite{hayes07}, placing emphasis on the relevant documents may improve the recall (new relevant articles may be found) 
while emphasizing the irrelevant documents  may affect precision (false positives may be removed).
Joachims recommends weighting the positive information four times higher than
the negative~\cite{joachims97}. A similar approach is used by De Lucia et al. ~\ref{INSERTREFHERE}, 
who advocated using settings of $\alpha$=1, $\beta$=0.75, $\chi$=0.25
(i.e. relevant documents are three times more important than irrelevant). 
The system used in this case study follows a similar line of thought, setting values of
$\alpha$=1, $\beta$=0.5, and $\chi$=0.15 for the three weighting parameters.  




\section{Instance Generator}
\subsection{What is DDP?}

\begin{figure}[!t]
~\hrule~\\

\includegraphics{arrt.pdf}

DDP assertions are either:

\bi
\item \textit{Requirements} (free text) describing the objectives
and constraints of the mission and its development process; 
\item \textit{Weights} (numbers) associated with requirements, reflecting
their relative importance; 
\item \textit{Risks} (free text) are
events that damage requirements; 
\item \textit{Mitigations}: (free
text) are actions that reduce risks; 
\item \textit{Costs}: (numbers) effort associated with mitigations, and repair costs for
correcting Risks detected by Mitigations; 
\item \textit{Mappings}: directed edges between
requirements, mitigations, and risks that capture quantitative relationships among them. 
\item \textit{Part-of relations}
structure the collections of requirements, risks and mitigations; 
\ei

~\hrule~
\caption{DDP's ontology}
\label{fig:ddpont}
\end{figure}

\begin{figure}[!t]
\includegraphics[width=3.5in]{ddpMoldel2.pdf}
\caption{A real-world DDP model}
\label{fig:modelpic}
\end{figure}

In a typical design session at the NASA Jet Propulsion Lab, a larger group of
designers refine a project's high-level design document. These designers are
NASA's top experts, and their time is important. Therefore, it is crucial that 
this design process be as efficient as possible. Tools are chosen for their ability to
provice interactive design advice in a clear and timely manner. 
Only brief assertions can be collected during these short design sessions. If 
more complicated assertions were to emerge, these experts may be unable to 
understand technical arguments from outside their field of expertise. 
Therefore, the chosen modeling tool must support a lightweight ontology. 

The "Defect Detection and Prevention" (DDP) tool is commonly used because it provides a 
succinct ontology for representing this design process. These models represent three core
concepts: requirements, risks, and risk-removing mitigations. These models are a powerful method
of modeling the relationships between project factors, yet are simple enough to meet the efficiency requirement.
 
\subsection{Anatomy of DDP}

The ontology shown in \fig{ddpont} and the actual model shown in \fig{modelpic} represent a high-level view 
of the DDP model. This is the view that the room of experts see during their design sessions. However, this graphical
interface is not usable by these search-based metaheuristic techniques. Instead, a flattened view of the tree is used. 
This flattened tree is made up of several distinct sections. 

Objectives, Risks, Mitigations: {\em <Integer>}
\bi
\item Model 2: 1,30,31
\item Model 4: 50,31,58
\item Model 5: 32,70,99
\ei

The structure of the entire model hinges on these three things. A user must supply the number of 
objectives, mitigations, and risks when the model generator is run. Any number of each may be used, as long as it is an integer
greater than one. 


Mitigation Costs: {\em <Integer>}
\bi
\item Model 2: 0-10,000 (Average: 863.4)
\item Model 4: 0-700,000 (Average: 81,732.8)
\item Model 5: 0-100,000 (Average: 14,687.1)
\ei

Mitigation costs are entirely project-dependent and, in a real-world scenerio, would be entered by a user.
The range and distribution of cost values is not consistent from model to model. 
The model generator generalizes by applying a rule that mitigation costs range from 0-(10,000*numObjectives). 


Objective Weights: {\em <Integer> (1-100)}
\bi
\item Model 4: 1-100 (Average: 72)
\item Model 5: 0.1-100 (Average: 8)
\ei

Objective weights fall between 0 and 100, and are typically assigned during a design session by consensus of the NASA exsperts. 
These values represent the importance of a specific objective. Only one fractional weight was found in the five real-world models
(a 0.1 value in model 5). As this only occurs once, it is ignored. The model generator randomly assigns an integer value somewhere in the 
range to each objective. 


Risk -> Objective Impact: {\em <Decimal> (0.01-1.0)}
\bi
\item Model 2: 0.1-0.9 (Average: 0.5)
\item Model 4: 0.1-1.0 (Average: 0.6)
\item Model 5: 0.01-1.0 (Average: 0.6)
\ei

The roImpact value is the impact that a risk will have on a certain objective. There are between one to forty objectives impacted per risk, and every
risk will effect an objective. This value is a decimal between 0.01 and 1.0. The model generator randomly picks both the number of objectives 
impacted per risk and the value that each impact has. The instance generator has safeguards in place to ensure that there are no
repeat objectives per risk and that every objective will be impacted. 

Mitigation -> Risk Effect: {\em <Decimal> (-inf - 1.0)}
\bi
\item Model 2: 0.1 - 1 (Average: 0.4)
\item Model 4: -1.7 - 1.0 (Average: 0.5)
\item Model 5: 0.001-1 (Average: 0.6)
\ei

Similar to roImpact, mrEffect is the effect that a mitigation will have on a risk if selected. Each mitigation will affect one to twenty risks. 
This effect is usually positive, a mitigation will relieve a risk by an amount between 0.1 and 1. However, sometimes a mitigation will make 
the effect of some risk worse. These are marked by negative values, most falling between -0.1 and -1. Some very rare cases (called {\em aggrivated}
effects) fall below -1. The instance generator randomly picks which risks are affected by a mitigation and by how much. Again, safeguards 
are in place to ensure no repeats and that every mitigation and risk is used. At a small probability (if a random decimal is greater than 0.99), an
effect is negative. That negative has, in turn, a 0.33 chance of being an aggrivated effect. These numbers were chosen to give a similar rate 
of inclusion to that seen in model 4. 

Finally, these values are used in a series of equations to determine the attainment and costs values. Each mitigation comes into play
during a specific phase of software development. In the real world, the designers know what round a phase is applied during. The
model generator splits the process into five phases (the most seen in our real DDP models) and randomly assigns mitigations to each phase. 
During each phase, the {\em rLikelihood} is calculated for each risk effected by the mitigations of that phase 
(determined by the mrEffects). 

\begin{equation}\label{eq:rlikelihood}
L[Risk] = L[Risk] * \prod_{M=1}^{numM}{(1 - M * mrEffect[M][Risk])}
\end{equation}

The same risks can be changed multiple times, this is why the equation takes the prior value of the likelihood into effect. 
If the mrEffect is a negative value, this equation takes on a different value. 

\begin{equation}\label{eq:rlikelihoodneg}
L[Risk] = min(1, (L[Risk] - M * mrEffect[M][Risk])) 
\end{equation}

If that effect is below -1, the likelihood is not calculated at all for that affected risk. 
Instead, a new value is calculated for the Aggrivated Impact of that risk (all AI values are initially set to 1). 

\begin{equation}\label{eq:ragg}
AI[Risk] = AI[Risk] * \prod_{M=1}^{numM}{(1 - M * mrEffect[M][Risk])}
\end{equation}

After all five phases of likelihood calculations have been concluded, the amount that each objective is at risk is obtained. 
For each objective, the following equation is calculated using the previously found likelihoods and the risk->objective impacts. 
Each objective is effected by the risks that impact it. 

\begin{equation}\label{eq:oatrisk}
AtRiskProp[O] = \sum_{R=1}^{numR}{(L[R] * AI[R] * roImpact[R][O])}
\end{equation}

These values are used to determine the attainment values for each objective. 
The attainment value is determined as:

\begin{equation}\label{eq: oattain}
Attain[O] = Weight[O] * (1 - min(1, AtRiskProp[O]))
\end{equation}

Finally, the total cost and total attainment are determined using these equations:

\begin{equation}\label{eq: totalA}
Attainment = \sum_{O=1}^{numO}{Attain[O]}
\end{equation}
\begin{equation}\label{eq: totalC}
Cost = \sum_{M=1}^{numM}{M * Cost[M]}
\end{equation}

The model generator determines the proper form of all of these equations and inserts them into the textual model format.

\section{Review of SBSE}

\subsection{Linear Programming}

Linear programming is slightly different from the other approaches 
used in search-based software engineering because it is not strictly
an algorithm. Rather, linear programming is a mathematical technique
that is guarenteed to locate a globally optimal solution. 

A set of decision variables with non-negative values ({\em $X_1$ ... $X_n$})
 are passed to the linear programming model. The goal is to maximize
the value of a given linear expression in terms of these decision variables. 

\begin{equation}\label{max}
Maximize \sum_{i=1}^{n}{C_i * X_i}
\end{equation}

Where \{{\em $C_1$ ... $C_n$}\} is the set of problem-specific coefficients.
These coefficients are subject to a series of constraints of the form:

\begin{equation}\label{coeffs}
\sum_{i=1}^{n}{a_j * X_i < b_j}
\end{equation}

Linear programming requires a clear determination of the goal to be
optimized for and a set of well-known and understood constraints. 
Therefore, it is generally only used for a very limited set of problems.
On those problems, it is guarenteed to find an optimal solution. 

Linear programming can be further constrained to what is called integer programming. 
This is accomplished by only allowing the decision variables to take on
integer values. Integer programming is even more useful than linear programming
because it can be applied to a larger set of problems. 

\subsection{Simulated Annealing}

Simulated Annealing is a classic stochastic search algorithm first described in 1953~\cite{metropolis53} and refined in 1983 ~\cite{kirkpatrick83}. 
This algorithm takes its name from a metallurgy technique. In real annealing, a material is heated,
then cooled multiple times. 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.

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure SimulatedAnnealing
2. STATE:= set of settings
3. SCORE:= score of MITIGATIONS
4. while TIME < MAX_TIME && SCORE < MIN_SCORE 
   //minScore is a constant score (threshold)
5.    find a NEIGHBOR close to STATE
6.    NEIGHBOR_SCORE:= score of NEIGHBOR
7.    if NEIGHBOR_SCORE > SCORE
8.        STATE:= NEIGHBOR
9.        SCORE:= NEIGHBOR_SCORE
10.   else if prob(SCORE, NEIGHBOR_SCORE, 
                   TIME, temp(TIME, MAX_TIME)) > RANDOM)
11.       STATE:= NEIGHBOR
12.       SCORE:= NEIGHBOR_SCORE
13.   TIME++
14. end while
15. return MITIGATIONS
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for Simulated Annealing}
\label{fig:simplesa}
\end{figure}

Simulated Annealing ``picks'' a neighboring set of states during each round. 
What exactly determines a neighbor depends on the problem domain. The implementation used with DDP models traverses 
the mitigation settings of the current state and randomly flips those mitigations at a 5\% chance. 
If the neighbor has a better score, Simulated Annealing travels to it and sets it as the new position. 
If this neighbor is not actually an improvement, the algorithm will decide whether or not to move to it based on the mathematical function:
\begin{equation}\label{eq:ps1}\small
prob(w,x,y,temp(y,z)) = e^{((w-x) * \frac{y}{temp(y,z)})}
\end{equation}
\begin{equation}\label{eq:ps}\small
temp(y,z) = \frac{(z-y)}{z}
\end{equation}
If the value of the {\tt prob} function is greater than another randomly generated number, Simulated Annealing will still
jump to the inferior state. 
Initially, the ``atoms'' (current solutions) 
will take large random jumps, sometimes even to sub-optimal solutions. This possibility of a random jump allows Simulated
Annealing to sample a large part of the search space, while avoiding being trapped in local minima.
Eventually,
the ``atoms'' will cool and stabilize, converging the search to a simple hill climber.

As shown in line 4 of \fig{simplesa}, the algorithm will continue to operate until the number of tries is exhausted or a score meets the threshold requirement. 

\subsection{Maxwalksat}

WalkSat is a local search method designed to address the NP-complete problem
of boolean satisfiability~\cite{kautz96}. MaxWalkSat is
a special variant of WalkSat that applies weights to each clause in a
conjunctive normal form equation~\cite{selman96}. 
While WalkSat tries to satisfy the entire set of clauses, MaxWalkSat
tries to maximize the sum of the weights of the satisfied
clauses. While Simulated Annealing dates from the 1950s, MaxWalkSat is slightly more "state of the art."

In some ways, both WalkSat and maxWalkSat can be viewed
as a variant of simulated annealing. Whereas simulated annealing always selects
the next solution randomly, the WalkSat algorithms will {\em sometimes}
perform a random selection while, other times, they will conduct a search to find a locally optimal solution.
 
\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure MaxFunSat
2. for TRIES:=1 to MAX-TRIES
3.    SELECTION:=A randomly generated assignment of all variables
4.    for CHANGED:=1 to MAX-CHANGES
5.        if SCORE satisfies THRESHOLD return
6.        CHOSEN:= a random selection of variabless from SELECTION
7.        with probability P
8.            flip a random setting in CHOSEN
9.        with probability (P-1)
10.           flip a setting in CHOSEN that maximizes SCORE
11.    end for
12. end for
13. return BESTSCORE
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for MaxWalkSat}
\label{fig:MWS}
\end{figure}


The MaxWalkSat procedure is detailed in \fig{MWS}. When run, the user supplies an ideal goal state, which is set as the threshold. 
If the current setting of mitigations satisfies that threshold, the algorithm terminates. 

MaxWalkSat begins by randomly setting a set of variables. From there, it will attempt to make a {\em single} change during each round until the threshold is met or the allowed number of changes runs out. 
A subset of all of the possbile varaibles is chosen at random and another random number P is generated. 
The value of P (which will fall between 0 and 1)  will determine the next step:
\bi
\item P$\le\alpha$: A stochastic decision is made. A setting is changed completely at random within subset C.
\item P$>\alpha$: A local search is conducted. Neighbors are tested until one is found that improves the current score.
\ei

If the threshold score has not been met by the time that the number of changes is exhausted, the MaxWalkSat algorithm resets. 
This small measure allows the algorithm to avoid the issue of local maxima. 
If the threshold is never met, MaxWalkSat will continue to reset until the maximum number of allowed resets is exhausted. 
Once this point is reached, the best setting found will be returned. 

\subsection{A*}

 A* is a best-first search algorithm that uses the distance traveled ($G$)
and estimated distance to goal ($H$)
to find the best path~\cite{hart68}. The algorithm has been proven to be optimal for a given scoring heuristic (as long as $H$ is underestimated) 
~\cite{dechter85}. A* has seen use in multiple fields ~\cite{norvig03,pearl84,stout97,hui04}, and was used for 
DDP optimization since all of the DDP-related algorithms use Euclidean distance as a measurement


\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure ASTAR
2. CURRENT_POSITION:= Starting assignment of mitigations
3. CLOSED[0]:= Add starting position to closed list
4.
5. while END:= false
6.    NEIGHBOR_LIST:=list of neighbors
7.    for each NEIGHBOR in NEIGHBOR_LIST
8.        if NEIGHBOR is not in CLOSED
9.            G:=distance from start
10.           H:=distance to goal
11.           F:=G+H
12.           if F<BEST_F
13.               BEST_NEIGHBOR:=NEIGHBOR
14.   end for
15.   CURRENT_POSITION:= BEST_NEIGHBOR
16.   CLOSED[++]:=Add new state to closed list
17.   if STUCK
18.       END:= true
19. end while   
20. return CURRENT_POSITION
\end{verbatim}
}
~\hrule~
\caption{Pseudocode for ASTAR}
\label{fig:ASTAR}
\end{figure}

%Our implementation of A*, called ASTAR, allows for two possible starting configurations. Like all of the other algorithms used for this experiment, ASTAR can randomly make assignments to each mitigation. This was the setting used for most of our experiments. However, A* is a deterministic algorithm. Given a {\em fixed} starting position and an {\em unchanging} search space, it should always come up with the same final answer. To test this, our ASTAR technique can be set to start from a fixed state where cost and attainment are both equal to 0. 

The ASTAR algorithm always moves forward. Backtracking is prevented by maintaining a {\em closed} list.
During each round, a list of neighbors is populated from the set of all possible states reached by taking a single step (in the case of DDP, a 
single mitigation change). 
If that neighbor is not on the closed list, two calculations are made: 
\bi
\item G = Distance from the start to the current state plus the additional distance between the current state and that neighbor.
\item H = Estimated distance from that neighbor to the goal.
\ei
The {\em best} neighbor is the one with the lowest score for $F$=$G$+$H$. The A* algorithm ``travels'' to that neighbor and adds it to the closed list. 
Part of the optimality of the A* algorithm is that the distance to the goal is underestimated. 
In the implementation used to optimize DDP, the goal is given as an unreachable state.
This maintains the optimality. The algorithm terminates once it stops finding better solutions.

\subsection{KEYS}

There are two main components to KEYS - a greedy search and the BORE ranking heuristic.

The greedy
search within KEYS explores a space of $M$ 
mitigations over a series of "eras" (equal to $M$). 
The entire set of mitigations is initially set at random. 
During each era, one additional mitigation is locked down by setting it to $M_i=X_j$, $X_j \in \{true,false\}$. 

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'' while
the remainder are sent to  ``rest''. 
\item[3:]
The mitigation values in the $input$ sets are then scored using BORE
(described below).
\item[4:]
The top ranked mitigations (the default is one, but the user may fix multiple mitigations at once) are fixed and stored in $selected[e]$.\ee
The search moves to era $e+1$ and repeats steps 1,2,3,4.
This process stops 
when every mitigation has a setting.  
The exact settings for $MaxTries$ and $\beta$ must be set via engineering judgment.
After some experimentation, we used $MaxTries=100$ and $\beta=10$.
For full details, see \fig{KEYS}. 
\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}

KEYS ranks mitigations using BORE ~\cite{clark05} (short for ``best or rest''), a Bayesian ranking heuristic.
BORE divides scores seen over the past $K$ runs into the top 10\%  $best$ and the remaining 90\% scores (the $rest$). 
The $best$ set is computed by studying the difference of each score and the best score seen in any era.
BORE 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 the  posterior  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) are then normalized to create
probabilities. This normalization cancels out the $P(E)$ factor in Bayes theorem.
For example, $K=10,000$ runs are divided into  the 1,000 {\em best} 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

To avoid the problem of unreliable low frequency evidence ~\cite{clark05}, \eq{ten}
is modified to include a support term.
the value of support should increase as the frequency of a value increases. 
Step 3 of KEYS' greedy search ranks values  via
\begin{equation}\label{eq:ps3}\small
P(best|E) * support(best|E) = \frac{like(best|E)^2}{like(best|E) + like(rest|E)}
\end{equation}

\subsection{KEYS2}

For each era, KEYS only fixes the top $N=1$ settings.
For the DDP models, costs and attainment improvements generally increase
for each era of KEYS.
KEYS could jump further and faster into the solution space by 
fixing $N\ge 1$ settings  per era.
Research evidence suggests that multiple equations could be safely fixed at once.
Therefore, KEYS2 improves the speed of KEYS by locking down an increasing number of mitigations each round.

Such a {\em jump} policy 
can be implemented as a
small change to KEYS:
\bi
\item
Standard KEYS
assigns the value of one to  \newline{\tt NUM\_MITIGATIONS\_TO\_SET} (see the pseudo-code of \fig{KEYS});
\item
Other variants of KEYS assigns larger values.
\ei
Several variants were experimented with before deciding that $i$ settings will be set during era $i$ .
Note that, in era 1, KEYS2 behaves exactly the same as KEYS
while
in (say) era 3, KEYS2 will
fix the top 3 ranked ranges. 
Since it sets more variables at each era,
KEYS2 terminates earlier than KEYS.

\subsection{Genetic Algorithms}

\begin{figure}
~\hrule~
{\scriptsize
\begin{verbatim}
1. Procedure GENA
2. GENERATION:=0
3. loop
4.    Recombine P(GENERATION):=R(P(GENERATION))
5.    Mutate P(GENERATION):=M(P(GENERATION))
6.    Evaluate F(P(GENERATION))
7.    Select P(GENERATION+1):=S(P(GENERATION))
8.    GENERATION++
9.    if(SCORE>GOAL||STOP=TRUE)
10.      return    
11. end loop  \end{verbatim}}      
~\hrule~
\caption{Pseudocode for a genetic algorithm}
\label{fig:gena}
\end{figure}

Genetic algorithms ~\cite{holland92} are a family of algorithms that
apply concepts of population and recombination. 
In a basic genetic algorithm \fig{gena}, some iterative process is conducted 
with an initially random population. Each round is referred to as a "generation"
and members of the population set are called "chromosomes." 

The iterative process continues until some threshold point has been met or a 
certain number of generations have passed. 
Each generation, selected members of the population are recombined, mixing their chromosomes. 
This mutates the offspring of this union, introducing evolutionary changes into the "gene pool."
A selection function determines the population that will "survive" 
from the mutated offspring and the original pool. Chromosomes that match the
fitness function are more likely to survive.

According to Harman ~\cite{harman07}, genetic algorithms are "the most widely 
applied search technique in SBSE." 
Apparently, this is laregely due to popularity and historical precident,
rather than any strong theoretical foundations. 

A variant of genetic algorithms, called genetic programming ~\cite{koza92}, has also
seen heavy use in the SBSE field. In genetic programming, the chromosome
is not a list, but is a tree.  This abstract tree represents a program 
and is evolved by a genetic algorithm.
Fitness is measured using a testing-basred approach that seeks to modify the
program so that it more closely meets a set of goals. 
\bibliographystyle{plain}
\bibliography{refs}

%\begin{thebibliography}{10}


%\end{thebibliography}


\end{document}

