The most widely used metaheuristic techniques are
\begin{itemize} \itemsep -14pt
\item gradient based techniques (\tion{gradBased})
\item evolutionary algorithms (\tion{ea})
\item tabu search (\tion{tabu})
\end{itemize}
These three techniques will be discussed in this section.
First some 
basic terminology used to describe 
the characteristics of different techniques
will be discussed.
Then the particulars of the techniques will be discussed.



\subsection{Introduction and Terminology}\label{sect:metaIntro}
Metaheuristic techniques are a set of high-level search
techniques that are used on problems that have input spaces
too large for a complete search.
The underlying assumption of these techniques is 
that although there is no guarantee they will find the
optimal solution, finding a near-optimal solution
is better than never finding the optimal solution.
Again, it is assumed that near-optimal solutions exist.


The two key components of a metaheuristic technique are
\begin{enumerate} \itemsep -14pt
\item objective function evaluation
\item new solution(s) generation
\end{enumerate}
These two steps can be thought of as 
1) where the search is and
2) where the search should go.
The objective function is used to measure the value of the 
candidate solution(s).  This function has to decode the 
candidate solution(s) and evaluate its desirability.
Using that information the technique then forms
its next generation candidate solution.
This next generation may or may not be an improvement
in terms of the objective function.
These two steps are alternated until some stopping condition is
reached.
The pseudocode in \fig{metaPseudo} describes, at a very abstract level,
how metaheuristic search techniques work.

\begin{figure}
\begin{algorithmic}[1]
\STATE generate initial candidate solution(s)
\REPEAT
\STATE evaluate candidate solution(s) \label{line:eval} 
\STATE generate new candidate solution(s) 
\STATE move to new solution(s) or keep old one(s) 
\UNTIL{stopping condition is reached}
\STATE report best candidate solution found
\end{algorithmic}
\caption{Metaheuristic pseudocode}
\label{fig:metaPseudo}
\end{figure}

There are several ways to describe the characteristics
of these techniques.
Some of the more important characteristics are
\begin{itemize} \itemsep -14pt
\item is the search local or global?
\item how is the neighborhood determined?
\item what type of solution encoding is needed?
\item how are exploration and exploitation balanced?
\item how robust is the technique is the presence of numerous local optima?
\end{itemize}
A search technique can be local or global, depending on
whether only solutions close to the current
solution are considered when new candidate solutions
are generated.
The neighborhood is the set of solutions that are
considered before a move is made.
How this set is determined may not be obvious.
Higher dimensionality functions will have larger neighborhoods,
since the current solution can move in many directions.
This may require restricting in which directions
the current solution can be modified when constructing its neighborhood.
Mixed typed or mixed unit inputs may require domain knowledge
to decide how great a change in one direction is equal to
a change in another direction.
The candidate solutions need to be encoded in a way
that the neighborhood operators can work on
and the objective function can efficiently evaluate.
Every search has to balance exploration and exploitation.
A search {\it explores} when it evaluates candidate solutions
from  portions of input space it hasn't visited before.
But the search must also investigate regions of the input
space where it has found promising solutions.
This is called {\it exploiting}.
If a technique sends too much time exploiting previously
visited regions of the input space, it may get stuck
in a local optimum.
But if a search never exploits known locations of promising
candidate solutions, solution quality may suffer.
A metaheuristic search technique has to balance when it
explores new regions of the input space and when it exploits
knowledge it has already learned.
Regardless of how exploration and exploitation are balanced,
since all metaheuristic search techniques are incomplete,
they may still get stuck in local optima.
Because of this each technique should have some method for
escaping from local optima.


\subsection{Gradient Based Techniques}\label{sect:gradBased}
In mathematics the gradient operator ($ \triangledown $)
can be used to find the direction of greatest
change for a multivariate function whose
partial derivatives exist.
When optimizing analytic functions the gradient
can often be calculated analytically.
For problem domains where the gradient can not be
calculated analytically, it must be done numerically.
By evaluating the objective function at points in
the neighborhood of the current candidate solution, 
an estimation of the gradient can be calculated.
As discussed in \tion{metaIntro},
how to generate this neighborhood is not always obvious
and often requires some domain knowledge.



\paragraph{Hill climbing}
The simplest gradient based technique is hill climbing.
A hill climber investigates the area around its current
position and moves the candidate solution to a neighbor
with a better score.
There are several variants of the hill climber.
The climber can move to the first candidate it finds that is better
than the current solution.  This is called 
{\it first-ascent} hill climbing.
The climber could alternatively investigate its entire neighborhood
and move the solution to the best neighbor it finds.
This is called {\it steepest-ascent} hill climbing.
Hill climbers terminate when they can not find a neighbor
that has a better score than the current candidate solution.
This means that the current solution is a local optimum.

