The previous chapter has discussed the challenge of balancing 
budget and attainment in DDP models.
This chapter will discuss the search-based software engineering field and some of the techniques used to address
such non-linear optimization problems.

\section{Search-Based Software Engineering}

As one might infer from the name, search-based software engineering is concerned with the reformulation 
of standard software engineering problems as search problems, and the application of heuristic techniques to solve
said problems. Many of the problems inherent to the software engineering field deal in the {\em balancing} of
competing factors. Do you want to finish with money left in the budget, or is it more important to deliver a robust feature set? 
You could replace the programmers on an under-performing project, but would it be worth the additional man-hours necessary to get the
new staff up and running? 

In many of these cases, there is no single {\em perfect} solution. In fact, there could be a dozen solutions with the same outcome. 
Instead of finding a single optimal value, software engineering problems are typically concerned with near-optimal solutions, 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. 
Because of this implied trade-off space, meta-heuristic search-based methods are ideal for producing
a set of potential solutions. 

According to Clark and Harman~\cite{harman04,harman01}, there are four key properties that must be met for a search-based software engineering
approach to be successful:
\bi
\item {\em A Large Search Space}: If there are only a small number of factors to compare, there is no need for a meta-heuristic approach. 
This is rarely the case, as software engineering typically deals in incredibly large search spaces (i.e. the space of all expressible programs
written in the JAVA language).  
\item {\em Low Computational Complexity}: If the first property is met, SBSE algorithms must sample a non-trivial population.
A typical run of one of these searches requires thousands of executions of a fitness evaluation (on a large model, KEYS might 
have to consult the DDP model ten-thousand times or more). 
Therefore, the computational complexity of the evaluation method
has a major impact on the overall search. 
\item {\em Approximate Continuity}: While it is not necessary for a function to be continuous, too much discontinuity
can mislead a search. Any search-based optimization must rely on an objective function for guidance, and 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 exists 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 in SBSE language~\cite{baresel04,harman04b}.
All four of these characteristics are prevalent in software engineering. As mentioned earlier, problems typically involve a large search space, 
and optimal solutions are generally impossible to know. 

Using these four properties, we can show that the optimization of DDP models is a SBSE problem, and that KEYS2 is a valid solution. 
Typical DDP models present a massive search space, encompassing hundreds to thousands of possible combinations of mitigation settings. 
Adding to that, one collection of mitigation settings must comment on dozens of individual mitigations. In one DDP model, there might be $2^{99}$ 
(${mitigation\:values}^{number\:of\:mitigations}$) possible combinations. With such a large number of combinations in the search space, any candidate
solution must execute in a short time. In Section \ref{sec:scaleup}, it is shown that KEYS2 operates at $O(N^2)$ and Section \ref{sec:runtimea} 
demonstrates that the algorithm
typically executes in less than half of a second on the largest DDP models available. DDP models do not represent a continuous search space - any model with 
{\em true/false} statements is, by definition, not continuous. However, this is not a problem, as the fitness function employed by KEYS2 (and
all algorithms used to assess DDP models) represents an approximately continuous trade-off between project costs and feature attainment. 
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 must be employed to calculate a selection of {\em near-optimal solutions}. By meeting all four of these conditions, 
DDP models (and the candidate search algorithms) represent a valid search-base software engineering problem.

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,arcuri09,ferrer09}, 
software maintenance ~\cite{harman02,mitchell02}, transformation~\cite{harman04b,fatiregun04,baresel04}
and software evolution ~\cite{belle02}.
The following subsections detail popular approaches to solving
such SBSE problems. 

\subsection{Hill Climbing and Simulated Annealing}\label{sec:sarw}

Hill Climbing is a commonly-used form of local search~\cite{mcminn04}. The basic idea is to 
start with an initial solution, taken randomly from the search space, and attempt to
improve it. The neighborhood of this initial point is investigated and, if a better 
solution is identified, the algorithm "climbs" to this neighbor and sets it as the new "current" solution.
Over a series of subsequent rounds, the hill climbing algorithm will repeat this process until 
no further improvements can be found. This process, of steady improvement, is called "hill climbing" 
because the algorithms scales "mountains" in the landscape of an objective function. The peaks of 
these hills represent solutions with localized maximum values, just as the lowest recorded levels represent
local minima. 

Hill Climbing algorithms typically employ one of two strategies at a given stage. In the first, called {\em steepest ascent}, 
all neighbors are evaluated. The neighbor showing the greatest improvement, according to the objective function, is chosen
to replace the current solution. 
The second strategy, {\em random ascent}, examines neighbors at random. The first neighbor to show an improvement is selected
as the replacement.  

These algorithms are widely used for several reasons - they are simple to understand, easy to implement, and very fast. 
However, they have a key flaw - it is easy for these methods to become 
stuck in local maxima or any area where the score plateaus 
(i.e. all neighbors have the same objective value, thus there is no improvement). 
They will then yield results that, 
while optimal for that section of the search space, are inferior to the global maxima. 
In any non-trivial landscape (which encompasses many of those seen in SBSE), results obtained with a hill climber are highly dependent 
on the starting solution. A common method of dealing with this risk is to allow the algorithm a set number of "restarts." In that case, 
it will pick a new starting position if it ever becomes trapped. This results in a larger sampling of the search space, which is likely to
produce a more globally optimal solution. The implementation of MaxWalkSat introduced in Section \ref{sec:mfw} is a 
hill climber (hybridized with a random search) with the ability to 
reset.  

Hill climbing techniques are widely used, but it could be desirable
for an algorithm to be less dependent on the starting position. 
Simulated annealing ~\cite{metropolis53,kirkpatrick83} is one commonly used alternative. 
Simulated annealing (SA) is introduced in more detail in Section \ref{sec:sa}. 
Like hill climbers, a simulated annealing algorithm will choose a 
random starting position and move towards better solutions in
the immediate neighborhood. However, by probabilistically accepting 
worse solutions, SA allows for a less-restrictive traversal of the 
search
space. As the algorithm progresses, its temperature function decreases (i.e. it cools according to the output of a controlling equation). 
Initially, the temperature
is kept at a high level, which increases the probability of accepting a poor solution. Thus, more of the search space will be explored. 
As the search progresses, movement stabilizes and plateaus. 
One must take caution when choosing a cooling
strategy - cool too quickly, and it is likely that the algorithm will return a sub-optimal solution. 

Tracey et al~\cite{tracey98,tracey00} used simulated annealing, a genetic algorithm (GA), a hill climber,
and a random search for finding the worst-case execution time (WCET) for a number of well-understood
programs written in the Ada language. In the search technique executed the path through the program that yielded the 
already known WCET, the trial would be deemed a success. Overall, the Simulated Annealing technique completed more trials
successfully than the genetic algorithm, and both of them vastly outperformed the random search and hill climber. 
Interestingly, their study found that varying the parameters of each optimization technique would have little effect on the end results,
except in the case where the starting temperature was too low for the SA algorithm. In that case, the dependency on the starting position 
was too high. 

