Local search algorithms

Local search algorithms

Hill-Climbing Search

It is an iterative method that begins with an arbitrary solution to a problem and seeks to improve it by progressively altering one aspect of the answer. An incremental modification is considered a new solution if it results in a superior solution.

Hill-Climbing (problem) is a function that 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])
do neighbor <- a highest_valued successor of current
if Value[neighbor] ≤ Value[current] then
return State[current]
current <- neighbor

Local Beam Search

This method maintains a total of k states at any given moment. These states are produced at random at first. The goal function is used to calculate the successors of these k states. The process comes to a halt if any of these successors are the objective function's maximum value. Otherwise, the states are arranged in a pool (initial k states and k number of successors of the states = 2k). The pool is then numerically sorted. As new starting states, the highest k states are chosen, and this method is repeated until the maximum value has been attained.

A solution state is returned by the function BeamSearch( issue, k).

start with k randomly generated states
generate all successors of all k states
if any of the states = solution, then return the state
else select the k best successors

Simulated Annealing

The process of heating and cooling metal to change its internal structure and affect its physical characteristics is called annealing. The metal's new structure is gripped when it cools, and the metal keeps its newly acquired traits.


  • Initialize k = 0; L = integer number of variables;
  • From i → j, search the performance difference Δ.
  • If Δ <= 0 then accept else if exp(-Δ/T(k)) > random(0,1) then accept;
  • Repeat steps 1 and 2 for L(k) steps.
  • k = k + 1;

Travelling Salesman Problem

This algorithm aims to identify a low-cost tour that departs from a city, stops in each city along the way precisely once, and returns to the same starting point.