Why DGAs work well on GA-hard functions?

Abstract

What makes a problem easy or hard for a genetic algorithm (GA)? Much previous work has studied this question by applying Walsh analysis.(4)) In this paper, we demonstrate a function that is GA-hard by analyzing the Walsh coefficients of this function's Walsh decomposition. Then, we construct five functions with differing degrees of difficulty for genetic algorithms. Some are GA-easy and some are GA-hard. In a previous paper,(29)) wh have proposed a novel selection method, disruptive selection. This method devotes more trials to both better solutions and worse solutions than it does to moderate solutions, whereas the conventional method allocates its attention according to the performance of each solution. Experimental results show that DGAs (GAs using disruptive selection) perform very well on both GA-easy and GA-hard functions. Finally, we discuss why DGAs outperform conventional GAs.