\section{Algorithms}

The following terms are used in the discussion of search algorithms:

\begin{list}{}{\itemsep -0.25em}
\item[{\em Feature}] An input to the COCOMO-family models.  A scale factor (e.g., $flex$), an effort multiplier (e.g., $acap$), or a defect remover (e.g., $aa$).
\item[{\em Value}] A number between 1 and 6 representing a feature's magnitude.
\item[{\em Range}] The set of valid values for a feature.
\item[{\em Setting}] The combination of a feature and range (e.g., $flex = 2, 3, 4$) or a feature and value (e.g., $acap = 3$).
\end{list}

The pseudocode assumes the following functions:

\begin{list}{-}{\itemsep -0.25em}
\item[$energy()$] Calculates the energy for the current settings.
\item[$settings()$] Compiles the current settings into a single data structure.
\item[$restore()$] Resets the search state to the given settings.
\item[$push()$ and $pop()$] Perform the stack operations of the same names.
\item[$count()$] Returns the number of items in the given collection.
\item[$most\_positive\_number()$] Returns the largest number that may be represented in the programming environment.
\item[$random()$] Returns a pseudorandom number between 0 and 1.
\item[$min()$] Returns the least-valued argument.
\end{list}

\subsection*{ISAMP}

Iterative sampling or ISAMP (Figure~\ref{fig:isamp}) is a simple stochastic search algorithm that builds solutions by randomly selecting a value for each feature.
The best such solution is held in memory and returned after $num\_tries$ attempts.
To avoid searching in high-energy areas of the search space, ISAMP stores the maximum energy seen so far.
If this energy is exceeded during an attempt, the solution is abandoned and the new maximum energy stored.
If an attempt runs to completion (i.e., all features are set), the maximum energy is reduced by some factor $r$.
This ensures that several consecutive unsuccessful attempts do not permanently raise the maximum energy to an overly permissive value.

\begin{figure}
\hrule
{\scriptsize\begin{verbatim}

 1 function isamp(num_tries, r)
 2   min_energy = most_positive_number()
 3   max_energy = 0
 4   for i = 1 to num_tries
 5     while not all features are set
 6       feature = random unset feature
 7       set feature to a random value
 8       current_energy = energy()
 9       if current_energy > max_energy
10         max_energy = current_energy
11         next i
12       else if current_energy < min_energy
13         min_energy = current_energy
14         best_settings = settings()
15     max_energy = max_energy * r
16   return best_settings
\end{verbatim}}
\hrule
\caption{Pseudocode for ISAMP.}
\label{fig:isamp}
\end{figure}

\subsection*{MaxWalkSat}

MaxWalkSat (Figure~\ref{fig:maxwalksat}) is a local search algorithm.
Given a random initial solution, MaxWalkSat attempts $num\_changes$ modifications to randomly selected features.
Some percentage of the time (given by the tuning parameter $p$), the modification is ``smart'':
for the selected feature, the algorithm chooses the value that minimizes $energy()$.
The rest of the time, a random range is chosen for the feature.
After $num\_tries$ attempts, the best solution is returned.

\begin{figure}
\hrule
{\scriptsize\begin{verbatim}

 1 function maxwalksat(num_tries, num_changes, p)
 2   min_energy = most_positive_number()
 3   for i = 1 to num_tries
 4     set some random features to random ranges
 7     for j = 1 to num_changes
 8       feature = random feature
 9       if p > random()
10         set feature to the value that minimizes energy()
11       else
12         set feature to a random range
13       current_energy = energy()
14       if current_energy < min_energy
15         min_energy = current_energy
16         best_settings = settings()
17   return best_settings
\end{verbatim}}
\hrule
\caption{Pseudocode for MaxWalkSat.}
\label{fig:maxwalksat}
\end{figure}

\subsection*{Simulated Annealing}

Simulated annealing (Figure~\ref{fig:simulated_annealing}) is a classic stochastic search algorithm that takes its inspiration from the metallurgical annealing process.
Like MaxWalkSat, simulated annealing begins with a random initial solution and makes $num\_changes$ modifications to randomly selected features.
Each modification is accepted or rejected based on the acceptance probability $p$.

The acceptance probability is a function of the current state's energy $E$, the new state's energy $E_{\text{new}}$, and the temperature $t$:
\[
p = e^{(E - E_{\text{new}})/t}
\]
On the $k$th of $k_{\text{max}}$ changes, the temperature is given by
\[
t = e^{-rk / k_{\text{max}}}
\]
where $r$ is a rate factor that controls how quickly the algorithm ``cools.''

Early in the search, the temperature is high, allowing ``bad'' modifications (those that result in higher energies) to be explored.
In this way, the algorithm may escape local minima in the search space.
As temperature decreases, such modifications are less and less likely to be accepted.
When the temperature approaches zero, simulated annealing begins to mimic a greedy search algorithm, only moving to a new state if it has a lower energy.

