Genetic programming IV : routine human-competitive machine intelligence / John R. Koza ... [and others].

Format:

Book

Contributor:

Koza, John R.

Series:

Genetic programming series

Language:

English

Subjects (All):

Genetic programming (Computer science).

Physical Description:

xxviii, 590 pages : illustrations ; 25 cm + 1 DVD (4 3/4 in.)

Other Title:

Genetic programming four

Genetic programming 4

Place of Publication:

Boston : Kluwer Academic Publishers, [2003]

Summary:

Genetic Programming IV: Routine Human-Competitive Machine Intelligence presents the application of GP to a wide variety of problems involving automated synthesis of controllers, circuits, antennas, genetic networks, and metabolic pathways. The book describes fifteen instances where GP has created an entity that either infringes or duplicates the functionality of a previously patented 20th-century invention, six instances where it has done the same with respect to post-2000 patented inventions, two instances where GP has created a patentable new invention, and thirteen other human-competitive results. The book additionally establishes:

GP now delivers routine human-competitive machine intelligence

GP is an automated invention machine.

GP can create general solutions to problems in the form of parameterized topologies.

GP has delivered qualitatively more substantial results in synchrony with the relentless iteration of Moore's Law.

Contents:

1.1 Genetic Programming Now Routinely Delivers High-Return Human-Competitive Machine Intelligence 3

1.1.1 What We Mean by "Human-Competitive" 3

1.1.2 What We Mean by "High-Return" 4

1.1.3 What We Mean by "Routine" 5

1.1.4 What We Mean by "Machine Intelligence" 6

1.1.5 Human-Competitiveness of the Results Produced by Genetic Programming 7

1.1.6 High-Return of the Results Produced by Genetic Programming 10

1.1.7 Routineness of the Results Produced by Genetic Programming 14

1.1.8 Machine Intelligence 15

1.2 Genetic Programming Is an Automated Invention Machine 15

1.2.1 The Illogical Nature of Invention and Evolution 19

1.2.2 Overcoming Established Beliefs 20

1.2.3 Automating the Invention Process 21

1.2.4 Patentable New Inventions Produced by Genetic Programming 22

1.3 Genetic Programming Can Automatically Create Parameterized Topologies 23

1.4 Historical Progression of Qualitatively More Substantial Results Produced by Genetic Programming in Synchrony with Increasing Computer Power 25

2 Background on Genetic Programming 29

2.1 Preparatory Steps of Genetic Programming 29

2.2 Executional Steps of Genetic Programming 31

2.2.1 Example of a Run of Genetic Programming 34

2.3 Advanced Features of Genetic Programming 38

2.3.1 Constrained Syntactic Structures 38

2.3.2 Automatically Defined Functions 39

2.3.3 Automatically Defined Iterations, Automatically Defined Loops, Automatically Defined Recursions, and Automatically Defined Stores 40

2.3.4 Program Architecture and Architecture-Altering Operations 40

2.3.5 Genetic Programming Problem Solver 41

2.3.6 Developmental Genetic Programming 41

2.3.7 Computer Code for Implementing Genetic Programming 42

2.4 Main Points of Four Books on Genetic Programming 42

2.5 Sources of Additional Information about Genetic Programming 45

3 Automatic Synthesis of Controllers 49

3.2 Design Considerations for Controllers 52

3.3 Representation of a Controller by a Block Diagram 53

3.4 Possible Techniques for Designing Controllers 58

3.4.1 Search by Hill Climbing 59

3.4.2 Search by Gradient Methods 60

3.4.3 Search by Simulated Annealing 61

3.4.4 Search by Genetic Algorithm and Genetic Programming 61

3.4.5 Previous Work on Controller Synthesis by Means of Genetic and Evolutionary Computation 62

3.4.6 Possible Approaches to Automatic Controller Synthesis Using Genetic Programming 62

3.5 Our Approach to the Automatic Synthesis of the Topology and Tuning of Controllers 64

3.5.1 Repertoire of Functions 65

3.5.2 Repertoire of Terminals 67

3.5.3 Representing the Plant 67

3.5.4 Automatically Defined Functions 68

