\chapter{Introduction}

\section{Summary}

In this dissertation we try to answer the following question: How do
we go about solving optimization problems, in general, and academic 
course scheduling (or timetabling) at the university level, in
particular? we give a detailed answer to the latter part, and
shed some light on the case of tackling optimization problems in
general.

To summarize, we have investigated a variety of optimization
algorithms, in particular, random search, hill climbing,
knowledge-based systems (or expert systems), and simulated
annealing-based methods to solve the course
scheduling  problem. The simulated annealing-based approach includes
mean-field annealing, simulated annealing with three different cooling
schedules, and the use of a rule-based preprocessor to provide a good
initial solution for annealing. 

The best results were obtained using simulated annealing with 
adaptive cooling and reheating as a function of cost, and a rule-based
preprocessor. This approach enabled us to obtain valid schedules for
the timetabling problem for a large university, using a complex cost
function that includes student preferences. None of the other methods
were able to provide a complete valid schedule.

\section{Objectives}

The primary objective of this dissertation is to shed light on how we
go about solving optimization problems in general, and to present
detailed analysis on deriving an approximate solution to the problem
of university course scheduling in particular.

In order to solve an optimization problem such as the TSP or
scheduling , we design a
series of steps, or a procedure, which we can tackle a problem
instance to which it claims to adhere and, ideally, be sure of getting
a good answer in a given amount of time\footnote{Usually we can avoid 
complications due to the Halting problem, as we address problems of
a simpler nature in which we are really fighting against
NP-completeness and are sure that a solution does exist.}.
Such a procedure is known as an `optimization algorithm'.

Sometimes we may be happy with (or forced to accept) a less than
optimal solution, in which case it may be easier to find a suitable
algorithm. We would like our algorithms to return as good an answer as
possible in as little time as possible, and these will be important
comparative judges of the merit of different algorithms. Again, this
is more subtle than it seems in that the time will vary from problem
instance to another, and we have to decide whether we want to minimize
the best case, the worst case or the average case. The reason
NP-complete problems are considered difficult is that all known
algorithms which guarantee the optimal solution will operate in
exponential time in the size of the problem in the worst case
scenario. For reasonably large problem instances this is impractical
and so we reduce our expectations of the solution from 'optimal' to
'good', and seek algorithms which can still search effectively in
these difficult search spaces. As well as average versus best/worst
case in time-requirements, we also want to understand average versus
best/worst case in quality of solution found.

The optimization problem we have closely tackled is university course
scheduling (or timetabling), which can be summarized as follows:

Given data sets of classes and their days, enrollments, and
instructors; rooms and their capacities, types, and locations;
distances between buildings; priorities of each building for different
departments; and students and their class preferences; 
the problem is to construct a feasible class schedule satisfying all 
the hard constraints and minimizing the  medium and soft constraints.
Hard constraints are space and time constraints that must be
satisfied, such as scheduling only one class at a time for any 
teacher, student, or classroom. Medium and soft constraints are
student and teacher preferences that should be satisfied if possible. 

\section{Brief Notes on NP-Completeness}
\subsection{Characteristic of NP-Complete Problems}

If we pick three different and known NP-complete problems, let say
{\bf Satisfiability}, {\bf Knapsack}, and {\bf Clique}, we would
notice the following characteristics about them.
\begin{itemize}
\item Each is solvable, and a relatively {\it simple} approach solves
  it (although the approach may be time-consuming). For each of them,
  we can simply enumerate all the possibilities: all ways of assigning
  the logical values of $n$ variables, all subsets of the set $S$, all
  subsets of $n$ vertices in $G$. If there is a solution, it will
  appear in the enumeration of all possibilities; if there is no
  solution, testing all possibilities will demonstrate that.

\item There are $2^n$ cases to consider if we use the approach of
  enumerating all possibilities (where $n$ depends on the
  problem). Each possibility can be tested in a relatively small
  amount of time, so the time to test all possibilities and answer
  {\it yes} or {\it no} is proportional to $2^n$.

\item They come from different fields; logic, number theory, and graph
  theory, respectively.

\item If it were possible to guess perfectly, we could solve each
  problem in relatively little time. For example, if someone could
  guess the correct assignment or the correct subset, we could simply
  verify that the formula had been satisfied or a correct sum had been
  determined, or a clique had been identified, etc. The verification
  process could be done in time bounded by a polynomial of the size of
  the problem.
\end{itemize}

\subsection{The Classes P and NP}
Let {\bf P} be the collection of all problems for which there is a
solution that runs in time bounded by a polynomial function of the
size of the problem. For example, you can determine whether an item is
in a list in time proportional to the size of the list (simply by
examining each element in the list to determine whether it is the
correct one), and you can sort all items in a list into ascending
order in time bounded by the square of the number of elements in the
list (using, for example, the well-known bubble sort algorithm.) There
may also be faster solutions; that is not important here. Both the
searching problem and the sorting problem are in {\bf P} because they
can be solved in time $n$ and $n^2$, respectively.

For most problems, {\bf polynomial time algorithms} are about the
limit of feasible complexity. Any problem that could be solved in time
$n^{1,000,000,000}$ would be in {\bf P}, even though for large values
of $n$, the time to perform such an algorithm might be
prohibitive. Notice also that we do not have to know an explicit
algorithm, we just have to be able to say that such an algorithm
exists.

By contrast, let {\bf NP} be the set of all problems that can be
solved in time bounded by a polynomial function of the size of the
problem, {\it assuming the ability to guess perfectly.} (in the
literature, this ``guess function'' is called an {\bf oracle machine}
or a {\bf nondeterministic Turing machine}.) This guessing is called
{\bf nondeterminism}.

Of course, no one can guess perfectly. Guessing is simulated by
cloning an algorithm and applying one version of it to each possible
outcome of the guess. Essentially, the idea is equivalent to a
computer programming language in which IF statements could be replaced
by GUESS statements: instead of testing a known condition and
branching depending on the outcome of the test, the GUESS statements
would cause the program to fork, following two or more paths
concurrently.

The ability to guess can be useful. For example, instead of deciding
whether to assign the value TRUE or FALSE to variable $v_1$, the
nondeterministic algorithm can proceed in two directions: one assuming
TRUE had been assigned to $v_1$, and the other assuming FALSE. As the
number of variables increases so does the number of possible paths to
be pursued concurrently.

Certainly every problem in {\bf P} is also in {\bf NP} because the
guess function does not have to be invoked. There is also a class
{\bf EXP}, which consists of problems for which a deterministic
solution exists in exponential time, $c^n$ for some constant $c$. As
noted earlier, every NP-complete problem has such a solution. Every
problem in {\bf NP} is also in {\bf EXP} so {\bf P} $\subseteq$ {\bf
  NP} $\subseteq$ {\bf EXP}.

\subsection{The Meaning of NP-Completeness}
The notion of {\bf NP-completeness} tries to capture the ``hardest''
problems in the class {\bf NP}. In other words, the way the class of
{\bf NP-completeness} is defined, if ever we were able to find a
polynomial time algorithm for Q, an {\bf NP-complete} problem, we can
then find a polynomial time algorithm for any problem X that is in the 
class {\bf NP} (and hence for every {\bf NP-complete} problem). This
follows by the definition of {\bf NP-completeness}.

Stephen Cook (give reference[cook71]) showed that the satisfiability
problem is {\bf NP-complete}, meaning that it can represent the entire
class {\bf NP}. His important conclusion was that {\it if} there is a
{\it deterministic}, polynomial time algorithm (one without guesses)
for the satisfiability problem, then there is a deterministic,
polynomial time algorithm for {\it every} problem in {\bf NP}; that
is, {\bf P} = {\bf NP}.

Richard Karp (give reference[karp72]) extended Cook's result by
identifying several other problems, all of which shared the property
that if any {\it one} of them could be solved in a deterministic
manner in polynomial time, then all of them could. The knapsack and
clique problems were identified by Karp. The results of Cook and Karp 
included the converse: if for even {\it one} of these problems (or any
NP-complete problem) it could be shown that there was {\it no}
deterministic algorithm that ran in polynomial time, then no
deterministic algorithm could exist for {\it any} of them.

Be careful to distinguish between a problem and an instance of a
problem. An {\bf instance} is a specific case: one formula, one
specific graph, or one particular set S. Certain simple graphs or
simple formulas may have solutions that are very easy and fast to
identify. A {\bf problem} is more general; it is the description of
all instances of a given type. For example, the formal statements of
the satisfiability, knapsack, and clique sections are statements of
problems because they tell what each specific instance of that problem
must look like. Solving a problem requires finding {\it one} general
algorithm that will solve {\it every} instance of that problem.

There are problems known to be solvable deterministically in
polynomial time ({\bf P}), and there are problems known {\it not} to
have a polynomial time solution ({\bf EXP} and beyond), so that {\bf
  P} $\subseteq$ {\bf EXP} and {\bf P} $\neq$ {\bf EXP}, meaning {\bf
  P} $\subset$ {\bf EXP}. The class {\bf NP} fits somewhere between
{\bf P} and {\bf EXP}: {\bf P} $\subseteq$ {\bf NP} $\subset$ {\bf
  EXP}. It may be that {\bf P} = {\bf NP}, or that {\bf P} $\neq$ {\bf
  NP}.

The significance of Cook's result is that NP-complete problems have
been studied for a long time by many different groups of prople:
logicians, operations research specialists, electrical engineers,
number theorists, operating systems specialists, and communications
engineers. If there were a practical (polynomial time) solution to any
one of these problems, you would hope that someone would have found it
by now. See Garey and Johnson's N-completeness catalog.


\section{Approximation Algorithms}

When facing an {\it NP}-complete optimization, we may want to consider
algorithms that do not produce optimum solutions, but solutions {\it
  guaranteed to ve close to the optimum}. Suppose that we wish to
obtain such solutions for an optimization problem, maximization or
minimization. For each instance $x$ of this problem, there is an
optimum solution with value $opt(x)$; let us assume that $opt(x)$ is
always a positive integer.

Suppose now that we have a polynomial algorithm $A$ which, when
presented with instance $x$ of the optimization problem, returns some
solution with value $A(x)$. Since the problem is {\it NP}-complete and
$A$ is polynomial, we cannot realistically hope that $A(x)$ is always
the optimum value. But suppose that we know that the following
inequality hold:

\be{appr}
{{|opt(x) - A(x)|} \over {opt(x)}} \leq \epsilon
\ee

where $\epsilon$ is some positive real number, hopefully very small,
that bounds from above the worst-case relative error of algorithm $A$.
(The absolute value in this inequality allows us to treat both
minimization and maximization problems within the same framework.) If
algorithm $A$ satisfies this inequality for all instances $x$ of the
problem, then it is called an {\bf $\epsilon$-approximation algorithm.}

Once an optimization problem has been shown to be {\it NP}-complete,
the following question becomes most important: Are there
$\epsilon$-approximation algorithms for this problem? And if so, how
small can $\epsilon$ be? Let us observe at the outset that such
questions are meaningful only if we assume that {\it p $\neq$ NP},
because, if {\it P = NP}, then the problem can be solved exactly, with
$\epsilon = 0$.

%% All {\bf NP-complete} optimization problems can therefore be
%% subdivided into theree large categories:
%% 
%% \begin{enumerate}
%% \item Problems that are {\bf fully approximable}, in that there is an
%% $\epsilon$-approximate polynomial-time algorithm for them for all
%% $\epsilon > 0$, however small. Of the {\bf NP-complete} optimization
%% problems we have seen, only two-machine scheduling (in which we wish
%% to minimize the finishing time D) falls into this most fortunate
%% category.
%%
%% \item Problems that are {\bf partly approximable}, in that there are
%% $\epsilon$-approximate polynomial-time algorithms for them for some
%% range of $\epsilon$'s, but --unless of course {\bf P = NP}-- this
%% range does not reach all the way down to zero, as with the fully
%% approximable problems. Of the {\bf NP-complete} optimization problems
%% we have seen, NODE COVER and MAX SAT fall into this intermediate class.
%%
%% \item Problems that are {\bf inapproximable}, that is, there is no
%% $\epsilon$-approximation algorithm for them, with however large
%% $\epsilon$ --unless of course {\bf P = NP}. Many {NP-complete}
%% optimization problems fall into this category.
%% \end{enumerate}

\section{Type of problems addressed}

A question to ask here is that: What problems can stochastic
optimization algorithms such as simulated annealing address?

Most of the algorithms we have looked at adhere to a simple set of 
requirements upon the space of problems to which they apply. In fact
we require no more of a problem than that:
\begin{enumerate}
\item we can generate a random solution,
\item a 'local perturbation' to a solution is defined,
\item such perturbations over all relevant parts of the solution space
  (this is usually naturally satisfied).
\end{enumerate}

All of the algorithms discussed below fall within this category. Also
note that because we search directly in the problem space, all the
algorithms we consider will return both the actual solution and its
cost (or value of utility depending upon the context). One can also
envisage algorithms which only return a bound upon the solution cost,
and not the actual solution. Whilst of theoretical value, in most
practical instances we would ordinarily require the solution as
well. Finally, it is important to note that:

\begin{itemize}
\item individual problem instances may vary enormously in
  difficulty. The average versus best or worse case difficulty (or
  complexity) of search and problem solving may depend in quite
  particular fashions on the method of problem selection. These issues
  were addressed later in greater depth.
\item these algorithms may not specify a natural termination
  condition, and in such cases heuristic principles must be
  used. Possibilities include: maximum running time, solution quality,
  time since last improvement; or combinations thereof.
\end{itemize}

In the descriptions which follow, we shall assume we are supplied with
a function `FITNESS: $\sum \rightarrow R$' which supplies us with the
solution quality. Without loss of generality, we assume higher
fitnesses are better.