\begin{figure}
\hrule
{\scriptsize\begin{verbatim}

 1 function simulated_annealing(num_changes, r)
 2   min_energy = most_positive_number()
 3   set some random features to random ranges
 4   current_energy = energy()
 5   current_settings = settings()
 6   for i = 1 to num_changes
 7     feature = random feature
 8     set feature to a random range
 9     new_energy = energy()
10     if new_energy < min_energy
11       min_energy = new_energy
12       best_settings = settings()
13     if new_energy < current_energy
14     or p(current_energy, new_energy, t(i, num_changes, r)) > random()
15       current_energy = new_energy
16       current_settings = settings()
17     else
18       restore(current_settings)
19   return best_settings
\end{verbatim}}
\hrule
\caption{Pseudocode for simulated annealing.}
\label{fig:simulated_annealing}
\end{figure}

\subsection*{Beam Search}

Beam search (Figure~\ref{fig:beam_search}) is a tree-based algorithm.
The search maintains a list of potential states sorted by increasing energy.
At each iteration, the best state is removed from the front of the list and explored.
New states are generated by removing values one by one from every feature not currently constrained to a single value.
When all new states have been generated, the list is once again sorted by increasing energy and then truncated to a maximum count of $beam\_width$.
Once the states list is empty, the best solution is returned.

\begin{figure}[!t]
\hrule
{\scriptsize\begin{verbatim}

 1 function beam_search(beam_width)
 2   min_energy = most_positive_number()
 3   states = null
 4   push(settings(), states)
 5   while count(states) > 0
 6     current_settings = pop(states)
 7     restore(current_settings)
 8     current_energy = energy()
 9     if current_energy < min_energy
10       min_energy = current_energy
11       best_settings = settings()
12     for each feature not set to a single value
13       for each value in feature
14         remove value from feature's range
15         push(settings(), states)
16         restore(current_settings)
17     sort states in order of increasing energy()
18     truncate states to a maximum count of beam_width
19   return best_settings
\end{verbatim}}
\hrule
\caption{Pseudocode for beam search.}
\label{fig:beam_search}
\end{figure}

\subsection*{A-STAR}

A-STAR (Figure~\ref{fig:a_star}) is also a tree-based algorithm.
New states are generated in the same fashion as in beam search.
Each state's $cost$ is calculated as
\[
cost = g + h
\]
where $g$ depends on the number of decisions we have already made, and $h$ depends on the distance to the theoretical zero-energy point.
Instead of investigating states in order of increasing energy, A* uses this $cost$ value to determine search order.

Since the list of states is not truncated as in beam search, a termination criterion is needed.
This is provided by counting the number of iterations $m$ that the best solution has not changed.
The search terminates when
\[
\frac{m}{n} \geq s
\]
where $n$ is the total number of iterations and $s$ is the required stability (a tuning parameter).
The search will not terminate, however, if $n$ is less than some $min\_n$.

\begin{figure}[!t]
\hrule
{\scriptsize\begin{verbatim}

 1 function a_star(min_n, s)
 2   min_energy = most_positive_number()
 3   max_energy = 0
 4   states = null
 5   push(settings(), states)
 6   n = 0, m = 0
 7   while count(states) > 0
 8     current_settings = pop(states)
 9     restore(current_settings)
10     current_energy = energy()
11     if current_energy > max_energy
12       max_energy = current_energy
13     if current_energy < min_energy
14       min_energy = current_energy
15       best_settings = settings()
16       m = 0
17     for each feature not set to a single value
18       for each value in feature
19         remove value from feature's range
20         push(settings(), states)
21         restore(current_settings)
22     for each state in states
23       store cost of state as g(state) + h(state, max_energy)
24     sort states in order of increasing cost
25     n = n + 1, m = m + 1
26     if n >= min_n and m / n >= s
27       exit while
28   return best_settings
29   
30 function g(settings)
31   return the percentage of values removed from all features' ranges
32 
33 function h(settings, max_energy)
34   restore(settings)
35   return energy() / max_energy
\end{verbatim}}
\hrule
\caption{Pseudocode for A-STAR.}
\label{fig:a_star}
\end{figure}
%
%\subsection*{KEYS}
%
%KEYS (Figure~\ref{fig:keys}) seeks to determine the ``key'' decisions that most effectively reduce energy.
%The algorithm explores all $n$ features over $n$ ``eras.''
%Within each era, KEYS generates $num\_trials$ solutions by setting each unset feature to a random value.
%These settings are then ranked according to a Bayesian ranking measure known as BORE (\underline{B}est \underline{O}r \underline{RE}st).
%
%BORE divides the randomly-generated solutions into the top 10\% {\em best} energies and bottom 90\% {\em rest} energies.
%Each setting is then ranked based on its probability of appearing in the top 10\%.
%The ranking statistic is a combination of the conditional probability $P(best|setting)$ and the support term $P(setting \cap best)$.
%Assuming $n = 10,000$ solutions and a $setting$ that appears 10 times in $best$ and 5 times in $rest$, calculation proceeds as follows:
%\[\begin{array}{lll}
%P(setting) &= \frac{n(setting)}{n(total)} = \frac{15}{10,000} &= 0.0015\\
%P(setting \cap best) &= \frac{n(setting \cap best)}{n(total)} = \frac{10}{10,000} &= 0.001\\
%P(best|setting) &= \frac{P(setting \cap best)}{P(setting)} = \frac{0.001}{0.0015} &= 0.667\\
%\text{ranking statistic} &= P(best|setting) \cdot P(setting \cap best)\\
%&= (0.667)(0.001) &= 0.000667
%\end{array}
%\]
%Once all settings are ranked, the best setting for an unset feature is applied, and the next era begins.
%
%\begin{figure}[!t]
%\hrule
%{\scriptsize\begin{verbatim}
%
% 1 function keys(num_trials)
% 2   current_settings = settings()
% 3   while not all features are set
% 4     states = null
% 5     for i = 1 to num_trials
% 6       for each unset feature
% 7         set feature to a random value
% 8       push(settings(), states)
% 9       restore(current_settings)
%10     sorted_settings = bore_rank(states)
%11     new_settings = sorted_settings - current_settings
%12     apply first setting in new_settings
%13     current_settings = settings()
%14   return current_settings
%\end{verbatim}}
%\hrule
%\caption{Pseudocode for KEYS.}
%\label{fig:keys}
%\end{figure}
%
\subsection*{SEESAW}