3.5.5 Three Approaches for Establishing Numerical Parameter Values 69

3.5.6 Constrained Syntactic Structure for Program Trees 73

3.6 Additional Representations of Controllers 73

3.6.1 Representation of a Controller by a Transfer Function 73

3.6.2 Representation of a Controller as a LISP Symbolic Expression 74

3.6.3 Representation of a Controller as a Program Tree 74

3.6.4 Representation of a Controller in Mathematica 75

3.6.5 Representation of a Controller and Plant as a Connection List 75

3.6.6 Representation of a Controller and Plant as a SPICE Netlist 78

3.7 Two-Lag Plant 87

3.7.1 Preparatory Steps for the Two-Lag Plant 88

3.7.2 Results for the Two-Lag Plant 102

3.7.3 Human-Competitiveness of the Result for the Two-Lag Plant Problem 111

3.7.4 AI Ratio for the Two-Lag Plant Problem 112

3.8 Three-Lag Plant 113

3.8.1 Preparatory Steps for the Three-Lag Plant 114

3.8.2 Results for the Three-Lag Plant 115

3.8.3 Routineness for the Three-Lag Plant Problem 119

3.8.4 AI Ratio for the Three-Lag Plant Problem 119

3.9 Three-Lag Plant with a Five-Second Delay 120

3.9.1 Preparatory Steps for the Three-Lag Plant with a Five-Second Delay 120

3.9.2 Results for the Three-Lag Plant with a Five-Second Delay 122

3.9.3 Routineness for the Three-Lag Plant with a Five-Second Delay 123

3.9.4 AI Ratio for the Three-Lag Plant with a Five-Second Delay 123

3.10 Non-Minimal-Phase Plant 125

3.10.1 Preparatory Steps for the Non-Minimal-Phase Plant 125

3.10.2 Results for the Non-Minimal Phase Plant 125

3.10.3 Routineness for the Non-Minimal Phase Plant Problem 127

3.10.4 AI Ratio for the Non-Minimal Phase Plant Problem 127

4 Automatic Synthesis of Circuits 129

4.1 Our Approach to the Automatic Synthesis of the Topology and Sizing of Circuits 131

4.1.1 Evolvable Hardware 134

4.2 Searching for the Impossible 135

4.2.1 Preparatory Steps for the RC Circuit with Gain Greater than Two 138

4.2.2 Results for the RC Circuit with Gain Greater than Two 142

4.2.3 Routineness of the Transition from a Problem of Controller Synthesis to a Problem of Circuit Synthesis 143

4.2.4 AI Ratio for the RC Circuit with Gain Greater than Two 145

4.3 Reinvention of the Philbrick Circuit 147

4.3.1 Preparatory Steps for the Philbrick Circuit 148

4.3.2 Results for the Philbrick Circuit 150

4.3.3 Human-Competitiveness of the Result for the Philbrick Circuit Problem 151

4.3.4 Routineness for the Philbrick Circuit Problem 152

4.3.5 AI Ratio for the Philbrick Circuit Problem 153

4.4 Circuit for the NAND Function 153

4.4.1 Preparatory Steps for the NAND Circuit 154

4.4.2 Results for the NAND Circuit 157

4.4.3 Human-Competitiveness of the Result for the NAND Circuit Problem 158

4.4.4 Routineness for the NAND Circuit Problem 159

4.4.5 AI Ratio for the NAND Circuit Problem 159

4.5 Evolution of a Computer 159

4.5.1 Preparatory Steps for the Arithmetic Logic Unit 160

4.5.2 Results for the Arithmetic Logic Unit 161

4.5.3 Routineness for the Arithmetic Logic Unit Circuit Problem 161

4.5.4 AI Ratio for the Arithmetic Logic Unit Circuit Problem 162

4.6 Square Root Circuit 162

4.6.1 Preparatory Steps for Square Root Circuit 163

4.6.2 Results for Square Root Circuit 165

4.6.3 Routineness for the Square Root Circuit Problem 168

4.6.4 AI Ratio for the Square Root Circuit Problem 168

4.7 Automatic Circuit Synthesis Without an Explicit Test Fixture 168

