Complex energy landscape mapping by histogram assisted genetic algorithm

A histogram assisted adjustment of fitness distribution in standard genetic algorithm is introduced and tested on four benchmark functions of complex landscapes, with remarkable improvement in performance, such as the substantial enhancement in the probability of detecting local minima. Numerical tests suggest that the idea of histogram assisted adjustment, or the "renormalization" of the fitness distribution, is generally advantageous for multi-modal function optimization. An analysis on the effect of the bin number of the histogram has also been carried out, showing that the performance of the algorithm is insensitive to this extra parameter as long as it is an order of magnitude smaller than the size of the population (N) in the genetic algorithm. This analysis suggests that the advantage of the introduction of histogram assisted fitness adjustment is a robust feature for genetic algorithm, since the adjustment of fitness enhances exploration by broadening the diversity of the population of chromosomes. In general, the advantage of this histogram assisted adjustment more than compensates the cost of computation resource in the construction of the histogram with O(N) time complexity. Suggestions of using this technique for the mapping of complex landscape are discussed. Copyright 2010 ACM