Since gradient based techniques are not guaranteed to find global optima, 
methods that use hill climbers often do multiple restarts.
After a local optimum is found, 
the hill climber is restarted from a new random starting point.
Using restarts usually leads to the finding of a different
optimum, increasing the likelihood that a high
quality near-optimal solution is found.
Of course this still does not guarantee finding the global
optimum.

\paragraph{Simulated annealing}
Simulated annealing (SA) \cite{kirkpatrick83,cerny85}
is a local search algorithm very similar
to hill climbing, with one important difference.
SAs will probabilistically make a move that does not improve
the objective function according to the
Boltzmann factor $e^{-(\triangledown E/T)}$, 
where $T$ is the {\it temperature} and
$\triangledown E$ is the change in the objective function.
Note that $e^{-(\triangledown E/T)} \rightarrow 0$ as
$T \rightarrow 0$, i. e. SAs converge to hill climbers
in the limit $T \rightarrow 0$.
Also note that
$e^{-(\triangledown E/T)} \rightarrow 0$ as
$\triangledown E \rightarrow \infty$,
i. e. the worse the move, the lower
the probability it will be taken.
\fig{SA} shows a how a search might
proceed in a 2-D example, if a simulated annealer was used.

\begin{figure}
\centering
\includegraphics[height=2.2in]{Figures/annealling}
\caption{Typical simulated annealer}\label{fig:SA}
\end{figure}

The cooling schedule (how the temperature changes during the search)
is the way that SAs control the trade-off between
exploration and exploitation.
At the start of an SA run, when the temperature is high,
the technique makes many bad moves and explores the search space.
But as the temperature is lowered, the technique makes fewer
and fewer bad moves and exploits what was learned 
(the possible location of a promising local optimum)
during the exploring phase.
Hence the benefit of allowing the SA to make bad moves is 
that these bad moves increase the amount of exploring done and
decrease the likelihood of the search getting stuck in low quality
local optima.  
As with restarting hill climbers, this technique can not
guarantee that the global optimum will be found.


\subsection{Evolutionary Algorithms}\label{sect:ea}
Evolutionary algorithms (EA) are inspired by Darwinian evolution
developed in biology.  
The key parts of evolutionary algorithms are
\begin{itemize} \itemsep -14pt
\item the population of candidate solutions
\item the candidate solutions are scored, based on how well they solve the problem
\item the candidate solutions are changed some to explore new possible solutions
\end{itemize}
Since more than one candidate solution is being considered,
evolutionary algorithms are non-local techniques.
Candidate solutions in EAs are encoded as 
{\it chromosomes}.
These chromosomes are usually bit vectors,
where each bit represents a single attribute of the solution.
Typically the chromosomes are fixed length,
but Whitley \etal \cite{whitley97messy} has
explored encoding master genes.
These master genes can turn off other genes,
so that while the chromosome stays a constant
length during the search, the information
expressed changes depending on how these
master genes are mutated during the search.
Exploitation and exploration are balanced
by the values of the mutation operators.
If mutation events are very common,
the search performs more exploration,
since the mutations push the search into new regions
of the search space.
If mutation events are not common,
the search performs more exploitation,
as the search stays in same region of the
search space.
An EA may have static mutation rates that don't change
during the search,
although it is common to find experimentation
with adaptive mutation rates \cite{chen98,zhang05}.
The two most common EAs are genetic algorithms (GAs)
and genetic programming (GPs).  
They will be discussed in the following section.
In addition Evolutionary Programming \cite{fogel66}
has been developed, but it will not be discussed here.


\subsubsection{Genetic Algorithms and Genetic Programming}
The following steps compose one {\it generation} in a 
genetic algorithm \cite{holland75,goldberg00}
\begin{enumerate} \itemsep +4pt
\item evaluate the individuals to determine their fitness score
\item construct a new intermediate population based on those fitness scores
\setstretch{1.3}
\item construct the next generation by using mutator operators on the intermediate population
\end{enumerate}
The evaluation of the individuals is done by the objective function
(usually called the fitness function by GA practitioners).
This function must be called once for every individual in the
population, every generation, hence it must be only modestly
computational intensive.

Their are several ways that the intermediate population can be constructed,
including proportional selection 
(also known as roulette wheel selection), 
stochastic universal sampling, and tournament selection.
Each of these selection methods has been studied to determine
some their characteristics.  
For example tournament selection was studied by Miller and Goldberg 
\cite{miller95genetic}, who investigated the relationship between 
selection pressure, tournament size, and noisy objective functions,
while stochastic universal sampling was studied by Baker
\cite{baker-1987a}, who demonstrated that this method was unbiased.