4.7.1 Preparatory Steps for the Lowpass Filter Problem Without an Explicit Test Fixture 169

4.7.2 Results for the Lowpass Filter Problem without an Explicit Test Fixture 173

4.7.3 Routineness for the Lowpass Filter Problem without an Explicit Test Fixture 174

4.7.4 AI Ratio for the Lowpass Filter Problem without an Explicit Test Fixture 174

5 Automatic Synthesis of Circuit Topology, Sizing, Placement, and Routing 175

5.1 Our Approach to the Automatic Synthesis of Circuit Topology, Sizing, Placement, and Routing 177

5.1.1 Initial Circuit 177

5.1.2 Circuit-Constructing Functions 178

5.1.3 Component-Creating Functions 179

5.1.4 Topology-Modifying Functions 181

5.1.5 Development-Controlling Functions 186

5.1.6 Developmental Process 186

5.2 Lowpass Filter with Layout 186

5.2.1 Preparatory Steps for the Lowpass Filter with Layout 186

5.2.2 Results for the Lowpass Filter with Layout 188

5.2.3 Human-Competitiveness of the Result for the Lowpass Filter Problem with Layout 195

5.2.4 Routineness of the Transition from a Problem of Circuit Synthesis without Layout to a Problem of Circuit Synthesis with Layout 196

5.2.5 AI Ratio for the Lowpass Filter Problem with Layout 197

5.3 60 dB Amplifier with Layout 197

5.3.1 Preparatory Steps for 60 dB Amplifier with Layout 197

5.3.2 Results for 60 dB Amplifier with Layout 199

5.3.3 Routineness for the 60 dB Amplifier Problem with Layout 202

5.3.4 AI Ratio for the 60 dB Amplifier Problem with Layout 203

6 Automatic Synthesis of Antennas 205

6.1 Our Approach to the Automatic Synthesis of the Geometry and Sizing of Antennas 206

6.2 Illustrative Problem of Antenna Synthesis 207

6.3 Repertoire of Functions and Terminals 209

6.3.1 Repertoire of Functions 209

6.3.2 Repertoire of Terminals 210

6.3.3 Example of the Use of the

Functions and Terminals 211

6.4 Preparatory Steps for the Antenna Problem 212

6.4.1 Program Architecture 212

6.4.2 Function Set 212

6.4.3 Terminal Set 212

6.4.4 Fitness Measure 212

6.4.5 Control Parameters 216

6.5 Results for the Antenna Problem 216

6.6 Routineness of the Transition from Problems of Synthesizing Controllers, Circuits, and Circuit Layout to a Problem of Synthesizing an Antenna 219

6.7 AI Ratio for the Antenna Problem 220

7 Automatic Synthesis of Genetic Networks 221

7.1 Statement of the Illustrative Problem 221

7.2 Representation of Genetic Networks by Computer Programs 223

7.2.1 Repertoire of Functions 223

7.2.2 Repertoire of Terminals 224

7.3 Preparatory Steps 224

7.3.1 Program Architecture 224

7.3.2 Function Set 224

7.3.3 Terminal Set 224

7.3.4 Fitness Measure 224

7.3.5 Control Parameters 225

7.4 Results 225

7.4.1 Routineness of the Transition from Problems of Synthesizing Controllers, Circuits, Circuits With Layout, and Antennas to a Problem of Genetic Network Synthesis 226

7.4.2 AI Ratio for the Genetic Network Problem 227

8 Automatic Synthesis of Metabolic Pathways 229

8.1 Our Approach to the Automatic Synthesis of the Topology and Sizing of Networks of Chemical Reactions 230

8.3 Types of Chemical Reactions 234

8.3.1 One-Substrate, One-Product Reaction 234

8.3.2 One-Substrate, Two-Product Reaction 243

8.3.3 Two-Substrate, One-Product Reaction 244

8.3.4 Two-Substrate, Two-Product Reaction 248

8.4 Representation of Networks of Chemical Reactions by Computer Programs 250

8.4.1 Representation as a Program Tree 250

8.4.2 Representation as a Symbolic Expression 255

