Is perturbation an effective restart strategy?

Search methods, such as Genetic Algorithms and Simulated Annealing are typically used to achieve the required scalability in challenging problems for which it is hard to find optimal, or even just "good enough' solutions. The majority of these methods involve steps where the state of the algorithm is modified in some way to escape a local optimum. The aim is to avoid premature convergence, which is when the search method converges (usually very early in the search) to a local optimum of poor quality [1, 2]. Previous research has shown that the performance of search strategies is affected by the structure of the fitness landscape [3, 4]. A fitness landscape is defined by three components: i) the search space, which is the set of all candidate solutions, ii) the fitness function, which assigns a fitness value to each solution, and the neighbourhood operator, which defines how solutions are connected, and as a results how the search strategy can traverse the landscape.