Random restart hill climbing
Suppose we have a optimisation problem where
Then we want to run Hill climbing but try to get around the issue with only finding local optimum by at the end of a run restarting in a new place.
There are lots of choices and optimisations to make here, we will need to decide a stopping condition.
- Number of iterations.
- Stop improving on the optimum value.
- A % of coverage of the points.
We can also make optimisations like remembering where a point lead us and choosing not to revisit the point - Memoization.
Run time
The run time can vary, however if we use Memoization we will try to save on number of times we run the function we are trying to optimise.
Correctness
This has a higher chance of finding a global optimum but no guarantee.