On the analysis of the (1+1) evolutionary algorithm with short-term memory

Given any randomized search algorithm, we can avoid re-evaluating the fitness of previously visited points by storing the information in memory. This idea is applied to the (1+1) evolutionary algorithm with standard mutation and the randomized local search (RLS) algorithm. Our analysis shows that a large reduction in running time can be obtained if we store recently visited points and execute those algorithms on some pseudo-boolean functions. Besides, the stored information can also be used to affect the generation of new search points. We illustrate this idea by designing an algorithm called progressive randomized local search. In contrary to RLS, it is capable of escaping from local maxima.