Analyzing Optimal Performance of Evolutionary Search with Restart as Problem Complexity Changes

Abstract

This research explores how the complexity of a problem domain affects the performance of an evolutionary search using a performance-based restart policy. Previous research indicates that using a restart policy to avoid premature convergence can improve the performance of an evolutionary algorithm. One method for determining when to restart the search is to track the fitness of the population and to restart when no measurable improvement has been observed over a number of generations. Our empirical evaluation of such a restart policy confirms improved performance over evolutionary search without restart, regardless of problem complexity. Our work further indicates that as problems become increasingly complex a universal restart scheme begins to emerge.