Exploring the influence of problem structural characteristics on evolutionary algorithm performance

The performances (success) of a hill climber (RMHC) and a genetic algorithm (upGA) on a set of test problems with varied structural characteristics are compared to learn whether problem structural characteristic can be a feasible solution-independent indicator of when a problem will be more easily solved by a genetic algorithm than by hill climbing. Evidence supporting this hypothesis is found in this initial study. In particular, other factors (modularity, transitivity and fitness distribution) being equal, highly modular problems with broad right-skewed degree distributions are more easily solved by upGA than by RMHC. Suggestions are made for further research in this direction.