Use of the Building Block Hypothesis to illuminate GA searchbehavior, as pursued by J. H. Holland and D. E. Goldberg,invites additional investigation.This paper investigates thespace actually searched by a GA, in light of the BuildingBlock Hypothesis, GA sampling and population size, in aneffort to develop more quantitative measures of GA hardnessfor problems where building block sizes can be estimated. APractical Search Index (PSI) is defined, related to the sizeof the space actively searched by the GA, in terms of sizesand numbers of building blocks. The results of the analysissuggest that hardness depends strongly on the sizes ofthe largest building blocks, premature convergence prevailswhen population size is not big enough to allow samplingand assembly of building blocks, and appropriate sizing dependson balancing the BB sampling and mixing costs. Aset of simple GA experiments on classical test functions atvarious population sizes, illustrates the relationship betweenthe PSI, population size, and efficiency of search.
['Zhenhua Li', 'Erik D. Goodman']
Practical Search Index as a Hardness Measure for Genetic Algorithms