Genetic Programming Theory and Practice II

This volume explores the emerging interaction between theory and practice in the cutting-edge, machine learning method of Genetic Programming (GP). The contributions developed from a second workshop at the University of Michigan's Center for the Study of Complex Systems where leading international genetic programming theorists from major universities and active practitioners from leading industries and businesses met to examine how GP theory informs practice and how GP practice impacts GP theory. Chapters include such topics as financial trading rules, industrial statistical model building, population sizing, the roles of structure in problem solving by computer, stock picking, automated design of industrial-strength analog circuits, topological synthesis of robust systems, algorithmic chemistry, supply chain reordering policies, post docking filtering, an evolved antenna for a NASA mission and incident detection on highways. Cover......Page 1 Series Editor......Page 3 Springer......Page 4 Contents......Page 6 Contributing Authors......Page 8 Preface......Page 14 Foreword......Page 16 1. Theory and Practice: Mind the Gap......Page 18 2. The Accounts of Practitioners......Page 19 3. GP Theory and Analysis......Page 21 4. Achieving Better GP Performance......Page 23 5. How Biology and Computation Can Inform Each Other......Page 26 6. Wrap up: Narrowing the Gap......Page 27 1. Introduction......Page 28 2. Related Work......Page 30 3. Modular GP through Lambda Abstraction......Page 31 4. The PolyGP System......Page 32 5. S&P 500 Index Time Series Data......Page 34 6. Experimental Setup......Page 36 Fitness Function......Page 38 7. Results......Page 39 8. Analysis of GP Trading Rules......Page 40 9. Analysis of Transaction Frequency......Page 42 10. Concluding Remarks......Page 45 References......Page 46 1. INTRODUCTION......Page 48 2. SYNERGY BETWEEN GP AND STATISTICAL MODEL BUILDING......Page 49 2.2 Unique Features of Statistical Model Building Attractive to GP......Page 50 3. METHODOLOGY......Page 51 3.1 Methodology for Designed Data......Page 52 3.2 Methodology for Undesigned Data......Page 56 4. FUTURE RESEARCH......Page 61 5. APPENDIX 1: GLOSSARY OF STATISTICAL TERMS......Page 62 References......Page 64 1. Introduction......Page 66 2. Background......Page 68 3. GA Population Sizing from the Perspective of Competing Building Blocks......Page 69 4. GP Definitions for a Population Sizing Derivation......Page 72 5. GP Population Sizing Model......Page 73 6. Sizing Model Problems......Page 75 Every BB in a tree is expressed......Page 76 Tunable building block expression......Page 77 7. Conclusions......Page 79 Acknowledgments......Page 80 References......Page 81 1. INTRODUCTION......Page 84 2. A HIERARCHICAL VIEW OF STRUCTURE......Page 86 3.1 Theory Concerning Lattice......Page 87 3.2 Practical Implications of Lattice......Page 89 4.1 Theory Concerning Network......Page 90 5. CONTENT......Page 94 5.1 Theory Concerning Content......Page 95 5.2 Practical Implications of Content......Page 97 6. CONCLUSIONS......Page 99 REFERENCES......Page 100 1. INTRODUCTION......Page 104 1.1 The Stock Picking Problems We Faced (a.k.a. Our Growth Market Problem)......Page 105 2. PROJECT DESCRIPTION OVERVIEW......Page 106 2.1 Acceptability Criterion – Does the resulting model agree with our intuition of how the markets work? Does it improve our knowledge?......Page 107 3.1 Factor Models Entering Problem......Page 108 4.1 Fitness Elements as a Proxy for Portfolio Performance......Page 109 4.2 Fitness Function Specification......Page 110 5.1 Program Representation......Page 111 5.2 Time-Series Selection: Avoiding Data Mining/Snooping Concerns......Page 112 5.4 Other Genetic Program Parameters......Page 113 6. GENETIC PROGRAMMING RESULTS 6.1 Simplification and Interpretation of Formulae......Page 115 7. POST GENETIC PROGRAMMING PORTFOLIO SIMULATIONS......Page 116 9. SUMMARY......Page 118 REFERENCES......Page 119 1. Introduction......Page 120 Module Acquisition Strategies......Page 121 3. Run Transferable Libraries......Page 122 4. Mnemosyne......Page 124 5. Initial Results......Page 125 6. Bias in Function Sets......Page 126 Multiplexer......Page 128 7. Subsequent Library Performance......Page 132 8. Debiasing Function Sets......Page 134 9. Conclusions and future work......Page 135 Appendix: The Mnemosyne Algorithm......Page 136 References......Page 137 TOWARD AUTOMATED DESIGN OF INDUSTRIAL-STRENGTH ANALOG CIRCUITS BY MEANS OF GENETIC PROGRAMMING......Page 138 1. INTRODUCTION......Page 139 2. ABILITY OF GENETIC PROGRAMMING TO PROFITABLY EXPLOIT INCREASED COMPUTER POWER......Page 143 3. EXPLOITING GENERAL KNOWLEDGE ABOUT CIRCUITS......Page 146 4. EXPLOITING PROBLEM-SPECIFIC KNOWLEDGE......Page 147 5. IMPROVING TECHNIQUES OF GENETIC PROGRAMMING......Page 149 6. GRAPPLING WITH A MULTI-OBJECTIVE FITNESS MEASURE......Page 151 7. CONCLUSIONS......Page 157 References......Page 158 1. Introduction......Page 160 2. Related Work......Page 161 Bond Graphs......Page 163 Analog Filter Synthesis by Bond Graph and Genetic Programming......Page 164 4. Evolving Robust Analog Filters by QHFC-GP......Page 166 5. Experiments and Results......Page 167 Analog Filters with Different Topologies Have Different Noise Robustness and Fault Tolerance Capability......Page 168 Evolving Robustness to Component Sizing Perturbations......Page 169 Evolving Robustness to Component Failure......Page 171 6. Conclusions and Future Work......Page 172 References......Page 173 1. Introduction......Page 176 2. Background......Page 177 3. Experimental Methods Experiments......Page 179 The GP......Page 180 Even Parity......Page 181 Battleship......Page 182 4. Results......Page 183 5. Discussion and Conclusions......Page 189 References......Page 190 1. Introduction......Page 192 3. The Method......Page 194 Linear GP with Sequence Generators......Page 195 A register machine as an Algorithmic Chemistry......Page 196 Evolution of an Algorithmic Chemistry......Page 197 Measures......Page 198 4. Description of Experiments......Page 199 Classification — Thyroid Problem......Page 200 Fitness......Page 201 Program Length and Connection Entropy......Page 202 Visualization of an Algorithmic Chemistry......Page 203 6. Summary and Outlook......Page 205 References......Page 206 1. Introduction......Page 208 2. CGP Technology......Page 210 ACGP Flowchart and Algorithm......Page 212 Distribution Statistics......Page 213 4. Illustrative Experiments......Page 214 Off–line Experiment......Page 215 Varying Iteration Length and Regrow......Page 218 Varying Population and Sampling Sizes......Page 220 5. Summary......Page 221 References......Page 223 1. Introduction......Page 224 The simulation......Page 225 Evolutionary process......Page 227 Championship rounds......Page 230 3. Genetic programming parameters......Page 231 4. Experimental design......Page 233 5. Hypotheses......Page 234 6. Discussion of results......Page 238 References......Page 240 1. Introduction......Page 242 2. Cartesian Genetic Programming......Page 243 Evolutionary Algorithm......Page 246 3. Docking......Page 247 Implementation......Page 248 Fitness Function......Page 249 Genome Sizes......Page 250 Output Node......Page 251 5. Experiments Comparing NDEA vs. EA......Page 253 Seeded Libraries......Page 254 Best Filter......Page 256 7. Results with Real Data......Page 257 8. Conclusions......Page 258 References......Page 259 1. INTRODUCTION......Page 262 2. BACKGROUND......Page 263 2.1 Post-Processing Analysis......Page 264 3. EXAMPLE STUDIES......Page 266 3.1 Well-behaved Runs......Page 268 3.2 Under-specified Behavior......Page 275 3.3 Unsupervised Results From Supervised Learning......Page 276 4. CONCLUSIONS......Page 278 REFERENCES......Page 279 1. Introduction......Page 280 Manual incident identification......Page 282 Correcting traffic data......Page 284 Traffic data sets......Page 285 Fitness Measure......Page 286 Evolving first-stage detectors......Page 287 Validating first-stage detectors......Page 289 4. Second Detection Stage......Page 290 Evolving second-stage detectors......Page 291 Validating Second-Stage Detectors......Page 292 5. Detection visualization......Page 295 6. Conclusions......Page 297 References......Page 299 1. Introduction......Page 300 Motivations for Symbolic Regression......Page 301 Problems with Symbolic Regression......Page 302 New Variant: Exploit the Pareto Front......Page 303 Model Performance......Page 304 Model Complexity Measures......Page 305 3. Defining Pareto Optimality......Page 306 Pareto Performance Metrics......Page 307 4. Pareto Exploitation: User Selection......Page 308 Algorithm Objectives......Page 309 The ParetoGP Algorithm......Page 310 Practitioner Comments......Page 311 6. ParetoGP Algorithm Performance......Page 312 Major Improvements Over Classical GP......Page 313 Obvious Extensions......Page 314 References......Page 315 1. Introduction......Page 318 2. ST5 Mission Antenna Requirements......Page 319 3. Evolved Antenna Design......Page 320 4. EA Run Setup......Page 325 6. Results Analysis......Page 326 Acknowledgments......Page 328 References......Page 329 Index......Page 334 The work described in this book was first presented at the Second Workshop on Genetic Programming, Theory and Practice, organized by the Center for the Study of Complex Systems at the University of Michigan, Ann Arbor, 13-15 May 2004. The goal of this workshop series is to promote the exchange of research results and ideas between those who focus on Genetic Programming (GP) theory and those who focus on the application of GP to various re- world problems. In order to facilitate these interactions, the number of talks and participants was small and the time for discussion was large. Further, participants were asked to review each other's chapters before the workshop. Those reviewer comments, as well as discussion at the workshop, are reflected in the chapters presented in this book. Additional information about the workshop, addendums to chapters, and a site for continuing discussions by participants and by others can be found at http://cscs.umich.edu:8000/GPTP-20041. We thank all the workshop participants for making the workshop an exciting and productive three days. In particular we thank all the authors, without whose hard work and creative talents, neither the workshop nor the book would be possible. We also thank our keynote speakers Lawrence ("Dave") Davis of NuTech Solutions, Inc., Jordan Pollack of Brandeis University, and Richard Lenski of Michigan State University, who delivered three thought-provoking speeches that inspired a great deal of discussion among the participants. Geometry is the cornerstone of computer graphics and computer animation, and provides the framework and tools for solving problems in two and three dimensions. This may be in the form of describing simple shapes such as a circle, ellipse, or parabola, or complex problems such as rotating 3D objects about an arbitrary axis. Geometry for Computer Graphics draws together a wide variety of geometric information that will provide a sourcebook of facts, examples, and proofs for students, academics, researchers, and professional practitioners. The book is divided into 4 sections: the first summarizes hundreds of formulae used to solve 2D and 3D geometric problems. The second section places these formulae in context in the form of worked examples. The third provides the origin and proofs of these formulae, and communicates mathematical strategies for solving geometric problems. The last section is a glossary of terms used in geometry. "Genetic programming theory and practice II explores the emerging interaction between theory and practice in the cutting-edge, machine learning method of Genetic Programming (GP). The contributions developed from a second workshop at the University of Michigan's Center for the Study of Complex Systems where leading international genetic programming theorists from major universities and active practitioners from leading industries and businesses met to examine how GP theory informs practice and how GP practice impacts GP theory."--Résumé de l'éditeur