LOCAL SEARCH ALGORITHM
Overview:
⚫ In many optimization problems, the path to the goal is
irrelevant; the goal state itself is the solution
⚫ For example, in the 8-queens problem, what matters is the final
configuration of queens, not the order in which they are added.
⚫ In such cases, we can use local search algorithms. They
operate using a single current state (rather than multiple
paths) and generally move only to neighbors of that state.
Applications:
⚫ The important applications of these class of problems are:
(a) integrated-circuit design,
(b)Factory-floor layout,
(c) job-shop scheduling,
(d)automatic programming,
(e)telecommunications network optimization,
(f)Vehicle routing, and
(g) portfolio management.
Key Advantages:
(1) They use very little memory – usually a constant
amount; and
(2) They can often find reasonable solutions in large or
infinite (continuous) state spaces for which systematic
algorithms are unsuitable.
HILL CLIMBING ALGORITHM
Overview:
⚫ Hill climbing is called discrete optimization algorithm. It
uses a simple heuristic function i,e. the amount of
distance the node is from goal.
⚫ The ordering of choice is a heuristic measure of the
remaining distance.
⚫ Hill climbing algorithm typically choices randomly among
the set of best successor if there is more than one.
Overview:
⚫ Hill-climbing is sometimes called greedy local search
because it grabs a good neighbor state without thinking
ahead about where to go next. Greedy algorithms often
perform quite well.
⚫ Example: When listening to someone playing flute, on the
transistor, tone and volume control are adjusted in a way
that makes the music melodious.
Hill Climbing – Algorithm:
⚫ The hill-climbing search algorithm as shown is simply a
loop that continually moves in the direction of increasing
value – that is, uphill.
⚫ It terminates when it reaches a “peak” where no neighbor
has a higher value.
Algorithm:
⚫ Function HILL-CLIMBING(Problem) returns a solution state
⚫ Inputs:Problem, problem
⚫ Local variables:Current, a node
⚫ Next, a node
⚫ Current = MAKE-NODE(INITIAL-STATE[Problem])
⚫ Loop do
⚫ Next = a highest-valued successor of Current
⚫ If VALUE[Next] < VALUE[Current] then return Current
⚫ Current = Next
⚫ End
Algorithm:
[Link] the initial node on the list start.
[Link] the list is empty or start=goal ,terminate the search
[Link] the first node from start and call node a
4. If a=goal, Terminate the search with success
[Link] if node has successors, generate all of them, find out how
far they are from the goal node. Sort them by examining
distance from the goal and put them to the beginning of start.
[Link] to step 2.
Problems with Hill Climbing:
⚫ Sometimes this procedure may lead to a position, which is
not a solution, but from which there is no move that
improves things.
⚫ This will happen if we have reached one of the following
three states.
States:
Problem 1: Foothills
⚫ A "local maximum” which is a state better than all its
neighbors, but is not better than some other states
farther away. Local maxim sometimes occurs within
sight of a solution. In such cases they are called
“Foothills".
⚫ Local maximum can be solved by backtrack to some
earlier state and go in a different direction.
Problem 2: Plateau
⚫ A "plateau'' which is a flat area of the search space, in
which neighboring states have the same value. On a
plateau, it is not possible to determine the best
direction in which to move by making local
comparisons.
⚫ Make a big jump in some direction to try to get to a
new section of search space.
Problem 3: Ridge
⚫ A "ridge" which is an area in the search that is higher
than the surrounding areas, and that itself has a slope,
but cannot be searched in a single move.
⚫ Apply two or more moves before doing the test. This
corresponds to moving in several directions at once.
REMEDIES
Random-restart hill-climbing:
⚫ is a variant in which reaching a local maximum causes the
current state to be saved and the search restarted from a
random point.
⚫ After several restarts, return the best state found. With
enough restarts, this method will find the optimal solution.
Gradient descent
⚫ It is an inverted version of hill-climbing in which better
states are represented by lower cost values.
⚫ Local minima cause problems instead of local maxima.
STIMULATED ANNEALING
Hill
⚫ Hill climbing suffers from the problem of getting stucked
at local maxima/minima .We try to overcome this problem
by
⚫ We could try a hill climbing algo using different start points.
⚫ We could increase the size of neighborhood so that we can
consider more of search space at each node.
⚫
Simulated Annealing: Basic Idea
⚫ From current state, pick a random successor state;
⚫ If it has better value than current state, then “accept the
transition,” that is, use successor state as current state;
⚫ Otherwise, do not give up, but instead flip a coin and accept the
transition with a given probability (that is lower as the successor is
worse).
⚫ So we accept to sometimes “un-optimize” the value function a
little with a non-zero probability.
⚫ Instead of restarting from a random point, we can allow the
search to take some downhill steps to try to escape local
maxima.
⚫ Probability of downward steps is controlled by temperature
parameter.
⚫ High temperature implies high chance of trying locally "bad"
moves, allowing nondeterministic exploration.
⚫ Low temperature makes search more deterministic (like
hill-climbing).
⚫ Temperature begins high and gradually decreases according to
a predetermined annealing schedule.
⚫ Initially we are willing to try out lots of possible paths, but over time
we gradually settle in on the most promising path.
⚫ If temperature is lowered slowly enough, an optimal solution will be
found.
⚫ In practice, this schedule is often too slow and we have to accept
suboptimal solutions.
Algorithm:
Figure The simulated annealing search algorithm, A version of stochastic hill climbing where some downhill
moves are allowed.
Application:
⚫ Basic Problems
⚫ Traveling salesman
⚫ Graph partitioning
⚫ Matching problems
⚫ Graph coloring
⚫ Scheduling
Application:
⚫ Engineering
⚫ VLSI design
⚫ Placement
⚫ Routing
⚫ Array logic minimization
⚫ Layout
⚫ Facilities layout
⚫ Image processing
⚫ Code design in information theory