Genetic Algorithms Digest Tuesday, 14 November 1989 Volume 3 : Issue 18 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - GA Workshop? - Re: GA for ANN (2) *************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) 1-2 Dec 89 - NIPS Workshop: NNs and GAs (v3n16) 15-19 Jan 90 - IJCNN Session on Evolutionary Processes (v3n10) Mar 90 - Double Auction Tournament - Sante Fe Institute (v3n12) 9 May 90 - Workshop on GAs, Sim. Anneal., Neural Nets - Glasgow (v3n15) 21-23 Jun 90 - 7th Intl. Conference on Machine Learning (submissions 1 Feb 90) (Send other activities to GA-List@aic.nrl.navy.mil) *************************************************************************** -------------------------------- Date: Tue, 24 Oct 89 11:08:07 EDT From: vose%VOSE.CS.UTK.EDU@cs.utk.edu Subject: GA Workshop? I have heard rumors about a GA workshop this summer and would like to attend. The problem is that I must apply for travel funds almost immediately. Please RUSH me information (or point me to it) so that I can ask my university for money to attend. The request process requires exact dates, locations, and dollar amounts, so any and all aid with respect to these questions will be appreciated. Thank you. Michael D. Vose [ See calendar above. - JJG] -------------------------------- Date: Thu, 2 Nov 89 09:30:17 PST From: Subject: Re: GA for ANN (1) Reply-To: tgd@CS.ORST.EDU > Date: Thu, 26 Oct 89 12:11:53 PDT > From: rudnick@cse.ogc.edu (Mike Rudnick) > Subject: GA for ANN design: questions > > > > > NetTalk required 60,000 training vectors, so if each member of each > > population must be trained that long and if it takes say, 10 > > operations per connection in training mode (that is typical in > > back-propagation), you get (after multiplying 1000 x 20000 x 60000 x > > 10000 x 10) about 10 ^ 17 operations. If you have a Cray II which is > > about a billion operations per second, you can figure it will take on > > the order of a year. Even the most massively parallel machines > > envisioned on the horizon will not come close to doing something like > > this in a few days of processing. And this is with a moderately sized > > network! Even with good algorithms you might knock off a couple > > orders of magnitude, but then as networks get larger you'll lose that > > gain rapidly. I share Hammerstrom's skepticism. In fact, consider that the nettalk learning task can be performed using Quinlan's ID3 algorithm with results that are within 1 percentage point of those obtained by back propagation (see Mooney et al in IJCAI-89 or my forthcoming paper). An unoptimized lisp implementation of ID3 requires about 1 CPU hour of SUN 4 time to perform this training, whereas a good C implementation of Backpropagation takes more than 60 CPU hours. Hence, even if GA's can speed up the training of neural networks, the time bound to beat is NOT 60 CPU hours, but 1 CPU hour, which makes Hammerstrom's argument even stronger. Thomas G. Dietterich Department of Computer Science Computer Science Bldg, Room 100 Oregon State University Corvallis, OR 97331-3902 -------------------------------- Date: Thu, 9 Nov 89 12:53:09 PST From: rik%cs@ucsd.edu (Rik Belew) Subject: Re: GA for ANN (2) There's been too much Email ink spilled lately about potential interactions between evolutionary algorithms and connectionist networks for me not to throw my two cents in. I announced a new tech report, "Evolution, learning and culture: Computational metaphors for adaptive algorithms" on this list a couple of weeks ago and I don't know whether the recent storm of messages has anything to do with that report or not. Anyway, some of the things I'll say below are better said there. Let me begin with Hammerstrom's analysis, related in [rudnick@cse.ogc.edu 26 Oct 89]. His basic point seems to be that connectionist algorithms (he uses NetTalk as his example) take a long time, and putting an evolutionary outer loop around them can only make matters worse. And if we are satisfied with the results of a single backpropagation (BP) search and the evloutionary loop is doing nothing more than randomly repeating this experiment, he may be right. But only if. First, who today is satisfied with vanilla BP in feed-forward networks? (And I'm not just BP bashing; almost all of what I say applies equally to other gradient descent connectionist learning algorithms.) A great deal of current research is concerned with both simplifying such nets to more minimal structures, and elaborating the nets (e.g., with recurrence) to solve more difficult problems. Also, BP performance is known to be highly variable under stochastic variation. Consequently most investigators do use an 'outer-loop' iteration, using multiple restarts to improve their confidence in the solution found. The Genetic Algoritms (GAs) can help with these connectionist problems. (To clarify, when I talk of 'evolutionary algorithms' I have some variant of John Holland's Genetic Algorithm in mind because I believe it to be the most powerful. But there are other evolution- like algorithms (eg, Ackley, Fogel Jr. & Sr.) and these may also prove useful to connectionists.) Second, there is a considerable body of work that shows that evolutionary search is far from random. GA's are extremely effective sampling procedures, at least on some kinds of problems. (See Goldberg's book or the most recent GA proceedings for characterizations of what makes a problem 'GA-hard'.) Further, there are reasons to believe that connectionist nets are a good problem for the GA: the GLOBAL SAMPLING performed by the GA is very compimentary to the LOCAL SEARCH performed by gradient descent procedures like BP. Bridges complains that we are compounding ignorance when we try to consider hybrids of connectionist and GA algorithms [clay@cs.cmu.edu 7 Nov 89]. But we are beginning to understand the basic features of connectionist search (as function approximators, via analysis of internal structure,etc.), and there are substantial things known about the GA, too (e.g., Holland's Schema Theorem and its progeny). These foundations do suggest deliberate research strategies and immediately eliminate others (eg, some of the naive ways in which we might encode a network onto a GA string). There are a tremendous number of ways the techniques can be combined, with the GA as simply an outer loop around a conventional BP simulation being one of the least imaginative. For example, when used in conjunction with the GA there is a very good question as to how long each BP training cycle must be in order to provide a useful fitness measure for the GA. Preliminary results of ours suggest much shorter training times are possible. Similarly, use of the GA seems to tolerate quicker search (i.e., higher learning rate and momentum values) than typical. Another rich dimension is just how a GA bit string is related to a net, from a literal encoding of every real number weight at one extreme to complex developmental programs that build nets at the other. One feature of these hybrids that should not be underestimated is that the GA offers a very natural mechanism for introducing PARALLELISM into connectionist algorithms, since each individual in a population can be evaluated independently. We have had some success exploiting this parallelism in two implementations, one in a SIMD (Connection Machine) environment and one using a heterogeneous mess of distributed computers. Finally we shouldn't let computer science drive the entire agenda. Theoretical biology and evolutionary neurophysiology have some extremely important and unresolved questions that models like these can help to address, for example concerning complex, Lamarckian-like interactions between the learning of individuals and the evolution of species. (I think the Harp et al. simulation may be particularly useful to evolutionary neurophysiologists.) One of the things that makes connectionism most exciting is that the same class of systems that interest (some) mathematicians as new statistical techniques also interest neuroscientists as a theory to coordinate their data collection. I think GA/connectionist hybrids are important for similar reasons: they make sense as algorithms AND they make sense as models of natural phenomena. This note has been long on enthusiasm and short on specifics. But some results have already been reported, by me and others. And I expect there to be many new results reported at the upcoming sessions (at IJCNN in Washington and at the NIPS workshop) devoted to this topic. So watch this space. Richard K. Belew rik%cs@ucsd.edu Assistant Professor CSE Department (C-014) UCSD San Diego, CA 92093 619 / 534-2601 or 534-5288 (messages) -------------------------------- End of Genetic Algorithms Digest ********************************