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

SCHEMA RECOMBINATION IN A PATTERN RECOGNITION PROBLEM

Irene Stadnyk*

Theoretical Division
Los Alamos National Laboratory
Los Alamos, NM 87545.


Abstract

A simple pattern recognition problem is presented, where a population of binary strings evolves under the genetic algorithm as it tries to match and recognize another population of binary strings. Sampling is used in the genetic algorithm to do matching, which determines fitness, and crowding, which allows subpopulations to form that recognize different pattern strings. To understand what subpatterns the recognizer strings chose as the regularities in the patterns and how these are organized as recognition improves, the theory of schemata is applied to the resulting recognizer string population. The schemata that are formed by recombining other schemata and mutating them with a low level of noise emerge in a default hierarchy. This hierarchy has general properties that apply to any knowledge representation used in such a pattern recognition system.


1 Introduction

Adaptive systems require a dynamic memory in which to store information about the environment. The memory must be organized in such a way so that relevant information can be retreived quickly and can be used to predict states of the environment based on the current states. Feedback from the environment should be used to have the system learn: the memory should be updated using the feedback so that it can make more accurate predictions in the future, even with partial or noisy information about the environment. The memory's predictions are also used to determine the performance or behavior of the system.

The adaptive system builds its memory by trying to find regularities in the environment that occur in more than one environmental state or occur frequently in the environment. These regularities based on similarity and repeateability are then used to form equivalence classes of environmental states that are then used to organize the memory. These form the basis of the learned model of the environment stored on memory.

In a population of adaptive systems, another requirement can be placed on the memory. The memory must be capable of being transmitted from one system to another. That is, a code representing instructions on how to build a functioning memory must be transmitted to the another system. The code consists of discrete units, which are transmitted in some partial sequential order. Once the code is formed, it does not change but rather is subjected to pressures of selection. It is transmitted throughout the population based on its fitness. It is not clear how the transmitted code is decoded and how it affects the structure and information represented in the receiving memory.

Adaptive system memories have been described in the paradigm of adaptive networks. Adaptive networks include autocatalytic networks of chemical reactions [3], the idiotypic network in the immune system [10], classifiers under the Bucket Brigade Algorithm [9], and nets abstracted from these systems [4]. Transmittable adaptive memories include self-reproducing "organsims" in cellular automata [12] and genetic algorithms [8].

This paper presents a model of an adaptive system based on genetics, which has a memory consisting of binary bit strings. The transmittability of the memory is not discusses since presumably the binary strings can be transmitted in a sequence of discrete bits. However, the organization of a memory consisting of binary strings is studied as the binary strings evolve under a genetic algorithm. The system with this memory is a simple pattern recognizer, based on pattern recognition in the immune system. The system's memory is a population of recognizer strings which try to recognize many pattern strings in parallel by picking out regularities in the pattern strings. The genetic algorithm generates new recognizer strings according to fitness. The fitness of each recognizer string is determined by how many bits it matches of how many pattern strings. Recognizer strings with above average fitness reproduce, and of those, the ones with higher fitness produce more offspring. Thus, recognizers that contain "subpatterns" or substrings of one or more pattern strings will prolifer-

____________________
*
Permanent address: EECS Department, The University of Michigan, Ann Arbor, MI 48109.
Arpanet address: ims@lanl.gov.

-27-

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.