Watson, Richard A., Gregory S. Hornby, and Jordan B. Pollack. “Hierarchical building-block problems for GA evaluation.” Parallel problem solving from nature (1998): 97-106.
URL1 URL2
Much research effort in the GA community has been directed at identifying what, if anything, GA’s are good for ([Forrest & Mitchell, 1993], [Goldberg, 1994], [Mitchell et al., 1995]). The building-block hypothesis ([Holland, 1975], [Goldberg, 1989]) directs our attention to problems which exhibit a decomposable structure, and the Royal-Road problems [Mitchell et al. 1992] were a first attempt at formalizing a problem with building-block components. Other models have been proposed since, but it remains unclear how to model (or solve) problems that exhibit interdependency between building-blocks - sometimes called ‘linkage’ or ‘cross-talk’. If, for example, the contribution of a building-block is nontrivially dependent on other building-blocks how can it be identified independently? And, if it is not independent, how can it reasonably be called a building-block? This paper offers clarification for the concepts of inter-dependent blocks, or partially decomposable problems, and introduces the Hierarchical-IFF (H-IFF) function which provides a canonical example of a class of hierarchical test problems. H-IFF is then used in some preliminary experiments to investigate the GA’s ability to manipulate interdependent building-blocks.