8.4.3 Representation as a System of Nonlinear Differential Equations 256

8.4.4 Representation as an Analog Electrical Circuit 259

8.4.5 Flexibility of the Representation 262

8.5 Preparatory Steps 263

8.5.1 Program Architecture 263

8.5.2 Function Set 264

8.5.3 Terminal Set 264

8.5.4 Fitness Measure 264

8.5.5 Control Parameters 267

8.6 Results for the Phospholipid Cycle 267

8.6.1 Routineness of the Transition from Problem of Synthesizing Controllers, Circuits, Circuits with Layout, Antennas, and Genetic Networks to a Problem of Synthesis of a Network of Chemical Reactions 274

8.6.2 AI Ratio for the Metabolic Pathway Problem for the Phospholipid Cycle 275

8.7 Results for the Synthesis and Degradation of Ketone Bodies 275

8.7.1 Routineness for the Metabolic Pathway Problem Involving Ketone Bodies 278

8.7.2 AI Ratio for the Metabolic Pathway Problem Involving Ketone Bodies 278

8.8 Future Work on Metabolic Pathways 278

8.8.1 Improved Program Tree Representation 278

8.8.2 Null Enzyme 278

8.8.3 Minimum Amount of Data Needed 278

8.8.4 Opportunities to Use Knowledge 279

8.8.5 Designing Alternative Metabolisms 279

9 Automatic Synthesis of Parameterized Topologies for Controllers 281

9.1 Parameterized Controller for a Three-Lag Plant 282

9.1.1 Preparatory Steps for the Parameterized Controller for a Three-Lag Plant 283

9.1.2 Results for the Parameterized Controller for a Three-Lag Plant 286

9.1.3 Routineness of the Transition from a Problem Involving a Non-Parameterized Controller to a Problem Involving a Parameterized Controller 290

9.1.4 AI Ratio for the Parameterized Controller for a Three-Lag Plant 291

9.2 Parameterized Controller for Two Families of Plants 291

9.2.1 Preparatory Steps for the Parameterized Controller for Two Families of Plants 292

9.2.2 Results for the Parameterized Controller for Two Families of Plants 296

9.2.3 Human-Competitiveness of the Result for the Parameterized Controller for Two Families of Plants 299

9.2.4 Routineness for the Parameterized Controller for Two Families of Plants 300

9.2.5 AI Ratio for the Parameterized Controller for Two Families of Plants 300

10 Automatic Synthesis of Parameterized Topologies for Circuits 301

10.1 Five New Techniques 301

10.1.1 New NODE Function for Connecting Distant Points 302

10.1.2 Symmetry-Breaking Procedure using Geometric Coordinates 303

10.1.3 Depth-First Evaluation 304

10.1.4 New TWO_LEAD Function for Inserting Two-Leaded Components 305

10.1.5 New Q Transistor-Creating Function 305

10.2 Zobel Network with Two Free Variables 306

10.2.1 Preparatory Steps for the Zobel Network Problem with Two Free Variables 307

10.2.2 Results for the Zobel Network Problem with Two Free Variables 310

10.2.3 Routineness fo the Transition from a Problem Involving a Non-Parameterized Circuit to a Problem Involving a Parameterized Circuit 311

10.2.4 AI Ratio for the Zobel Network Problem with Two Free Variables 312

10.3 Third-Order Elliptic Lowpass Filter with a Free Variable for the Modular Angle 312

10.3.1 Preparatory Steps for the Third-Order Elliptic Lowpass Filter with a Free Variable for the Modular Angle 313

10.3.2 Results for the Lowpass Third-Order Elliptic Filter with a Free Variable for the Modular Angle 318

10.3.3 Routineness for the Lowpass Third-Order Elliptic Filter with a Free Variable for the Modular Angle 324

10.3.4 AI Ratio for the Lowpass Third-Order Elliptic Filter with a Free Variable for the Modular Angle 324

10.4 Passive Lowpass Filter with a Free Variable for the Passband Boundary 324

10.4.1 Preparatory Steps for the Passive Lowpass Filter with a Free Variable for the Passband Boundary 325