Tracey~\cite{tracey00,tracey98b} also applied a variety of techniques, including SA and a GA, to the problem of specification conformance. 
The conformance of an implementation to its original specification is checked by executing the test object with some generated 
testing data, which is then validated against the specification. The two subsystems chosen for this experiment come from a safety-critical
nuclear primary protection system, written in the Pascal language. 
The search techniques were wildly successful in finding the "mutant" situations that did not conform to the specification. 
Both the annealer and genetic algorithm identified all of the 170 existing violations. The hill climber and random search only found about
90\% of the anomalies. 

Mahdavi et al~\cite{mahdavi03} used hill climbing algorithms to study the problem of automated software module clustering, which is 
important for systems with unclear module boundaries of where structure had degraded as the system evolved. 
In their work, they demonstrate that the results from a set of multiple "climbs" can be combined to form the building blocks for 
subsequent clustering efforts. Each climb outputs a module dependency graph, and when these graphs are looked at in sequence, 
common features emerge that may indicate a good cluster. When that dependency graph is used as the input for the next hill-climb, that 
execution tends to reach even higher score peaks. 
This process substantially reduces the search space and reveals certain hard-wired portions of the solution. 

\subsection{Tabu Search}

Tabu search~\cite{glover89,glover90} is a popular meta-heuristic search method. 
Like a hill climber, a tabu search picks a random starting position, 
examines its local neighborhood for locations that better satisfy
an objective function, and jumps to these positions.
Tabu search distinguishes itself by modifying the neighborhood 
structure at each stage. The solutions admitted to the new neighborhood
are determined through the use of memory structures.
These memory structures constrain the search
space by classifying certain moves as forbidden ({\em taboo}), and
frees the search through a mechanism that allows the algorithm to 
forget certain taboos over time. 
This ensures that a tabu search (TS) algorithm
never becomes stuck in a local maxima, and that it never falls back into
one of these points once it emerges from it. 

The most important internal structure in a tabu search is the 
{\em tabu list}, a move list that blocks certain portions of the 
neighborhood deemed to violate a list of logical rules (as informed by
the objective function).
In the simplest form, this list is a memory of the solutions that have
been recently visited. By listing these locations as taboo, the search
will never spend time revisiting covered ground.
Items will gradually expire from this list as their user-supplied
{\em tabu tenure} expires. 
Other facets of the tabu list are dependent on the constraints of the
search problem. For instance, a tabu search covering the traveling
salesperson problem may have a list prohibiting certain
arcs from being removed over the next $N$ moves. 

By marking certain attributes as being taboo, entire portions of the
search space will be constrained. Unfortunately, these regions may
still include optimal solutions. 
To avoid this problem, a list of {\em aspirational criteria} is used
(this may be as simple as reconsidering any solution that is taboo, yet
yields a better score when subjected to the objective function).
If any of these criteria are satisfied, the tabu list will be overridden
and that state may reenter the neighborhood.

In a recent article~\cite{diaz08}, Diaz et al. applied tabu search to the task of 
automatic generation of structural software tests. Such structural test generation is almost
exclusively conducted by evolutionary algorithms (genetic algorithms, particle swarm optimization), which makes the choice of 
tabu search interesting. Their test generator, TSGen, manipulates its tabu list by utilizing 
one cost function for intensifying the search and another for diversifying the search when such intensification is unsuccessful. 
The algorithm combines its memory list with a backtracking process in order to avoid becoming stuck in localized areas. 
In order to test their tabu search, they set it loose on three structural testing problems - one a standard benchmark
(the triangle classifier problem)
and two more complex (line rectangle classifier and the distance between two dates). On all three problems, TSGen achieved 100\% coverage 
in a fraction of the time that it took a random search to address the problem.

Stardom~\cite{stardom98} has benchmarked the efficiency of several meta-heuristic techniques on the problem of finding adequate covering arrays 
(also called packing arrays).
Covering arrays are used in software testing to account for the numerous possible configurations that a piece of software can be executed under.
It is often impossible to test every possible configuration; therefore, covering arrays are used to select the ideal subset of configurations to
test.  
In a series of experiments where the goal was to find the best covering array possible in the shortest amount of time, Stardom found that 
genetic algorithms were completely ineffective in comparison to simulated annealing and tabu search. The simulated annealer 
was very useful for finding covering arrays when an array's neighborhood was smaller, but overall, the tabu search returned the highest-quality
solutions.

In a similar piece of research, Kari Nurmela used a tabu search to construct covering arrays that would, ideally, improve
on previous upper-bounds on the size of an optimal covering array~\cite{nurmela04}. Covering arrays contain a parameter $t$ where, in any $t$ coordinate positions,
all combinations of those coordinate values occur at least once. 
When $t=2$, all vectors for a covering array are binary, and the make-up of an optimal array is known; however, for all other cases,
only upper and lower-bounds can be known. 
Nurmela's tabu search selects an uncovered t-combination at random and checks for rows that require the change of a single element such
that the row will cover the selected combination. The algorithm will move based on which element requires the lowest cost to change. 
That element will be added to the tabu list, preventing any further changes to it for a set period of time.
Their tabu search was able to improve upper bounds, with the caveat that the more time given to the algorithm, the better the results returned. 

