Gradient searchAcknowledgement
Simulated annealing
A*
Tabu search
Genetic algorithms
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.
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
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.
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.
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:
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
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.