10.4.2 Results for the Passive Lowpass Filter with a Free Variable for the Passband Boundary 328

10.4.3 Routineness for the Passive Lowpass Filter with a Free Variable for the Passband Boundary 331

10.4.4 AI Ratio for the Passive Lowpass Filter with a Free Variable for the Passband Boundary 332

10.5 Active Lowpass Filter with a Free Variable for the Passband Boundary 332

10.5.1 Preparatory Steps for the Active Lowpass Filter with a Free Variable for the Passband Boundary 333

10.5.2 Results for the Active Lowpass Filter with a Free Variable for the Passband Boundary 335

10.5.3 Routineness for the Active Lowpass Filter with a Free Variable for the Passband Boundary 339

10.5.4 AI Ratio for the Active Lowpass Filter with a Free Variable for the Passband Boundary 339

11 Automatic Synthesis of Parameterized Topologies with Conditional Developmental Operators for Circuits 341

11.1 Lowpass/Highpass Filter Circuit 342

11.1.1 Preparatory Steps for the Lowpass/Highpass Filter 342

11.1.2 Results for the Lowpass/Highpass Filter 344

11.1.3 Routineness of the Transition from a Parameterized Topology Problem without Conditional Developmental Operators to a Problem with Conditional Developmental Operators 348

11.1.4 AI Ratio for the Lowpass/Highpass Filter Problem 348

11.2 Lowpass/Highpass Filter with Variable Passband Boundary 348

11.2.1 Preparatory Steps for the Lowpass/Highpass Filter with Variable Passband Boundary 349

11.2.2 Results for the Lowpass/Highpass Filter with a Variable Passband Boundary 350

11.2.3 Routineness for the Lowpass/Highpass Filter with a Variable Passband Boundary 357

11.2.4 AI Ratio for the Lowpass/Highpass Filter with a Variable Passband Boundary 357

11.3 Quadratic/Cubic Computational Circuit 358

11.3.1 Preparatory Steps for the Quadratic/Cubic Computational Circuit 358

11.3.2 Results for the Quadratic/Cubic Computational Circuit 360

11.4 A 40/60 dB Amplifier 364

11.4.1 Preparatory Steps for the 40/60 dB Amplifier 364

11.4.2 Results for 40/60 dB Amplifier 366

12 Automatic Synthesis of Improved Tuning Rules for PID Controllers 367

12.1 Test Bed of Plants 371

12.2 Preparatory Steps for Improved PID Tuning Rules 374

12.2.1 Program Architecture 375

12.2.2 Terminal Set 375

12.2.3 Function Set 375

12.2.4 Fitness Measure 375

12.2.5 Control Parameters 376

12.3 Results for Improved PID Tuning Rules 376

12.4 Human-Competitiveness of the Results for the Improved PID Tuning Rules 382

12.5 Routineness of the Transition from Problems Involving Parameterized Topologies for Controllers to a Problem Involving PID Tuning Rules 385

12.6 AI Ratio for the Improved PID Tuning Rules 385

13 Automatic Synthesis of Parameterized Topologies for Improved Controllers 387

13.1 Preparatory Steps for Improved General-Purpose Controllers 387

13.1.1 Function Set 388

13.1.2 Terminal Set 388

13.1.3 Program Architecture 389

13.1.4 Fitness Measure 389

13.1.5 Control Parameters 390

13.2 Results for Improved General-Purpose Controllers 390

13.2.1 Results for First Run for Improved General-Purpose Controllers 390

13.2.2 Results for Second Run for Improved General-Purpose Controllers 398

13.2.3 Results for Third Run for Improved General-Purpose Controllers 402

13.3 Human-Competitiveness of the Results for the Improved General-Purpose Controllers 411

13.4 Routineness for the Improved General-Purpose Controllers 412

13.5 AI Ratio for the Improved General-Purpose Controllers 412

14 Reinvention of Negative Feedback 413

14.1 Genetic Programming Takes a Ride on the Lackawanna Ferry 414

14.1.1 Fitness Measure 414

14.1.2 Initial Circuit, Function Set, Terminal Set, and Control Parameters 415

