¹ School of Computer Science China Univ. of Geosciences Wuhan 430074, China
² Dept. of Electrical and Computer Engineering 2120 Engineering Building Michigan State Univ., E. Lansing, MI 48824

---

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 investigates 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 hardness 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. The results of the analysis suggest that hardness depends strongly on the sizes of the largest building blocks, premature convergence prevails when population size is not big enough to allow sampling and assembly of building blocks, and appropriate sizing depends on balancing the BB sampling and mixing costs. A set of simple GA experiments on classical test functions at various population sizes, illustrates the relationship between the PSI, population size, and efficiency of search.

Index Terms—genetic algorithm, building blocks, search space, practical search index,building block sampling, population size, GA hardness

[PDF]

Cite: Zhenhua Li and Erik D. Goodman, " Practical Search Index as a Hardness Measure for Genetic Algorithms," Journal of Computers vol. 8, no. 8, pp. 2034-2041, 2013.