Genetic Algorithms and Their Applications: "Proceedings of the Second International Conference on Genetic Algorithms : July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, Ma"

By John J. Grefenstette; International Conference on Genetic Algorithms et al. | Go to book overview

REDUCING BIAS AND INEFFICIENCY IN THE SELECTION ALGORITHM
James Edward Baker Vanderbilt University
Abstract
Most implementations of Genetic Algorithms experience sampling bias and are unnecessarily inefficient. This paper reviews various sampling algorithms proposed in the literature and offers two new algorithms of reduced bias and increased efficiency. An empirical analysis of bias is then presented.
1. Introduction
Genetic Algorithms (GAs) cycle through four phases[4]: evaluation, selection, recombination and mutation. The selection phase determines the actual number of offspring each individual will receive based on its relative performance. The selection phase is composed of two parts: 1) determination of the individuals' expected values; and 2) conversion of the expected values to discrete numbers of offspring. An individual's expected value is a real number indicating the average number of offspring that individual should receive. Hence, an individual with an expected value of 1.5 should average, 1 ½ offspring. The algorithm used to convert the real expected values to integer numbers of offspring is called the sampling algorithm. The sampling algorithm must maintain a constant population size while attempting to provide accurate, consistent and efficient sampling. These three goals lead to the bias, spread and efficiency measures described below:
1) bias -- Bias is defined to be the absolute difference between an individual's actual sampling probability and his expected value[3]. To ensure proper credit assignment to the represented hyperplanes, the expected values should be sampled as accurately as possible. The optimal, zero bias is achieved whenever each individual's sampling probability equals his expected value.
2) spread -- Let f(i) be the actual number of offspring individual i receives in a given generation. We define the "spread" as the range of possible values for f(i). Furthermore, we define the "Minimum Spread" as the smallest possible spread which theoretically permits zero bias. Hence, the Minimum Spread is one in which

f (i) ∈

〉ev(i)⌋, ⌈ev(i)⌉ Where ev(i) = expected value of individual i.

Whereas the bias indicates accuracy, the spread indicates precision. Hence the spread reveals the sampling algorithm's consistency.

3) efficiency -- It is desirable for the sampling algorithm not to increase the GAs' overall time complexity. CAs' other phases are O(LN) or better, where L. - length of an individual and N = population size.
All currently available sampling algorithms fail to provide both zero bias and Minimum Spread[3]. Yet an accurate sampling algorithm is crucial. All of the GAs' theoretical support presupposes the ability to implement the intended expected values. How much the existing inaccuracies have affected the GAs' performance is unknown. However, inaccuracies of sufficient magnitude to alter performance should be either understood or eliminated. This paper offers an empirical analysis of one of the most common sampling algorithms[5] -- Remainder Stochastic Sampling without Replacement--and introduces two new sampling algorithms designed to reduce or eliminate these inaccuracies.Section 2 reviews and compares previously proposed sampling algorithms. Section 3 introduces an improved sampling algorithm which can be partially executed in parallel. Section 4 introduces a sampling algorithm of zero bias, Minimum Spread and optimal O(N) time complexity. Section 5 presents an empirical analysis of these algorithms and section 6 provides a summary and conclusions.
2. Previous Work
The basic characteristics of various sampling algorithms[3] are presented in Table 1. The first four algorithms are stochastic and involve basically the same technique:
Determine R, the sum of the competing expected values.
-- 1-1 map the individuals to contiguous segments of the real number line, [0..R), such that each individual's segment is equal in size to its competing expected value.
-- Generate a random number within [0..R).
-- Select the individual whose segment spans the random number.
-- Repeat the process until the desired number of samples is obtained.

-14-

Notes for this page

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items
Notes
Cite this page

Cited page

Style
Citations are available only to our active members.
Buy instant access to cite pages or passages in MLA 8, MLA 7, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

(Einhorn 25)

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Note: primary sources have slightly different requirements for citation. Please see these guidelines for more information.

Cited page

Bookmark this page
Genetic Algorithms and Their Applications: "Proceedings of the Second International Conference on Genetic Algorithms : July 28-31, 1987 at the Massachusetts Institute of Technology, Cambridge, Ma"
Table of contents