14.2 Results for the Problem of Reducing Amplifier Distortion 415

14.3 Human-Competitiveness of the Result for the Problem of Reducing Amplifier Distortion 418

14.4 Routineness for the Problem of Reducing Amplifier Distortion 419

14.5 AI Ratio for the Problem of Reducing Amplifier Distortion 419

15 Automated Reinvention of Six Post-2000 Patented Circuits 421

15.1 The Six Circuits 423

15.1.1 Low-Voltage Balun Circuit 423

15.1.2 Mixed Analog-Digital Variable Capacitor 423

15.1.3 Voltage-Current Conversion Circuit 423

15.1.4 Low-Voltage High-Current Transistor Circuit 424

15.1.5 Cubic Function Generator 424

15.1.6 Tunable Integrated Active Filter 426

15.2 Uniformity of Treatment of the Six Problems 426

15.3 Preparatory Steps for the Six Post-2000 Patented Circuits 428

15.3.1 Initial Circuit 428

15.3.2 Program Architecture 433

15.3.3 Function Set 433

15.3.4 Terminal Set 434

15.3.5 Fitness Measure 435

15.3.6 Control Parameters 444

15.4 Results for the Six Post-2000 Patented Circuits 444

15.4.1 Results for Low-Voltage Balun Circuit 444

15.4.2 Results for Mixed Analog-Digital Variable Capacitor 451

15.4.3 Results for High-Current Load Circuit 454

15.4.4 Results for Voltage-Current Conversion Circuit 458

15.4.5 Results for Cubic Function Generator 461

15.4.6 Tunable Integrated Active Filter 466

15.5 Commercial Practicality of Genetic Programming for Automated Circuit Synthesis 478

15.6 Human-Competitiveness of the Results for the Six Post-2000 Patented Circuits 481

15.7 Routineness for the Six Post-2000 Patented Circuits 481

15.8 AI Ratio for the Six Post-2000 Patented Circuits 482

16 Problems for Which Genetic Programming May Be Well Suited 483

16.1 Characteristics Suggesting the Use of the Genetic Algorithm 483

16.2 Characteristics Suggesting the Use of Genetic Programming 484

16.2.1 Discovering the Size and Shape of the Solution 484

16.2.2 Reuse of Substructures 486

16.2.3 The Number of Substructures 495

16.2.4 Hierarchical References among the Substructures 496

16.2.5 Passing Parameters to Substructures 497

16.2.6 Type of Substructures 499

16.2.7 Number of Arguments Possessed by Substructures 500

16.2.8 The Developmental Process 500

16.2.9 Parameterized Topologies Containing Free Variables 504

16.3 Characteristics Suggesting the Use of Genetic Methods 505

16.3.1 Non-Greedy Nature of Genetic Methods 505

16.3.2 Recombination in Conjunction with the Population in Genetic Methods 506

17 Parallel Implementation and Computer Time 515

17.1 Computer Systems Used for Work in This Book 516

17.1.1 Alpha Parallel Computer System 516

17.1.2 Pentium Parallel Computer System 517

18 Historical Perspective on Moore's Law and the Progression of Qualitatively More Substantial Results Produced by Genetic Programming 523

18.1 Five Computer Systems Used in 15-Year Period 523

18.2 Qualitative Nature of Results Produced by the Five Computer Systems 524

18.3 Effect of Order-of-Magnitude Increases in Computer Power on the Qualitative Nature of the Results Produced by Genetic Programming 526

19.1 Genetic Programming Now Routinely Delivers High-Return Human-Competitive Machine Intelligence 529

19.2 Genetic Programming Is an Automated Invention Machine 530

19.3 Genetic Programming Can Automatically Create Parameterized Topologies 530

19.4 Genetic Programming Has Delivered Qualitatively More Substantial Results in Synchrony with Increasing Computer Power 531

Appendix A Functions and Terminals 533

Appendix B Control Parameters 539

Appendix C Patented or Patentable Inventions Generated by Genetic Programming 551.

Notes:

Includes bibliographical references (pages 555-573) and index.

ISBN:

1402074468

OCLC:

51817183