Using disruptive selection to maintain diversity in Genetic Algorithms

Abstract

Genetic algorithms are a class of adaptive search techniques based on the principles of population genetics. The metaphor underlying genetic algorithms is that of natural evolution. With their great robustness, genetic algorithms have proven to be a promising technique for many optimization, design, control, and machine learning applications. A novel selection method, disruptive selection, has been proposed. This method adopts a nonmonotonic fitness function that is quite different from conventional monotonic fitness functions. Unlike conventional selection methods, this method favors both superior and inferior individuals. Since genetic algorithms allocate exponentially increasing numbers of trials to the observed better parts of the search space, it is difficult to maintain diversity in genetic algorithms. We show that Disruptive Genetic Algorithms (DGAs) effectively alleviate this problem by first demonstrating that DGAs can be used to solve a nonstationary search problem, where the goal is to track time-varying optima. Conventional Genetic Algorithms (CGAs) using proportional selection fare poorly on nonstationary search problems because of their lack of population diversity after convergence. Experimental results show that DGAs immediately track the optimum after the change of environment. We then describe a spike function that causes CGAs to miss the optimum. Experimental results show that DGAs outperform CGAs in resolving a spike function.