Volume 8 Number 8 (Aug. 2013)
Home > Archive > 2013 > Volume 8 Number 8 (Aug. 2013) >
JCP 2013 Vol.8(8): 2034-2041 ISSN: 1796-203X
doi: 10.4304/jcp.8.8.2034-2041

Practical Search Index as a Hardness Measure for Genetic Algorithms

Zhenhua Li1 and Erik D. Goodman2
1 School of Computer Science China Univ. of Geosciences Wuhan 430074, China
2 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.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Jul 19, 2019 News!

    Vol 14, No 7 has been published with online version   [Click]

  • Jun 21, 2019 News!

    Vol 14, No 6 has been published with online version   [Click]

  • Apr 28, 2019 News!

    Vol 14, No 5 has been published with online version 7 papers are published in this issue after peer review   [Click]

  • Mar 20, 2019 News!

    Vol 14, No 3 has been published with online version   [Click]

  • Read more>>