A theoretical analysis of the HIFF problem

Nicholas Freitag McPhee; Ellery Fussell Crane

doi:10.1145/1068009.1068201

A theoretical analysis of the HIFF problem

Nicholas Freitag McPhee, Ellery Fussell Crane

Computer Science (Morris)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Scopus citations

Abstract

We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical analysis. We first review the use of Stephen's exact schema equations and schema basis to compute the changes in population distributions over time. We then use the tools described above to solve for the limit distributions of the 2 and 4-bit HIFF problems, and show that these limit distributions are essentially one-dimensional. We also show that a combination of fitness and the number of break points (a rough measure of distance in crossover space) in a string can be used to almost completely explain the limit distribution in the 4-bit HIFF problem.

Original language	English (US)
Title of host publication	GECCO 2005 - Genetic and Evolutionary Computation Conference
Editors	H.G. Beyer, U.M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E.W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, al et al
Pages	1153-1160
Number of pages	8
DOIs	https://doi.org/10.1145/1068009.1068201
State	Published - 2005
Event	GECCO 2005 - Genetic and Evolutionary Computation Conference - Washington, D.C., United States Duration: Jun 25 2005 → Jun 29 2005

Publication series

Name	GECCO 2005 - Genetic and Evolutionary Computation Conference

Conference

Conference	GECCO 2005 - Genetic and Evolutionary Computation Conference
Country/Territory	United States
City	Washington, D.C.
Period	6/25/05 → 6/29/05

Keywords

Distance Metrics
Evolutionary Computation
Hierarchical-if-and-only-if (HIFF) Problem
Limit Distributions
Schema Theory

Publisher link

10.1145/1068009.1068201

Find It

Find It at U of M Libraries

Cite this

McPhee, N. F., & Crane, E. F. (2005). A theoretical analysis of the HIFF problem. In H. G. Beyer, U. M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, & A. et al (Eds.), GECCO 2005 - Genetic and Evolutionary Computation Conference (pp. 1153-1160). (GECCO 2005 - Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1068009.1068201

A theoretical analysis of the HIFF problem. / McPhee, Nicholas Freitag; Crane, Ellery Fussell.
GECCO 2005 - Genetic and Evolutionary Computation Conference. ed. / H.G. Beyer; U.M. O'Reilly; D. Arnold; W. Banzhaf; C. Blum; E.W. Bonabeau; E. Cantu-Paz; D. Dasgupta; K. Deb; al et al. 2005. p. 1153-1160 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

McPhee, NF & Crane, EF 2005, A theoretical analysis of the HIFF problem. in HG Beyer, UM O'Reilly, D Arnold, W Banzhaf, C Blum, EW Bonabeau, E Cantu-Paz, D Dasgupta, K Deb & A et al (eds), GECCO 2005 - Genetic and Evolutionary Computation Conference. GECCO 2005 - Genetic and Evolutionary Computation Conference, pp. 1153-1160, GECCO 2005 - Genetic and Evolutionary Computation Conference, Washington, D.C., United States, 6/25/05. https://doi.org/10.1145/1068009.1068201

McPhee, Nicholas Freitag ; Crane, Ellery Fussell. / A theoretical analysis of the HIFF problem. GECCO 2005 - Genetic and Evolutionary Computation Conference. editor / H.G. Beyer ; U.M. O'Reilly ; D. Arnold ; W. Banzhaf ; C. Blum ; E.W. Bonabeau ; E. Cantu-Paz ; D. Dasgupta ; K. Deb ; al et al. 2005. pp. 1153-1160 (GECCO 2005 - Genetic and Evolutionary Computation Conference).

@inproceedings{80537ad5c9454c2680c4df91a3909ba8,

title = "A theoretical analysis of the HIFF problem",

abstract = "We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical analysis. We first review the use of Stephen's exact schema equations and schema basis to compute the changes in population distributions over time. We then use the tools described above to solve for the limit distributions of the 2 and 4-bit HIFF problems, and show that these limit distributions are essentially one-dimensional. We also show that a combination of fitness and the number of break points (a rough measure of distance in crossover space) in a string can be used to almost completely explain the limit distribution in the 4-bit HIFF problem.",

keywords = "Distance Metrics, Evolutionary Computation, Hierarchical-if-and-only-if (HIFF) Problem, Limit Distributions, Schema Theory",

author = "McPhee, {Nicholas Freitag} and Crane, {Ellery Fussell}",

year = "2005",

doi = "10.1145/1068009.1068201",

language = "English (US)",

isbn = "1595930108",

series = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

pages = "1153--1160",

editor = "H.G. Beyer and U.M. O'Reilly and D. Arnold and W. Banzhaf and C. Blum and E.W. Bonabeau and E. Cantu-Paz and D. Dasgupta and K. Deb and {et al}, al",

booktitle = "GECCO 2005 - Genetic and Evolutionary Computation Conference",

}

TY - GEN

T1 - A theoretical analysis of the HIFF problem

AU - McPhee, Nicholas Freitag

AU - Crane, Ellery Fussell

PY - 2005

Y1 - 2005

N2 - We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical analysis. We first review the use of Stephen's exact schema equations and schema basis to compute the changes in population distributions over time. We then use the tools described above to solve for the limit distributions of the 2 and 4-bit HIFF problems, and show that these limit distributions are essentially one-dimensional. We also show that a combination of fitness and the number of break points (a rough measure of distance in crossover space) in a string can be used to almost completely explain the limit distribution in the 4-bit HIFF problem.

AB - We present a theoretical analysis of Watson's Hierarchical-if-and-only-if (HIFF) problem using a variety of tools. These include schema theory and course graining, the concept of effective fitness, and statistical analysis. We first review the use of Stephen's exact schema equations and schema basis to compute the changes in population distributions over time. We then use the tools described above to solve for the limit distributions of the 2 and 4-bit HIFF problems, and show that these limit distributions are essentially one-dimensional. We also show that a combination of fitness and the number of break points (a rough measure of distance in crossover space) in a string can be used to almost completely explain the limit distribution in the 4-bit HIFF problem.

KW - Distance Metrics

KW - Evolutionary Computation

KW - Hierarchical-if-and-only-if (HIFF) Problem

KW - Limit Distributions

KW - Schema Theory

UR - http://www.scopus.com/inward/record.url?scp=32444443636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32444443636&partnerID=8YFLogxK

U2 - 10.1145/1068009.1068201

DO - 10.1145/1068009.1068201

M3 - Conference contribution

AN - SCOPUS:32444443636

SN - 1595930108

SN - 9781595930101

T3 - GECCO 2005 - Genetic and Evolutionary Computation Conference

SP - 1153

EP - 1160

BT - GECCO 2005 - Genetic and Evolutionary Computation Conference

A2 - Beyer, H.G.

A2 - O'Reilly, U.M.

A2 - Arnold, D.

A2 - Banzhaf, W.

A2 - Blum, C.

A2 - Bonabeau, E.W.

A2 - Cantu-Paz, E.

A2 - Dasgupta, D.

A2 - Deb, K.

A2 - et al, al

T2 - GECCO 2005 - Genetic and Evolutionary Computation Conference

Y2 - 25 June 2005 through 29 June 2005

ER -

A theoretical analysis of the HIFF problem

Abstract

Publication series

Conference

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this