N91- 4o50 GENETIC ALGORITHMS Lui Wang Steven E. Bayer Software Technology Branch Engineering Technology Group Lyndon B. Johnson Space Center The MITRE Corporation National Aeronautics and Space Administration 1120 NASA Road One, Suite 600 Houston, TX 77058 Houston, TX 77058 [email protected] bayer@ mpad.span.nasa.gov ABSTRACT Genetic algorithms are highly parallel, mathematical, adaptive search procedures (i.e., problem-solving methods) based loosely on the processes of natural genetics and Darwinian survival of the fittest. This paper introduces basic genetic algorithm concepts, discusses genetic algorithm applications, and presents results from a project to develop a software tool that will enable the widespread use of genetic algorithm technology. INTRODUCTION Background Genetic algorithms (GAs) were pioneered by John Holland in his research on adaptation in natural and artificial systems (1). This research outlined a logical theory of adaptive systems. In essence, biological adaptive systems strive to optimize single individuals or entire species for specific environments to increase the chance of survival. Holland simulated the methods used when biological systems adapt to their environment in computer software models-the genetic algorithms-to solve optimization and machine learning problems. The following paragraphs briefly discuss two types of adaptation strategies which are observed in many biological systems and inspired the basic framework of genetic algorithms. Adaotation. One form of adaptation pertains to the way an individual changes within its environment to promote survival. Examples include the development of antibodies specific to certain diseases, or the enlargement of muscles needed for daily activities. The way we learn, and the neural changes that accompany learning, is another example of how an individual adapts within its environment. The effects of this form of adaptation are not imprinted on the genome (the genetic makeup of a species); that is, they are not passed on from generation to generation. On the other hand, individual adaptation does promote the survival of the individual within an environment-survival of the fittest-and enhances that individual's net reproductive advantage through a natural selection where fitter members of a population are more likely to reproduce. All species have used adaptive search for millions of years, through an evolutionary search process, to improve the way a species lives and survives within its environment. Therefore, adaptation also refers to evolution and modification of an entire species to fit its environment. This is the process of making a species environmentally fit. An appropriate example can be seen in the way many plant species have evolved their flower to resemble a female bee or wasp that attracts the male counterpart and promotes pollination. This evolutionary or species adaptation is imprinted on the genome and ispassed on to subsequent generations. Thus natural, biological systems continuously use adaptive search to improve genomes-that is, to improve the species-and to promote the survival offitter individuals and genomes through natural selection. Genetic Algorithms. Genetic algorithms are highly parallel, mathematical, adaptive search procedures (i.e., problem-solving methods) based loosely on the processes of natural genetics and Darwinian survival of the fittest. These algorithms apply genetically-inspired operators to populations of potential solutions in an iterative fashion, creating new populations while searching for an optimal (or near-optimal) solution to the problem at hand. Population is a key word here: the fact that many points in the space are searched in parallel sets genetic algorithms apart from other search operators. Another important characteristic of genetic algorithms is the fact that they are very effective when searching (e.g., optimizing) function spaces that are not smooth or, 76 combine several measurements from different types of sensors and maintainadesired state of this non-linear system. The concept can easily be expanded todetect potential component failures and generate immediate advisory messages for corrective actions. Suitability of currently available fuzzy hardware for real-time monitoring and diagnosis isalso being investigated. SUMMARY Applications of fuzzy logic in autonomous orbital operations are described in this paper with past accomplishments atJSC. Current ongoing as well as future activities planned are also described. The main objective of all these activities is to increase autonomy in orbital operations and thus achieve a higher level of operational efficiency desired for future space operations. The approach is to develop modular control that can be upscaled for greater autofiomy in an integrated environment. The initial step is to develop a software controller and then tointegrate it with hardware at the appropriate level. As the activities progress, detail testing is performed to check out implementation and integration of components. Our preliminary results promise a very successful utilization of fuzzy logic inautonomous orbital operations. REFERENCES 1.Zadeh, L. : "Fuzzy Sets", Information and Control, vol. 8, pp. 338-353, 1965. 2. Klir G. J. ; and Folger T. A. :Fuzzy sets, Uncertainty, and Information, Prentice Hall, New Jersey, 1988. _ .... 3. Lea, R. N. ;and Giarratano, J. : An Expert System Program Using Fuzzy Logic For Shuttle Rendezvous Sensor Control, proceedings of ROBEXS'86, pp. 32_i_)g6.. 4. Lea, R. N. ; and Jani, Y. : Spacecraft Attitude Control System Based on Fuzzy Logic Principles, proceedings of ROBEXS'89, 1989. 5. lea, R. N. ;Togai, M. ;Teichrow, J. ;and Jani, Y. :Fuzzy Logic Approach toCombined Translational and Rotational Control of a Spacecraft inProximity of the Space Station, Proceedings of the IFSA'89, pp. 23-29 1989. 6. Rogers, M. ;and Hoshiai, Y. :The Future Looks 'Fuzzy', NEWSWEEK, May 28, 1990. 7. Johnson, R. C. :Clear Leader Emerges : Japan at fuzzy fore, EETimes, Sept. 11, 1989. 8. Armstrong, L. ; and Gross, N. : Why _uzzy Logic' beats black-or-white thinking, Science & Technology section, BUSINESS WEEK, May 21, 1990. 9. Yasunobu, S. ; and Miyamoto, S. : "Automatic Train Operation System by Predictive Control", Industrial Applications of Fuzzy Control, Sugeno, M. ('Ed.), 1-18, North-Holland: Amsterdam, 1985. 10.Perkins, C, ;Teichrow, J. ;and Horstkotte, E. :Fuzzy-C development system :A complete overview, Togai InfraLogic Inc., SOAR-89 conference held at Johnson Space Center, Houston, July 25-27, 1989. 11. Teichrow, J. ; and Horstkotte, E. :Fuzzy-C compiler User's manual, v2.0b, Togai InfraLogic Inc., Irvine, California, April 1989. 12. Lee, C. C. ; and Berenji, H. R. : An Intelligent Controller Based On Approximate Reasoning And Reinforcement Learning, Proc. of IEEE Int. Symposium onIntelligent Control, Albeny, NY 1989. 13.Lea, R. N. •Automated Space Vehicle Control for Rendezvous Proximity Operations, Telematics and Informatics, vol. 5, no. 3, pp 179-185, I988. 14. Lea, R. N. : Applications of fuzzy sets to Rule-based Expert System Development, Telematics and Informatics, vol. 6, nos. 3/4, pp 403-406, 1989. 15.Edwards, H. C. ;and Bailey, R. :The Orbital Operations Simulator User's Guide, LinCom corporation, ref. LM85-1001-01, June 87. 16. Video Conference Demonstration from Johnson Space Center, International Workshop On Fuzzy Systems Applications (IFSA-88), Iizuka, Fukuoka, Japan, August 20-24 1988. 17. Lea, R. N., Giarratano, L,_Fritz, R. H., and Jani, Y. K. : Fuzzy Logic Control for Camera Tracking System, Proceedings of the 8th International Congress of Cybernetics and Systems, New York, lune 1990. 18. Pal, S. K. : 'Fuzziness, Image Information and Scene Analysis' in An Introduction to Fuzzy Logic Applications in Intelligent Systems edited by R. R. Yager &L. A. Zadeh, Khwer Academic Publishers (to appear). 75 continuous-functiwonhsichareverydifficult(orimpossiblteo)search using calculus based methods. Genetic algorithms are also blind: that is, they know nothing of the problem being solved other than payoff or penalty (i.e., objective function) information. The basic iterative model of the genetic algorithms isshown in figure 1. A new population iscreated from an existing population by means of evaluation, selection, and reproduction. This process repeats itself until the population converges on an optimal solution or some other stopping condition isreached. The initial population consists a set of individuals (i.e., potential solutions) generated randomly or heuristically. In the classical genetic algorithm, each member is Current _ Hew represented by a fixed-length binary string of Population Population bits (a chromosome) that encodes parameters of the problem. This encoded string can be decoded to give the integer values for these parameters. Once the initial population has been created, Selection the evaluation phase begins. The genetic algorithms require that members of the population can be differentiated according to goodness orfitness. The members that are Figure 1. The Iterative Genetic Algorithm Model. more fitare given a higher probability of participating during the selection and reproduction phases. Fitness is measured by decoding a chromosome and using the decoded parameters as input tothe objective function. The value returned by the objective function (or some transformation of i0 is used as the fitness value. During the selection phase, the population members are given a target sampling rate which isbased on fitness and determines how many times a member will mate during this generation-that is, how many offspring from this individual will be created in the next population. The target sampling rate (usually not a whole number) must be transformed into an integer number of matings for each individual. There are many ways of determining the target sampling rate and the actual number of matings. Suffice ittosay that individuals that are more fitare given a reproductive advantage over less fitmembers. During the reproduction phase, two members of the mating pool (i.e., members of the population with non-zero mating counts) are chosen firomrandom and genetic operators are applied totheir genetic material toproduce two new members for the next population. This process is repeated until the next population is filled. The recombination phase usually involves two operators: crossover and mutation. A simple crossover operation is illustrated infigure 2. During crossover, the two parents exchange substring information (genetic material) at a random position inthe chromosomes toproduce two new strings. Crossover occurs according to a crossover probability, usually between 0.5 and 1.0. The crossover operation searches for better building blocks within the genetic material which rossover Point combine to create optimal or near- Parent Strings Child Strings optimal problem parameters and, therefore, problem solutions, when the Figure 2. The Crossover Operation. string isdecoded. The mutation operation, shown infigure 3, is a secondary genetic algorithm. It is used to maintain deversity in the population-that is, to keep the population from prematurely converging on one solution-and 77 to create genetic material that may not be present in the current population. The mechanics of the mutation operation are simple: for each position in a string created during crossover, change the value I Mutations at that position according to a mutation probability. The mutation probability is usually very low-less than 0.05. Figure 3. The Mutation Operation. Genetic Algorithm Applications Since genetic algorithms provide a set of efficient, domain-independent search methods, they have been used for a wide range of applCIEfftion_..Table 1Iist_ some oftheGA appiications ranging from science and engineering to business and social sciences applications. The following sections briefly describe several of these applications. _. Goldberg (3) applied genetic algorithms and classifier systems to optimization and machine learning problems in natural gas pipeline control. He focussed on a 10-compressor, 10-pipe, steady-state, serial pipeline problem. The object was to minimize the power consumed subject to maximum and minimum pressure and pressure ratio constraints. Goldberg andSamtani (4) used a simple genetic algorithm to optimize a 10-member plane truss. The objective was to minimize the weight of the structure subject to maximum and minimum stress constraints on each member. In both cases, optimal or near-optimal results were obtained. Medical Image Processing. Fitzpatrick, et al. (5), used genetic z,gorithms to perform image registration for an arterial examination system known as digital subtraction angiography. Using this system, a physician examines arteries using two x-rays: one taken of the artery unaltered and one taken after injection of a dye into the artery. The two x-ray images are subtracted one pixel at a time; the result is a picture of the interior wall of the artery. Movement of the artery between the time each x-ray is taken results in a distorted image. Fitzpatrick, et al., used genetic algorithms to f'md a set of equations that transform or register the two images. Robot Path Planning. A Mobile Transporter system is being designed for on-orbit use with Space Station Freedom which will be capable of traversing the station's truss structure. The Mobile Transporter's func.tion is to facilitate space station maintenance tasks _indir-a-n_portation of material arou-nd the station. The Software Technology Branch has investigated the use of genetic algorithms for Mobile Transporter path planning (6). The objectives of these activities are to produce an optimum trajectory for the Mobile Transporter that avoids collisions with objects attached to the truss and to minimize the length of the path between the Mobile Transporter and the target position. Machine Learning. Genetic algorithms have been used in an area of machine learning called classifier systems. CFassifier systems learn ff-tten production rules that guide the performance of a production system. Holland has used classifier systems in studies of economic models, specifically mathematical stock market models. The genetic algorithm creates new rules for trading and selling stocks. TABLE 1. Genetic Algorithm Applications in Search and Optimization [taken from (2)] Year Investigators Des_riplj'0n BIOLOGY 1967 Rosenberg Simulation of the evolution of single-celled organism populations 1970 Weinberg Outline of cell population simulation including metalevel GA 1984 Perry Investigation of niche theory and speciation with GAs 1986 Grosso Simulation of diploid GA with explicit subpopulations and migration 1987 Sannier and Goodman GA adapts structures responding to spatial and temporal food availability 78 tocreategenetimc ateriathlatmaynotbe present in the current population. The mechanics of the mutation operation are simple: for each position in a string created during crossover, change the value I Mutations I at that position according to a mutation probability. The mutation probability is usually very low-less than 0.05. Figure 3. The Mutation Operation. Genetic Algorithm Applications Since genetic algorithms provide a set of efficient, domain-independent search methods, they have been used for a wide range of applications. Table 1lists some of the GA applications ranging from science and engineering to business and social sciences applications. The following sections briefly describe several of these applications. Engineering. Goldberg (3) applied genetic algorithms and classifier systems to optimization and machine learning problems in natural gas pipeline control. He focussed on a 10-compressor, 10-pipe, steady-state, serial pipeline problem. The object was to minimize the power consumed subject to maximum and minimum pressure and pressure ratio constraints. Goldberg and Samtani (4) used a simple genetic algorithm to optimize a 10-member plane truss. The objective was to minimize the weight of the structure subject to maximum and minimum stress consla'aints on each member. In both cases, optimal or near-optimal results were obtained. Medical Image Processing. Fitzpatrick, et al. (5), used genetic a,gorithms to perform image registration for an arterial examination system known as digital subtraction angiography. Using this system, a physician examines arteries using two x-rays: one taken of the artery unaltered and one taken after injection of a dye into the artery. The two x-ray images are subtracted one pixel at a time; the result is a picture of the interior wall of the artery. Movement of the artery between the time each x-ray is taken results in a distorted image. Fitzpatrick, et al., used genetic algorithms to find a set of equations that transform or register the two images. Robot Path Planning. A Mobile Transporter system is being designed for on-orbit use with Space Station Freedom which will be capable of traversing the station's truss structure. The Mobile Transporter's function is to facilitate space station maintenance tasks and transportation of material around the station. The Software Technology Branch has investigated the use of genetic algorithms for Mobile Transporter path planning (6). The objectives of these activities are to produce an optimum trajectory for the Mobile Transporter that avoids collisions with objects attached to the truss and to minimize the length of the path between the Mobile Transporter and the target position. Machine Learning. Genetic algorithms have been used in an area of machine learning called classifier systems. Classifier systems learn if-then production rules that guide the performance of a production system. Holland has used classifier systems in studies of economic models, specifically mathematical stock market models. The genetic algorithm creates new rules for trading and selling stocks. TABLE 1. Genetic Algorithm Applications in Search and Optimization [taken from (2)] Year Investigators Descrip_i0n BIOLOGY 1967 Rosenberg Simulation of the evolution of single-celled organism populations 1970 Weinberg Outline of cell population simulation including metalevel GA 1984 Perry Investigation of niche theory and speciation with GAs 1986 Grosso Simulation of diploid GA with explicit subpopulations and migration 1987 Sannier and Goodman GA adapts structures responding to spatial and temporal food availability 78 continuous--functions which are very difficult (or impossible) to search using calculus based methods. Genetic algorithms are also blind: that is, they know nothing of the problem being solved other than payoff or penalty (i.e., objective function) information. The basic iterative model of the genetic algorithms is shown in figure 1. A new population is created from an existing population by means of evaluation, selection, and reproduction. This process repeats itself until the population converges onan optimal solution or some other stopping condition isreached. The initial population consists a set of individuals (i.e., potential solutions) generated randomly or heuristically. In the classical genetic algorithm, each member is Current _ New Population Popula_lon represented bya fixed-length binary string of bits (a chromosome) that encodes parameters of the problem. This encoded string can be decoded to give the integer values for these parameters. Once the initial population has been created, o_,._ SeIec_. ion the evaluation phase begins. The genetic algorithms require that members of the population can be differentiated according to goodness orfitness. The members that are Figure 1. The Iterative Genetic Algorithm Model. morefit are given a higher probability of _--_- : :: .... _: _ _ _ _ _ _ participating during the selection and reproduction phases. Fitness is measured by decoding a chromosome and using the decoded parameters as input tothe objective function. The value returned by the objective function (or some transformation of it)isused as the fitness value. During the selection phase, the population members are given a target sampling rate which is based on fimess and determines how many times a member will mate during this generation-that is, how many offspring from this individual will be created in the next population. The target sampling rate (usually not a whole number) must be transformed into an integer number of matings for each individual. There are many ways of determining the target sampling rate and the actual number of matings. Suffice itto say that individuals that are more fit are given a reproductive advantage over less fit members. During the reproduction phase, two members of the mating pool (i.e., members of the population with non-zero mating counts) are chosen from random and genetic operators are applied totheir genetic material toproduce two new members for the next population. This process is repeated until the next population is filled. The recombination phase usually involves two operators: crossover and mutation. A simple crossover operation is illustrated infigure 2. During crossover, the two parents exchange substring information (genetic material) at a random position inthe chromosomes toproduce two new strings. Crossover occurs according to a crossover probability, usually between 0.5 and 1.0. The crossover operation searches for better building blocks within the genetic material which _ovof Point combine to create optimal or near- Parent Strings Child Strings optimal problem parameters and, therefore, problem solutions, when the Figure 2. The Crossover Operation. string isdecoded. The mutation operation, shown infigure 3, is a secondary genetic algorithm. It isused to maintain deversity in the population-that is, to keep the population from prematurely converging on one solution-and 77 TABLE1.(Continued.) Year Investigators Description COMPUTESRCIENCE 1967 aagley Parameter search inhexapawn-like game evaluation function via GA 1979 RaghavanandBirchard GA-based clustering algorithm 1982 _y Probabilities automation identification attempt via GA 1984 Gordon Adaptive document description using GA 1985 Rendell GA search for game evaluation function 1987 RaghavanandAgarwal Adaptive document clustering using GAs ENGINEERING &OPERATIONS RESEARCH 1981 Goldberg Mass-spring-dashpot system identification with simple GA 1982 Etter, Hicks, and Cho Recursive adaptive filter design using a simple GA 1983 Goldberg Steady-state and transient optimization of gas pipeline using GA 1985 Davis Bin-packing and graph-coloring problems via GA 1985 Davis Outline ofjob shop scheduling procedure via GA 1985 Davis and Smith VLSI circuit layout via GA 1985 Fourman VLSI layout compaction with GA 1985 Goldberg and Kuo On-off, steady-state optimization of oil pump-pipeline system with GA 1986 Glover Keyboard configuration design using aGA 1986 Goldberg and Samtani Structural optimization (plane truss) via 1986 Goldberg and Smith Blind knapsack problem with simple GA 1986 Minga Aircraft landing strut weight optimization with GA 1987 Davis and Coombs Communications network link size optimization using GA 1987 Davis and Rittter Classroom scheduling via simulated annealing with metalevel GA IMAGE PROCESSING &PATTERN RECOGNITION 1970 Cavicchio Selection of detectors forbinary pattern recognition 1984 Fitzpatrick, et al. Image registration via GA tominimize image differences 1985 Englander Selection ofdetectors for known image classification 1985 Gillies Search for image feature detectors via GA 1987 Stadnyk Explicit pattern class recognition using partial matching PHYSICAL SCIENCES 1985 Shaefer Nonlinear equation solving with GA for fitting potential surfaces SOCIAL SCIENCES 1979 Reynolds GA-like adaptation inmodel of prehistoric hunter-gatherer behavior 1981 Smith and De Jong Calibration of population migration model using GA search 1985 Axelrod Simulation of the evolution of behavioral norms with GA 1985 Axelrod Iterated prisoners dilemma problem solution using GA THE SPLICER PROJECT This section introduces the Splicer Project. It presents background material and discusses the objectives of the project, the approach taken, results todate, current status and possibilities for future work. Background The Splicer Project isa project within the Software Technology Branch at NASA's Johnson Space Center. The purpose of the project isto develop a tool that will enable the widespread use of genetic algorithm technology. 79 The charter of the Software Technology Branch is to develop and/or acquire generic software tools for emerging technologies. Genetic algorithms are just one of the many technologies being investigated within the Software Technology Branch: other areas and tools are expert systems (CLIPS), neural networks (NETS), fuzzy logic, scheduling (COMPASS), software reuse, and intelligent computer-aided training. The MITRE Corporation supports the Software Technology Branch on multiple projects and is responsible for evaluating the viability and robustness of genetic algorithms and for supporting the Software Technology Branch with respect to the development and acquisition of software tools related to this technology. Objectives The Software Technology Branch is interested in applying genetic algorithms within various domains: e.g., robot path planning, job shop scheduling. The original goal of the Splicer Project was to create a flexible, generic tool. As such, the tool would: ...... _:.: • Implement the basic genetic algorithms defined in the literature • Define the interfaces for and allow users to develop interchangeable fitness modules • Provide a graphic, event-driven user interface Subsequent goals include the following: • Distribution of the tool in the public domain • Support for multiple computing platforms • Extension of the tool for additional genetic algorithm functionality • Use of the tool for genetic algorithm research ° Augmentation of the tool and special user interfaces for specific application domains Approach _. The design chosen for the Splicer tool is shown in figure 4. This design consists of four components: a genetic algorithm kernel and three types of interchangeable libraries or modules: representation libraries, fitness modules, and user interface ilbraries. A genetic algorithm kernel was developed that is I i:_:! independent of representation (i.e., problem Qen°.° I I Ii encoding), fitness function, or user interface type. Algorithm _, ,_ Representation iii[_ The GA kernel comprises all functions necessary Kernel _ Library for the manipulation of populations. These functions include the creation of populations and population members, the iterative population model, fitness scaling, parent selection and sampling, and the generation of population |lil 'n'"°"I -I lii| statistics. In addition, miscellaneous functions are included in the kernel (e.g., random number generators). Different types of problem-encoding schemes and Figure 4. Splicer Project Design functions are defined and stored in interchangeable representation libraries. This allows the GA kernel to be used for any representation scheme. At present, the Splicer tool provides representation l_raries for binary strings and for permutations. These libraries contain functions for the definition, creation, and decoding of genetic swings, as well as multiple crossover and mutation operators. Furthermore, the Splicer tool defines the appropriate interfaces to allow users to create new representation libraries (e.g., for use with vectors or grammars). Fitness functions are defined and stored in interchangeable fitness modules. Fitness modules are the only piece of the Splicer system a user will normally be required to create or alter to solve a particular problem. Within a 80 The charter of the Software Technology Branch is to develop and/or acquire generic software tools for emerging technologies. Genetic algorithms are just one of the many technologies being investigated within the Software Technology Branch: other areas and tools are expert systems (CLIPS), neural networks (NETS), fuzzy logic, scheduling (COMPASS), software reuse, and intelligent computer-aided training. The MITRE Corporation supports the Software Technology Branch on multiple projects and is responsible for evaluating the viability and robustness of genetic algorithms and for supporting the Software Technology Branch with respect to the development and acquisition of software tools related to this technology. Objectives The Software Technology Branch is interested in applying genetic algorithms within various domains: e.g., robot path planning, job shop scheduling. The original goal of the Splicer Project was to create a flexible, generic tool. As such, the tool would: • Implement the basic genetic algorithms defined in the literature • Define the interfaces for and allow users to develop interchangeable fitness modules • Provide a graphic, event-driven user interface Subsequent goals include the following: • Distribution of the tool in the public domain • Support for multiple computing platforms • Extension of the tool for additional genetic algorithm functionality • Use of the tool for genetic algorithm research • Augmentation of the tool and special user interfaces for specific application domains Approach D._iga. The design chosen for the Splicer tool is shown in figure 4. This design consists of four components: a genetic algorithm kernel and three types of interchangeable libraries or modules: representation libraries, fitness modules, and user interface libraries. A genetic algorithm kernel was developed that is ...... M independent of representation (i.e., problem encoding), fitness function, or user interface type. Algorithm Kernel The GA kernel comprises all functions necessary I Genetic Library for the manipulation of populations. These functions include the creation of populations and population members, the iterative population model, fitness scaling, parent selection and sampling, and the generation of population statistics. In addition, miscellaneous functions are _l Fitness included in the kernel (e.g., random number generators). Figure 4. Splicer Project Design Different types of problem-encoding schemes and functions are defined and stored in interchangeable representation libraries. This allows the GA kernel tobe used for any representation scheme. At present, the Splicer tool provides representation libraries for binary strings and for permutations. These libraries contain functions for the definition, creation, and decoding of genetic strings, as well as multiple crossover and mutation operators. Furthermore, the Splicer tool defines the appropriate interfaces to allow users to create new representation libraries (e.g., for use with vectors or grammars). Fitness functions are defined and stored in interchangeable fitness modules. Fitness modules are the only piece of the Splicer system a user will normally be required to create or alter to solve a particular problem. Within a 80 TABLE 1. (Continued.) year _ Investigators I_sc_p_on COMPUTER SCIENCE 1967 Bagley Parameter search inhexapawn-like game evaluation function via GA 1979 Raghavan and Birehard GA-based clustering algorithm 1982 Gerardy Probabilities automation identification attempt via GA 1984 Gordon Adaptive document description using GA 1985 Rendell GA search for game evaluation function 1987 Raghavan and Agarwa/ Adaptive document clustering using GAs ENGINEERING &OPERATIONS RESEARCH 1981 Goldberg Mass-spring-dashpot system identification with simple GA 1982 Etter, Hicks, and Cho Recursive adaptive filter design using a simple GA 1983 Goldberg Steady-state and transient optimization of gas pipeline using GA 1985 Davis Bin-packing and graph'coloring problems via GA 1985 Davis Outline ofjob shop scheduling procedure via GA 1985 Davis and Smith VLSI circuit layout via GA :_ : 1985 Fourman VLSI layout compaction with GA _iii::.... _ 1985 Goldberg and Kuo On-off, steady-state optimization of oil pump-pipeline system with GA 1986 Glover Keyboard configuration design using aGA 1986 Goldberg and Samtani Structural optimization (plane truss) via 1986 Goldberg and Smith Blind knapsack problem with simple GA 1986 Minga Aircraft landing strut weight optimization with GA 1987 Davis and Coombs Communications network link size optimization using GA 1987 Davis and Rittter Classroom scheduling via simulated annealing with metalevel GA IMAGE PROCESSING &PATTERN RECOGNITION 1970 Cavicchio Selection of detectors forbinary pattern recognition 1984 Fitzpatrick, et al. Image registration via GA tominimize image differences 1985 Englander Selection of detectors for known image classification 1985 Gillies Search for image feature detectors via GA • 1987 Stadnyk Explicit pattern class recognition using partial matching PHYSICAL SCIENCES 1985 Shaefer Nonlinear equation solving with GA for fitting potential surfaces SOCIAL SCIENCES 1979 Reynolds GA-like adaptation inmodel of prehistoric hunter-gatherer behavior 1981 Smith and DeJong Calibration ofpopulation migration model using GA search 1985 Axelrod Simulation of the evolution of behavioral norms with GA 1985 Axekod iterated prisoners dilemma problem solution using GA THE SPLICER PROJECT This section inla'oduces the Splicer Project. Itpresents background material and discusses the objectives of the project, the approach taken, results todate, current status and possibilities for future work. Background The Splicer Project is a project within the Software Technology Branch at NASA's Johnson Space Center. The purpose of the project isto develop a tool that will enable the widespread use of genetic algorithm technology. 79