Entropy-based efficiency enhancement techniques for evolutionary algorithms

This paper introduces the notion of an entropy measurement for populations of candidate solutions in evolutionary algorithms, developing both conditional and joint entropy-based algorithms. We describe the inherent characteristics of the entropy measurement and how these affect the search process. Following these discussions, we develop a recognition mechanism through which promising candidate solutions can be identified without the need of invoking costly evaluation functions. This on-demand evaluation strategy (ODES) is able to perform decision making tasks regardless of whether the actual fitness evaluation is necessary or not, making it an ideal efficiency enhancement technique for accelerating the computational process of evolutionary algorithms. Two different evolutionary algorithms, a traditional genetic algorithm and a multivariate estimation of distribution algorithm, are employed as example targets for the application of our on-demand evaluation strategy. Ultimately, experimental results confirm that our method is able to broadly improve the performance of various population-based global searchers. (C) 2011 Elsevier Inc. All rights reserved.