\subsection{Genetic and Evolutionary 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. They are inspired by Darwin's Theory of Evolution, with the general idea being to 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), 
multiple solutions are considered, forming a population.
Because the initial population is unlikely to have the "best" solution, some form of diversity must 
be induced into the population.
Such diversity can be
maintained by using the crossover and mutation operations.
During each generation, several "good" solutions (as scored by a predetermined objective function) are chosen by
the selection mechanism to generate children for the next generation. The makeup of these children is influenced 
by the crossover operator. This function combines 
parts of the chromosomes, the solution presented by each parent, and inserts them into the offspring with probability $P_{crossover}$.
An example of a crossover can be seen in \fig{crossover}, where the child solution inherits genes from its parents.  
A mutation mechanism, demonstrated in \fig{mutation}, is used to instill small changes in the 
chromosomes of each offspring. This 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 new grouping of offspring forms a new population, and the 
process is repeated until a certain threshold 
(commonly in performance score, number of generations, or a set time period) has passed. 

\begin{figure}
\begin{center}
\includegraphics[width=4.25in]{crossover.png}
\end{center}
\caption{Demonstration of the crossover operation, from~\cite{rela04,ryan00}.} 
\label{fig:crossover}
\end{figure}

\begin{figure}
\begin{center}
\includegraphics[width=4.25in]{mutation.png}
\end{center}
\caption{Demonstration of the mutation operation, from~\cite{rela04,ryan00}.} 
\label{fig:mutation}
\end{figure}

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 mutation mechanisms
to generate offspring.
\item Discard the old population and repeat the process.
\item Stop if $time > maxtime$ (in number of generations or some real-time threshold).
\ei

Genetic algorithms are a
specific subset of the broader field of evolutionary algorithms, which use mechanisms inspired by biological evolution 
to generate offspring and test them against some 
pre-determined fitness function.  
Evolutionary algorithms have been found to be effective for finding a group of near-optimal solutions for
the kind of complex problems that are not suited to a brute force approach (that is, where the search space is too large).
Evolutionary algorithms cannot always find the best possible solution in a reasonable amount of time. However, 
they are generally able to generate a solution that is "good enough." 

SBSE, as a formal research field, is still in its youth. There are still
an unfathomable number of problems to explore, and an equal number of approaches to
these problems. Genetic algorithms have become an increasingly popular approach to solving search problems.
A single glance at the "best paper" nominees for the SBSE and 
Search-based Testing categories at the recent 2009 ACM Genetic and Evolutionary Computation Conference
reveals a number of exciting advances in the field. 
Some of the research presented includes:
\bi
\item Gueorhuiev et al~\cite{gue09} explored software project planning under the hypothesis 
that all large-scale projects inevitably contain a degree of uncertainty, which in turn leads to
overruns. The authors have formulated this issue as a multi-objective SBSE problem where project
robustness and completion time are designated as competing objectives. 
Their genetic algorithm, SPEA II~\cite{zitzler99}, searches for the pareto front, the {\em sweet spots}, 
in the solution space where there exists an optimal balance of the two opposed goals. 
While increased robustness generally
results in longer completion times, there exist spots in localized regions 
where the manager can trade {\em small} amounts of one objective for
{\em large} gains in the other. SPEA II seeks out these spots. 
The authors tested their problem and algorithm on 
four large real-world projects from around the world, evaluated over two different models of uncertainty.
The results provided interesting insight into the projects studied, and overall accuracy was favorable 
compared to that of a random search.
\item Phil McMinn introduced a novel approach to testability transformations~\cite{mcminn09}, source-to-source program
transformations intended to improve the testability of a project. In his research, transformations are used to generate
a {\em pseudo-oracle}, an alternate version of a program whose output can be compared directly to the original. 
Differences in the generated output could indicate a fault in the original program. Two transformations are utilized - one
highlighting numerical or roundoff errors, the second detecting race conditions in multi-threaded code. 
After one of these pseudo-oracles is generated, any number of SBSE techniques may be used to find differences between the programs. 
Both genetic algorithms and random searches were able to utilize the oracles to identify faults and assess their severity. 
Additionally, genetic algorithms were found to be able to explicitly maximize the differences between the originals and the oracles, which allowed
for the generation of test cases where failures are highly pronounced. 
\item Harman et al~\cite{harman09} presented an application of genetic algorithms to sensitivity analysis, which is a 
technique addressing problems with unreliable cost estimates on software projects. 
In particular, the authors use SBSE techniques to aid a theoretical decision maker in exploring sensitivity of the cost estimates
for the {\em Next Release Problem} (several examples of this problem are discussed in Section \ref{sec:emod}). In short, the "Next Release Problem" is concerned with finding 
the appropriate balance between customer satisfaction and available resources for the ($N+1$)th version of a project. 
Harman's paper presents single and multi-objective formulations of the NRP with sensitivity analysis on both real-world
and synthetic data, tested using a greedy algorithm and the NSGA-II~\cite{deb02} genetic algorithm.
While some of their results were expected - such as a strong correlation between the level of inaccuracy and the impact on the 
selection of requirements - they also found notable exception to the trends. They show that unusually sensitive patterns occur in real-world
data and how their algorithms clearly identify them.
\item The majority of existing work on evolutionary testing, the automated generation of software test cases, 
is targeted towards procedural languages.
Ferrer et al proposed an evolutionary testing method for object-oriented (OO) languages~\cite{ferrer09} that addresses the
{\em inheritance} feature.   
Their approach uses information mined from the class hierarchy to help test generators better guide
the search process. The authors define a branch distance for logical expressions containing the $instanceof$ 
operator from the Java language. They then explore two mutation operators based on this distance metric. 
They study the behavior of these mutation operators over nine object-oriented software projects. The
results gleaned from this benchmarking prove favorable, demonstrating that information collected from the class
hierarchy does help in the search for better test cases. 
\item Much of the research in applying SBSE to software testing has been of an empirical nature - proposed techniques
are validated on software testing benchmarks. Andrea Arcuri's work~\cite{arcuri09} asks {\em why} these meta-heuristic 
techniques are effective in the testing of software projects. Such insight could theoretically be used to design new, more
successful, approaches. Her work combines an empirical and theoretical analysis, and exploits the benefits of both. 
She analyzes the testing of Red-Black Trees, considering a white-box scenario in which the full coverage of all the branches of the
software is sought, evaluated over four different search techniques (random search, hill climbing, an evolutionary algorithm, and a genetic
algorithm). Rather than treating these algorithms as black-boxes, she tries to look inside of them for properties of the search problem
that can be exploited. These discovered properties are used to tune the evolutionary and genetic algorithms, as well as to further 
constrain the random search and hill climber. 
\item Rhys et al.~\cite{rhys09} are concerned with the automatic generation of test data for Matlab code. 
The most critical, and often error-prone, sections of software applications are code that performs complicated
mathematical functions. This code is very difficult to test due to the data types used and the complex mathematics. 
The authors have chosen Matlab as an example of widely-used mathematical software, and they have used its matrix data types
and associated relational operators to extend previous work on search-based test generation. 
Their paper introduces a technical framework fro instrumenting Matlab code, a method of representing matrix data types in a genetic algorithm,
an extended set of branch distance functions, a rank-based selection mechanism that combines this branch distance with a cost component, 
and the identification of linear algebra functions that lead to difficulties when present in relational predicates. 
They benchmark a genetic algorithm capable of utilizing this information against a standard random search. 
A set of experiments proves that, despite
the inherent challenges of mathematical software, automated search methods can generate feasible test data. 
\ei

This snapshot of current research in using genetic algorithms on SBSE problems shows the health and popularity of this approach. 
KEYS and GAs have never been directly compared, but in some ways, it could be said that KEYS operates in a similar manner to a genetic algorithm.
At each "generation," KEYS produces a set of solutions and finds one "best" solution from the population. It uses that one solution to fix
a setting (a "chromosome") for the next generation. There are a number of key differences - GAs produce offspring by combining all "good" solutions
for a generation while KEYS only uses one member of the population to influence a new generation - but it could be interesting to compare the 
two approaches. My hypothesis is that standard GAs would be too slow to compete with KEYS; however, it is possible that certain features of 
these algorithms could be imported into future iterations of my algorithms. 

\subsection{Particle Swarm Optimization}

Particle swarm optimization (PSO), introduced in 1995 by Kennedy and Eberhart~\cite{kennedy95,eberhart95}, 
attempts to solve search problems by mimicking the 
social optimization conducted in any form of group behavior.
Groups of creatures - birds, fish, bees, even humans - solve problems
by working with their neighbors. As they talk to others around them, 
their beliefs, intentions, and desires change. Individuals working
in swarms tend to, over time, converge into a stable behavior in a close
space. This type of optimization is the basis of PSO. 

In the PSO algorithm, a swarm of particles are used to represent
potential solutions. Each of those particles, $i$, is associated 
with a velocity vector $V_i = [v_{i}^{1},v_{i}^{2},...,v_{i}^{D}]$
and a position vector $X_i = [x_{i}^{1},x_{i}^{2},...,x_{i}^{D}]$ 
($D$ is equal to the number of dimensions in the solution space).
The velocity and position of each particle is initialized to 
random vectors withing the range of the search space. Each
round, the velocity and position of particle $i$ on a dimension
$d$ are updated as follows: 
\begin{equation}\label{eq:psovelocity}
v_{i}^{d} = \omega v_{i}^{d} + c_{1}rand_{1}^{d} (pBest_{i}^d - x_{i}^{d}) + c_{2}rand_{2}^{d} (nBest^d - x_{i}^{d})  
\end{equation}
\begin{equation}\label{eq:psoposition}
x_{i}^{d} = x_{i}^{d} + v_{i}^{d}
\end{equation}
where $c_1$ and $c_2$ are acceleration coefficients. The original
creators recommend a fixed value of 2.0 for each, but other researchers
prefer ad-hoc values~\cite{suganthan99} or ones that vary with 
time~\cite{ratnaweera04} (with a larger $c_1$ at the beginning, and a 
larger $c_2$ at the end).
$rand_{1}^{d}$ and $rand_{2}^{d}$ are two uniformly distributed
random numbers generated for dimension $d$. 
$pBest_i$ is the position found to date with the highest score 
(as indicated by the problem's objective function), and $nBest$
is the top-scoring position in the current neighborhood. Note that
in some implementations of PSO, $pBest_i$ is split into {\em local} and
{\em global} values.

$\omega$ is an inertial weight introduced into the PSO algorithm by 
Shi and Eberhart~\cite{shi98}. The inertia linearly decreases over a series
of generations according to:
\begin{equation}\label{eq:psointertia}
\omega= \omega_{max}-(\omega_{max}-\omega_{min}){g \over{G}}
\end{equation}
where $g$ is the current generation, and $G$ is a predefined maximum
number of generations. ~\cite{shi98,shi99} recommend that $\omega_{min}$
and $\omega_{max}$ be set to 0.4 and 0.9 respectively. \
Research
has also been conducted with a fuzzy adaptive inertial factor~\cite{shi01}
and a randomized $\omega$~\cite{eberhart01}.

A user-specified parameter, $V_{max}^{d}$, is used as an upper bound
on the velocity of dimension $d$. Thus, if the magnitude of the velocity
 $|v_{i}^{d}|$ 
exceeds $V_{max}^{d}$, then $v_{i}^{d}$ is set equal to $V_{max}^{d}$,
with the sign (positive or negative) determined by the original value
of $v_{i}^{d}$. 

Each round, the particles evaluate the fitness of each candidate solution
and remember the locations of the top-scoring solutions. Each particle
makes their $pBest_i$ available to the local neighborhood, and the 
neighborhood best ($nBest$) is updated to match the very best 
candidate solution in the entire local area. These "best" values
are used to help guide the velocity and position functions described in
equations \ref{eq:psovelocity} and \ref{eq:psoposition}. The algorithm 
reaches convergence when all particles approach a certain
value and the fitness function stops reporting better values. PSO 
algorithms tend to stop either then the velocity function has slowed 
down to zero, a certain number of generations have passed, or if convergence has been detected. To prevent 
convergence at a local maxima, stagnation operators are sometimes used
to reset the particles if they stop at a position known to be 
sub-optimal.

Particle swarm algorithms come with their own share of weaknesses. 
Like any other population-based evolutionary algorithm, PSO 
can be computationally inefficient. Further, the standard algorithm 
can easily become trapped in local optima. A number of approaches have
been proposed to address both issues ~\cite{ho08,andrews06,liang05,zhan09} (often 
by incorporating techniques from genetic algorithms~\cite{andrews06} 
or local search~\cite{liang05}). 
Despite these limitations, particle swarm optimization has become a popular approach in the search-based software engineering field 
because it is easy to implement, easy to parallelize, and gradient-free ~\cite{wilke05}. 

Ferriera et al.~\cite{ferriera08} have used particle swarm optimization to study errors in
network protocols. 
Failures in network protocols are critical, thus they must be verified in order to ensure that 
they meet all requirements.
Such verification can be performed using model checking; however, the large number of required states 
limits the size of the models that are possible to check. 
Particle swarm optimization was chosen to optimize these models because of the algorithm's parallel nature, 
which allows it to outperform other approaches that would fail due to the size of the search space.
PSO cannot be used to verify these network protocols, but it can efficiently find errors in the software.
The authors have implemented their experiment in the Java Pathfinder model checker. 
The PSO algorithm was able to generate better quality results than exhaustive algorithms and it could
assess protocols that exhausted the memory constraints of other techniques. 

Windisch ~\cite{windisch07} researched the efficiency of particle swarm optimization in evolutionary structural testing.
In such structural testing, an algorithm automatically generates test cases with the goal of achieving high 
code coverage. 
He and his coauthors performed experiments with twenty-five artificial test objects and thirteen more complex real-world projects. 
While both PSO and a GA needed more time to optimize as the number of parameters increased, a more detailed analysis revealed
that the GA was unable to reach the global maxima within the given number of function evaluations when it had to optimize more than
one parameter. The PSO algorithm reached it when optimizing one, two or three parameters. In situations where both algorithms
converged successfully, PSO often reached better solutions given the same number of iterations.
In thirteen of nineteen experimental cases reported, PSO outperformed the GA by orders of magnitude. In the remaining six cases, the GA reached
better results, but not by any statistically significant amount. In general, GA featured a slightly faster convergence for
simple functions whereas PSO outperformed GA on complex functions with larger search spaces.

Diaz-Aviles et al. recently presented an approach, using Particle Swarm Optimization, to automatically 
optimizing the retrieval quality of ranking functions~\cite{diazaviles09}. 
Their method, Swarm-Rank, learns a ranking function by optimizing the
combination of various types of evidence, such as content and
hyperlink features. At the same time, it works to maximize the mean average precision of the results returned. 
In a series of experiments on benchmarking datasets, they compared Swarm-Rank against the standard BM25, 
as well as the sate-of-the-art RankingSVM and RankBoost algorithms. Swarm-Rank always outperformed 
BM25 and was found to be competitive with both RankingSVM and RankBoost on ranking relevant documents at the very top positions (often
outperforming at least one of the two).

\subsection{Ant Colony Optimization}

Ant Colony Optimization, as formalized by Dorigo and Gambardella~\cite{dorigo97}, is a meta-heuristic swarm intelligence
method similar to the previously discussed particle swarm optimization. 
In an ant colony optimization (ACO) algorithm, a series of cooperating agents work to 
find optimal solutions to search problems in a manner similar to real-life ants. 
Certain species of ants are known to be able to find the shortest path from a food source to their 
nest without any visual guidance~\cite{beckers92}. 
Instead, these ants follow a chemical trail, a {\em pheromone}, left by ants that have visited this food source in the past (this process 
is demonstrated in figure \ref{fig:ants}). 
Similarly, during ant colony optimization, the agents traverse a graph, choosing paths by incorporating information
based on solutions and their qualities achieved by other agents during elapsed iterations (that is, the "pheromones" left by past "ants").
Through the accumulation of pheromones, the agents will be able to converge upon a set of high-scoring solutions and the shortest path 
to achieve said solutions.

\begin{figure}
\fbox{
	\begin{minipage}{6.33in}
	\begin{center}
	\includegraphics[width=6in]{aco.png}
	\end{center}
	\caption{A demonstration of how real-life ants locate food, from~\cite{dorigo97}.\newline In (a), an ant has arrived at a fork in the path. As expected, some ants will travel in one direction and some in the other - shown in (b). (c) shows that, since ants move at a constant speed, the ants that took the lower path will arrive at the food first. Thus, as seen in (d), pheromone accumulates at a higher rate on the shorter path (which means that the probability of an ant choosing that path will grow over time).}
	\label{fig:ants}
	\end{minipage}
}
\end{figure}

The ACO meta-heuristic ultimately breaks down into three phases: generate solutions, update pheromones, and conduct daemon actions.  
The typical form of a solution depends on the type of search problem
being explored, but they can be simplified as paths through some kind of graph
space. At each step during the construction phase, every agent in 
the system adds one vertex to its path. The ant will then choose to move from
vertex $i$ to vertex $j$ with probability:
\begin{equation}\label{eq:acoprob}
P_{i,j} = {{(\tau_{i,j}^{\alpha})(\eta_{i,j}^{\beta})}\over{\Sigma(\tau_{i,j}^{\alpha})(\eta_{i,j}^{\beta})}}
\end{equation}
where $\tau_{i,j}$ is the amount of pheromone left on $edge_{i,j}$
and $\eta_{i,j}$ is the {\em desirability} of that edge. The 
desirability is defined as a function of the a priori information 
known about the search problem. For instance, desirability could be
the gain in the score from an objective function achieved by taking that
step. The $\alpha$ and $\beta$ exponents are user-supplied weights
used to determine the influence of the pheromones versus the 
desirability. 

At each stage of the problem, an ant will typically have to choose
between several competing edges. This is done through a process called
{\em roulette selection}, where all actions are given a probability
(see equation \ref{eq:acoprob}) and the ant chooses a random number
between zero and one. The probability of selecting an action is added
to a sum, and if adding another probability to that sum would push
the sum beyond the random number, that action is chosen as the ant's
next step. That vertex is used to mutate the ant's current solution, 
and the ant steps forward in the search space. 

Once every agent has selected their next action, a "pheromone update"
takes place. This phase has two steps - evaporation and deposit.
In the evaporation step, a certain amount of pheromone is removed 
on each edge according to:
\begin{equation}\label{eq:acoevap}
\tau_{i,j}= (1-\rho)\tau_{i,j}
\end{equation}
where $\rho$ is a user-supplied {\em evaporation control rate}. The
second step, the deposit, adds pheromones to each visited graph edge as
follows:
\begin{equation}\label{eq:acodeposit}
\tau_{i,j}^{k} = \tau_{i,j}^{k} + {{1}\over{C_{k}}}
\end{equation} 
where $C_k$ is the calculated cost of the $k$th ant's solution. 
This deposit process, over time, will cause the amount of pheromones
on a "good" edge to increase far in excess of the evaporation rate. In
turn, this will make certain sections of the solution space far more
attractive to each ant, guiding them towards the optimal corners. 

The third phase, {\em daemon actions}, is a name given to the set of 
post-processing steps required by the search problem. This phase is 
optional and highly problem-specific. 

Although the most obvious use of ant colony optimization is on combinatorial optimization problems such as the
traveling salesperson problem ~\cite{colorni91,dorigo97} or the quadratic assignment problem~\cite{maniezzo94,dorigo99}, 
ACO is well-suited to any problem that is 
rapidly-changing or that requires that the current "best" solution be
updated regularly~\cite{harman07}. Until 2007, ant colony optimization saw
little use in search-based software engineering, but that has changed rapidly over the past three years years. 

Prandtstetter and Raidl~\cite{prandtstetter09} recently applied ant colony optimization and variable neighborhood search (also known as VNS,
basically a hill climber with resets) to 
what is technically an software engineering problem, though an unconventional one - the reconstruction of shredded documents.
The authors consider four different construction heuristics, favoring quick solutions over slightly more complete ones. Those
heuristics were Prim's method, border similarity, 
and two additional heuristics based on the fact that the edges of pages (the margins) are typically left blank. 
The ACO algorithm then applies randomized versions of these heuristics.
In experimental tests, the ACO far outperforms the VNS approach in terms of solution quality (obtaining higher-quality solutions in thirty-four of
forty-five cases). However, the VNS shows shorter execution times. 
The solutions obtained from the ACO algorithm are some of the best to date in document reconstruction, often recreating a large portion of the 
original text document.

Chicano and Alba~\cite{chicano08} applied ant colony optimization to the problem of 
finding safety property violations in concurrent models. 
Their approach, ACOhg, modifies ant behavior with internal resorts
in order to search very large landscapes.
ACOhg is applied to concurrent models in edge-case scenarios, where
other methods have previously failed.  
In experiments conducted over nine models, ACOhg had a 100\% success
rate in finding the error path, outperforming a standard A* search.
During this search, ACOhg expanded fewer paths than A* and, as a 
consequence, used less memory.

Ayari et al. have applied ant colony optimization to fault-based
testing~\cite{ayari07}.
Evolutionary algorithms are usually applied to this task - 
fault-based testing is expensive and evolutionary algorithms have been
proven to lower the cost of test generation. 
The authors propose an ant-based scheme, augmented with a 
probability density estimation mechanism, for automatic test-input
generation in the context of mutation testing.  
They compared their approach with a standard genetic algorithm,
a random search, and a hill climber on two different 
JAVA-based testbeds. On both projects, the ACO vastly outperformed
all of the other approaches (with mean mutation scores of 89\% and 88\%
against the 35\% and 42\% scored by the next-best solution, the GA). 

\subsection{Other Methods}

As documented by the search-based SE literature~\cite{clarke03,harman01,harman04,rela04}
and Gu et al~\cite{gu97},
there are many other possible optimization methods.
Some of these are:
\bi
\item 
Gradient descent methods assume that an objective function $F(X)$ is 
differentiable at any single point $N$. A Taylor-series approximation of
$F(X)$ can be shown  to 
decrease fastest if the negative gradient ($-\Delta F(N)$) is followed 
from point $N$. 
\item
Discrete methods
	assume that model variables have a finite range (that may be quite small)
	while continuous methods assume the existence of numeric values with a very large
	(possibly infinite) range.  
\item
Some methods map discrete values (true/false) into a continuous range (1/0)
	and then use integer programming methods like CPLEX~\cite{mittle07}
	to achieve results. 
\item
	Other methods find overlaps in goal expressions and generate a binary decision diagram (BDD)
	where parent nodes store the median of overlapping children nodes.
\item
	Sequential versions of most optimization algorithms exist. These implementations 
run on one CPU while parallelized methods spread the work over a distributed CPU farm. 
\ei
	This survey of related work is hardly exhaustive - Gu et al. lists hundreds of other methods and no
single researcher can experiment with them all.
	All the algorithms studied in this thesis are discrete and sequential.
	I have spent some time exploring parallel versions of the KEYS optimizers but, as of yet, the communication overhead
	outweighs the benefits of parallelism.

As for the general class of gradient descent methods, I do not use them because they assume
the objective function being optimizing is essentially continuous. Any model with an "if" statement
in it is not continuous since, at the "if" point, the program's behavior may become  discontinuous.
The DDP requirements models studied in this thesis are discontinuous at every subset of every possible mitigation.

Likewise, I do not explore the more specific class of  integer programming  methods for two reasons.
	First, Coarfa et
	al.~\cite{coarfa00} found that  integer programming-based approaches
	ran an order of magnitude slower than discrete methods like
	the 
	MaxWalkSat and KEYS2 algorithms, thus violating the speed requirement.  
Similar results 
have been reported by Gu et.al  where discrete
	methods ran one hundred times faster than integer programming~\cite{gu97}.

Harman offers another reason to avoid integer programming methods.
In his search-based SE
manifest~\cite{harman01}, he argues 
that many SE problems are
over-constrained and, thus, there may exist no precise solution that
covers all constraints. 
This implies that a complete solution over all variables is impossible and  partial solution based on 
heuristic search methods are  preferred.
Such methods may  not be complete; however, as Clarke~\cite{clarke03} remarks, ``...software engineers
face problems which consist, not in finding {\em the} solution,
but rather, in engineering an {\em acceptable} or 
{\em near-optimal solution} from a large number of alternatives."

% \section{Requirements Analysis Tools}

%There exist many powerful requirements analysis tools.
%Hamid et al. and Sterman ~\cite{hamid91,sterman00} explored a method called continuous simulation (also referred to as system dynamics).
%Continuous simulation has been used in a large variety of fields - it uses a series of feedback loops and time delays to model a complex system, which aids in the explanation 
%of nonlinearity. 
%State-based simulation, which includes petrinet and data-flow approaches, is fairly standard in 
%requirements analysis~\cite{akhavi93,harel90}.
%Another well-explored approach is hybrid-simulation~\cite{martin01,donzelli01,setamanit07}, 
%which combines discrete event simulation and systems dynamics.
%Iwasaki~\cite{iwasaki89} and Bratko~\cite[chapter 20]{bratko01} have conducted significant research studying logic-based 
%and qualitative-based methods (which commonly use a logic language like Prolog).
%Mi and Scacchi ~\cite{mi90} developed an environment for rule-based simulation of requirements analysis.
 
%	One can find these models being used in the requirements phase (the DDP model, for instance), 
%pattern-based design refactoring~\cite{france03}, software integration~\cite{denno03}, 
%	model-based security~\cite{jurjens06}, and performance assessment~\cite{bals04}.
%	Many researchers have proposed support environments to
%	help explore the increasingly complex models that engineers are
%	developing. Gray et al ~\cite{gray06} have developed the Constraint-Specification
%	Aspect Weaver (C-Saw), which uses aspect-oriented approaches ~\cite{filman04}
%	to help engineers in the process of model transformation.
%	Likewise, Cai and Sullivan ~\cite{cai05} describe a formal method and tool called
%	{\em Simon} that ``supports interactive construction of formal models,
%	derives and displays design structure matrices... and supports
%	simple design impact analysis.'' 

%	Other tools of note are lightweight formal methods such as ALLOY ~\cite{jackson02}
%	and SCR~\cite{heitmeyer02}, as well as the UML tools that allow
%	for the execution of life cycle specifications 
%	(e.g. CADENA~\cite{child06}).

 
%	Many of the above tools were built to maximize the expressive power of the representation language or the constraint language
%	used to express invariants. What distinguishes the work in this thesis is that the work in this thesis is that the KEYS2 
%algorithm is 
%	{\em willing to trade off
%	representational or constraint expressiveness 
%	for faster runtimes}.
%	There exists a class of ultra-lightweight model languages which can be processed very quickly.
%	Any of the tools listed in the last paragraph could be considered candidate
%	solutions to the problem explored in this thesis, if it can be shown that their processing 
%can generate tame and well-behaved decision ordering diagrams in a timely manner.

\section{Treatment Learning}\label{sec:tlearning}

The field of data mining uses techniques from statistics and artificial intelligence to find small, yet relevant, patterns in large sets of data.
The standard practice in this field is to {\em classify}, to look at an object and make a guess 
at what category it belongs to. As new evidence is examined, these guesses are refined and improved. 
While this paradigm doesn't directly map into the terminology utilized by the DDP requirements models, a related example of classification
might be to look at a series of projects that use DDP models during the planning phase and ask how many risks those projects mitigated. If, say,
that project mitigated greater then 75\% of risks, then a classifier could categorize that project as {\em attainment-maximized} and anything below 
that as {\em cost-minimized} (as those projects decided that some risk was acceptable in order to save part of the budget). 

Treatment learning~\cite{me03c} focuses on a different goal. It does not try to determine {\em what is}, it tries to determine {\em what could be}. 
Classifiers read a collection of data and collect statistics that 
are then used that to place unseen data into
a series of discrete categories. Treatment learners work in reverse. 
They take the classification of a
piece of evidence (that is, the category that it belongs to) and try to reverse-engineer the statistical 
evidence that led a classifier to assign the data to a particular class. 
For instance, rather than deciding whether a project was {\em attainment-maximized} or {\em cost-minimized}, a treatment learner might
try to identify which mitigations should have been enabled for an ideal cost-attainment balance (note that this is {\em exactly} what KEYS does). 
Treatment learners take that evidence and use it to produce a treatment---a small set of rules that, 
if imposed, will change the expected classification distribution.  By filtering the data for 
entries that follow
the rules set in the treatment, you should be able to identify {\em why} a particular classification was reached.

Ultimately, classifiers will strive to increase the representational accuracy. 
They will assess the data and grow a collection of statistical rules with the goal of
making more and more accurate categorizations. 
As a result, if the data is complex, the decision tree output by the classifier will also be complex. 
Treatment learning instead focuses on minimality:  what is the {\em smallest} rule that can be imposed to cause the {\em largest} change. Often, these rules are as simple as filtering for the data where, say, the wind speed
on the outside of an aircraft is between 25 and 45 knots. 

Stated formally, treatment learning is a form of minimal
contrast-set association rule learning. 
The treatments contrast undesirable situations with the 
desirable ones (represented by weighted classes).
Treatment learning, however, is different from other contrast-set methods
like STUCCO~\cite{bay99} because of its focus on minimal theories. 
Conceptually, a treatment learner explores all
possible subsets of the attribute ranges looking for good 
treatments. Such a search is infeasible in practice so the art of
treatment learning lies in quickly pruning unpromising attribute
ranges (i.e. ignoring those that, when applied, lead to a class distribution where the 
target class is in the minority). 

Earlier, I pointed out that KEYS behaves similarly to a treatment learner.
KEYS is designed to provide settings for a model, and then test the model
output against a continuous objective function. Settings that maximize this function are saved and imposed on subsequent rounds. 
A treatment learning algorithm reflects over pre-classified historical data and identifies the features that lead to a particular 
target class, then recommends using those features as a filter to only leave examples of the target class. 
KEYS can, in fact, be thought of as a treatment learner that also deals with the other steps of the process that standard treatment 
learners ignore. Rather than reflecting over historical data, KEYS generates a one-hundred record dataset every round when it comes up with a series
of random model configurations. KEYS then enters those model configurations into an objective function, and receives a score in return. 
While this technically results in a series of continuous scores, those scores are effectively turned into two binary classes ({\em best} and
{\em rest} around a threshold point. The KEYS algorithm then uses those classifications to identify the exact mitigation (and its value) 
that led to the most "best" classifications. That setting is imposed, and subsequent rounds identify additional settings. 
Effectively, KEYS is a treatment learner that also generates and classifies its own data, then continues operating until all settings are fixed.

In the following subsections, I will detail two treatment learning algorithms.

\subsection{TAR3}

TAR3~\cite{hu02, gundy07,gundy09,schumann09} (and its predecessor TAR2~\cite{me03c}) are based on two fundamental concepts---lift and support.  The {\em lift} of a treatment is the change that some decision
makes to a set of examples after imposing that decision.
TAR3 is given a set of training examples $E$. 
Each example $e\in E$  contains a set of attributes, each with a specific value (which have 
commonly been discretized into a series of ranges).
These attributes (and the range their values fall within are directly mapped to a specific classification
(stated formally - {$R_i, R_j, ... \rightarrow C$}).
The individual class symbols $C_1$, $C_2$,... 
are ranked and sorted based on a utility score
({$U_1 < U_2 < ... < U_C$}, where $U_C$ is the target class). 
Within dataset $E$, these classes
occur at certain frequencies ($F_1$, $F_2$,..., $F_C$)
where $\sum F_i$ = 1 (that is, each class occupies a fraction of the overall dataset).
A treatment T of size M is a conjunction of attribute
value ranges {$R_1 \wedge R_2... \wedge R_M$} (these ranges are obtained by discretizing
and combining several of the original continuous attribute values). Some subset of the dataset ($e \subseteq E$) 
is contained within the treatment; that is, if the treatment is used to filter $E$, 
$e \subseteq E$ is what will remain. In that subset, the classes 
occur at frequencies $f_1$, $f_2$,..., $f_C$. 
TAR3 seeks the smallest treatment $T$ which induces the biggest changes in
the weighted sum of the utilities multiplied by the frequencies of the
classes. This score, the score of $e \subseteq E$ where $T$ has been imposed, is divided by the score of 
the baseline (dataset $E$ when no treatment has been applied). Formally, the lift is defined as
\begin{equation}\label{eq:lift}
\mathit{lift} = {\sum_c{U_c f_c} \over \sum_c{U_c F_c}}.
\end{equation}


The classes used for treatment learning are assigned a score {$U_1 < U_2 < ... < U_C$} and the
learner uses this to assess the class frequencies resulting
from applying a treatment by finding the subset of the inputs that 
falls within the reduced treatment space. 
In normal operation, a treatment learner conducts
{\em controller learning}; that is, it finds a treatment which selects
for better classes and rejects worse classes. 
By reversing the scoring function, treatment learning can also select
for the worst classes and reject the better classes. This
mode is called {\em monitor learning} because it 
locates the one thing
we should most watch for.

Real-world datasets, especially those from hardware systems, 
contain some {\em noise} ---incorrect or misleading data 
caused by accidents and miscalculations. 
If these noisy examples are perfectly correlated with failing examples,
the treatment may become overfitted. 
An overfitted model may come with a massive lift score, but it does not
accurately reflect the details of the entire dataset. 
To avoid overfitting, learners need to adopt a threshold and reject all
treatments that fall on the wrong side of this threshold. We define this
threshold as the {\em minimum best support}.

\begin{figure}{
\begin{center}
\includegraphics[width=3in]{iris.png}
\end{center}}
\caption{Probability distribution of individual attribute scores.}
\label{fig:tar3lift}
\end{figure}

Given the desired class, the best support is the ratio of the frequency 
of that class within the treatment subset to the frequency of 
that class in the overall dataset. To avoid overfitting, TAR3 rejects 
all treatments with best support lower than a user-defined minimum 
(usually 0.2). As a result, the only treatments returned by TAR3 will have 
both a high {\em lift} and a high {\em best support}. This is also the reason
that TAR3 prefers smaller treatments. The fewer rules adopted, the more 
evidence that will exist supporting those rules.

TAR3's lift and support calculations can assess the effectiveness of a 
treatment, but they are not what generates the treatments themselves.
A naive treatment learner might attempt to test all subsets of all ranges
of all of the attributes. Because a dataset of size $N$ had $2^N$ possible
subsets, this type of brute force attempt is inefficient. The art
of a good treatment learner is in finding good heuristics for generating
candidate treatments. 

The algorithm begins by discretizing every continuous attribute into smaller
ranges by sorting their values and dividing them into a set of equally-sized
bins. It then assumes the small-treatment effect; that is, it only builds
treatments up to a user-defined size. Past research~\cite{gundy07,gundy09}
has shown that a treatment's size should be less than four attributes. 
TAR3 will then only build treatments from the discretized ranges with 
a high heuristic value. 

TAR3 determines which ranges to use by first determining the lift score of
each attribute's value ranges (that is, the score of the class distribution obtained by filtering for the
data instances that contain a value in that particular range for that particular attribute). 
These individual scores are then sorted and 
converted into a cumulative probability distribution, as seen in~\fig{tar3lift}. 
TAR3 randomly selects values from this distribution, meaning that low-scoring ranges are unlikely to be selected. To build a treatment, $n$ (random from $1$...max treatment size)
ranges are selected and combined. These treatments are then scored and sorted. 
If no improvement is seen after a certain number of rounds, TAR3 terminates 
and returns the top treatments. 

\subsection{TAR4.1}

TAR3, while effective at generating informative treatments, is not a very efficient algorithm.
It stores all examples from the dataset in RAM and requires three scans of the data in order to
discretize, build theories, and rank the generated treatments. 
The TAR4.1 treatment learner was designed to address these inefficiencies~\cite{gay10b}. 
Modeled after the SAWTOOTH~\cite{orrego04} incremental Naive Bayes classifier, TAR4.1's scoring heuristic
allows for 
an improved runtime, lower memory usage, and a better ability to scale to large datasets.

Naive Bayes classifiers
offer a relationship between  fragments of evidence $E_i$,
a prior probability for
a class $P(H)$, and a posteriori  probability
$P(H|E)$ defined by
\begin{equation}\label{eq:bayes}
P(H|E)= \prod_iP(E_i|H) \frac{P(H)}{P(E)}.
\end{equation}
For numeric features, a features mean $\mu$ and standard deviation $\sigma$ are used in
a Gaussian  probability function~\cite{Witten05}:
\begin{equation}\label{eq:bayes2}
f(x) = 1/(\sqrt{2\pi}\sigma)e^{-\frac{(x-\mu)^2}{2\sigma^2}}.
\end{equation}

TAR4.1 still requires two passes through the data, for discretization and for building treatments. 
These two steps function in exactly the same manner as the corresponding steps in the TAR3 learner. 
TAR4.1, however, eliminates the final pass by building a scoring cache during the BORE classification stage. 
As explained previously, examples are placed in a $U$-dimensional hypercube during classification, with one dimension for
each utility. Each example $e \in E$ has a normalized distance $0 \leq D_i \leq 1$ from an {\em apex}, an area where
the best examples reside. When BORE classifies examples into {\em best} and {\em rest}, that normalized distance is added as a score,
called $D_i$ (the euclidean distance from 0),
to the $\mathit{down}$ table and a seperate score, $1-D_i$ (or, the distance from the best), is entered into the $\mathit{up}$ table.

When treatments are scored by TAR4.1, the algorithm does a linear-time table lookup instead of scanning the entire dataset. Each
range $R_j \in \mathit{example}_i$ adds scores $\mathit{down}_i$ and $\mathit{up}_i$ to counters 
$F(R_j|\mathit{rest})$ and $F(R_j|\mathit{best})$. These counters are a summation of scores for a 
range $R_j$ across the dataset, and represent how often data examples containing that range appear in the
{\em best and rest}. 
These summations are then used to compute the following probability and likelihood equations:
\begin{eqnarray}
P(\mathit{best}) = {\sum_i{\mathit{up}_i}\over{\sum_i{\mathit{up}_i} + \sum_i{\mathit{down}_i}}}, \\
P(\mathit{rest}) = {\sum_i{\mathit{down}_i}\over{\sum_i{\mathit{up}_i} + \sum_i{\mathit{down}_i}}}, \\
P(R_j|\mathit{best}) = {{F(R_j|\mathit{best})}\over{\sum_i{\mathit{up}_i}}}, \\
P(R_j|\mathit{rest}) = {{F(R_j|\mathit{rest})}\over{\sum_i{\mathit{down}_i}}}, \\
L(\mathit{best}|R_k \wedge R_l \wedge ...) = \prod_x{P(R_x|\mathit{best})*P(\mathit{best})},\\
L(\mathit{rest}|R_k \wedge R_l \wedge ...) = \prod_x{P(R_x|\mathit{rest})*P(\mathit{rest})}. 
\end{eqnarray}
TAR4.1 finds the {\em smallest} treatment $T$ that {\em maximizes}
\begin{equation}\label{eq:tada}
P(\mathit{best}|T) = {{{L(\mathit{best}|T)}^2}\over{L(\mathit{best}|T) + L(\mathit{rest}|T)}}.
\end{equation}

Note the squared term in the top of the equation, $L(\mathit{best}|T)^2$. 
The standard Naive Bayes design
assumes independence between all attributes and keeps singleton counts. By not squaring that term, TAR4.1 adds
redundant information, which alters
the generated probabilities. In effect, it produced treatments with high scores, but without the {\em support} 
required by the TAR3 algorithm.
By squaring that term, the likelihood that a range appears in an area of top scores, 
those treatments that lack support are pruned in favor of those that have both a good score and support. 

It should also be pointed out that Equation \ref{eq:tada}, the formula that TAR4.1 uses to choose treatments,
is the same formula used by KEYS to choose optimal model settings (see Section \ref{sec:keysalgo}. Both algorithms 
judge the scores output by an objective function according to a Bayesian ranking measure. Therefore, they would 
likely make comparable decisions when applied to the same problems. However, as pointed out earlier, the two algorithms
are not directly comparable as TAR4.1 is generally only used in a single-round process and requires data to be pre-classified. 

\section{Summary}

In this chapter, I have discussed algorithms and fields of research that are related to the work conducted in this thesis.

The requirements satisfaction problem that I have studied can be though of as a search-based software engineering problem. 
We want to {\em search} for the set of mitigations that will allow us to attain the most requirements at the lowest price. 
KEYS and the algorithms benchmarked against it all reflect aspects of the SBSE field. We use MaxWalkSat, a hybrid random search/
hill climber that utilizes resets to escape local maxima. Our experiments also make use of simulated annealing, which is extremely
popular in SBSE research. I have also discussed tabu search, genetic algorithms, particle swarm optimization, and ant colony optimization
in detail.

This chapter has discussed the concept of treatment learning, a machine learning method that takes a backlog 
of classified data, weights the classes by {\em desirability}, and identifies which features (and which values of those features)
are the most pivotal in predicting for a target class. The KEYS algorithm can be thought of as a treatment learner that generates and
classifies its own data, and then continues operating until all features have fixed settings. 

In fact, the entire treatment learning field can be thought of as an over-elaboration of a very simple idea - 
that there exist a small number of important variables that, if controlled, lead to optimal solutions. This idea is the very basis of the
KEYS algorithm, which I will present in detail in the next chapter. 

I will now shift from the general to the specific. The next chapter presents a series of algorithms - taken from various aspects of 
the SBSE paradigms presented in this chapter - that will be used to address the DDP problem.
