next up previous
Next: Part II: Theory Up: The work in this Previous: The work in this

Part I: Applications

Perhaps the most dramatic change in the field since the previous volumes of Advances has been the growth in the number of real-world applications. This is an important sign of the maturity of the field; early GP work included many applications, but many of these were simple and it was rare that the applied work solved hard problems that workers in the application areas really needed to have solved. In several recent cases, however, GP researchers have teamed up with engineers or researchers in other fields and the resulting teams have applied GP tools to significant real-world problems. In other cases the transition to real-world applications has been made without the aid of GP specialists, a sign that GP technology is ready for more widespread use. We chose to start this volume with the applications in part because we would like to show those outside GP that it is feasible to apply it to outstanding problems in their fields. We also feel that GP researchers working on theoretical issues or on extensions to GP technique should keep one eye trained on the real-world uses of GP.

Chapter 2, ``An Automatic Software Re-Engineering Tool based on Genetic Programming'' by Conor Ryan and Laur Ivan, attacks the difficult and commercially important problem of automatically transforming serial programs into functionally identical parallel programs written in a C-like syntax. The authors argue that their Paragen system extracts parallelism at least as well as human experts in much less time, and that it serves an important need as no other fully automatic parallelization techniques are currently available. They also argue that GP is particularly well-suited to this application area because it is not only able to spot and exploit code patterns but also to explore the possibilities of moving and transforming code in ways that humans would not.

In Chapter 3, ``CAD Surface Reconstruction from Digitized 3D Point Data with a Genetic Programming/Evolution Strategy Hybrid'' by Robert E. Keller, Wolfgang Banzhaf, Jörn Mehnen and Klaus Weinert, we see GP applied in another commercially important area. In many modern manufacturing processes, after development, prototypical physical workpieces are digitized to obtain their descriptions. Unfortunately, a digitized representation is not sufficient as a computer-aided design object and it is necessary to derive from it an appropriate construction-oriented CAD surface representation before it can be provided as input to rapid-prototype systems or used in other design or construction processes. The authors present a system, SURREAL, that uses a hybrid of GP and Evolution Strategies [Rechenberg, 1994] to perform the requisite ``surface reconstruction'' task. SURREAL simultaneously performs pattern recognition and structure evolution. It exploits the variable-length representation of genetic programming to explore search spaces without pre-defined dimensionality. The authors note that SURREAL has potential uses beyond the obvious manufacturing applications; for example, it should perform better than existing reconstruction approaches for highly irregular surfaces such as human faces, with possible applications in cosmetics, medicine, entertainment, and person identification.

Carolyn Penstein Rosé provides a promising new GP-based approach to a classical artificial intelligence problem in Chapter 4, ``A Genetic Programming Approach for Robust Language Interpretation.'' The problem of robust language interpretation is to construct a representation of the meaning of a sentence which is independent of its words by using a predefined set of meaning-encoded primitives in relation to each other. A parsing grammar first handles the task, but, because it is necessarily incomplete, it fails on extra-grammatical sentences that fall outside its domain producing only partially-parsed sub-expressions. ROSE uses genetic programming to search the space of possible relationships between the meaning representation of these grammatical sub-expressions in order to construct an accurate and complete representation of the entire sentence. The ROSE system depends on GP to be efficient. Using GP obviates the need for an expensive, maximally flexible parser and, as a repair strategy, it avoids the need for hand-coded repair rules. Overall, the author states that ROSE ``yields a significantly better time/quality trade-off than previous non-GP approaches''.

In Chapter 5, ``Time Series Modeling Using Genetic Programming: An Application to Rainfall-runoff Models,'' P. A. Whigham and P. F. Crapper apply a novel grammar-based variant of GP to a hydrological modeling problem. Their system discovers rainfall-runoff relationships for two different catchments on different continents and with different climates. They show it is more robust than previous methods when rainfall-runoff correlation are poor and when the assumptions built into other methods do not hold. The authors also note that while other machine learning techniques have been applied to rainfall-runoff modeling, their GP-based system produces models that are more readily interpretable in terms of processes and behaviors used in the application area.

In Chapter 6, ``Automatic Synthesis, Placement, and Routing of Electrical Circuits by Means of Genetic Programming,'' John R. Koza and Forrest H Bennett III present the latest enhancements to their work on GP applications to electrical circuit design. In this chapter they demonstrate for the first time how a single GP process can automatically create the topology, component sizing, placement, and routing of analog electrical circuits, a process that normally requires several human engineers with specialized design skills. In addition to a general description of their technique they provide a detailed example of the evolution of an analog low pass filter. They also point out that GP has now produced many results that are competitive with human-produced results, including many for which patents have previously been awarded, and they discuss GP as an ``invention machine''.

Chapter 7, ``Quantum Computing Applications of Genetic Programming'' by Lee Spector, Howard Barnum, Herbert J. Bernstein and Nikhil Swamy, presents work on applying GP to computers that don't yet exist--``quantum computers'' that will manipulate the states of atomic-scale objects to gain efficiencies not achievable with digital computers based on classical physics. Even though large-scale quantum computers do not yet exist GP can be used in conjunction with a simulated quantum computer both to discover new quantum computer algorithms and to help explore the the potential power of quantum computing. The authors demonstrate the evolution of several better-than-classical quantum algorithms including both previously discovered and new examples.

next up previous
Next: Part II: Theory Up: The work in this Previous: The work in this
Bill Langdon