After many experiments with the search algorithms described above, we observed that the best values for each feature were often either the minimum or maximum for the allowed range.
The reason for this is simple: Since all functions in the COCOMO-family models are monotonic, the most dramatic effects occur at the extreme ends of the ranges.
SEESAW was created to exploit this observation.

In SEESAW, shown in Figure~\ref{fig:seesaw_r}, a random unset feature is selected at each iteration.
Its minimum and maximum values are tested, and the value that results in the lower energy is selected.
If the new energy is less than the current energy, the feature is set, and the algorithm proceeds to the next iteration.
However, if the new energy is greater than the current energy, the setting has a probability $p$ of being rejected.
This tuning parameter effectively allows the algorithm to delay ``lose-lose'' decisions (where both the minimum and maximum value result in a higher energy) until the end of the search.

%The deterministic SEESAW-D (Figure~\ref{fig:seesaw_d}) explores {\em all} unset features at each iteration.
%Minimum and maximum values are tested for each feature, and the resulting energies are stored.
%Once all features have been explored, the setting that results in the lowest energy is applied.

\begin{figure}[!t]
\hrule
{\scriptsize\begin{verbatim}

 1 function seesaw(p)
 2   current_energy = energy()
 3   current_settings = settings()
 4   while not all features are set
 5     feature = random unset feature
 6     min_value = minimum value for feature
 7     max_value = maximum value for feature
 8     set feature to min_value
 9     energy_for_min = energy()
10     set feature to max_value
11     energy_for_max = energy()
12     if energy_for_min < current_energy
13     or energy_for_max < current_energy
14     or p < random()
15       current_energy = min(energy_for_min, energy_for_max)
16       set feature to the value that corresponds to current_energy
17       current_settings = settings()
18     else
19       restore(current_settings)
20   return current_settings
\end{verbatim}}
\hrule
\caption{Pseudocode for SEESAW.}
\label{fig:seesaw_r}
\end{figure}

\begin{center}
\begin{tabular}{r|rrr}
  &win &loss& tie\\\hline
Beam& 120& 12& 60\\
SEESAW& 105& 16& 71\\
A-STAR& 83& 47& 62\\
SA& 59& 88& 45\\
MaxWalkSat& 41& 99& 52\\
ISAMP& 24& 147& 21\\
Baseline& 0& 192& 0\\
\end{tabular}
\end{center}

%\begin{figure}[!t]
%\hrule
%{\scriptsize\begin{verbatim}
%
% 1 function seesaw_d()
% 2   current_settings = settings()
% 3   while not all features are set
% 4     states = null
% 5     for each unset feature
% 6       min_value = minimum value for feature
% 7       max_value = maximum value for feature
% 8       set feature to min_value
% 9       push(settings(), states)
%10       set feature to max_value
%11       push(settings(), states)
%12     sort states in order of increasing energy()
%13     best_settings = first state's settings
%14     new_setting = best_settings - current_settings
%15     apply new_setting
%16     current_settings = settings()
%17   return current_settings
%\end{verbatim}}
%\hrule
%\caption{Pseudocode for SEESAW-D.}
%\label{fig:seesaw_d}
%\end{figure}
%
