Genetic Algorithms Digest Thursday, 24 March 1988 Volume 2 : Issue 10 - Send submissions to GA-List@NRL-AIC.ARPA - Send administrative requests to GA-List-Request@NRL-AIC.ARPA Today's Topics: - Classifier Systems - Parallel GAs - GAs for Image Registration - GA Research at Mitre Corp. -------------------------------- Date: Mon, 21 Mar 88 19:20:03 GMT From: Gary Roberts Subject: Research on Classifier Systems APPLICATION AREA: Discovery Learning in a Rich Simulated Environment GENERAL APPROACH: I am experimenting with various modifications to the standard classifier systems. GA TOOL: Classifiers are produced via genetic algorithm. RESULTS: I have attempted duplication of Wilson's "Animat" as reported in "Knowledge Growth in an Artificial Animal", from the 1985 GA Conference proceedings. So far, I have not managed to match that performance level. Note, however, that I have not yet implemented the distance metric described. It does not appear difficult. PROBLEMS: None, at the moment. -------------------------------- Date: Tue, 22 Mar 88 09:31:36 EST From: "Worthy N. Martin" Subject: Parallel GAs I am actively working on a parallel version of GA which Dana Richards, Jim Cohoon and I refer to as Punctuated Equilibrium - GA. This model is being designed with message passing multiprocessors in mind. Our results on the ordered linear array (OLA) problem were presented at the last GA conference. We are currently expanding the model and applying it to several VLSI problems. Worthy Martin -------------------------------- Date: Wed, 23 Mar 88 20:45:03 CST From: John Grefenstette Subject: GAs for Image Registration This note describes some work that Mike Fitzpatrick and I have done at Vanderbilt University. APPLICATION AREA: Medical image registration. The problem is to compensate for patient/camera motion occurring between the taking of two x-ray images, so that the earlier mask image can be subtracted from the later one to produce a clear image of particular arteries (into which dye has been injected in the meantime.) Unavoidable motion by the patient/camera produces blurs, or motion artifacts, that may require a repetition of the procedure. GENERAL APPROACH: We define a parameterized class of transformations that may compensate for the motion, and use GAs to search for high performance transformations. The evaluation of a transformation is based on the average gray-level pixel difference between the target image and the transformed mask image. Minimizing this difference generally minimizes the motion artifacts, since the only remaining difference comes from the (generally small) artery. GA TOOL: Genesis, interfaced to a displaytool that allows us to watch as the image improves. RESULTS: Preliminary results have been very encouraging, but we are just beginning to experiment with real coronary artery images. From the GA point of view, the most interesting results concern the performance of GAs when the evaluation function is too complex to compute exactly, but can be estimated by sampling. In our problem, the computation of the exact difference between two images requires involves thousands of pixel comparisons. However, we have found that GAs do extremely well with fairly crude estimates. For example, we routinely estimate the "fitness" of a transformation by sampling about 20 pixels, so that it becomes feasible to evaluate several thousand candidate transformations in a few cpu minutes. We have explored tradeoffs between the number of samples per eval and the population size, as well as between the samples per trial and the number of generations that can be run in a fixed amount of time. For more details, see: Fitzpatrick, J. M., D. R. Pickens, J. J. Grefenstette, R. R. Price and A. E. James, (1987). A technique for automatic motion correction in DSA. Optical Engineering 26(11), (pp. 1085-1093). Grefenstette J. J. and J. M. Fitzpatrick, (1985). Genetic search with approximate function evaluation. Proceedings of the First International Conference Genetic Algorithms and Their Applications (pp. 112-120). Pittsburgh, PA: Lawrence Erlbaum Assoc. Grefenstette J. J. and J. M. Fitzpatrick, (1987). Genetic algorithms using Monte Carlo function evaluations. Submitted to Machine Learning Journal. PROBLEMS: We are in the process of doing an extensive experimental comparison of a number of search techniques in this domain, including GAs, simulated annealing, iterated hill-climbing, and specialized methods. -------------------------------- Date: Wed, 23 Mar 88 12:14:58 EST From: jima@mitre.arpa Subject: GA Research at Mitre Corp. John, Good to hear from you! Yes, I definitely want to be on the GA list. Please also add Karl Keller, keller@mitre.arpa, if he's not on it already. OK. Our application area is tactical intelligence (for now, anyway), although we've put a lot of effort into building a simulation environment that should be appropriate to other domains. The problem as we've defined it is one of unsupervised learning by predicting an adversary's actions. The idea is to implement the bucket-brigade and similar approaches in a reasonably standard production system to demonstrate its appropriateness for a large class of AI programs. This year we are developing a formal analysis and empirical evidence of the behavior of these algorithms for credit assignment, with particular interest in absolute measures of utility in complex inference networks (the usual approach leading to utility measures that depend in part on the ply of the rules in a rule chain). We hope to buffer all hypothesized new structural relations in the domain throughg a hypothetical worlds facility (which is making the tracking of rule wealths pretty interesting). The only new relations we are presently worried about are new rules. Part of our work in rule generation has been to make sense of crossover for structured representations. We will be reexpressing operators in meta-level rules in hopes of apportioning credit for successful adaptations among them. Tool: Pattern-invoked (RETE) rule interpreter which inferences over terms of a domain. Terms and relations (including rules themselves) are declaratively represented in a frame system, rules are the procedural updating mechanisms for the domain, much like in KRYPTON. Right now LISP code generates new rules by, e.g., a crossover-like operater, but, as mentioned, we are working to have that taken over by a set of meta-rules (summer). Results: There are some problems with just importing the bucket brigade into a production system environment for rule evaluation (mainly the one mentioned above and the confounding of rule utility and its "reliability"). For unsupervised domains the algorithm actually seems more appropriate. Keller has found a nice meta-level procedure for speeding up apportionment which is a powerful generalization of the bridging idea. Crossover is an interesting search operator which is hard to interpret for context-sensitive representations, but something in the ballpark has been implemented, and the right thing can probably be done with a powerful grammatical representation of rule derivations. We haven't done it yet, though. Problems: Other than catching the AI chill? We don't have a measure for partial match that we really believe in/ is reasonable to compute for production systems, although we get by with OPS-like syntactic solutions. As mentioned, the tracking of credit in multiple worlds is pretty bad, but even worse is that sequences of new hypotheses (new worlds) that unify in "normal" systems should properly fail to unify in ours. This can happen because the same rule will usually have different wealths in the worlds leading up to the unified world. Our (my) main problem, though, is the bit-string representation that is erroneously (yes!) viewed as optimizing implicit parallism. Some chance that we'll be able to turn our attention to that this summer, after meta-level inference is in place. (We should all be so lucky to have such problems!) Jim Antonisse MITRE -------------------------------- End of Genetic Algorithms Digest ********************************