The two mutation operators used are the point mutation operator
and the crossover operator.
The point mutation operator works by probabilistically 
flipping individual bits among the chromosome population.  
An individual may have 0 or more bits
flipped by the point mutation operator.
A pictorial representation of the point mutation operator is shown
in \fig{pointmutation}.
The crossover operator works by probabilistically exchanging
information between two individuals in the population.
There are several versions of the crossover operator, including
the one-point, the two-point, and the uniform.
The one-point operator selects a single location along
the chromosome and exchanges the portion of the chromosome
after that point from one individual
with the corresponding portion from another individual.
The two-point operator selects two locations along the
chromosome and swaps the information between
those two points between two individuals.
The uniform operator probabilistically swaps each
gene along the chromosome.
A pictorial representation of a one-point crossover operator is shown
in \fig{GAcross}.

\begin{figure}
\centering
\includegraphics[width=3.6in]{Figures/point-mutation}
\caption{Example of a point mutation\cite{ryan00}}\label{fig:pointmutation}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=3.6in]{Figures/crossover}
\caption{Example of a one-point crossover event\cite{ryan00}}\label{fig:GAcross}
\end{figure}

There is also research on the topic of encoding schemes.
Natural encoding has been advocated \cite{michalewicz96}
since that eliminates the need to encode and decode the individuals
before scoring them, 
but new mutation and cross-over operators need to be developed
for each new problem.
Runtime speed ups have also been been reported with natural representation
\cite{michalewicz91}. 
The topic of encoding schemes will be revisited in \tion{rethinking}.


Genetic programming \cite{koza92,negnevitsky02}
is similar to genetic algorithms, except
that the representation being ``evolved''
is a computer program.
To ensure that all mutations are still valid programs,
the representation chosen is often an abstract syntax tree.
Since this representation is so different from the typical
representation used in GA,
specialized mutation operators have to be used.
For example, a crossover event in a GP search might
look like \fig{astcross}.
Besides specialized mutation operators, 
GPs use the same three basic steps discussed at
the start of this section.


\begin{figure}
\centering
\includegraphics[width=3.6in]{Figures/AST-crossover}
\caption{Example of crossover event in genetic programming \cite{ryan00}}\label{fig:astcross}
\end{figure}



\subsection{Tabu Search}\label{sect:tabu}

%With most complete search methods, such as depth first or branch and 
%bound, a (partial) history is retained in memory.
%This memory is used to 
%prevent revisiting old solutions.
%While every solution visited is not usually kept in 
%memory, the completeness requirements of these techniques
%restricts the ways in which this memory is added to and
%utilized.

Tabu search \cite{glover86,glover93tabu}
(a type of adaptive memory programming, or AMP) 
attempts to use memory in a flexible fashion,
without recording the exact history of the search.  
Like SA, tabu search is a local algorithm.
However, its neighborhood depends on previous moves.  
After each move is made a {\em tabu list} is updated based on
the move.  The list may contain the exact move, or it may 
contain certain attributes of the move.  
Members of this list have some form of tenure, 
so that they are eventually evicted from the list.
This makes tabu search more scalable to large problems,
since it does not attempt to store a complete history
of its progress.
In addition, multiple tabu lists might be maintained.
For example, when solving the {\it minimum k-tree} problem
\cite{lokketangen94}
it is useful to maintain a separate list for edges 
that are dropped from the current solution and 
for edges that are added to the current solution.
When constructing future neighborhoods,
moves that match a move on the list (or share an attribute that is
on the list) are not considered.  
That is, tabu tries to explore
regions of the space that it has not visited previously.
It is left to the practitioner to decide if a move
should be considered tabu if it has any attributes
that are in the tabu list or whether it must have
several (or all) attributes on the tabu list to
be considered tabu.
Similarly, when maintaining multiple tabu lists, 
a move may be considered tabu if it has attributes
on any of the lists, or if
a move can be considered tabu only if its attributes are on 
several (or all) of the tabu lists.


%A final consideration when determining if a move is tabu
%are {\it aspiration criteria}.
%A move that is considered tabu due to the tabu list(s),
%may still be allowed if it passes some aspriation criterion.
%An obvious criterion could be, if the objective score increases
%due to a tabu move, allow that move.
%{\it There is no reason the aspriation criteria has to relate to
%the objective score though.}

The time each move (or attribute) remains on a tabu list
is called its {\it tabu tenure}.  
This value of this tenure can be very flexible.
If multiple lists are being maintained, each list can have
a different tenure.
The tenure for the different lists can be static or dynamic.
The value of the tenure is the main
way tabu search balances exploration with exploitation.
Longer tenures forces tabu search to explore more
the of the search space, as large parts will 
be considered tabu.
Shorter tenures increases exploitation, allowing the
technique to stay in a smaller part of the search space
(without necessarily requiring it).
For this reason, the tabu tenure may be a monotonically
decreasing function, making it similar to the
cooling schedule in SAs.
This results in more exploration at the beginning of the search,
with more exploitation as the tabu tenure decreases.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../thesis"
%%% End: 
