Nibba group: Local Search Algorithms

Local Search Algorithms

They start from a prospective solution and then move to a neighboring solution. They can return a valid solution even if it is interrupted at any time before they end.
Hill-Climbing Search It is an iterative algorithm that starts with an arbitrary solution to a problem and attempts to find a better solution by changing a single element of the solution incrementally. If the change produces a better solution, an incremental change is taken as a new solution. This process is repeated until there are no further improvements.
function Hill-Climbing (problem), returns a state that is a local maximum.
inputs: problem, a problem
local variables: current, a node
neighbor, a node
current ←Make_Node(Initial-State[problem])
loop
do neighbor ← a highest_valued successor of current
if Value[neighbor] ≤ Value[current] then
return State[current]
current ← neighbor
end
Disadvantage: This algorithm is neither complete, nor optimal.

Local Beam Search

In this algorithm, it holds k number of states at any given time. At the start, these states are generated randomly. The successors of these k states are computed with the help of objective function. If any of these successors is the maximum value of the objective function, then the algorithm stops.
Otherwise the (initial k states and k number of successors of the states = 2k) states are placed in a pool. The pool is then sorted numerically. The highest k states are selected as new initial states. This process continues until a maximum value is reached.
function BeamSearch( problem, k), returns a solution state.
start with k randomly generated states

loop
generate all successors of all k states
if any of the states = solution, then return the state
else select the k best successors
end
Simulated Annealing Annealing is the process of heating and cooling a metal to change its internal structure for modifying its physical properties. When the metal cools, its new structure is seized, and the metal retains its newly obtained properties. In simulated annealing process, the temperature is kept variable.
We initially set the temperature high and then allow it to ‘cool' slowly as the algorithm proceeds. When the temperature is high, the algorithm is allowed to accept worse solutions with high frequency.
Start
5. Initialize k = 0; L = integer number of variables; 6. From i -> j, search the performance difference ∆. 7. If ∆ <= 0 then accept else if exp(-/T(k)) > random(0,1) then accept; 8. Repeat steps 1 and 2 for L(k) steps. 9. k = k + 1;
Repeat steps 1 through 4 till the criteria is met.
End
Travelling Salesman Problem In this algorithm, the objective is to find a low-cost tour that starts from a city, visits all cities en-route exactly once and ends at the same starting city.
Start Find out all (n -1)! Possible solutions, where n is the total number of cities.