Communications of the ACM
Home/Magazine Archive/November 1999 (Vol. 42, No. 11)/Evolutionary Computation For Discovery/Full Text
Communications of the ACM
Evolutionary Computation For Discovery
It sounds a bit strange to use the words "evolution" and "discovery" together. We think of evolution as a slow, incremental process of gradual change and discovery more in terms of abrupt "Eureka!" events. And yet there is at least one arena in which these two notions fit hand-in-glove: the use of evolutionary computation techniques to facilitate and automate important aspects of discovery in science and engineering. Space constraints do not permit a comprehensive survey of the wide variety of fascinating work in this area. Rather, this article will simply illustrate the use of evolutionary techniques for discovery by looking at the details of a few interesting examples.
The term "evolutionary computation" refers to the use of evolutionary algorithms to solve difficult computational problems. Genetic Algorithms (GAs) are the most well known and most widely used evolutionary algorithms. However, there are other species of evolutionary algorithms, such as evolution strategies and evolutionary programming which are also used quite effectively. Today, the field is a large, vibrant community of scientists and engineers developing a wide variety of new evolutionary algorithms and applications. There are many good books and Web-based materials on evolutionary computation.
Our focus in this article is the use of evolutionary computation to facilitate and automate discovery. To see how this might be accomplished, think of the discovery process as one of exploring large, complex spaces in search of interesting objects that have particularly desirable or unusual properties. Humans, when faced with such tasks, generally explore only a limited number of regions due to both time constraints and a rather strong set of conceptual biases as to how and where to explore. Automated tools capable of exploring additional parts of the space guided by useful computational biases offer the possibility of discovering new and interesting objects.
To illustrate these ideas we look at several examples of spaces being successfully explored using evolutionary techniques resulting in an increasing number of interesting discoveries.
Discovering New Heuristics
Many of the interesting problems in areas such as design, manufacturing, and scheduling have at their core one or more difficult combinatorial optimization problems to be solved. Invariably, these are known to be NP-hard problems and so the focus is on finding good heuristics capable of producing acceptable solutions quickly. These heuristics are typically developed by humans based on insights into the structure and properties of a particular domain. Successful heuristics are incorporated into working procedures and tools.
However, the world is not static. New configurations, new components, or new constraints appear on a regular basis that can significantly change problem characteristics and reduce the effectiveness of existing heuristics. On the other hand, the time and cost involved in developing new heuristics can be quite significant. One strategy for reducing such development costs is to use an evolutionary algorithm to automate the process of developing new heuristics.
Dave Davis of Tica Technologies and Tony Cox of Cox Associates have collaborated for a number of years on GA applications for difficult problems in telecommunications network design. Both the capabilities of and demands on telecommunications equipment are constantly changing and, as a consequence, heuristics for NP-hard network design problems are not only difficult to develop, but can quickly become outdated. Davis and Cox have been successful in using GAs to produce alternative network designs that typically reduce overall costs by factors of 1020%. The resulting designs have quite different properties than human-generated designs, and have served as a generator of new design heuristics in the following way. In studying the GA-generated designs to understand better how such significant cost savings were achieved, important insights have been obtained that can then be incorporated into design methodologies.
For example, in one case involving backhaul networks [2], it was immediately clear that the GA-produced networks were exploiting two important cost-saving opportunities missed by human designers: a loophole in the tariff structure that shifted some of the cost to other carriers, and more emphasis on exploiting existing underutilized capacity in the network even if that resulted in longer routing paths. Such insights continue to be generated and have resulted in the perception of GAs playing a key role in innovative network design.
Dave Schaffer and Larry Eshelman at Philips Electronics have been using GAs successfully to evolve effective heuristics in an even more direct fashion [6]. Philips has developed highly automated assembly lines for producing printed circuit boards, a key element of which is a machine with up to 16 independent placement arms for mounting individual components on a circuit board. For a particular circuit board, decisions regarding the number of such machines or the assignment of tasks to individual arms to achieve optimal throughput is known as NP-hard. In this case, the overall scheduling problem is so difficult that even the best of the hand-constructed heuristics have only resulted in below-acceptable levels of performance.
Schaffer and Eshelman were able to significantly improve on this situation by carefully designing a parameterized space of heuristics to be explored by a GA. Using this approach they have been able to discover heuristics which significantly outperform existing heuristics and result in acceptable levels of throughput. In some cases it was obvious what exploitable properties of a circuit board and the mounting machines the GA has discovered, providing feedback to the designers. In other cases no obvious interpretations exist. In all cases their system continues to serve as the best source of heuristics for this complex scheduling task.
Tactics and Strategies
An intriguing and unexpectedly useful application of evolutionary techniques is a design testing tool. Complex artifacts such as controllers for autonomous vehicles must undergo rigorous testing and certification before they can be fielded. Typically, test engineers spend a good deal of time and energy devising complex scenarios to test and evaluate such systems. However, it is quite possible that hand-constructed test scenarios can have significant gaps, particularly when faults are due to complex combinations of events.
An interesting approach to improving the testing process is to develop a language for describing testing scenarios that permits an evolutionary algorithm to explore the space of test scenarios written in that language in order to discover new and interesting scenarios which expose design faults. Grefenstette and Schultz have developed a GA-based system for doing so that has proved to be quite effective [6]. For example, the GA-based tester discovered scenarios fairly quickly that resulted in a (simulated) autonomous underwater vehicle crashing into the bottom of the ocean floor because of the inability of the onboard controller to deal simultaneously with steering and ballast problems. The success of this GA-based testing has lead to its incorporation into standard testing procedures, and is being seriously considered for other programs including NASA unmanned space projects.
Similar sorts of discoveries are becoming routine in the field of evolutionary robotics. Here, the notion is to provide high-level goals and objectives, and automate the process of discovering the strategies necessary to achieve these goals. A nice example of this is the Samuel system, a GA-based rule learning system used to evolve surprisingly complex and interesting robot behaviors [7].
For example, one of the tasks to be learned was how to find the way to a distant rendezvous point through fairly narrow openings. The onboard sonar sensors were such that the narrow openings could only be seen by looking directly at them from a fairly close range. In general, this would require a fairly complex series of maneuvers involving stopping, starting, turning, and switching from forward to reverse, not unlike what we might do when maneuvering a car into a tight spot. However, this particular robot had the property that it could move a bit faster and more flexibly in reverse. The GA-based rule learner discovered how to exploit this property for this particular task by evolving an elegant reverse sweep tactic for efficiently aligning itself in front of one of the narrow openings.
Much more difficult are tasks involving multiple robots that interact in cooperative ways to solve problems. However, there is growing evidence that evolutionary techniques can aid in the discovery of multiagent strategies as well.
Conclusions
I've only been able to touch on a few examples of evolutionary discoveries. There are many other equally interesting developments, such as the discovery of new features for solving difficult image understanding problems [1], the use of genetic programming [4] to discover novel Lisp programs, the use of evolution strategies to invent new optical filter designs [5], and the use of evolutionary programming for drug design [3]. Readers are encouraged to dig deeper by taking advantage of the wide variety of books and Web-based materials available. A good starting point is www.aic.nrl.navy.mil/galist.
The field of evolutionary computation has had a fairly strong focus on optimization problems posed in terms of searching spaces in which the objects themselves were fairly simple linear structures (for example, a fixed set of N parameters). However, knowledge in the form of theories, heuristics, and so on, has a much more complex syntactic and semantic structure, and much less well-defined notions of optimality associated with it.
What the examples in this article suggest is it is possible to use evolutionary techniques to explore spaces involving objects of significantly richer structure than fixed-length linear vectors as well as discover interesting and useful entities. As we continue to develop and refine these techniques, they will become an increasingly important tool for automating the discovery process in a wide variety of domains.
References
1. Bala, J., De Jong, K., Huang, J., Vafaie, H., and Wechsler, H. Using learning to facilitate the evolution of features for recognizing visual concepts. Evolution. Comput. 4, 3 (Fall, 1996), 297312.
2. Cox, L., Davis, L. Lu, L., Orvosh, D., Sun, X., and Sirovica, D. Reducing the costs of backhaul networks for pcs companies using genetic algorithms. Heurist. 2, 1 (Spring, 1996), 116.
3. Gehlhaar, D., Verkhivker, G., Rejto, P., Sherman, C., Fogel, D., Fogel, L., and Freer, S. Molecular recognition of the inhibiter ag-1343 by hiv-1 protease: Conformationally flexible docking by evolutionary programming. Chem. Biol. 2, 5 (May 1995), 317324.
4. Koza, J. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Bradford Books, Cambridge, Mass., 1992.
5. Rechenberg, I. Evolutionsstrategie '94. Frommann-Holzboog, Stuttgart, Germany, 1994.
6. Schaffer, J. Application of a genetic algorithm to finding high-performance configurations for surface mount device assembly lines. In Handbook of Evolutionary Computation, T. Bäck, D. Fogel, and Z. Michalewicz, Eds. Oxford University Press, New York, 1997.
7. Schultz, A., Grefenstette, J., and Adams, W. Robo-shepherd: Learning complex robotic behaviors. In Proceedings of the International Symposium on Robotics and Automation. (Montepellier, France, May 2830, 1996). M. Jamshidi, F. Pin, and P. Dauchez, Eds. ASME Press, New York, 1996, pp. 763768.
8. Schultz, A., Grefenstette, J., and De Jong, K. Learning to break things: Adaptive testing of intelligent controllers. In Handbook of Evolutionary Computation, T. Bäack, D. Fogel, and Z. Michalewicz, Eds. Oxford University Press, New York, 1997.
©1999 ACM 0002-0782/99/1100 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 1999 ACM, Inc.
No entries found