Table of contents

  • Title Page i
  • Acknowledgements iii
  • Conference Program v
  • Finite Markov Chain Analysis of Genetic Algorithms 1
  • Introduction 1
  • Conclusions 8
  • Acknowledgements 8
  • References 8
  • An Analysis of Reproduction and Crossover in a Binary-Coded Genetic Algorithm 9
  • Introduction 9
  • Conclusions 12
  • References 12
  • Reducing Bias and Inefficiency in the Selection Algorithm 14
  • Abstract 14
  • References 18
  • Altruism in the Bucket BrigaĎe 22
  • 8. Conclusions 26
  • Schema Recombination in a Pattern Recognition Problem 27
  • Abstract 27
  • References 35
  • An Adaptive Crossover Distribution Mechanism for Genetic Algorithms 36
  • Abstract 36
  • References 40
  • Genetic Algorithms with Sharing for Multimodal Function Optimization 41
  • Introduction 41
  • Conclusion 48
  • References 48
  • The Argot Strategy: Adaptive Representation Genetic Optimizer Technique 50
  • Section: 4. Acknowledgements 54
  • Section: 5. References 54
  • Nonstationary Function Optimization Using Genetic Algorithms with Dominance and Diploidy 59
  • Introduction 59
  • Conclusions 68
  • Genetic Operators for High-Level Knowledge Representations 69
  • Abstract 69
  • 6. References 76
  • Tree Structured Rules in Genetic Algorithms 77
  • Introduction 77
  • Bibliography 81
  • Genetic Algorithms and Classifier Systems Foundations and Future Directions 82
  • Abstract 82
  • Appendix. 89
  • References. 89
  • Greedy Genetics 90
  • Introduction 90
  • References 98
  • Incorporating Heuristic Information into Genetic Search 100
  • Abstract 100
  • 6. References 104
  • Appendix 2 106
  • Using Reproductive Evaluation to Improve Genetic Search and Heuristic Discovery 108
  • Introduction 108
  • Conclusions 115
  • References 115
  • Toward a Unified Thermodynamic Genetic Operator 116
  • Introduction 116
  • Conclusion 121
  • Appendix 121
  • References 122
  • Towards the Evolution of Symbols 123
  • Abstract 123
  • Supergran: A Connectionist Approach to Learning, Integrating Genetic Algorithms and Graph Induction 132
  • Introduction 132
  • References 139
  • Parallel Implementation of Genetic Algorithms in a Classifier System 140
  • Abstract 140
  • Summary 145
  • References 145
  • Punctuated Equilibria: A Parallel Genetic Algorithm 148
  • Introduction 148
  • References 154
  • A Parallel Genetic Algorithm 155
  • Abstract 155
  • References 157
  • Genetic Learning Procedures in Distributed Environments 162
  • Abstract 162
  • References 169
  • Parallelisation of Probabilistic Sequential Search Algorithms 170
  • Abstract 170
  • References 173
  • Parallel Genetic Algorithm for a Hypercube 177
  • Abstract 177
  • References 182
  • Bucket Brigade Performance: I. Long Sequences of Classifiers 184
  • Abstract 184
  • References 195
  • Bucket Brigade Performance: Ii. Default Hierarchies 196
  • Abstract 196
  • References 201
  • Multilevel Credit Assignment in a Genetic Learning System 202
  • Abstract 202
  • Acknowledgements 206
  • On Using Genetic Algorithms to Search Program Spaces 210
  • A Genetic System for Learning Models of Consumer Choice 217
  • Abstract 217
  • References 222
  • A Study of Permutation Crossover Operators on the Traveling Salesman Problem 224
  • Introduction 224
  • Summary 229
  • Notes 229
  • References 230
  • A Classifier-Based for Discovering Scheduling Heuristics 231
  • Abstract 231
  • Conclusions 234
  • References 235
  • Using the Genetic Algorithm to Generate Lisp Source Code to Solve the Prisoner's Dilemma 236
  • Introduction 236
  • Bibliography 239
  • Bibliography 240
  • Optimal Determination of User-Oriented Clusters: an Application for the Reproductive Plan 241
  • References 245
  • The Genetic Algorithm and Biological Development 247
  • Abstract 247
  • References 251
  • Genetic Algorithms and Communication Link Speed Design: Theoretical Considerations 252
  • Introduction 252
  • Conclusion 256
  • Genetic Algorithms and Communication Link Speed Design: Constraints and Operators 257
  • Introduction 257
  • Conclusion 260
Settings

Settings

Typeface
Text size Smaller Larger Reset View mode
Search within

Search within this book

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Help
Full screen
Items saved from this book
  • Bookmarks
  • Highlights & Notes
  • Citations
/ 260

matching results for page

    Questia reader help

    How to highlight and cite specific passages

    1. Click or tap the first word you want to select.
    2. Click or tap the last word you want to select, and you’ll see everything in between get selected.
    3. You’ll then get a menu of options like creating a highlight or a citation from that passage of text.

    OK, got it!

    Cited passage

    Style
    Citations are available only to our active members.
    Buy instant access to cite pages or passages in MLA 8, MLA 7, APA and Chicago citation styles.

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

    "Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

    1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

    Cited passage

    Thanks for trying Questia!

    Please continue trying out our research tools, but please note, full functionality is available only to our active members.

    Your work will be lost once you leave this Web page.

    Buy instant access to save your work.

    Already a member? Log in now.

    Search by... Author
    Show... All Results Primary Sources Peer-reviewed

    Oops!

    An unknown error has occurred. Please click the button below to reload the page. If the problem persists, please try again in a little while.