Watson, Richard A., Gregory S. Hornby, and Jordan B. Pollack. “Modeling building-block interdependency.” In International Conference on Parallel Problem Solving from Nature , pp. 97-106. Springer, Berlin, Heidelberg, 1998.
URL1 URL2
The Building-Block Hypothesis appeals to the notion of problem decomposition and the assembly of solutions from sub-solutions. Accordingly, there have been many varieties of GA lest problems with a structure based on building-blocks. Many of these problems use deceptive fitness functions to model interdependency between the bits within a block. However, very few have any model of interdependency between building-blocks; those that do are not consistent in the type of interaction used intra-block and inter-block. This paper discusses the inadequacies of the various lest problems in the literature and clarifies the concept of building-block interdependency. We formulate a principled model of hierarchical interdependency that can be applied through many levels in a consistent manner and introduce Hierarchical If-and-only-if (H-1FF) as a canonical example. We present some empirical results of GAs on H-1FF showing that if population diversity is maintained and linkage is tight then the GA is able to identify and manipulate building-blocks over many levels of assembly, as the Building-Block Hypothesis suggests.