Accounting for Noise in the Sizing of Populations* *Portions of this paper are excerpted from a paper by the authors entitled “Genetic Algorithms, Noise, and the Sizing of Populations” (Goldberg, Deb, & Clark, 1991).

Foundations of genetic algorithmsPublished 1 January 1993

David E. Goldberg, Kalyanmoy Deb, James H. Clark

Citations33

TL;DR

Results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between two distinct types of GA behavior, which may one day lead to rigorous proofs of convergence for recombinative GAs operating on problems of bounded deception.

Abstract

This paper considers the effect of noise on the quality of convergence of genetic algorithms (GAs). A population-sizing equation is derived to ensure that minimum signal-to-noise ratios are favorable to the discrimination of the best building blocks required to solve a problem of bounded deception. In five test problems of varying degrees of nonlinearity, nonuniform scaling, and nondeterminism, the sizing relation proves to be a conservative predictor of average correct convergence. These results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between two distinct types of GA behavior. Besides discussing a number of extensions of this work, the paper discusses how these results may one day lead to rigorous proofs of convergence for recombinative GAs operating on problems of bounded deception.

Keywords

Computer Science

Choice Reviews OnlineGenetic algorithms in search, optimization, and machine learning

49,278 Citations1989

This book brings together the computer techniques, mathematical tools, and research results that will enable both students and practitioners to apply genetic algorithms to problems in many fields.

The MIT Press eBooksAdaptation in Natural and Artificial Systems

35,568 Citations1992John H. Holland

Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.

Foundations of genetic algorithmsA Comparative Analysis of Selection Schemes Used in Genetic Algorithms

2,400 Citations1991David E. Goldberg, Kalyanmoy Deb

A number of selection schemes commonly used in modern genetic algorithms are compared on the basis of solutions to deterministic difference or differential equations, verified through computer simulations to provide convenient approximate or exact solutions and useful convergence time and growth ratio estimates.

Deep Blue (University of Michigan)An Analysis Of The Behavior Of A Class Of Genetic Adaptive Systems.

1,299 Citations1975Kenneth DeJong

View PDF

SIAM Journal on ComputingGenetic Algorithms and the Optimal Allocation of Trials

1,201 Citations1973John H. Holland

This study gives a formal setting to the difficult optimization problems characterized by the conjunction of substantial complexity and initial uncertainty, and the necessity of acquiring new models to solve these problems.

Genetic algorithms, noise, and the sizing of populations

597 Citations1991David E. Goldberg, Kalyanmoy Deb +1 more

Results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between what a physicist might call two distinct phases of GA behavior, and how these results may one day lead to rigorous proofs of convergence for recombinative G As operating on problems of bounded description.

Foundations of genetic algorithmsAnalyzing Deception in Trap Functions

342 Citations1993Kalyanmoy Deb, David E. Goldberg

It is found that the necessary and sufficient condition for an l-bit fully deceptive trap function is that all order l — 1 schemata are misleading, and it is observed that the trap functions commonly used in a number of test suites are not fully deceptive.

Genetic Algorithms and the Variance of Fitness.

103 Citations1991David E. Goldberg, Mike Rudnick

The paper applies these calculations to the sizing of GA pop ulations and to the adjust ment of the schema th eorem to account for fitness variance and may be viewed as a step along the road to rigorous convergence proofs for recombin ative genet ic algorithms.

Accounting for Noise in the Sizing of Populations* *Portions of this paper are excerpted from a paper by the authors entitled “Genetic Algorithms, Noise, and the Sizing of Populations” (Goldberg, Deb, &amp; Clark, 1991).

TL;DR

Abstract

Keywords

Accounting for Noise in the Sizing of Populations* *Portions of this paper are excerpted from a paper by the authors entitled “Genetic Algorithms, Noise, and the Sizing of Populations” (Goldberg, Deb, & Clark, 1991).