\section{Combinatorial Optimization}
Combinatorial optimization refers to the problem of minimizing a
function of a large but finite set of variables. The cost function or
energy function $E(\vec{x})$ assigns a real number to each possible
state $\vec{x}$ of the system. The configuration space $X$ is given by
the finite set of all possible system configurations
$\{\vec{x}\}$. The problem is then that of finding the global minimum 
of $E(\vec{x})$ over all $\vec{x}$ in $X$.

The existence of a large number of local but not global minima of
$E(\vec{x})$ in configuration space conspires against the success of
heuristic optimization methods. Algorithms such as simulated annealing
is an improvement upon downhill algorithms in that it provides a
mechanism for getting out of such local minima. It should be noted
that while the notion of global minima is an absolute one that depends
only on the cost function $E(\vec{x})$, the concept of local minima is
relative to the topology since it implies comparing the value of
$E(\vec{x})$ with that of $E(\vec{x}^{'})$ for those $\vec{x}^{'}$
which are neighbors of $\vec{x}$.

The topology of configuration space is defined by the neighbor
relation. A natural definition of neighborhood for optimiztion
problems is given by the move set: a small rearrangment of the system
that produces a new trial configuration from the present one. Distance
$d(\vec{x}, \vec{x}^{'})$ between two states is then defined as the
minimum number of moves needed to turn one into other; and the
neighborhood of a given state $\vec{x}$ is the set of all states
$\vec{x}^{'}$ which can be reached from $\vec{x}$ with one move,
i.e. $d(\vec{x}, \vec{x}^{'}) = 1$.

\section{Techniques for Constraint-Directed Scheduling}
Christopher Beck, in his PhD thesis ~\cite{JCB} (ref: Beck-99),
discusses among other 
things, constraint-directed techniques that have been applied to
scheduling. These are heuristic commitment technigues, propagators,
and retraction techniques. In the discussion he uses the term {\it
  commitment} to refer to a decision made during search. It is
referred to or conceptualized as a constraint that is added to or
removed from the constraint graph. For example, assigning a start time
to an activity can be modeled as the assertion of a unary equals
commitment on the activity, while sequencing two activities can be
represented as the assertion of a binary precedence constraint between
the two activities.

\subsection{Heuristic Commitment Techniques}
A heuristic commitment technique is a procedure that finds new
commitments to be added to the graph in order to (heuristically) move
toward a solution. In traditional constraint-directed search (and,
indeed, artificial intelligence search more generally) heuristic
commitments are the primary component of a search for a solution. A
critical component of constraint-directed scheduling techniques,
therefore, is the technique used to generate and select the heuristic
commitments to make. We will be looking at a number of heuristics that
have been applied to constraint-directed scheduling.

\subsection{Intuitions on Heuristic Performance}
Here we present intuitions about the nature of heuristic commitment
techniques. These intuitions are speculative and their investigation
forms the basis of our future work on heuristics.

We believe that there are two characteristics that correlate highly
with the success of a heuristic commitment technique.

\begin{enumerate}
\item The Short dead-end Proof Intuition: the ability of a heuristic
  to quickly discover that the search is at a dead-end. Imagine a
  search that progresses through a series of states to state S. Assume
  that there are no solutions in the subtree below S, but that we are
  unable to prove this at state S. Some heuristic commitments must be
  made to explore  the subtree below S in order to prove that S is a
  dead-end. A heuristic that is able, through its heuristic
  commitments and subsequent propagation, to prove a dead-end while
  exploring a small number of states in the subtree will be superior
  to on that must explore a larger subtree.

\item The Few Mistakes Intuition: a high likelihood of making a
  commitment that leads to a solution. A heuristic that has a higher
  likelihood of making a commitment that leads to a solution, that is
  one that does not result in a dead-end, is likely to be a higher
  quality heuristic than one with a lower probability of making the
  correct decision.
\end{enumerate}
 
These two characteristics are independent from the perspective that if
either characteristic were infallible, search performance would be
independent of the other characteristic. If a heuristic never made a
commitment that resulted in a dead-end state, the ability to detect
such a state is irrelevant. Similarly, if a search could immediately
detect that it was a dead-end, then the quality of the commitments is
irrelevant: any mistake is immediately detected and repaired.

Withe real, fallible heuristics, these two characteristics interact:
it may be the case that a heuristic with a high probability of making
the right decision results in a relatively large effort in dicovering
when it has made a mistake. Conversely, a heuristic with a lower
probability of making a right decision may be able to find a shorter
proof of a dead-end (on average) and therefore recover from mistakes
quickly. The best heuristic will be the one that minimizes the size of
the overall search tree and this may well be achieved by some
trade-off between the two characteristics.

\section{Local Search}
Local search is meant to represent a large class of similar techniques 
that can be used to find a good solution from a problem. The idea is
to think of the solution space as being represented by an undirected
graph. That is, each possible solution is a node in the graph. An edge 
in the graph representd a possible move we can make between solutions.
For an optimization problem such as scheduling, even if we want to 
we could never hope of writing down the graph of the problem search
space.  

Therefore, the simple idea of local search is that we never actually
try to write the whole graph down; we just move from one possible
solution to a ``nearby'' possible solution, either for as long as we
like, or until we happen to find an optimal solution.

To set up a local search algorithm, we need to have the following:
\begin{enumerate}
\item A set of possible solutions, which will be the vertices in our
local search graph.
\item A notion of what the {\it neighbors} of each vertex in the graph 
are. For each vertex $x$, we will call the set of adjacent vertices
$N(x)$. The neighbors must satisfy several properties: $N(x)$ must be
easy to compute from $x$ (since if we try to move from $x$ we will
need to compute the neighbors), if $y \in N(x)$ then $x \in N(y)$ (so
it makes sense to represent neighbors as undirected edges), and $N(x)$ 
cannot be too big, or more than polynomial in the input size (so that
the neighbors of a node are easy to search through).
\item A cost function, from possible solutions to the real
numbers. For example, $f(s^*): {\cal R} \rightarrow {\cal R}$.
\end{enumerate}

The most basic local search algorithm (say to minimize the cost
function) is easily described:

\begin{enumerate}
\item Pick a starting point $x$.
\item While there is a neighbor $y$ of $x$ with $f(y) < f(x)$, move to 
it; that is, set $x$ to $y$ and continue.
\item Return the final solution.
\end{enumerate}

\subsection{The Reasoning Behind Local Search}
The idea behind local search is clear; if keep getting better and
better solutions, we should end up with a good one. Pictorially, if we 
``project'' the state space down to a two dimensional curve, we are
hoping that the picture has a sink, or a {\it global optimum}, and
that we will quickly move toward it. See Figure~\ref{local-search-1}.

%\vspace{0.1cm}
\begin{figure}[tbp]
\begin{center}
\begin{picture}(370,250)
\psfig{figure=state-space.eps,height=370pt,width=250pt,angle=-90}
\end{picture}
\end{center}
\caption{A very nice state space.}
\label{local-search-1}
\end{figure}

There are two possible problems with this of thinking. First, even if
the space does look this way, we might not move quickly enough toward
the right solution. Also, for any reasonably large scale optimization
problem, such as scheduling, if we start with a bad solution
(i.e. something with a very large cost), it will take a lot of moves
to reach the minimum. Generally, however, this is not much of a
problem, as long as the cost function is reasonably simple.

The more important problem is that the solution space might not look
at all the way as shown in Figure~\ref{local-search-1}. For example,
our cost function might not change smoothly when we move from a state
to its neighbor. Also, it may be that there are several {\it local
optima}, in which case our local search algorithm will hone in a local 
optimum and get stuck. See Figure~\ref{local-search-2}.

\begin{figure}[tbp]
\begin{center}
\begin{picture}(360,200)
\psfig{figure=local-optima.eps,height=360pt,width=200pt,angle=-90}
\end{picture}
\end{center}
\caption{A state space with many local optima; it will be hard to find 
the best solution. The global optimum ($x^*$) is at the dark circle,
while open circles represent local optima.}
\label{local-search-2}
\end{figure}

The second problem, that the solution space might not ``look nice'',
is crucial, and it underscore {\it the importance of setting up the
problem}. When we choose the possible moves between solutions --- that 
is, when we construct the mapping that gives us the neighborhood of
each node --- we are setting up how local search will behave,
including how the cost function will change between neighbors, and how 
many local optima there are. How well local search will work depends
tremendously on how smart one is in setting up the right
neighborhoods, so that the solution space really does look the way we
would like it to.

\subsection{Examples of Neighborhoods}
\begin{itemize}
\item Course Scheduling: A possible neighborhood structure is two
assignments of a set of classes to a set of rooms over a give set of
time slots, if the two assignments differ only in one class
assignments. That is in the first assignment, class (A) is assigned to 
room (B) and class (C) is assigned to room (D); while in the second
assignment, class (A) is assigned to room (D) and class (C) to room
(B).
\item MAX3SAT: A possible neighborhood structure is two truth
assignments are neighbors if they differ in only one variable. A more
extensive neighborhood could make two truth assignments neighbors if
they differ in at most two variables; this trades increased
flexibility for increase size in the neighborhood.
\item Traveling Salesperson: The K-opt neighborhood of $x$ is given by 
all tours that differ in at most $k$ edges from $x$. In practice,
using the 3-opt neighborhood seems to perform better than the 2-opt
neighborhood, and using 4-opt or larger increases the neighborhood
size to a point where it is inefficient.
\end{itemize}

\subsection{Considerations to keep in mind}

There are several aspects of local search algorithms that we can vary, 
and all can have an impact on performance.

For example:
\begin{enumerate}
\item What are the neighborhoods $N(x)$?
\item How do we choose an initial starting point?
\item How do we choose a neighbor $y$ to move to? (Do we take the
first one we find, a random neighbor that improves $f$, the neighbor
that improves $f$ the most, or do we use other criteria?)
\item What if there are ties?
\end{enumerate}

There are other practical things to consider. Can we re-run the
algorithm several times? Can we try several of the algorithms on
different machines? Issues like these can have a big impact on actual
performance. However, perhaps the most important issue is to think of
the right neighborhood structure to begin with; if this is right, then 
other issues are generally secondary, and if this is wrong, the
likelihood of success is not that great.

\subsection{Local Search Variations}
There are several approaches tthat ake advantage of search strategies
in which cost-deteriorating neighbors are accepted. In particular, we
mention {\it simulated annealing}, {\it tabu search}, {\it genetic
algorithms}, and {\it neural nets} (via mean field annealing).

In the descriptions of the local search methods which follow, we will
assume we are supplied with a function `FITNESS: $\sum \rightarrow R$'
which supplies us with the solution quality. Without loss of
generality, we assume higher fitnesses are better.

\begin{itemize}
\item {\bf Hill-climbing}: This is the name for the basic variation,
where one moves to a vertex of lower (or possibly equal) cost. See
Figure~\ref{HC-algorithm}.

\begin{figure}[tbp]
{\bf Hill Climbing} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a random solution $\sigma_{best} \in \Sigma$
\item repeat
\item $\;\;\;\;$Pick a random solution $\sigma \in \Sigma$
\item $\;\;\;\;$repeat
\item $\;\;\;\;\;\;\sigma$' $\leftarrow$ Perturbation($\sigma$)
\item $\;\;\;\;\;\;$ if FITNESS($\sigma$') $>$ FITNESS($\sigma$)
\item $\;\;\;\;\;\;$ then  $\sigma \leftarrow \sigma$'
\item $\;\;\;\;$until No fitter perturbations of $\sigma$ exist
\item $\;\;\;\;$if FITNESS($\sigma$) $>$ FITNESS($\sigma_{best}$)
\item $\;\;\;\;$then $\sigma_{best} \leftarrow \sigma$
\item until No time remains
\item return $\sigma_{best}$
\end{enumerate}
\end{center}
\caption{Hill Climbing Algorithm}
\label{HC-algorithm}
\end{figure}

This algorithm is called hill-climbing, because the inner loop (steps
4-8) move uphill (not necessarily in the steepest direction in the
basic algorithm) until a summit is reached. The outer loop (steps
2-11) mean that the algorithm tries to find further hills if given
enough time, and finally returns the highest peak it has visited when
time runs out (this algorithm is sometimes called `iterated hill
climbing' because of the existence of the outer loop).

To use this algorithm we obviously require that the perturbation
function be defined.

Whether hill-climbing works well as an optimization algorithm depends
upon the local\footnote{Local being defined by the perturbation
  operator, of course.} structure of the landscape --- if high points
in the landscape are surrounded by a smooth slopes leading away long
distances in the space, then any points picked on those slopes will
lead to the top of the hill. The set of all such points is known as
the `attracting set', or `capture basin' of the peak of the hill. If,
on the other hand, tall peaks are surrounded by great crevasses then
hill climbing will perform poorly. This image in terms of fitness
landscape is extremely important in trying to understand when and why
a particular algorithm will perform.

\item {\bf Motropolis rule}: Pick a random neighbor, and if the cost
is lower, move there. If the cost is higher, move there with some
probability (that is usually set to depend on the cost
differential). The idea is that possibly moving to a worse state helps 
avoid getting trapped at local minima.

\item {\bf Simulated annealing}: (see other chapters for more
details) This method is similar to the Metropolis rule, except that
the probability of going to a higher cost neighbor varies with time
and is gradually decreased in the course of the algorithm's
execution. Lowering the {\it acceptance probability} is controlled by
a set of parameters whose values are determined by a {\it cooling
schedule}. Like most local search algorithms, simulated annealing is
normally used as an approximation algorithm, for which much faster
convergence rates are acceptable (ref: Aarts and Korst-89a).

\item {\bf Tabu Search}: It combines the deterministic iterative
improvement algorithm with a possibility to accept cost-increasing
solutions. In this way the search is directed away from local minima,
such that other parts of the search space can be explored. The next
solution visited is always chosen to be a {\it legal neighbor} of the
current solution with the best cost, even if the cost is worse than
that of the current solution. The set of legal neighbors is restricted 
by a {\it tabu list} designed to prevent us going back to recently
visited solutions. The labu list is dynamically updated during the
execution of the algorithm. The tabu list defines solutions that are
not acceptable in the next few iterations. However, a solution on the
tabu list may be accepted if its quality is in some sense good enough, 
in which case it is said to attain a certain {\it aspiration
leve}. See Figure \ref{TS-algorithm}.

\begin{figure}[tbp]
\begin{center}
\begin{enumerate}
\item {\bf begin TABU}
\item $\;\;$select an initial solution $i \in S$;
\item $\;\;$initialize tabu list $T$ and aspiration function $A$;
\item $\;\;${\bf while} the {\it stopping condition is not met} {\bf do}
\item $\;\;\;\;$compute the best $i^{'}$ in $N(i)$
\item $\;\;\;\;\;\;$subject to tabu list $T$ and aspiration function $A$;
\item $\;\;\;\;$$i \leftarrow i^{'}$;
\item $\;\;\;\;$update tabu list $T$;
\item $\;\;\;\;$update aspiration function $A$;
\item $\;\;${\bf end while}
\item {\bf end TABU}
\end{enumerate}
\end{center}
\caption{Tabu search paradigm}
\label{TS-algorithm}
\end{figure}


\item {\bf Genetic algorithms}: (see Figure \ref{GA-algorithm})
This search strategy is based on a
theme borrowed from Holland's {\it genetic algorithms} approach. (ref: 
Holland-75, Goldberg-89). Holland uses concepts from population
genetics and evolution theory to construct algorithms that try to
optimize the {\it fitness} of a {\it population} of elements through
{\it recombination} and {\it mutation} of their genes. There are many
variations known in the literature of algorithms that follow these
concepts. One example is {\it genetic local search}. The general idea
is as follow:
\begin{itemize}
\item Step 1, {\it initialize}. Construct an initial population of $n$ 
solutions.
\item Step 2, {\it improve}. Use local search to replace the $n$
solutions in the population by $n$ local optima.
\item Step 3, {\it recombine}. Augment the population by adding $m$
offspring solutions; the population size now equals $n+m$.
\item Step 4, {\it improve}. Use local search to replace the $m$
offspring solutions by $m$ local optima.
\item Step 5, {\it select}. Reduce the population to its original size 
by selecting $n$ solutions from the current population.
\item Step 6, {\it evolute}. Repeat Step 3 through 5 until a stop
criterion is satisfied.
\end{itemize}
Evidently, {\it recombination} is an important step, since here one
must try to take advantage of the fact that more than local optimum is 
available, i.e., one most exploit the structure present in the
available local optima.

\begin{figure}[tbp]
{\bf Genetic Algorithm} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a population $P = \{\sigma_1,\ldots,\sigma_n\}$ drawn
  randomly from $\Sigma$
\item repeat
\item $\;\;\;\;$Form a selection:
\item $\;\;\;\;\;$ $S \leftarrow$ Selection($P$, Fitness())
\item $\;\;\;\;$$P \leftarrow \emptyset$
\item $\;\;\;\;$repeat
\item $\;\;\;\;\;\;$Pick a pair $\sigma_a$,$\sigma_b$ from $S$
\item $\;\;\;\;\;\;$Form the offspring:
\item $\;\;\;\;\;\;\;\;$ $\sigma_{ab,1}$,$\sigma_{ab,2}$ $\leftarrow$
  Crossover($\sigma_{a}$,$\sigma_{b}$)
\item $\;\;\;\;\;\;$ $P \leftarrow P \cup
  \{\sigma_{ab,1}$,$\sigma_{ab,2}\}$
\item $\;\;\;\;$until Population is full: $|P| = n$
\item until $P \approx$ converged to a single solution
\item return $\sigma =$ arg $max_{\sigma \in \Sigma}$
  $\{$Fitness($\sigma$)$\}$
\end{enumerate}
\end{center}
\caption{Genetic Algorithm}
\label{GA-algorithm}
\end{figure}

\item {\it Artificial Neural networks}: Consist of networks of
elementary nodes (neurons) that are linked through weighted
connections. The nodes represent computational units, which are
capable of performing a simple computation, consisting of a summation
of the weighted inputs, followed by the addition of a constant called
the threshold or bias, and the application of a nonlinear response
function. The result of the computation of a unit constitutes its
output. This output is used as an input for the nodes to which it is
linked through an outgoing connection. The overall task of the network
is to achieve a certain network configuration, for instance a required
input-output relation, by means of the collective computation of the
nodes. This process is often called {\it self-organization}. Over the
years a large variety of neural network models have been proposed,
which differ in the net architecture and the computational model used
for self-organization. In many models, the self-organization of the 
network tries to find a stable network configuration. For models such
as the {\it Hopfield network} or the {\it Boltzmann machine}, the
self-organization can be modeled in terms of local search. Here the
issue of escaping from local optima is again of prime importance. In a 
a number of cases it is resolved by applying probabilistic methods, as 
in simulated annealing. This takes to the mean field annealing model
outlined in another chapter.

\item {\it Random Search}:
If we don't have enough time to search all possible solutions, we
could just generate solutions randomly for the length of time
available, and retain the best one as our result. We formalize this as
follows(see Figure \ref{RS-algorithm}):

\begin{figure}[tbp]
{\bf Random Search} ($\Sigma$)
\begin{center}
\begin{enumerate}
\item Pick a random solution $\sigma \in \Sigma$
\item {\bf repeat}
\item $\;\;\;\;$Pick a random solution $\sigma$' $\in \Sigma$
\item $\;\;\;\;$If FITNESS($\sigma$') $>$ FITNESS($\sigma$)
\item $\;\;\;\;\;\;$then $\sigma \leftarrow \sigma$'
\item until No time remains
\item return $\sigma$
\end{enumerate}
\end{center}
\caption{Random Search Algorithm}
\label{RS-algorithm}
\end{figure}

It is quite clear that unless good solutions are pretty dense in the
search space, a random search will almost always not perform
well. However, another use of random search is as a benchmark --- a
standard level from which to compare other algorithms and with which
to produce a very simple measure of how difficult a problem is (such
comparisons will never be ideal, however, for at least the reason that
different computer architectures and compilers may have different
levels of performance across different types of computer code).

Choices for termination condition in the random search include time or
solution quality. However since we cannot expect solutions of very
good quality, the only practical condition is on the allowable search
time.

\end{itemize}

It is not at all clear on which problem classes these algorithms are
expected to perform well. If we are presented with a new problem
demanding a solution we would like to be able to know a priori which
of these algorithms is expected to perform best. To do this, we need a
formal interpretation of their dynamics, motion in search space and
convergence properties. From these we can derive a set of tests or
summary of inherent advantages and disadvantages which will let to
pick the best algorithm for a given purpose. Given that our search
problem is difficult, it is unlikely that a first guess approach will
yield sufficiently good answers (for whatever purpose we had in mind),
so we cannot be happy with that status quo. Somehow the structure of
the search space (the almost infinite set of possible perturbation
operators and the generated fitness landscapes) is is vital in
dictating how the space should be searched efficiently.

In more direct terms, we must think about a process for generating or
transforming solutions in a manner which we intuitively feel takes
into account the deep structure of the problem. In short, without an
understanding of the manner in which optimization algorithms operate,
for every new case we need to invent a new heuristic, or rule of
thumb, which seems particularly relevant. Clearly, this poses great
difficulties for the unfortunate algorithm designer.
