Professor, CSE
Director, ECSL
Conference Publications
A significant challenge in designing robot systems that learn from a teacher's demonstration is the ability to map the perceived behavior of the trainer to an existing set of primitive behaviors. A main difficulty is that the observed actions may constitute a combination of individual behaviors' outcomes, which would require a decomposition of the observation onto multiple primitive behaviors. This paper presents an approach to robot learning by demonstration that uses a potential-field behavioral representation to learn tasks composed by superposition of behaviors. The method allows a robot to infer essential aspects of the demonstrated tasks, which could not be captured if combinations of behaviors would not have been considered. We validate our approach in a simulated environment with a Pioneer 3DX mobile robot
We investigate the use of genetic algorithms to play real-time computer strategy games and focus on solving the complex spatial reasoning problems found within these games. To overcome the knowledge acquisition bottleneck found in using traditional expert systems, scripts, and decision trees as done in most game AI, we use genetic algorithms to evolve game players. The spatial decision makers in these game players use influence maps as a basic building block, from which they construct and evolve influence map trees containing complex game playing strategies. With co-evolution we attain arms-race like progress, leading to the evolution of robust players superior to their handcoded counterparts.
We investigate the use of genetic algorithms to play real-time computer strategy games. To overcome the knowledge acquisition bottleneck found in using traditional expert systems, scripts, or decision trees we use genetic algorithms to evolve game players. The spatial decision makers in our game players use influence maps as a basic building block from which they construct and evolve trees containing complex game playing strategies. Information from influence map trees is combined with that from an A* pathfinder, and used by another genetic algorithm to solve the allocation problems present within many game decisions. As a first step towards evolving strategic players we develop this system in the context of a tactical game. Results show the co-evolution of coordinated attacking and defending strategies superior to their hand-coded counterparts
Game Environments provide a good domain for serious simulations such as those used in training Navy Conning officers. Currently, a typical training scenario requires multiple personnel to play each of the boats and this is expensive. We propose an approach to addressing this issue by developing intelligent, autonomous controllers for each boat. Significant challenges toward achieving these goals are the realism of behavior exhibited by the automated boats and their real-time response to change. In this paper, we describe a control architecture that enables the real-time response of boats and the reeprtoire of realistic behaviors we developed for this application. We demonstrate the capabilities of our system with experimental results
Behavior based architectures have many parameters that must be tuned to produce effective and believable agents. We use genetic algorithms to tune simple behavior based controllers for predators and prey. First, the predator tries to maximize area coverage in a large asymmetric arena with a large number of identically tuned peers. Second, the GA tunes the predator against a single prey agent. Then, we tune two predators against a single prey. The prey evolves against a default predator and an evolved predator. The genetic algorithm finds high-performance controller parameters after a short length of time and outpaces the same controllers hand tuned by human programmers after only a small number of evaluations.
We use case-injected genetic algorithms for learning how to competently play computer strategy games. Case-injected genetic algorithms combine genetic algorithm search with a case-based memory of past problem solving attempts to improve performance on subsequent similar problems. The case-injected genetic algorithm improves performance on later problems in the sequence by learning from cases recorded earlier in the sequence. Since game-play in strategy games usually boils down to optimally allocating resources to achieve in-game mission objectives, we describe how a case-injected genetic algorithm player can play our game by solving the sequence of resource allocation problems generated by opponent moves during game-play. When retrieving and using cases recorded from human game-play, results show that case injection effectively biases the genetic algorithm toward producing plans that contain appropriate elements of plans produced by human players.
We use case injected genetic algorithms to learn how to competently play compute r strategy games that involve long range planning across complex dynamics. Imperfect knowledge presented to players requires them adapt their strategies in order to anticipate opponent moves. We focus on the problem of acquiring knowledge learned from human players, in pa rticular we learn general routing information from a human player in the context of a strike force planning game. By incorporating case injection into a genetic algorithm, we show methods for in corporating general knowledge elicited from human players into future plans. In effect allowing the GA to take important strategic elements from human play a nd merging those elements into its own strategic thinking. Results show that with an appropriate representation, case injection is effectiv e at biasing the genetic algorithm toward producing plans that contain important strategic elements used by human players. that contain important strategic elements used by human players.
We present a case-injected genetic algorithm player for Strike Ops, a real-time strategy game. Such strategy games are fundamentally resource allocation optimization problems and our previous work showed that genetic algorithms can play such games by solving the underlying resource allocation problem. This paper shows how we can learn to better respond to opponent actions (moves) by using case-injected genetic algorithms. Case-injected genetic algorithms were designed to learn to improve performance in solving sequences of similar problems and thus provide a good fit for responding to opponent actions in Strike Ops which result in a sequence of similar resource allocation problems. Our results show that a case-injected genetic algorithm player learns from previously encountered problems in the sequence to provide better quality solutions in less time for the underlying resource allocation problem thus improving response time by the genetic algorithm player. This improves the responsiveness of the game and the quality of the overall playing experience.
This paper describes an approach for better application personalization by learn ing user-context. We present Sycophant, context-sensitive calendaring applicatio n capable of generating four different types of reminders. Sycophant uses a Genetics-Based Machine Learning technique, XCS, to learn the type of reminder preferred by a user and successfully performs this user-context learning for three different us ers. XCS performs as well as a decision tree learner in predicting whether or no t to generate a reminder and outperforms the decision tree learner in learning t o predict the correct reminder.
Current computer applications and user interfaces lack user context and are not successful in learning user preferences to improve user interaction. We present Sycophant, a context learning calendaring application program which is designed to learn a mapping from user-related contextual features to reminder actions. In this paper, we consider the feasibility of using a geneticsbased machine learning technique, XCS, for the purpose of learning this mapping from a set of context features to reminder actions as a predictive data-mining task. We compare XCS u 2019s performance with a decision tree algorithm on this learning task and show that XCS outperforms the decision tree learner.
We use a parallel multi-objective genetic algorithm to drive a search and recons truction spectroscopic analysis of plasma gradients in inertial confinement fusi on (ICF) implosion cores. In previous work, we had shown that our serial multi-o bjective Genetic Algorithm was a good method to solve two-criteria X-ray spectro scopy diagnostics problems. However, this serial version was slow and we therefo re could not incorporate better physics and more criteria to solve larger proble ms and handle larger data sets. In this paper, we develop and use a parallel mul ti-objective genetic algorithm based on a master-slave model to solve three crit eria spectroscopic analysis problems. The algorithm works well in reconciling ex perimental observations with theoretical physics model parameters. In addition, theoretical analysis and experimental results on the parallelized version show g ood scalability with up to 150 processors. This reduces the time for running t he GA from 9.6 hours to 5.9 minutes.
We use a parallel multi-objective genetic algorithm to drive a search and recons truction spectroscopic analysis of plasma gradients in inertial confinement fusi on (ICF) implosion cores. In previous work, we had shown that our serial multi-o bjective Genetic Algorithm was a good method to solve two-criteria X-ray spectro scopy diagnostics problems. However, this serial version was slow and we therefo re could not incorporate better physics and more criteria to solve larger proble ms and handle larger data sets. In this paper, we develop and use a parallel mul ti-objective genetic algorithm based on a master-slave model to solve three crit eria spectroscopic analysis problems. The algorithm works well in reconciling ex perimental observations with theoretical physics model parameters. In addition, theoretical analysis and experimental results on the parallelized version show g ood scalability with up to 150 processors. This reduces the time for running t he GA from 9.6 hours to 5.9 minutes.
First-person shooter robot controllers (bots) are generally rule-based expert systems written in C/C++. As such, many of the rules are parameterized with values, which are set by the software designer and finalized at compile time. The effectiveness of parameter values is dependent on the knowledge the programmer has about the game. Furthermore, parameters are non-linearly dependent on each other. This paper presents an efficient method for using a genetic algorithm to evolve a set of parameters for bots which play as well as parameters tuned by a human with expert knowledge about the game's strategy. This indicates genetic algorithms as being a potentially useful method for tuning bots.
Spiking neural networks are computationally more powerful than conventional artificial neural networks. Although this fact should make them especially desirable for use in evolutionary autonomous agent research, several factors have limited their application. This work demonstrates an evolutionary agent with a sizeable recurrent spiking neural network containing a biologically motivated columnar visual cortex. This model is instantiated in spiking neural network simulation software and challenged with a dynamic image recognition and memory task. We use a genetic algorithm to evolve generations of this brain model that instinctively perform progressively better on the task. This early work builds a foundation for determining which features of biological neural networks are important for evolving capable dynamic cognitive agents.
Current computer applications lack user context and do not learn to use this context to improve user interaction. In this paper we present Sycophant, a context learning calendar application program which learns a mapping from user-related contextual features to application actions. In this preliminary work, Sycophant achieves good accuracy in learning this mapping. In addition, we find that including external context such as the presence or absence of motion and speech provides better performance in learning accurate mappings.
We use case injected genetic algorithms to learn how to competently play computer strategy games that involve long range planning and complex dynamics. Such games inspire, and are inspired by, military training simulations on which trainees spend considerable time honing their skills. By instrumenting the game interface, we unobtrusively acquire knowledge in the form of cases from human experts playing the game and use case-injected genetic algorithms to incorporate this knowledge in evolving competent game players. The games we have focused on have two sides, Blue and Red, and an evolved player can thus serve two purposes. A competent player for Blue serves as a decision aid for a Blue trainee. At the same time, a competent Blue player serves as a training opponent for a Red trainee. Results in the context of a strike force planning game show that with an appropriate representation, case injection is effective at biasing the genetic algorithm towards producing competent plans that contain important strategic elements used by human players.
We use case injected genetic algorithms to learn how to competently play computer strategy games. Strategic computer games involve long range planning across complex dynamics and imperfect knowledge presented to players requires them to anticipate opponent moves and adapt their strategies accordingly. In this paper, we address the problem of acquiring knowledge learned from human players, in particular we learn general routing information from a human player in the context of a strike planning game. By incorporating case injection into a genetic algorithm, we show methods for learning general knowledge from human players to incorporate into future plans. Results show that with an appropriate representation, case injection is effective at biasing the genetic algorithm toward producing plans that contain important strategic elements used by human players.
We use case injected genetic algorithms to learn to competently play computer strategy games. Such games are characterized by player decision in anticipation of opponent moves and imperfect knowledge of game state. Within the broad goal of developing effective and general methods of anticipatory play, this paper investigates anticipation in the context of trap avoidance in an immersive, 3D strike planning game. Case injection allows acquiring player knowledge from experience and incorporating acquired knowledge into future game play. Results show that with an appropriate representation case injection is effective at biasing the genetic algorithm toward producing plans that both avoid traps and carry out the mission effectively.
We investigate the use of case injection to bias the results of a genetic algorithm (GA) in two scenarios. First, when the problem we are attempting to bias by case injection is identical to the problem from which the injected cases were gathered. Second, when the problem we are attempting to bias is different (to varying degree) from the problem from which the injected cases were gathered. In the first scenario, we find that injection of cases does lead to preferential convergence to solutions similar to the runs from which the cases are gathered. While previous work on case injected genetic algorithms had shown an improvement in solution quality and time to solution when solving a sequence of similar problems, we believe there has been no prior investigation of using case injection to intentionally alter convergence away from the most fit solution and toward another desired solution. This paper shows that injecting cases into similar problems does in fact bias the GA solutions of those problems. The more similar the injected problem is to the problem from which the cases were gathered, the more marked is the solution bias effect. We find that case injection can still be used to bias GA results even when the problems differ significantly. This technique has application where we wish a GA to derive solutions similar to (for example) known good solutions or human derived solutions, when, because of incomplete modeling information, the numerical formulation of the problem itself and its fitness function do not necessarily contain all information about the problem. This has potential applications in human modeling and in developing quality opponents in gaming applications.
This paper describes a technique for combining genetic algorithm with a long term memory of past problems solving attempts to obtain better performance over time on sets of similar design problems. Rather than starting anew on each design, we periodically inject a genetic algorithm� population with appropriate intermediate design solutions to similar, previously solved problems. Experimental results on a configuration design problem; the design of an adder and circuits similar to adders, demonstrate the performance gains from our approach and show that our system learns to take less time to provide quality solutions to a new design problem as it gains experience from solving other similar design problems. We hope that this simple technique will help in implementing evolutionary computing applications in industry.
This paper describes a technique for evolving similar solutions to similar configuration design problems. Using the configuration design of combination logic circuits as a testbed, the paper shows that combining genetic algorithms with a case-based memory leads to improved performance on sets of similar design problems. In this approach, rather than starting from scratch on each design, we periodically inject a genetic algorithm's population with appropriate partial solutions to similar previously attempted problems. Experimental results on the combinational logic design of parity checkers and adders shows that this system takes less time to provide better quality solutions to new design problems as it gains experience from solving other similar design problems. The designs generated by the combined system also tend to be more similar than those generated by a randomly initialized genetic algorithm.
We use a genetic algorithm to calibrate a spatially and temporally resolved cellular automata to model mining activity on public land in Idaho and western Montana. The genetic algorithm searches through a space of transition rule parameters of a two dimensional cellular automata model to find rule parameters that fit observed mining activity data. Previous work by one of the authors in calibrating the cellular automaton took weeks - the genetic algorithm takes a day and produces rules leading to about the same (or better) fit to observed data. These preliminary results indicate that genetic algorithms are a viable tool in calibrating cellular automata for this application. Experience gained during the calibration of this cellular automata suggests that mineral resource information is a critical factor in the quality of the results. With automated calibration, further refinements of how the mineral-resource information is provided to the cellular automaton will probably improve our model.
We describe the use of object oriented techniques for the specification, architecting, and design of an enterprise monitoring application. Monitoring applications provide situational awareness and monitor aspects of an enterprise's activities. Drawing from a wide variety of static and dynamic data sources, they typically allow a user to specify items of interest, and drill down to obtain real-time or near-real time information on such items. Our paper describes the use of standard UML for modeling and the issues in architecting and designing our J2EE framework based application.
This paper describes the use of a genetic algorithm to solve a hydrology design problem - determining an optimal or near-optimal prescription of Best Management Practices in a Flood-prone watershed. The model has proved capable of discovering design prescriptions that are more cost-effective than existing designs, promising significant financial benefits in a shorter time period. The approach is flexible enough to be applied to any watershed with basic precipitation and soil data
X-ray spectroscopy diagnostics have been widely used as a standard technique to determine the temperature and density of astrophysical and laboratory plasmas. We use a Pareto optimal genetic algorithm to drive a search of model parameters that simultaneously produces high-quality fits of spectra and spatially resolved emissivity profiles. We parallelized genetic algorithm to run on a Beowulf machine and achieved linear speed-up. The parallel code allows us to use larger populations resulting in improved reliability.
Development of robotic controllers for complex behavioral tasks is difficult when the exact nature or complexity of an environment is not known in advance. This paper explores the use of genetic algorithms to evolve neural network controllers that exhibit generalized complex behavior. We compare the performance of the evolved controllers to those developed by human programmers.
This paper investigates the effect of injection percentage on the performance of a case-injected genetic algorithm for combinational logic design. A case-injected genetic algorithm is a genetic algorithm augmented with a case-based memory of past problem solving atempts which learns to improve performance on sets of similar design problems. In this approach, rather than starting anew on each design, we periodically inject a genetic algorithm's population with appropriate intermediate design solutions to similar previously solved problems. Experimental results on a configuration design problem; the design of a parity checker, demonstrate the performance gains from our approach and show that our system learns to take less time to provide quality solutions to a new design problem as it gains experience from solving other similar design problems.
This paper presents a new approach to genetic algorithm based design. We use genetic algorithms augmented with a case-based memory of past design problem solving attempts to obtain better performance over time on sets of similar design problems. Rather than starting anew on each design, we periodically inject a genetic algorithm's population with appropriate intermediate design solutions to similar, previously solved problems. Experimental results on a configuration design problem; the design of a parity checker circuit, demonstrate the performance gains from our approach and show that our system learns to take less time to provide quality solutions to a new design problem as it gains experience from solving other similar design problems.
This paper presents a new approach to the problem of allocating strike force assets in a dynamic targeting environment. We develop a nonlinear programming formulation that encompasses both strike and suppression responsibilities as well as multi-target and multi-threat allocations. Our approach uses a genetic algorithm augmented with a case-based memory, containing population members from past problem solving attempts, to obtain better performance over time on sequences of similar allocation problems. The case-base acts as an associative long-term memory of problem solving experience. Rather than starting with a randomly initialized population on each new allocation problem, we periodically inject a genetic algorithm's population with appropriate cases (encoded allocation strategies) from similar, previously solved problems. Using hamming distance as a simple distance (similarity) metric for choosing appropriate cases, our experimental results demonstrate the performance gains from our approach and show that our system learns to take less time to provide quality solutions to new allocation problems as it gains experience from solving other similar allocation problems.
We investigate the problem of allocating strike force assets in a dynamic targetting environment using a genetic algorithm. The nonlinear programming formulation developed in this paper encompasses both strike and suppression responsibilities as well as multi-target and multi-threat allocations. Partitioning the allocation strategy matrix into strike and suppression components results in a more effective search. Results on two constructed problems show that the genetic algorithm quickly and reliably finds optimal or near-optimal allocations.
We consider the problem of gender classification from frontal facial images using genetic feature subset selection. We argue that feature selection is an important issue in gender classification and demonstrate that Genetic Algorithms (GA) can select good subsets of features (i.e., features that encode mostly gender information), reducing the classification error. First, Principal Component Analysis (PCA) is used to represent each image as a feature vector (i.e., eigen-features) in a low-dimensional space. Genetic Algorithms (GAs) are then employed to select a subset of features from the low-dimensional representation by disregarding certain eigenvectors that do not seem to encode important gender information. Four different classifiers were compared in this study using genetic feature subset selection: a Bayes classifier, a Neural Network (NN) classifier, a Support Vector Machine (SVM) classifier, and a classifier based on Linear Discriminant Analysis (LDA). Our experimental results show a significant error rate reduction in all cases. The best performance was obtained using the SVM classifier. Using only 8.4 of the features in the complete set, the SVM classifier achieved an error rate of 4.7% from an average error rate of 8.9% using manually selected features.
We consider the problem of gender classification from frontal facial images using feature selection and neural networks. We argue that feature selection is an important issue in gender classification and we demonstrate that by removing features that do not encode important gender information from the image representation of faces, the error rate can be reduced significantly. Automatic feature subset selection distinguishes the proposed method from previous gender classification approaches. First, Principal Component Analysis (PCA) is used to represent each image as a feature vector (i.e., eigen-features) in a low-dimensional space, spanned by the eigenvectors of the covariance matrix of the training images (i.e., coefficients of the linear expansion). A Genetic Algorithm (GA) is then used to select a subset of features from the low-dimensional representation by removing certain eigenvectors that do not seem to encode important information about gender (e.g., eigenvectors encoding information about glasses). Finally, a Neural Network (NN) is trained to perform gender classification using the selected eigen-feature subset. Experimental results demonstrate a significant improvement in error rate reduction. Using a subset of eigen-features containing only 18% of the features in the complete set, the average NN classification error goes down to 11.3% from an average error rate of 17.7%.
X-ray spectroscopy of laser-driven imploded ICF cores has proved to be a powerful diagnostic of spatially-averaged temperature and density plasma conditions at the collapse of ICF implosion experiments. Temperature and density time-histories can be extracted from the analysis of time-resolved X-ray line spectra using the temperature and density sensitivity of line intensities and Stark-broadened line shapes. The next step in the spectroscopy of imploded cores is the bracketing of core plasma gradients as a function of time. To this end, we discuss a method which is based on the self- consistent and simultaneous simulation and analysis of time-resolved X-ray line spectra and X-ray monochromatic images. Abel inversion of X-ray monochromatic images provide line emissivity spatial profiles; this information is critical for the determination of gradients in the core. An efficient computational implementation of this spectroscopic analysis requires a robust search and optimization algorithm that can look for simultaneous, good spectra and emissivity fits as a function of temperature and density gradient functions. In this way we can also study the uniqueness of the solution, the effects of noise in the data, and explore different functional forms for the gradients and their parameterization. In this connection, we present the implementation of a Niched Pareto Genetic Algorithm technique that has proven successful in this analysis. Results are illustrated for several synthetic data cases based on the Ar Heb and Li-like satellites composite spectral feature. We also discuss the application of this technique to the analysis of data recorded in ICF implosion experiments driven with the GECCO XII laser system at Osaka University.
X-ray spectroscopy of laser-driven imploded ICF cores has proved to be a powerful diagnostic of spatially-averaged temperature and density plasma conditions at the collapse of ICF implosion experiments. Temperature and density time-histories can be extracted from the analysis of time-resolved X-ray line spectra using the temperature and density sensitivity of line intensities and Stark-broadened line shapes. The next step in the spectroscopy of imploded cores is the bracketing of core plasma gradients as a function of time. To this end, we discuss a method which is based on the self- consistent and simultaneous simulation and analysis of time-resolved X-ray line spectra and X-ray monochromatic images. Abel inversion of X-ray monochromatic images provide line emissivity spatial profiles; this information is critical for the determination of gradients in the core. An efficient computational implementation of this spectroscopic analysis requires a robust search and optimization algorithm that can look for simultaneous, good spectra and emissivity fits as a function of temperature and density gradient functions. In this way we can also study the uniqueness of the solution, the effects of noise in the data, and explore different functional forms for the gradients and their parameterization. In this connection, we present the implementation of a Niched Pareto Genetic Algorithm technique that has proven successful in this analysis. Results are illustrated for several synthetic data cases based on the Ar Heb and Li-like satellites composite spectral feature. We also discuss the application of this technique to the analysis of data recorded in ICF implosion experiments driven with the GECCO XII laser system at Osaka University.
X-ray spectroscopy diagnostics have been widely used as a standard technique to determine the temperature and density of astrophysical and laboratory plasmas. Traditional techniques have relied on performing an interactive search with a graphical user interface to select theoretical model parameters that best fit the data. We use a Pareto optimal genetic algorithm to drive a search of model parameters that produce high- quality simultaneous fits of spectra and spatially-resolved emissivity profiles. Preliminary results indicate that our Pareto optimal genetic algorithm is able to quickly find physically meaningful solutions.
X-ray spectroscopic analysis is a powerful tool for plasma diagnostics. We use genetic algorithms to automatically analyze experimental X-ray line spectra and discuss a particular implementation of the genetic algorithm suitable for our problem. Since spectroscopic analysis may be computationally intensive, we also investigate the use of case injected genetic algorithms for quicker analysis of several similar (time resolved) spectra. Preliminary results are promising and genetic algorithms seem to provide a reliable and robust approach for automated analysis of X-ray line spectra.
We use an interactive genetic algorithm to divide and conquer large traveling salesperson problems. Current genetic algorithm approaches are computationally intensive and may not produce acceptable tours within the time available. Instead of applying a genetic algorithm to the entire problem, we let the user interactively decompose a problem into subproblems, let the genetic algorithm separately solve these subproblems and then interactively connect subproblem solutions to get a global tour for the original problem. Our approach significantly reduces the computing time to find high quality solutions for large traveling salesperson problems. We believe that an interactive approach can be extended to other visually decomposable problems.
We present and use a sequence similarity metric to solve sets of similar problems with case injected genetic algorithms. Rather than starting anew on each problem, we periodically inject a genetic algorithm's population with appropriate intermediate solutions to similar, previously solved problems. Using simple syntactic similarity measures, our experimental results from optimizing a series of traveling salesman problems demonstrates the robustness of our approach. Results show that compared to a randomly initialized genetic algorithm, our system learns to take decreasing time to provide better solutions to a new problem as it gains experience from solving other similar problems.
We use genetic algorithms to find geologically plausible sub-surface models from seismic travel-time data. Given a sub-surface model, the physics of wave propagation through refractive media can be used to compute travel times for seismic waves. However, in practice, we have to solve the inverse problem: travel-times are available and the problem is to infer sub-surface structure. This inverse problem is fundamental to seismology. To determine the suitability and applicability of genetic algorithms to this seismic inversion problem, we tested a number of different genetic algorithm parameters and operators. Experiments with two synthetic seismic models shows that large population sizes are critical to generating good seismic velocity models and that our two-dimensional crossover operators always performed better than one-dimensional crossover. The genetic algorithms also produces models that fit the data better than models produced by simulated annealing. We believe that our results together with the easy parallelizability of genetic algorithms make a strong case for their use in seismic inversion.
We use genetic algorithm to attack the vehicle routing problem with time windows. Previous work has shown that although merge crossover works better than traditional cross operators for this problem, it does poorly on problems with non-random customer locations. In this paper we modify the merge crossover operator to achieve better performance on problems with clustered customer locations. Our algorithm optimally solved three out of six benchmark problems and came within 0.23% of the optimal on the rest.
This paper uses genetic algorithms augmented with a case-based memory of past problem solving attempts to obtain better performance over time on sets of similar problems. When confronted with a problem we seed a genetic algorithm's initial population with solutions to similar, previously solved problems and the genetic algorithm then adapts its seeded population toward solving the current problem. We address the issue of selecting ``appropriate'' cases for injection and introduce a methodology for solving similar problems using genetic algorithms combined with case-based memory. Combinational circuit design serves as a structured testbed and provides insight that is used to validate the feasibility of our approach on other problems. Results indicate that seeding a small percentage of the population with ``appropriate'' cases improves performance on similar problems and that the combined system usually takes less time to provide a solution to a new problem as it gains experience (memory) from solving other similar problems.
This paper explores the feasibility of augmenting genetic algorithms with a long term memory. During a genetic algorithm run, we periodically store individuals in a database. When confronted with a new problem, instead of starting from scratch, we inject the solutions to previously solved similar problems (from the database) into the initial population of the genetic algorithm. We evaluate the performance of the genetic algorithm with such a long term memory on a set of benchmark traveling salesman problems. In addition, we compare the performance of these augmented genetic algorithms when trained on traveling salesman problems of varying similarity. Preliminary results indicate that we can always get better performance with injection of previous solutions to similar problems.
We combine genetic algorithms and case-based reasoning principles to find optimally directed solutions to open shop scheduling and open shop re-scheduling problems. Appropriate solutions to open shop scheduling problems are injected into the genetic algorithm's population to speed up and augment genetic search on a related open shop re-scheduling problem. Preliminary results indicate that the combined genetic algorithm – case-based reasoning system quickly finds better solutions than the genetic algorithm alone.
This paper describes an approach to incorporating domain knowledge into genetic algorithm search. WE use genetic algorithms to attack system configuration design problems; specifically, the structural design and optimization of trusses. Since there exists a large amount of domain knowledge on this problem we describe the incorporation of this knowledge for guiding genetic search. We outline the problem, the heuristics used, and the encoding of the problem in light of available domain knowledge. Preliminary results point toward the effectiveness of combining genetic algorithms with knowledge-based systems.
This paper defines a class of spaces which are easy for genetic algorithms and hard for stochastic hill–climbers. These spaces require genetic recombination for successful search and are partially deceptive. Problems where tradeoffs need to be made subsume spaces with these properties. Preliminary results comparing a genetic algorithm without crossover against one with two–point crossover support these claims. Further we show how a genetic algorithm using pareto optimality for selection, outperforms both. These results provide insight into the kind of spaces where recombination is necessary suggesting further study of properties of such spaces, and what it means to be GA–easy and hill–climbing hard.