2
$\begingroup$

I am currently reading about local search techniques. I understand that local search algorithms tend to get stuck in local optima and therefore usually do not find globally optimal solutions. Thus, there are more sophisticated approaches that enable us to leave local optima and may improve the overall solution quality (e.g. simulated annealing or genetic algorithms).

What I'm thinking about is the following: As far as I understand it, the simplest approaches like hill-climbing (best-fit) are at least guaranteed to find locally optimal solutions with regard to the specified neighborhood. Don't we lose this property when using simulated annealing or genetic algorithms? Even for the first-fit version of hill-climbing it is no longer guaranteed to find a local optimum while getting the advantage of a possible runtime reduction.

Is it a tradeoff between an increased possibility to reach globally optimal solutions (or a reduced runtime in the first-fit hill-climbing case) and a higher risk of not even getting a locally optimal solution?

$\endgroup$
  • 1
    $\begingroup$ There is a simple fix to your problem: run local search on top of simulated annealing. $\endgroup$ – Yuval Filmus Nov 10 '19 at 17:44
  • $\begingroup$ Also in some definitions of simulated annealing, setting temperature to zero is equivalent to local search. $\endgroup$ – Laakeri Nov 10 '19 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.