\section{Local Search}
Idea: keep a single “current” state, and try to improve it.  Move
only to neighbors of that node.
Advantages:
\begin{itemize}
  \item No need to maintain a search tree.
  \item Use very little memory.
  \item Can often find good enough solutions in continuous or large
state spaces.
\end{itemize}
\subsection{Hill climbing (greedy local search)}
\begin{itemize}
  \item Looks only to immediate good neighbors and not beyond.
  \item Search moves uphill: moves in the direction of increasing elevation/value to find the top of the mountain.
  \item Terminates when it reaches a pick.
  \item Can terminate with a local maximum, global maximum or can get stuck and no progress is possible.
  \item A node is a state and a value.
\end{itemize}
\paragraph{Variants}
\begin{itemize}
  \item Sideways moves: escape from plateaux where best successor
    has same value as the current state
  \item Random-restart: overcomes local maxima,
    either find a goal or get several possible solution
    and pick the max
  \item Stochastic hill climbing chooses at random among the
    uphill moves.
\end{itemize}
\subsection{Local Beam Search}
\begin{itemize}
  \item Maintains $k$ states instead of one state.
  \item Select the $k$ best successor, and useful information is
    passed among the states.
\end{itemize}
\paragraph{Stochastic beam search}
\begin{itemize}
  \item Choose $k$ successors are random.
  \item Helps alleviate the problem of the the states
    agglomerating around the same part of the state space
\end{itemize}
\subsection{Genetic algorithms}
\begin{itemize}
  \item A variant of stochastic beam search.
  \item Successor states are generated by combining two parents
    rather by modifying a single state.
  \item Starts with $k$ randomly generated states, called
    \textbf{population}. Each state is an \textbf{individual}.
  \item The objective function is called \textbf{fitness
    function}
  \item Better states have high values of fitness function
\end{itemize}
\paragraph{Implementation}
\begin{itemize}
  \item Pairs of individuals are selected at random for
    reproduction w.r.t. some probabilities.
  \item A \textbf{crossover point} is chosen randomly in the string.
  \item Offspring are created by crossing the parents at the
    crossover point.
  \item Each element in the string is also subject to some
    \textbf{mutation} with a small probability.
\end{itemize}