Are there local search algorithms that make use of memory to give better solutions?

Question

I have been studying local search algorithms such as greedy hill-climbing, stochastic hill-climbing, simulated annealing, etc. I have noticed that most of these methods take up very little memory as compared to systematic search techniques.

Are there local search algorithms that make use of memory to give significantly better answers than those algorithms that use little memory (such as crossing local maxima)?

Also, is there a way to combine local search and systematic search algorithms to get the best of both worlds?

Answer 1

You could parallelize the search by dividing the global space in distinct regions/subsets. Then apply in each region a local search. This way you can search the global space systematically, more exhaustively and perhaps in different ways (e.g by applying a different local search method to each region). Finally you can compare the results and choose the best one.

Answer 2

Tabu search uses memory to rule out parts of the neighborhood for local search, allowing the trajectory to typically pass through local optima instead of getting stuck in them.