Genetic programming Complex adaptive systems - Koza J.R.pdf

(5468 KB) Pobierz
Page i
Genetic Programming
Page ii
Complex Adaptive Systems
John H. Holland, Christopher Langton, and Stewart W. Wilson, advisors
Adaptation in Natural and Artificial Systems: An Introductory Analysis with
Applications to Biology, Control, and Artificial Intelligence,
MIT Press edition
John H. Holland
Toward a Practice of Autonomous Systems: Proceedings of the First European
Conference on Artificial Life
edited by Francisco J. Varela and Paul Bourgine
Genetic Programming: On the Programming of Computers by
Means of Natural Selection
John R. Koza
Page iii
Genetic Programming
On the Programming of Computers by Means of Natural Selection
John R. Koza
A Bradford Book
The MIT Press
Cambridge, Massachusetts
London, England
Page iv
Sixth printing, 1998
© 1992 Massachusetts Institute of Technology
All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying,
recording, or information storage or retrieval) without permission in writing from the publisher.
Set from disks provided by the author.
Printed and bound in the United States of America.
The programs, procedures, and applications presented in this book have been included for their instructional value. The publisher and the
author offer NO WARRANTY OF FITNESS OR MERCHANTABILITY FOR ANY PARTICULAR PURPOSE and accept no liability with
respect to these programs, procedures, and applications.
Pac-Man
®
—© 1980 Namco Ltd. All rights reserved.
Library of Congress Cataloging-in-Publication Data
Koza, John R.
Genetic programming: on the programming of computers by means of natural selection/
John R. Koza.
p. cm.—(Complex adaptive systems)
"A Bradford book."
Includes bibliographical references and index.
ISBN 0-262-11170-5
1. Electronic digital computers—Programming. I. Title. II. Series.
QA76.6.K695 1992
006.3—dc20
92-25785
CIP
Page v
to my mother and father
Page vii
Contents
Preface
Acknowledgments
1
Introduction and Overview
2
Pervasiveness of the Problem of Program Induction
3
Introduction to Genetic Algorithms
ix
xiii
1
9
17
4
The Representation Problem for Genetic Algorithms
5
Overview of Genetic Programming
6
Detailed Description of Genetic Programming
7
Four Introductory Examples of Genetic Programming
8
Amount of Processing Required to Solve a Problem
9
Nonrandomness of Genetic Programming
10
Symbolic Regression—Error-Driven Evolution
11
Control—Cost-Driven Evolution
12
Evolution of Emergent Behavior
13
Evolution of Subsumption
14
Entropy-Driven Evolution
15
Evolution of Strategy
16
Co-Evolution
63
73
79
121
191
205
237
289
329
357
395
419
429
Page viii
17
Evolution of Classification
18
Iteration, Recursion, and Setting
19
Evolution of Constrained Syntactic Structures
20
Evolution of Building Blocks
439
459
479
527
21
Evolution of Hierarchies of Building Blocks
22
Parallelization of Genetic Programming
23
Ruggedness of Genetic Programming
24
Extraneous Variables and Functions
25
Operational Issues
26
Review of Genetic Programming
27
Comparison with Other Paradigms
28
Spontaneous Emergence of Self-Replicating and Evolutionarily Self-Improving
Computer Programs
29
Conclusions
Appendix A: Computer Implementation
Appendix B: Problem-Specific Part of Simple LISP Code
Appendix C: Kernel of the Simple LISP Code
Appendix D: Embellishments to the Simple LISP Code
Appendix E: Streamlined Version of EVAL
Appendix F: Editor for Simplifying S-Expressions
Appendix G: Testing the Simple LISP Code
Appendix H: Time-Saving Techniques
Appendix I: List of Special Symbols
Appendix J: List of Special Functions
Bibliography
Index
553
563
569
583
597
619
633
643
695
699
705
735
757
765
771
777
783
787
789
791
805
Page ix
Preface
Organization of the Book
Chapter 1 introduces the two main points to be made.
Chapter 2 shows that a wide variety of seemingly different problems in a number of fields can be viewed as problems of program induction.
No prior knowledge of conventional genetic algorithms is assumed. Accordingly, chapter 3 describes the conventional genetic algorithm and
introduces certain terms common to the conventional genetic algorithm and genetic programming. The reader who is already familiar with
genetic algorithms may wish to skip this chapter.
Chapter 4 discusses the representation problem for the conventional genetic algorithm operating on fixed-length character strings and
variations of the conventional genetic algorithm dealing with structures more complex and flexible than fixed-length character strings. This
book assumes no prior knowledge of the LISP programming language. Accordingly, section 4.2 describes LISP. Section 4.3 outlines the
reasons behind the choice of LISP for the work described herein.
Chapter 5 provides an informal overview of the genetic programming paradigm, and chapter 6 provides a detailed description of the
techniques of genetic programming. Some readers may prefer to rely on chapter 5 and to defer reading the detailed discussion in chapter 6
until they have read chapter 7 and the later chapters that contain examples.
Chapter 7 provides a detailed description of how to apply genetic programming to four introductory examples. This chapter lays the
groundwork for all the problems to be described later in the book.
Chapter 8 discusses the amount of computer processing required by the genetic programming paradigm to solve certain problems.
Chapter 9 shows that the results obtained from genetic programming are not the fruits of random search.
Chapters 10 through 21 illustrate how to use genetic programming to solve a wide variety of problems from a wide variety of fields. These
chapters are divided as follows:
•
symbolic
regression; error-
driven
evolution—chapter
10
•
control and
optimal control;
cost-driven
evolution—chapter
11
Page x
•
evolution of emergent behavior—chapter 12
•
evolution of
subsumption—chapter
13
•
entropy-
driven
evolution—chapter
14
•
evolution of strategies—chapter 15

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin