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

ABSTRACT

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.

REFERENCES

• 1: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 2: John H. Holland, Building Blocks, Cohort Genetic Algorithms, and Hyperplane-Defined Functions, Evolutionary Computation, v.8 n.4, p.373-391, December 2000 [doi>10.1162/106365600568220]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
GA hardness, building block sampling, building blocks, genetic algorithm, population size, practical search index, search space