Are there local search algorithms that make use of memory to give better solutions?
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.