A practical search index and population size analysis based on the building block hypothesis

Use of the Building Block Hypothesis to illuminate GA search behavior, as pursued by J. H. Holland and D. E. Goldberg, invites additional investigation. This paper re-examines the space actually searched by a GA, in light of the Building Block Hypothesis, GA sampling and population size, in an effort to develop more quantitative measures of GA di±culty for problems where building block sizes can be estimated. A Practical Search Index (PSI) is defined, related to the size of the space actively searched by the GA, in terms of sizes and numbers of building blocks. When BBs are hierarchical, the PSI can be used at various stages of BB assembly. Difficulty depends strongly on the sizes of the largest building blocks, rather than on the size of the entire search space, for GAs dominated by crossover. Premature convergence prevails when population size is not adequate to allow sampling and assembly of building blocks. Appropriate sizing depends on balancing the BB sampling and mixing costs. A set of simple GA experiments on classical test functions with clear building block structures (One-Max, RR1, RR2, RRJH, HIFF, etc.) at various population sizes, illustrates the relationship between the PSI, population size, and efficiency of search.