Local search

Gradient search
Simulated annealing
A*
Tabu search
Genetic algorithms
Acknowledgement
Many of the presentations of this lecture are excerpted from the lecture note by Boonserm Kijsirikul from his "AI2" lecture (with his permission).

In this lecture we explore several popular search techniques.  Most of this techniques are used extensively in artificial intelligence research.  We will show the overview of search technique according to AI work as follows:

search
  blind search
    exhausive search
    partial search
      bread-first search
      depth-first search
  heuristic search
    best-first search
    A*
    minimax
    beam search
    hill-climbing search
    simulated annealing

Many of these methods can be regarded as the search in graph, where a graph represented the problem space (called state space in AI lingua ). We also discuss two advanced techniques: Tabu search and Genetic algorithms.

Gradient search (Hill climbing)

The easiest way to explain this technique is to consider an optimization problem.  In an optimization problem, there is an "objective function" and "constraints", where the objective function is the function we want to maximize or minimize its value subject to the constraints.  Minimization and maximization is a dual problem, min f is max or -f.  Visualise an graph where the axis x is the value of parameter(s) we want to find and the axis y is f(x) where f(x) is the objective function.  Gradient search is the search that uses the information about the slope of this f(x) as the guide to decide which direction to adjust the value x (such that min f(x) ).

  x_i+1  =  x_i + del(x)

del(x) is determined by f'(x)  (slope of f).  The magnitude (step size of adjustment) affects the speed of convergence (how fast it is to find the correct answer).  The step size is also adjustable during the iteration of the search algorithm.  This is similar to "climb the hill".  A simple and well-known gradient search method is called "steepest descent" (follows the direction that gives the most improvement).  This is comparable to the greedy method.

If f(x) contains only one peak, climbing the hill to the top is easy (even with multi parameters).  However if f(x) contains many small peaks, the simple search procedure can be trapped at the "local minima" because at the local minima to proceed further the search procedure will have to pass through the period that the cost is "increasing".  The simple gradient search do not have this ability.

algorithm
hill-climbing
1  evaluate initial state
   if initial state = goal state
   then stop
   else current state = initial state
2  do until find goal state or there is no operator to change the current state
   2.1  choose an operator which has not been used with the current state to produce a new state
   2.2  evaluate the new state
        if the new state = goal state
        then stop
        else
          if the cost of the new state is better
          then current state = new state
          else continue

Simulated Annealing

To escape from the local minima we need a way to "jump" out of it.  Simulated annealing offers a systematic to perform this "jump".  Simuted annealing imitates the annealing in physics where the melting of a solid starts from a high temperature and then cooling, lowering the temperature, eventually ends in  a final state where the total energy is minimum.

Let p denotes a probability to change state, del(E) an energy level (positive), T the temperature and k a constant.

  p = exp( -del(E)/kT )

When T is lower, p is also smaller.  We use del(E) as the change of objective function and T is called the annealing schedule.

algorithm
simulated-annealing
1  evaluate initial state
   if initial state = goal state
   then stop
   else current state = initial state
2  best-so-far = current state
3  T = constant
4  do until find the solution or there is no operator to change the current state
   4.1  choose an operator that has not been used with the current state to produce a new state
   4.2  evaluate the new state
        delE = cost of current state - cost of new state
        if new state = goal state
        then stop
        else
          if cost of new state is better than cost of current state
          then  current state = new state
                update best-so-far
          else  assign new state to current state with probability p
                ( if p > random(0..1) then current state = new state)
   4.3  change T
5 return best-so-far

How to determine the annealing schedule?  (how to adjust T).  When T = 0 it is similar to a simple hill climbing.

A* (pronounce A-star)

In some problem, we can separate the cost function (heuristic function) into two parts:

  f'(s) = g(s) + h'(s)

where g is the cost from initial state to current state
      h' is the estimate of cost from current state to goal state
f' then is the estimate cost from initial state to goal state.

An important property of h' is that if it is underestimate the true cost then it is guarantee that the path from initial state to goal state will be optimal.

Tabu search

Tabu search is based on the concept of "intelligent" search.  It used a form of memory to remember previous search points and prohibited re-searching in that set. It has
1)  Adaptive memory -- it memorises some information during search.  This improves the efficiency.
2)  Responsive exploration -- it searches some not-so-good path which sometimes gains more information than searching only good path.

Two kinds of memory are used: recency-based memory and frequency-based memory.  The memory is designated as short-term and long-term respectively.  How the memory is used?  Consider the following hill-climbing algorithm:

problem
  find x that min f(x), N(x) denotes neighborhood of x in the search space X.

hill-climbing
1  choose x in X to start the process.
2  find x' in N(x) such that f(x') < f(x)
3  if no such x' can be found, x is the local minimum and the method stops.
4  otherwise, designate x' to be the new x and goto 2

For tabu search the memory is used to determine N(x).  Let N*(x) be the new neighborhood.   The memory is used as follows:

Short term memory

  N*(x) is subset of N(x)
  the tabu status is used to eliminate some member of N(x) -> N*(x)
  characteristic of previous solutions are designate as "tabu-active" to prevent searching the future solution with the same characteristic.
  "aspiration criteria" is used to switch "tabu-active" to non-active when it is found that the previous solution is better.
  N*(x) changes for every search step

Long term memory

  N*(x) may be superset of N(x)
  long term memory is used to restart the search (once the search by short term memory get stuck)
  long term memory determined the new starting point

This is rather difficult if you don't see any example.  The detailed example can be found in Ajarn Boonserm Kijsirikul's lecture note in AI2.

algorithm
tabu-search
choose an initial solution x in X
x* = x, k = 1
initialize tabu short-term memory and long-term memory
while the stopping condition is not met do
  k = k + 1
  generate a candidate set N*(x) including x' with tabu-active
     which satisfies aspiration criteria
  find a best x' in N*(x)
  if local optimum reached then
    if no improvement made over a period then
      apply long term memory to restart the process and find a new x'
  x = x'
  update tabu memory and adjust search parameters
  if f(x') < f(x*) then x* = x'
end

Genetic algorithms  (GA)

Genetic algorithms are a class of algorithms inspired by natural evolution.  GA  is based on a population of candidates (as opposed to other method which is based on one point search and improve that point).  Initially the solution is randomly generated and they are improved by genetic operations.  A solution is encoded as a fixed length string.  The most popular form is the string of {0,1}.  The genetic operators are :  reproduction, crossover (recombination) and mutation. Reproduction selects the good solutions and copies them to the next generation.  Crossover combines solutions from two good parents. Mutation introduces new solution into the population by randomly change some parts of the solution. This produces a new population which the quality of solution is improved.  Selection of the parents is based on their "fitness".  The fitness of the solution measures its quality.  This is determined by the problem.

GA is a weak search method (as opposed to other method which is strong).  It is good for many class of problems but not specifically tuned to be excellent for a single problem.

algorithm
genetic-algorithm
  initialise a population P
  measure the fitness of P
  while termination condition is not met
    reproduce P -> P'
    crossover P -> P'
    mutate P -> P'
    measure the fitness of P'
    P = P'
end

One descendant of GA is Genetic Programming (GP) in which the solution is represented as a tree instead of a fixed length string.  This enables a more flexible representation such as:  a tree can be a "program" that compute the solution, a tree can be a "symbolic expression" that express the solution.

You can read more about GA and GP at my website  and  my publication list.   I do research mostly in this area.