Genetic Algorithms Digest Thursday, 15 December 1988 Volume 2 : Issue 25 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - GA implementation problems - Re: Classifier systems problems -------------------------------- From: thefool@ATHENA.MIT.EDU Date: Mon, 12 Dec 88 08:59:31 EST Subject: GA implementation problems As part of a horse racing genetic learning algorithm system I developed, I created several ga diagnosis techniques that might be helpful to others. I am interested in hearing from people who 1) have had difficulty setting up a ga system 2) have solved hard *implementation* problems with gas -- Michael de la Maza thefool@athena.mit.edu -------------------------------- From: "Leonard" Date: Wed, 14 Dec 88 15:39:58 PST Subject: Re: Classifier systems problems Mr. Michael R. Hall writes: "[I would generally advise against Michigan approach classifier systems for program induction as well, but that's another story.]" Inasmuch as I am working with a Michigan style classifier system -- altered to be sure, but still a system that applies genetic operators to single production rules rather than to sets of them in the manner of either Smith or Grefenstette -- this is a story that I would honestly like to hear. If I'm on the wrong track, I want to know sooner rather than later. I appreciated Mr. Hall's remarks about the problem of premature convergence and his recommendation of speciation as the preferred solution. There are, however, a number of approaches to speciation. Holland, in "Adaptation in Natural and Artificial Systems," pp. 164-170, discusses the concept in terms of one-armed bandits and stable queues and makes a point of the fact that, given his model, speciation can take place in the absence of isolation. Other researchers, explicitly interested in techniques for promoting speciation (or niche formation? -- the concepts get conflated), have used either some measure of a string's similarity to the rest of the population to condition mating (preselection, crowding, sharing functions) or a restrictive mating strategy (mating templates). References to all of these approaches are found in Goldberg's "Genetic Algorithms." There is yet another method that I've tried with some success -- multiple reproductive schedules. Each classifier has a string that specifies WHEN it will reproduce. Each position in the string is associated with a prime number or a multiple of primes. When a classifier has a '1' in a given position it will reproduce in every 'year' that is divisible without remainder by the number associated with that position. A 'year' is defined a some number of iterations through the problem set. This arrangement has good effects. The influence of strong individuals is buffered by the fact that they cannot mate with the entire population. Their influence must spread through classifiers that have a variegated reproductive schedule. In other words, the classifier population is graded between those that have high mutability/responsiveness and those that are comparatively staid. This prevents premature convergence. In the earlier cycles of a run, presuming that you begin with a randomly generated population, this grading provides a kind of time-released randomness as succesive sets of classifiers hit their first '1'. It is interesting to observe that sometimes the functional role of a set of classifiers or their trophic depth CAN become highly correlated with a particular reproductive schedule (i.e., niche and species will converge). The use of multiple reproductive schedules can incidentally give you many of the benefits of having competing rule populations, but you let the system (for better or worse) define the size and membership of those groups on its own. If all goes well I should have a paper about this ready for the 3rd ICGA deadline. Comments from anyone who has tried something similar would be deeply appreciated -- especially, of course, if this strategy has been abandoned for reasons that I have yet to discover. -------------------------------------------------------------------- Leonard Lutomski AIR Center for Applied Artificial Intelligence xt.a08@stanford 1791 Arastradero Road 415-493-3550 Palo Alto, CA 94302 -------------------------------- End of Genetic Algorithms Digest ********************************