Genetic Algorithms Digest Thursday, May 26, 1994 Volume 8 : 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 (Info in /pub/galist/FTP) Today's Topics: - Hello, Policy, and Etiquette - Long bit string summary - paper available - Seeking an encoding of 2D structure of ARN - New Genetic Programming Books Available - GA bibliography very soon in press - Ph.D. Dissertation Available ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) The IEEE Conference on Evolutionary Computation, Orlando(v7n26) Jun 26-30, 94 FOGA94 Foundations of GAs Wkshop, Estes Park, Colorado(v7n26)Jul 30-Aug 3, 94 SAB94 3rd Intl Conf on Sim of Adaptive Behavior, Brighton(v7n11) Aug 8-12, 94 ECAI-94, 11th European Conference on AI, Amsterdam (v7n23) Aug 8-12, 94 ECAI-94 Wkshp on Applied Genetic & Other Evol Algs, Amsterdam(v8n5) Aug 9, 94 IEEE/Nagoya Univ WW Wkshp on Fuzzy Logic & NNs/GAs, Japan(v7n33) Aug 9-10, 94 ISRAM94 Special Session on Robotics & GAs, Maui, Hawaii (v7n22) Aug 14-17, 94 Evolution Artificielle 94, Toulouse, France (v8n10) Sep 19-23, 94 COMPLEX94 2nd Australian National Conference, Australia (v7n34) Sep 26-28, 94 PPSN-94 Parallel Problem Solving from Nature, Israel (v7n32) Oct 9-14, 94 GAs in Image Processing and Vision Colloquium, Savoy Place (v8n16) Oct 20, 94 AI'94 Workshop on Evol Comp, Armidale, NSW, Australia (v8n15) Nov 22, 94 EP95 4th Ann Conf on Evolutionary Programming, San Diego,CA(v8n6) Mar 1-4, 95 ICANNGA95 Intl Conf on Artificial NNs and GAs, France (v8n10) Apr 18-21, 95 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 95 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: William M. Spears (GA-List Moderator) Date: Thursday, May 26, 1993 Subject: Hello, Policy, and Etiquette Greetings and Felicitations. I would like to thank Connie Ramsey for the introduction, and for the excellent job she did moderating the GA-List. Moderating GA-List is a time consuming process, which Connie handled with tact and politeness. I hope you will all bear with me as I learn the ropes. One thing that I'd like to do while I'm moderator is to increase the amount of discussion on GA-List. While GA-List serves a useful role as an announcer of CFPs, papers, etc., it also can serve as an informal mechanism for discussion on GA topics of interest. Any help I receive in that regard will be appreciated. Another issue concerns the sheer size of GA-List. We receive a lot of mail, and not all of it is appropriate for GA-List. Thus, I am including a set of policies and guidelines that should help, because they allow the submitter to evaluate the appropriateness of his/her submission. Bill ===================================================================== GA-List Policies: The GA-List mail addresses can only be distributed with the permission of the International Society for Genetic Algorithms (ISGA), and only for GA-related purposes. It is the policy of the ISGA to not allow advertisements per se, although a simple announcement of a new product or service is allowed. The announcement should have a brief description of the product or service, and a contact point for those that are interested. GA-List will allow conference announcements and job positions to be posted. The GA-List moderator will not honor subscribe requests that are not from that person. GA-List Etiquette and Protocol: 1) Permission. You may copy GA-List digests (or parts thereof) for research purposes, as long as these copies are not sold. If you wish to sell copies (or parts thereof), you must obtain permission of the current moderator and all submitters of that material. The GA-List is a forum for informal discussion. Individual submissions (or parts thereof) should not be quoted and cited in text without the permission of the author. If you include private email from another person in your submission, please obtain permission from that person. 2) Patience. GA-List receives a lot of mail, which has to be sifted through carefully. You may see a few digests appear before your message shows up. This happens because the backlog can be large, and because not all topics have the same priority. I urge submitters to be aware of dates, and not send items at the last minute. 3) Appropriateness and Attention to Detail All submissions to GA-List should directly pertain to the field of evolutionary computation and/or classifier systems, be in good taste, and be as concise as possible. I will not perform stylistic editing, so please take the time to format your message neatly using a 80 column page, or I will use it as is. Also, please be careful to send messages to the correct email address. GA-List is for submissions to the digest. GA-List-Request is for administrative requests. For those of you who have a change of email address, please give both your new and OLD address, so we can delete the old address from our database. ===================================================================== ------------------------------ From: David Levine Date: Tue, 17 May 1994 17:27:25 -0500 Subject: Long bit string summary Below is an (edited) summary of responses to my query on the use of GAs on long bit strings. Thanks to all those who replied (and gave permission to include their replies.) dave levine David Levine levine@mcs.anl.gov (708)-252-6735 Fax: (708)-252-5986 MCS 221 C-216 Argonne National Laboratory Argonne, Illinois 60439 ================================================ From: whitley@CS.ColoState.EDU (darrell whitley) We are successfully doing seismic data interpretation on large problems--approximately 6000 bits. The problem is characterized by numerous local minima. The function is also noisy; the evaluation involves computing a cross correlation across 600 variables for approximately 600 time steps. Thus, the evaluation function is only sampled at a rate of 10%. ================================================ From: ds1@philabs.Philips.COM (Dave Schaffer) I have solved (i.e. run and got an answer) a real world problem with 3365 bits (can't disclose details yet). That was the largest, but this class typically gives us 500-1000 bit chromosomes and chromosomes of more than 1000 bits are not rare. Larry Eshelman has played with a 4-bit parity problem using a GA to set weights for a neural net with 10 hidden layers with 10 nodes in each and each weight codes with 6 bits. This gives you > 6000 bits. ================================================ From: h987pal@huella.bitnet (Karoly Pal) I have read your enquiry about longest bit strings used in GA. I am sure there are people who used GA-s for problems with longer strings than myself: in my latest papers (quite recently submitted) I applied GA to a spin-lattice problem with 900-bit strings, that is probably longer than average. If you are interested in these papers, I can send you hard copies, but in that case please, let me know your full postal address. Cheers, Karoly Pal ================================================ From: deb@iitk.ernet.in (kalyanmoy deb) I have used GAs in a filter design problem that had a chromosome length of 16,384. Since the problem had to do FFT and IFFT of a 128X128 image, it was taking a lot of time to compute function value. Nevertheless, GAs have found better filters than a hillclimbing method reported in the literature. Let me know if you need any more information. ================================================ From: levine@mcs.anl.gov (david levine) I have used an island model steady-state GA (ala Genitor II) along with a local search heuristic to solve set partitioning problems (combinatorial optimization). With "enough" subpopulations I solved all the test problems I tried (~30) with <= 3k bits to optimality. I also found optimal solutions to two problems of 5k and 6.7k bits, respectively. On two larger problems (35k and 43k bits), using 128 subpopulations, I found solutions within half a percent and five percent of the (known) optimal solution, respectively. ------------------------------ From: Andrew Wuensche <100020.2727@CompuServe.COM> Date: 03 May 94 12:21:25 EDT Subject: paper available The following SFI working paper (94-04-025) is available (in hard copy only). To request copies, send email to: wuensch@santafe.edu or write to Andy Wuensche 48 Esmond Road London W4 1JQ, UK dont forget to give a surface mail address. COMPLEXITY IN ONE-D CELLULAR AUTOMATA; Gliders, Basins of Attraction and the Z parameter. ================================================== Andrew Wuensche Santa Fe Institute, and University of Sussex - School of Cognitive and Computing Sciences ABSTRACT What do we mean by complexity in the changing patterns of a discrete dynamical system? Complex one-D CA rules support the emergence of interacting periodic configurations - gliders, glider-guns and compound gliders made up of interacting sub-gliders - evolving within quiescent or periodic backgrounds. This paper examines gliders and their interactions in one-D CA on the basis of many examples. The basin of attraction fields of complex rules are typically composed of a small number of basins with long transients (interacting gliders) rooted on short attractor cycles (non-interacting gliders, or backgrounds free of gliders). For CA rules in general, a relationship is proposed between the quality of dynamical behaviour, the topology of the basin of attraction field, the density of garden-of-Eden states counted in attractor basins or sub-trees, and the rule-table's Z parameter. High density signifies simple dynamics, and low - chaotic, with complex dynamics at the transition. Plotting garden-of-Eden density against the Z parameter for a large sample of rules shows a marked correlation that increases with neighbourhood size. The relationship between Z and the lambda parameter is described. A method of recognising the emergence of gliders by monitoring the evolution of the lookup frequency spectrum, and its entropy, is suggested. REFERENCES Wuensche,A., and M.J.Lesser. "THE GLOBAL DYNAMICS OF CELLULAR AUTOMATA; An Atlas of Basin of Attraction Fields of One-Dimensional Cellular Automata", (diskette included), Santa Fe Institute Studies in the Sciences of Complexity, Reference Vol.I, Addison-Wesley, 1992. Wuensche.A.,"THE GHOST IN THE MACHINE; Basins of Attraction of Random Boolean Networks", in Artificial Life III, Santa Fe Institute Studies in the Sciences of Complexity, Addison-Wesley, 1993. ------------------------------ From: carmona@nausikaa.cert.fr (Olivier Carmona) Date: Mon, 11 Apr 94 17:39:43 +0200 Subject: Seeking an encoding of 2D structure of ARN We are working on making predictions on 2D conformationnal structures of ARN with GA. I would like to ask if someone can give us some advices on encoding an ARN in 2D. For instance, we can code each links between two bases (base = nucleotide) by a simple sequence of integer indicating for the the element number i in the list to wich base the base i is connected to(or 0 if no links). But a huge number of chromosom would be incorrect, because if a base i is linked with j then j is linked with i. Moreover our fitness function is a sum of probability (from the Mc Gaskill matrix) of individual appariements and not of the combination of appariements. Please correct my awful english. ------------------------------ From: kinnear@adapt.com Date: Tue, 17 May 94 15:27:54 EDT Subject: New Genetic Programming Books Available Folks, There are a couple of new books on Genetic Programming that you might be interested in knowing more about. The first is called "Advances in Genetic Programming", edited by Kenneth E. Kinnear, Jr. (me), and the second is "Genetic Programming II", by John Koza. Both are from MIT Press. An annotated version of this table of contents (with a paragraph briefly describing each chapter) is available at the GP ftp site: ftp site: ftp.cc.utexas.edu file: /pub/genetic-programming/papers/AiGP.atoc.txt You might also find the following FORTHCOMING items of interest: Genetic Programming II Automatic Discovery of Reusable Programs John R. Koza Genetic Programming II Video The Next Generation John R. Koza You can read more about all of these books in the file: ftp site: ftp.cc.utexas.edu file: /pub/genetic-programming/papers/GPfromMITPress.txt [ WMS: This message has been heavily edited. Please contact kinnear@adapt.com and/or koza@cs.stanford.edu for further information. Reviews of the books and products would be most welcome on GA-List.] ------------------------------ From: Jarmo Alander Date: Wed, 18 May 1994 10:00:46 +0300 Subject: GA bibliography very soon in press Hello, I have been collecting a bibliography of GA papers. The bibliography currently contains about 3000 indexed entries from well over 2000 authors. The referenced contributions are books, journal articles, proceedings papers, thesis (both Master's and PhD), reports and patents i.e. all material that has been published. It does not contain references to manuscripts. Everyone who wants his/her contribution to appear neatly indexed in the very soon to be published volume should: - check the current list of his/her contributions (Either get a version of the bib via anonymous ftp from site alife.santafe.edu file /pub/USER-AREA/EC/refs/2500GArefs.ps.gz or ask the list of your personal contributions by e-mail from jal@uwasa.fi or ja@hutcs.hut.fi) - send paper copies of his/her published contributions to Jarmo Alander Department of Computer Science University of Vaasa P.O. Box 700 FIN-65101 Vaasa Finland no later than 15. 6. 1994. Don't forget to include complete bibliographical data i.e. include the title pages of proceedings, journals etc for exact referencing. If your contribution is available via ftp, give the site and complete file names. If your article has not yet been published don't send it now but just relax and wait until it has been published and its complete bibliographical record is fixed. It will be included in future editions. [ WMS: Pricing information has been deleted. ] Yours very truly, Jarmo Alander ------------------------------ From: order@netcom.com (Walter Alden Tackett) Date: Wed, 18 May 1994 10:57:28 -0700 Subject: Ph.D. Dissertation Available PH.D. DISSERTATION AVAILABLE: CENG Technical Report 94-13 Recombination, Selection, and the Genetic Construction of Computer Programs Walter Alden Tackett Computer Engineering Division Department of Electrical Engineering - Systems University of Southern California Los Angeles, California, USA 90089-2562 [ WMS: Pricing information has been removed. ] This dissertation will soon be available from University Microfilms as well. An anonymous ftp version is available from santafe.edu in the directory pub/Users/tackett/phd, and from the Genetic Programming archives at ftp.cc.utexas.edu. Other sites TBD. File information and abstract are given below. The directory contains five files (in theory): README (this file) watphd_1.ps.Z watphd_2.ps.Z watphd_3.ps.Z - The dissertation is broken up into three equal-sized parts in compressed postscript format, suitable for unix, Mac, etc. The postscript was generated with a MSWindows driver for Adobe Postscript v3.0 cartridge on an HP LaserJet IIP. Filtered via dos2unix -ascii and compressed with the Unix compress command. wtphd_mw.zip - Same three parts, in original form as .doc files generated by MSWord 6.0a under Windows/NT, and compressed/archived via pkzip -ex. Use this if you have Word 6 (sorry to hear that), not compatible with earlier versions of Word or with Word on the Mac. Abstract: Recombination, Selection, and the Genetic Construction of Computer Programs Walter Alden Tackett University of Southern California Abstract Computational intelligence seeks as a basic goal to create artificial systems which mimic aspects of biological adaptation, behavior, perception, and reasoning. Toward that goal, genetic program induction - "Genetic Programming" - has succeeded in automating an activity traditionally considered to be the realm of creative human endeavor. It has been applied successfully to the creation of computer programs which solve a diverse set of model problems. This naturally leads to questions such as: * Why does it work? * How does it fundamentally differ from existing methods? * What can it do that existing methods cannot? The research described here seeks to answer those questions through investigations on several fronts. Analysis is performed which shows that Genetic Programming has a great deal in common with heuristic search, long studied in the field of Artificial Intelligence. It introduces a novel aspect to that method in the form of the recombination operator which generates successors by combining parts of favorable strategies. On another track, we show that Genetic Programming is a powerful tool which is suitable for real-world problems. This done first by applying it to an extremely difficult induction problem and measuring performance against other state-of-the-art methods. We continue by formulating a model induction problem which not only captures the pathologies of the real world, but also parameterizes them so that variation in performance can be measured as a function of confounding factors. At the same time, we study how the properties of search can be varied through the effects of the selection operator. Combining the lessons of the search analysis with known properties of biological systems leads to the formulation of a new recombination operator which is shown to improve induction performance. In support of the analysis of selection and recombination, we define problems in which structure is precisely controlled. These allow fine discrimination of search performance which help to validate analytic predictions. Finally, we address a truly unique aspect of Genetic Programming, namely the exploitation of symbolic procedural knowledge in order to provide "explanations" from genetic programs. ------------------------------ End of Genetic Algorithms Digest ******************************