The Building Block Fallacy

Thornton, Chris (1997) The Building Block Fallacy. Complexity International, 4. ISSN 1320-0682

[img] PDF
Restricted to SRO admin only

Download (140kB)

Abstract

Genetic Algorithms (GAs) are increasingly used for such purposes as deriving programs (Koza 1992) and producing designs for robots (Cliff 1993). According to the building-block hypothesis and schema analysis of Holland (Holland 1975) the GA is an efficient search method. However, empirical work has shown that in some cases the method is outperformed by simpler processes such as random-permutation hill climbing (Forrest & Mitchell 1996; Lang 1995). The present paper re-examines Holland's framework (as formulated by Goldberg - Goldberg 1989) and finds that such in-practice failures are predictable given the implications of the schema analysis. The high efficiency of the GA method is commonly attributed to its "implicit parallelism"; that is, its ability to develop candidate solutions in parallel, without focussing on any particular solution at any one time. However, this efficiency is hard to realise because there is a deep contradiction between the building-block hypothesis and the schema theorem.

Item Type: Article
Additional Information: Publisher's version is freely available at the official url.
Schools and Departments: School of Engineering and Informatics > Informatics
Subjects: Q Science > QA Mathematics > QA0075 Electronic computers. Computer science
Depositing User: Chris Keene
Date Deposited: 29 Feb 2008
Last Modified: 13 Mar 2017 12:09
URI: http://sro.sussex.ac.uk/id/eprint/1469
Google Scholar:14 Citations

View download statistics for this item

📧 Request an update