Genetic Algorithms Digest Monday, May 26 1992 Volume 6 : Issue 17 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL - anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL (see v6n5 for details) Today's Topics: - Technical report available - Info on a new book - GA's and Protein folding refs? - Two papers from 91 Conference wanted - NN hyperplane animator - Genitor Code Package of Colorado State, D. Whitley - Handling restrictions - Need individuals to serve on dissertation committee - Benefits of crossover - Employment Announcement, GA related ********************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) COGANN, Combinations of GAs and NNs, @ IJCNN-92 (v5n31) Jun 6, 1992 ARTIFICIAL LIFE III, Santa Fe, NM Jun 15-19, 1992 Evolution as a computational process, Monterey (v6n9) Jun 22-24, 1992 ML-92, Machine Learning Conference, Aberdeen (v6n8) Jul 1-3, 1992 10th National Conference on AI, San Jose, Jul 12-17, 1992 FOGA-92, Foundations of Genetic Algorithms, Colorado (v5n32) Jul 26-29, 1992 COG SCI 92, Cognitive Science Conference, Indiana, (v5n39) Jul 29-1, 1992 ECAI 92, 10th European Conference on AI (v5n13) Aug 3-7, 1992 Parallel Problem Solving from Nature, Brussels, (v5n29) Sep 28-30, 1992 SAB92, From Animals to Animats, Honolulu (v6n6) Dec 7-11, 1992 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ********************************************************************** ---------------------------------------------------------------------- From: dorigo@ICSI.Berkeley.EDU (Marco Dorigo) Date: Mon, 27 Apr 92 15:11:13 PDT Subject: Technical report available The following technical report is available and can be requested from: Marco Dorigo International Computer Science Institute 1947 Center Street Suite 600 Berkeley, California 94704-1105 USA tel (510) 643-9153 fax (510) 643-7684 e-mail: dorigo@icsi.berkeley.edu. Title: Implicit Parallelism in Genetic Algorithms Authors: A. Bertoni, M.Dorigo Report n : 92-012 - Politecnico di Milano - Italy Abstract: In this paper we revisit Holland's theorem on implicit parallelism. Holland demonstrated a O(n^3/c1) lower bound to the number of schemata usefully processed by the genetic algorithm in a population of n = c1 * 2^l binary strings, with c1 a small integer. We show that Holland's result is probabilistic in nature and we give similar results in the case of arbitrary c1. ------------------------------ From: zbyszek@unccvax.uncc.edu (Zbigniew Michalewicz) Date: Wed, 29 Apr 92 15:37:35 EDT Subject: Info on a new book A new book on genetic algorithms will appear shortly: Title of Book: "Genetic Algorithms + Data Structures = Evolution Programs" Author: Zbigniew Michalewicz Publisher: Springer-Verlag, (Artificial Intelligence Series) Publication date: June, 1992. ISBN#: 0-387-55387-8 Other: Hardcover, 250pp., 48 figures, 29 tables. Price: approx. $41.00 TABLE OF CONTENTS: Preface Table of Contents Introduction Part I Genetic Algorithms 1. GA: What Are They? 2. GA: How Do They Work? 3. GA: Why Do They Work? 4. GA: Selected Topics Part II Numerical Optimization 5. Binary or Float? 6. Fine Local Tuning 7. Handling Constraints 8. Evolution Strategies and Other Methods Part III Evolution Programs 9. The Transportation Problem 10. The Traveling Salesman Problem 11. Graph Problems, Scheduling, and Partitioning 12. Machine Learning Conclusions To order: * call 1-800-SPRINGE(R), i.e., 1-800-777-4643 (in NJ call (201)348-4033) * FAX your request (201) 348-4505 Thank you Zbigniew Michalewicz Mail: Department of Computer Science E-mail: zbyszek@unccvax.uncc.edu University of North Carolina Phone: (704) 547-4873 Charlotte, NC 28223 Fax: (704) 547-2352 ------------------------------ From: peb@autodesk.com (Paul Baclace {Xanalogical User Interfaces}) Date: Thu, 30 Apr 92 14:40:21 PDT Subject: GA's and Protein folding refs? I am looking for previous work on Protein Folding using GA's. Previous work seems to use Neural Networks to recognize combinations and recall structure, but a GA could possibly speed up a series of single point optimizations, I think. If you have done work in this are, please send me mail. Paul E. Baclace peb@autodesk.com --------------------------------------- From: kcj@matilda.vut.edu.au (Kate Juliff) Date: Sun, 3 May 92 15:07:57 EST Subject: Two papers from 91 Conference wanted I would like to get hold of the two papers from the 1991 Conference. I believe they are anavailable in Australia. Will some kind soul help me? The papers are by Husbands & Mill and Muhlenbein, Schomisch & Born Thanks in advance, Kate Juliff kcj@matilda.vut.edu.au ------------------------------ From: booker@starbase.MITRE.ORG (Lashon Booker) Date: Tue, 5 May 92 09:26:38 EDT Subject: NN hyperplane animator This announcement may be of interest to the GA community. Lashon ***** Begin Included Message ***** From: pratt@cs.rutgers.edu Date: Mon, 4 May 92 18:01:05 EDT Subject: Announcing the availability of a hyperplane animator ----------------------------------- Announcing the availability of an X-based neural network hyperplane animator ----------------------------------- Lori Pratt and Paul Hoeper Computer Science Dept Rutgers University Understanding neural network behavior is an important goal of many research efforts. Although several projects have sought to translate neural network weights into symbolic representations, an alternative approach is to understand trained networks graphically. Many researchers have used a display of hyperplanes defined by the weights in a single layer of a back-propagation neural network. In contrast to some network visualization schemes, this approach shows both the training data and the network parameters that attempt to fit those data. At NIPS 1990, Paul Munro presented a video which demonstrated the dynamics of hyperplanes as a network changes during learning. This video was based on a program implemented for SGI workstations. At NIPS 1991, we presented an X-based hyperplane animator, similar in appearance to Paul Munro's, but with extensions to allow for interaction during training. The user may speed up, slow down, or freeze animation, and set various other parameters. Also, since it runs under X, this program should be more generally usable. This program is now being made available to the public domain. The remainder of this message contains more details of the hyperplane animator and ftp information. ****** 1. What is the Hyperplane Animator? The Hyperplane Animator is a program that allows easy graphical display of Back-Propagation training data and weights in a Back-Propagation neural network. Back-Propagation neural networks consist of processing nodes interconnected by adjustable, or ``weighted'' connections. Neural network learning consists of adjusting weights in response to a set of training data. The weights w1,w2,...wn on the connections into any one node can be viewed as the coefficients in the equation of an (n-1)-dimensional plane. Each non-input node in the neural net is thus associated with its own plane. These hyperplanes are graphically portrayed by the hyperplane animator. On the same graph it also shows the training data. 2. Why use it? As learning progresses and the weights in a neural net alter, hyperplane positions move. At the end of the training they are in positions that roughly divide training data into partitions, each of which contains only one class of data. Observations of hyperplane movement can yield valuable insights into neural network learning. 3. How to install the Animator. Although we've successfully compiled and run the hyperplane animator on several platforms, it is still not a stable program. It also only implements some of the functionality that we eventually hope to include. In particular, it only animates hyperplanes representing input-to-hidden weights. It does, however, allow the user to change some aspects of hyperplane display (color, line width, aspects of point labels, speed of movement, etc.), and allows the user to freeze hyperplane movement for examination at any point during training. How to install the hyperplane animator: 1. copy the file animator.tar.Z to your machine via ftp as follows: ftp cs.rutgers.edu (128.6.25.2) Name: anonymous Password: (your ID) ftp> cd pub/hyperplane.animator ftp> binary ftp> get animator.tar.Z ftp> quit 2. Uncompress animator.tar.Z 3. Extract files from animator.tar with: tar -xvf animator.tar 4. Read the README file there. It includes instructions for running a number of demonstration networks that are included with this distribution. DISCLAIMER: This software is distributed as shareware, and comes with no warantees whatsoever for the software itself or systems that include it. The authors deny responsibility for errors, misstatements, or omissions that may or may not lead to injuries or loss of property. This code may not be sold for profit, but may be distributed and copied free of charge as long as the credits window, copyright statement in the ha.c program, and this notice remain intact. ------------------------------ From: Chris Whitley Date: Thu, 7 May 92 15:35:41 MDT Subject: Genitor Code Package of Colorado State, D. Whitley Hi! Anyone who has obtained a copy of the Genitor package from the genetic algorithm research group at Colorado State University (Darrell Whitley's crew), I would really appreciate your taking a moment to give me some feedback on your experience with it. I am the author of the code, and it is part of my thesis project. Any comments you give me will be anonymous, but may be included in my thesis. 1. Why did you obtain Genitor code? Was it merely curiosity, because you wanted to see how a genetic algorithm worked, because you were interested in the Genitor algorithm in particular, because you wanted to use it for a specific application, what? 2. What, if any, application did you use the Genitor package for? 3. How long did it take you to figure out how to use the Genitor package? Was it a easy, difficult, painful? 4. Did you read the documentation, or just look at the examples? 5. Did you already have your own genetic algorithm code in house? If so, did Genitor replace any of your code? 6. I'd be happy to hear anything you have to tell me about your experience, or to answer any questions you might have. Thanks in advance for answering! Chris Whitley Chris.Whitley@FtCollinsCO.NCR.COM (303)223-5100 ------------------------------ From: Anthony Katz Date: Fri, 8 May 92 12:37:37 BST Subject: Handling restrictions I am trying to use a GA solution for an optimisation problem. The problem is the restrictions of the model. To kill every illegal chromo after crossover would too rapidly diminish the population. (zero value -> kill ). To modify the chromo minimally into a legal one, could be very complicated and take up a serious amouunt of time. My experience has led me to beleive that there are two types of restrictions, fatal and non fatal. The non-fatal can be given a relatively lower value, and the fatal kill. Deciding which type of broken restriction` is which has proved difficult, bur it looks promosing. Being a new-comer to this field, I would welcome advice from anyone on dealing with restrictions. Thanks, Anthony Katz ak3@doc.ic.ac.uk Imperial College London. ------------------------------ From: HOLMES@mscf.med.upenn.edu Date: Wed, 22 Apr 92 17:38 EDT Subject: Need individuals to serve on dissertation committee To whom it may concern: I am trying to locate university faculty in the Philadelphia area who are interested in GAs; I need at least one such individual to serve on a dissertation committee. Is it possible to forward to me a list of participants in GA-List, especially those from Drexel University (if any)? Thanks for your help! John H. Holmes Clinical Epidemiology Unit University of Pennsylvania School of Medicine Philadelphia, PA 19104 215-898-7838 (voice) ------------------------------ From: Melanie Mitchell Date: Mon, 11 May 92 18:33:40 -0400 Subject: Benefits of crossover In reply to Mike Hobbs message on "Cross-over vs Mutation": There are a number of points to be made here. First, crossover most certainly does not help on every problem. One class of problems where it does not help was discussed in a paper by Stephanie Forrest and myself, "The performance of genetic algorithms on Walsh polynomials: Some anomalous results and their explanation", in the 1991 ICGA proceedings. One reason crossover did not work on the functions we were studying was that there was no information from lower order building blocks. There are other reasons crossover can also fail to help as well. In general, it is an open (but very important) problem to characterize the class of problems on which crossover helps. The "building blocks hypothesis" says that crossover helps when short, low-order, fit schemas recombine to form even more highly fit higher-order schemas. This is a start, but it is not specific enough. There has been some work in the GA community on trying to understand in more detail when crossover will help. Some examples of some recent papers concerning this are: Eshelman et al., "Biases in the crossover landscape", in the 1989 ICGA proceedings. Manderick et al., "The genetic algorithm and the structure of the fitness landscape", in the 1991 ICGA proceedings. Schaffer and Eshelman, "On crossover as an evolutionarily viable strategy", in the 1991 ICGA proceedings. Mitchell, Forrest, and Holland, "The royal road for genetic algorithms: Fitness landscapes and GA performance", in Proceedings of the First European Conference on Artificial Life (MIT Press, 1992). Forrest and Mitchell, "Towards a stronger building-blocks hypothesis: Effects of relative building-block fitness on GA performance" (To appear in FOGA 2). Fogel and Atmar, "Comparing genetic operators with Gaussian mutations in simulated evolutionary processes using linear systems. Biological Cybernetics 63, 111-114, 1990. There are others as well, but this gives a start. It may be that your application is one of the problems on which crossover won't help too much. But on the other hand, you are using uniform crossover, which is highly destructive of schemas. On certain problems single-point or two-point crossover will help and uniform crossover won't. There are a number of papers on this in the various ICGA proceedings, including the Schaffer and Eshelman paper listed above. Also .06 per bit is a very high mutation rate, and thus mutation may be destroying any benefit crossover might give. Hope this is of some help. Melanie Mitchell AI Lab University of Michigan ------------------------------ From: ds1@philabs.Philips.Com (Dave Schaffer) Date: Tue, 12 May 92 14:28:35 EDT Subject: Employment Announcement, GA related INDUSTRIAL DYNAMICS RESEARCH Genetic Algorithms Project: The Industrial Dynamics Research Department of Philips Laboratories is seeking highly motivated researchers to contribute to activities in Genetic Algorithms (GAs). The project goals include applying GAs to real problems in design and manufacturing and conducting research to improve our understanding of GAs as successful adaptive processes. The ideal candidate has: - MS or PhD in Computer Science, Electrical Engineering, Operations Research or related fields. - Theoretical knowledge of and experience with genetic algorithms; - Skill at programming in C under the UNIX operating system; - A strong motivation to advance the state of the art in genetic algorithms and apply this understanding to practical engineering problems; - An ability to work interactively with a creative group of researchers and experts from various application domains. Philips Laboratories is located on the east side of the Hudson River, about an hour's drive north of New York City. We offer a competitive benefits and salary package. Interested individuals should send their resumes to: Mary Beth Morley mba@philabs.philips.com (914) 945-6056 Philips Laboratories 345 Scarborough Road Briarcliff Manor, NY 10510 Philips is an equal opportunity employer. ------------------------------ End of Genetic Algorithms Digest ******************************