 |
 |
 |
 |
| |
|||||
|
|
 |
By Lashon Booker Over the past two decades, computational algorithms based on Charles Darwin’s principles of evolution have developed from academic curiosities into practical and effective tools for scientists and engineers. The techniques of evolutionary computation have become increasingly widespread and effective in finding solutions for search, design, and optimization problems that have proven difficult to solve by more conventional methods. Because new computing paradigms may be better suited for implementing evolutionary algorithms and because these algorithms are capable of generating solutions that are often novel and surprising, it is likely that evolutionary computation will be a key technology facilitating innovative design and problem solving in the 21st century. 
Biologically Inspired Algorithms Evolutionary computation refers to a class of general-purpose search algorithms based on the principles of biological evolution and natural selection. These algorithms implement biologically inspired computations that manipulate a population of candidate solutions (the “parents”) to generate new variations (the “offspring”). At each step (or “generation”) in the computation, the least promising candidates in the population are discarded and replaced by the new candidates (“survival of the fittest”). The process continues until a satisfactory solution to the problem has been found. The collection of techniques in use today is derived from three research paradigms that arose independently in the late 1950s and early 1960s. Genetic algorithms (and a subsequent variant called genetic programming) exploit the inheritance of genetic traits, emphasizing the importance of recombination and the adaptive properties of populations. Evolutionary strategies focus on the inheritance of behavior traits rather than genetic traits, and emphasize the key role that mutation plays in evolutionary search. Evolutionary programming also emphasizes the inheritance of behavior traits, but at the level of species rather than at the level of individuals. The distinctions between these paradigms have blurred in recent years, and the more inclusive term, evolutionary computation, is often used to emphasize that the various algorithms share many features. The power of evolutionary computation algorithms is derived from a very simple heuristic assumption: the best solutions to a problem will be found in regions of the search space containing relatively high proportions of good solutions and these key regions can be identified by strategic and robust sampling of the space. In practice, these algorithms have proven strongly capable of finding improvements in complex, nonlinear search spaces. They have been applied to a wide variety of search and optimization problems in government and industry, and are becoming increasingly available as standard features in COTS tools for engineering design and optimization applications. MITRE has applied these techniques successfully to several sponsor problems, including adaptive route planning for finding mobile targets and improving the performance of air traffic flow management strategies. Two recent trends are likely to enhance the role that evolutionary computation will play in the application of computing power to solve complex problems in the 21st century. First, the methods of evolutionary computation appear to be well aligned with the development of such new computing paradigms as DNA computing. Second, evolutionary techniques are becoming increasingly effective at finding innovative solutions that open the eyes of engineers to possibilities they might not have otherwise considered. The remainder of this article discusses these two trends. DNA Computing DNA computing (DNAC) refers to the use of biological molecules, primarily deoxyribonucleic acid (DNA) and ribonucleic acid (RNA), for computational purposes. A computation with biological molecules is carried out by using enzymes and techniques from molecular biology to apply a sequence of modifications to molecules in a test tube. Each modification corresponds to a step in the overall computation. Biological molecules provide a massively parallel substrate for computation. A test tube of DNA can include as many as 1021 DNA molecules, each with the potential to encode up to 400 bits of data. This corresponds to a storage density of 1 bit per cubic nanometer, a substantial increase over the density of 1 bit per 1012 cubic nanometers available in existing storage media such as video tape. Because every chemical operation used to manipulate the molecules is applied to all of the DNA in the container simultaneously, each molecule can be viewed as a separate processor in a multi-processor computing device. Though a chemical reaction can take minutes or hours to perform, the massively parallel processing power and memory available at the molecular level result in computations involving millions more operations per second than is possible with current state-of-the-art supercomputing technology. DNAC devices don’t appear to be suitable for applications involving simple problems or requiring quick responses, but they do hold promise for tackling large problems that are well beyond the reach of existing supercomputers. In order to realize this potential, better algorithms need to be developed for DNAC devices. The algorithms available today solve problems using brute force search. Under the assumption that a population of 1021 candidate solutions to a problem will always contain the optimal solution, current algorithms simply use filtering techniques to discard the molecules representing suboptimal solutions. Clearly, these algorithms quickly become infeasible as the size of the problem grows. In realistic combinatorial problems, it is not uncommon to encounter search spaces containing more than 10100 potential solutions. Even given the massive parallelism of DNAC operations, more efficient algorithms are needed to solve such problems. Genetic algorithms are a particularly attractive candidate to fill this void. Population sizes that are billions of times larger than those available on conventional computers should make the parallel search conducted by genetic algorithms much more efficient. Moreover, since genetic algorithms are designed to work with probabilistic operators, the algorithms’ performance is not likely to be degraded by the occasional errors that are common in DNAC operations. Techniques in molecular biology known as “in vitro evolution” provide a set of laboratory procedures that can extract molecules with unique functional properties from large pools of random molecular sequences. The computational steps involved are remarkably similar to the operations needed to implement a genetic algorithm. Research is currently underway to implement these algorithms for DNAC devices and determine if the potential advantages can be realized in practice. Innovative Solutions Evolutionary computation is being used more frequently as an approach to developing more efficient, innovative, and in some cases patented designs for all kinds of products ranging from engines and structural trusses to antennas and light bulbs. As research advances increase the repertoire of problems that can be approached in this way, evolutionary computation will become a valuable tool for stimulating the imaginations and ingenuity of human engineers as they formulate advanced concepts or look for new designs. Beyond designing new artifacts, there is even the intriguing possibility of using evolutionary computation to help discover how to use those artifacts more effectively. Researchers at Boeing recently developed a prototype that suggests this idea is feasible. They used simple, evolutionary techniques in a simulation to automatically discover new tactical maneuvers for agile fighter aircraft in a carefully restricted set of combat scenarios. MITRE research is advancing the state of the art in this area by developing new, more robust techniques for discovering innovative behaviors and operational concepts automatically from experience in a simulation. Doing this involves running behavior models in a simulation and gathering information about the performance. In the Automated Discovery of Innovative Tactics and Behaviors research project, MITRE investigators are pioneering a new approach that combines insights from three technical areas: evolutionary computation, complex adaptive systems, and reinforcement learning. This approach has the potential to lead to practical algorithms that can be applied to a broad range of challenging applications. Eventually, the products of this research should enable MITRE sponsors to conduct more careful investigation and testing of new systems and concepts in such ambitious initiatives as the Army Future Combat Systems. For more information, please contact Lashon Booker using the employee directory. |
Solutions That Make a Difference.® |
|
|
