Professor, CSE
Director, ECSL
Journal Publications
We use case-injected genetic algorithms to learn to competently play computer strategy games. Case-injected genetic algorithms periodically inject individuals that were successful in past games into the population of the GA working on the current game, biasing search towards know successful strategies. Computer strategy games are fundamentally resource allocation games characterized by complex long-term dynamics and by imperfect knowledge of the game state. The case-injected genetic algorithm plays by extracting and solving the game s underlying resource allocation problems. We show how case injection can be used to learn to play better from a human s or system s game-playing experience and our approach to acquiring experience from human players showcases an elegant solution to the knowledge acquisition bottleneck in this domain. Results show that with an appropriate representation, case injection effectively biases the genetic algorithm towards producing plans that contain important strategic elements from previously successful strategies.
Genetic algorithms (GAs) augmented with a case-based memory of past design problem-solving attempts are used to obtain better performance over time on sets of similar design problems. Rather than starting anew on each design, a GA’s population is periodically injected with appropriate intermediate design solutions to similar, previously solved design problems. Experimental results on configuration design problems: the design of parity checker and adder circuits, demonstrate the performance gains from the approach and show that the 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 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 attempts 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 acquiring and using problem specific knowledge during genetic algorithm search. A genetic algorithm augmented with a case-based memory of past problem solving attempts, learns to obtain better performance over time on sets of similar problems. Rather than starting anew on each problem, we periodically inject a genetic algorithm’s population with appropriate intermediate solutions to similar, previously solved problems. Perhaps, counter-intuitively, simply injecting solutions to previously solved problems does not produce very good results. We provide a framework for evaluating this genetic algorithm based machine learning system and show experimental results on a set of design and optimization problems. These results demonstrate the performance gains from our approach and indicate that our system learns to take less time to provide quality solutions to a new problem as it gains experience from solving other, similar, problems in design and optimization.
We investigate the application of genetic algorithms (GAs) for recognizing real two-dimensional (2-D) or three-dimensional (3-D) objects from 2-D intensity images, assuming that the viewpoint is arbitrary. Our approach is model-based (i.e., we assume a predefined set of models), while our recognition strategy lies on the recently proposed theory of algebraic functions of views. According to this theory, the variety of 2-D views depicting an object can be expressed as a combination of a small number of 2-D views of the object. This implies a simple and powerful strategy for object recognition: novel 2-D views of an object (2-D or 3-D) can be recognized by simply matching them to combinations of known 2-D views of the object. In other words, objects in a scene are recognized by predicting their appearance through the combination of known views of the objects. This is an important idea, which is also supported by psychophysical findings indicating that the human visual system works in a similar way. The main difficulty in implementing this idea is determining the parameters of the combination of views. This problem can be solved either in the space of feature matches among the views (image space) or the space of parameters (transformation space). In general, both of these spaces are very large, making the search very time consuming. In this paper, we propose using GAs to search these spaces efficiently. To improve the efficiency of genetic search in the transformation space, we use singular value decomposition and interval arithmetic to restrict genetic search in the most feasible regions of the transformation space. The effectiveness of the GA approaches is shown on a set of increasingly complex real scenes where exact and near-exact matches are found reliably and quickly
The time-dependent gradient structure of a laser compressed, high energy density plasma has been determined using a method based on the simultaneous analysis of time-resolved X-ray monochromatic images and X-ray line spectra from Ar-doped D2 implosion cores. The analysis self-consistently determines the temperature and density gradients that yield the best fits to the spatial emissivity profiles and spectral line shapes. This measurement is important for understanding the atomic kinetics, radiation transfer and plasma dynamics associated with the implosion process. In addition, since the results are independent of hydrodynamic simulations they are also important for comparison with detailed fluid dynamic models of hot dense plasmas.
An algorithmic method for the analysis of X-ray line spectra using genetic algorithms is presented. This technique permits the extraction of diagnostic information on the emitting medium from the spectral data. As an exampled of themethod, plasma electron number density and temperature are extracted from the analysis of X-ray spectral data recorded in an Ar-doped inertial-confinement-fusion core. For the studey of a sequence of gradually changing spectra, a combination of genetic algorithms and case-based reasoning that learns from experience is used to accelerate the analysis. The techniqus is general and can be applied to other plasma spectroscopy studies including analysis of spatially and temporally resolved line absorption or emission data.
This paper examines the feasibility of using genetic algorithms augmented with a long term memory toattack similar traveling salesman problems. The proposed learning systems combines a genetic problem solver with a case-base or data-base of past problem solving attempts to increase performance with experience. Instead of starting from scratch, we retreive and inject the solutions of previously solved similar problems into the initial population of genetic algorithms to provide a performance boost. In this paper we are more concerned with relative improvement in performance over time rather than with absolute performance and our results on a number of problems indicate that we can always get better performance with the combined system. If, as we believe, the results are generalizable, combining a case-base with a genetic algorithm will benefit most purely genetic algorithm implementations.
We reduce stability robustness analysis for linear, time-invariant, discrete-time systems to a search problem and attack the problem using genetic algorithms. We describe the problem framework and the modifications that needed to be made to the canonical genetic algorithm for successful application to robustness analysis. Our results show that genetic algorithms can successfully test a sufficient condition for instability in uncertain linear systems with nonlinear polynomial structures. Three illustrative examples demonstrate the new approach.
We use a genetic algorithm augmented with a long term memory to design control strategies for a simulated robot, a mobile vehicle operating in a two-dimensional environment. The simulated robot has five touch sensors, two sound sensors, and two motors that drive locomotive tank tracks. A genetic algorithm trains the robot in several specially-designed simulation environments for evolving basic behaviors such as food approach, obstacle avoidance, and wall following. Control strategies for a more complex environment are then designed by selecting solutions from the stored strategies evolved for basic behaviors, ranking them according to their performance in the new complex environment and introducing them into a genetic algorithm's initial population. This augmented memory-based genetic algorithm quickly combines the basic behaviors and finds control strategies for performing well in the more complex environment.
Pareto optimal designs are the best designs that can be produced for a given problem formulation for a given set of criteria when the criteria are not combined in any way. If the goal is to improve the performance in those criteria then it is possible to manipulate the problem formulation to achieve an improvement. The approach adopted is to encode the formulation in a genetic algorithm and to allow the formulation to evolve in the direction of improving Pareto optimal designs. A set of rules (in the form of a shape grammar), the execution of which produces a design, is encoded as the genes in a genetic algorithm. However, the rule set is allowed to evolve, not just the order of execution of rules. We present an example demonstrating both the approach and its utility in improving Pareto optimal designs.
When confronted by a problem, human designers often work forward from similar previously solved problems to solve the current problem. Based on this principle, we propose a new learning system especially suited for design using case-based reasoning principles to augment genetic algorithm search. 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. Preliminary results on open-shop scheduling and re-scheduling indicate the feasibility of this approach.
This paper describes the encoding of domain knowledge for use by a genetic algorithm. We use the domain of system configuration design problems; specifically, the structural design and optimization of trusses to ground our discussion and results. The approach applies evolutionary principles to the optimally directed configuration design of complex structures and incorporates engineering domain knowledge into a genetic algorithm to synthesize the topology, geometry, and component properties of the structure. Preliminary results indicate that genetic algorithms with domain knowledge can generate feasible and useful designs.
This paper focusses on that form of learning which relates to exploration, rather than generalization. It uses the notion of exploration as the modification of state spaces within which search and decision making occur. It demonstrates that the genetic algorithm formalism provides a computational construct to carry out this learning. The process is exemplified using a shape grammar for a beam section. A new shape grammar is learned which produces a new state space for the problem. This new state space has improved characteristics.
This paper describes a system for explaining solutions generated by genetic algorithms (GAs) using tools developed for case-based reasoning (CBR). In addition, our work empirically supports the building block hypothesis (BBH) which states that genetic algorithms work by combining good sub-solutions called building blocks into complete solutions. Since the space of possible building blocks and their combinations is extremely large, solutions found by GAs are often opaque and cannot be easily explained. Ironically, much of the knowledge required to explain such solutions is implicit in the processing done by the GA. Our system extracts and processes historical information from the GA using knowledge acquisition and analysis tools developed for case-based reasoning. If properly analyzed, the resulting knowledge base can be used: to shed light on the nature of the search space, to explain how a solution evolved, to discover its building blocks, and to justify why it works. Such knowledge about the search space can be used to tune the GA in various ways. As well as being a useful explanatory tool for GA researchers, our system serves as an empirical test of the building block hypothesis. The fact that it works so well lends credence to the theory that GAs work by exploiting common genetic building blocks.