An iterative mutual information histogram technique for linkage learning in evolutionary algorithms

This paper introduces a new algorithm for determining the appropriate linkage between variables for an evolutionary algorithm. It operates in an iterative mode, as a pre-processing step before the evolutionary algorithm is run. The technique works by estimating the mutual information between variables, based on truncation-selected groups from random populations. To check for significance of differences between mutual information values, histograms are used, along with the standard, minimum error thresholding procedure. A stopping criterion is easily constructed, based on the functional form of the distribution of zero mutual information estimates. The technique is illustrated on a variety of problems, and shown to have polynomial time complexity for bounded deception. The technique´s extension to alphabets of arbitrary cardinality is straightforward, and approximate techniques for real-valued algorithms are discussed. Given its efficacy and extensibility, the technique could prove a useful alternative to other linkage learning techniques.