Genetic Algorithms Digest Thursday, June 24, 1993 Volume 7 : 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: - Niching Workshop -- Call for participation - patterns within strings - ideas for this problem - Help needed on CS-1 - Double-stranded genetic algorithms - Variable-Length Genotype GA's - forwarded from comp.ai.genetic - GAucsd enhancements - Papers available (2 messages) - correction to TCGA report number 93001 - Call for abstracts for the journal Economic and Financial Computing - Pattern Recognition and GA's, a conference - The Evolutionary Models In Soc Sci Mail/File Server ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) ICGA-93, Fifth Intl. Conf. on GAs, Urbana-Champaign (v6n29) Jul 17-22, 93 COLT93, ACM Conf on Computational Learning Theory, UCSC (v6n34) Jul 26-28, 93 Machine Learning & Knowledge Acq. Workshop (IJCAI), France (v7n1) Aug 29, 93 IEE/IEEE Workshop on Nat Alg in Signal Processing, Essex (v7n5) Nov 15-16, 93 AI'93 Workshop on Evolutionary Computation, Melbourne, Aust(v7n16) Nov 16, 93 EP94 3rd Ann Conf on Evolutionary Programming, San Diego (v7n7) Feb 24-25, 94 The IEEE Conference on Evolutionary Computation, Orlando(v7n10) Jun 26-30, 94 SAB94 3rd Intl Conf on Sim of Adaptive Behavior, Brighton(v7n11) Aug 8-12, 94 PPSN-94 Parallel Problem Solving from Nature, Israel (v7n9) Oct 9-14, 94 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: mahfoud@gal4.ge.uiuc.edu (Sam Mahfoud) Date: Wed, 16 Jun 1993 22:01:49 -0500 Subject: Niching Workshop -- Call for participation CALL FOR PARTICIPATION Workshop on Niching Methods at ICGA-93 When: July 20 or 21st during ICGA (Exact date/time to be decided) Description: This workshop will examine current and proposed methods for the formation and maintenance of subpopulations in the GA. Topics include, but are not limited to: 1. Niching Methodology: --Modifications to the GA which induce subpopulations --Modifications to the GA which maintain stable subpopulations --Full niching algorithms --Expected Behavior --Theoretical Results --Maintenance of Diversity 2. Applications of Niching Methods: --Multimodal function optimization --Multi-objective function optimization --Machine Learning and Classification --Simulating biological, adaptive, and ecological systems --Practical/Real-World Applications The workshop will consist of short summaries of current research, followed by a group discussion in which all attendees are encouraged to make comments or pose questions. Research Summaries: If you would like to present a short summary (3-5 minutes) of your research related to niching, please send a 1 or 2 paragraph description of the research, along with your name and e-mail address to one of the organizers (e-mail addresses below). The exact time limit for summaries will depend upon the number of participants, but will not exceed 5 minutes and will be strictly enforced. An overhead projector will be available; we recommend no more than 3 transparencies per summary. Participants are encouraged to bring copies of their recent, related research to distribute, including drafts of preliminary papers or lists of their publications. DEADLINE: July 1st. Other Attendees: To register, please send your name and e-mail address to one of the organizers (e-mail addresses below), so that they can adequately plan for attendance and keep you informed of the workshop. DEADLINE: July 1st. Organizers: Sam Mahfoud (mahfoud@gal4.ge.uiuc.edu) Alan Schultz (schultz@aic.nrl.navy.mil) ------------------------------ From: Jim Van Zandt Date: Fri, 11 Jun 93 09:06:37 -0400 Subject: any ideas for this problem? Mike - > I have a number of strings. Each string is made up of a finite (and > small) number of symbols. ... I know that a small subset of these > strings belong to a certain group. ... I conjecture that some pattern > within the string is the deciding factor (for membership in the group > or not). .. I need to find the pattern... > > What kind of genetic-search, pattern recognition, classifier, > etc. can I use for this? > > Mike Levin Interesting problem. I'd suggest GA chromosomes consisting of one or more regular expressions, each preceded by a sign bit. To evaluate, you would first determine which expressions appeared in the string. For each of these, you'd add or subtract one to a counter (depending on the corresponding sign bit). The sign of the answer would represent the decision for that string. You'd have to decide how to weight type I and type II errors and "can't decide" (counter=0). One elaboration would be to assign weights to your original group assignments and use as your score the correlation coefficient between your number and that determined by the GA. (One obvious optimization would be to reverse all the signs if the final correlation coefficient turns out negative.) You might also use weights rather than just signs in the GA chromosomes. You'll need to allow variable numbers and lengths of regular expressions -- sounds like an application for "messy genetic algorithms" [1]. [1] Kalyonmoy Deb, "Binary and Floating-Point Optimization Using Messy Genetic Algorithms", TCGA Report 91004, Dept. of Engineering Mechanics, University of Alabama, Tuscaloosa AL 35487, 26 Apr 91. ------------------------------ From: Gihan P Seneviratne Date: Tue, 15 Jun 1993 11:48:46 +0100 Subject: Help needed on CS-1 Dear Netters, I have two problems with Holland and Reitman's Cognitive system Level 1 [CS-1] Suppose 9 classifiers are in a chain with the corresponding predicted payoff values as follows; Cl 1 2 3 4 5 6 7 8 9 PPF 250 -> 500 -> 1000 -> 750 -> 1000 -> 250 -> 350 -> 500 -> 200 if this chain causes a payoff of 1000, at the end my problems are 1. How can I adjust the ATTENUATION of each of the first eight classifiers? 2. How can I adjust the Predicted payoff of each of the above 9 classifiers? [Please give rules clearly] Please email your replies to Thanks in Advance Gihan(S) ------------------------------ From: korfhage@lis.pitt.edu (fac robert korfhage) Date: Fri, 18 Jun 93 10:30:25 EDT Subject: Double-stranded genetic algorithms Is anybody doing work on "double-stranded" genetic algorithms? We've been applying genetic algorithms to query modification in information retrieval, and are interested in using the technique at two different levels. Our "genes" are individual search terms. One level, which is what we've been doing, is weighting of the individual terms. The second level, which we haven't attacked yet, is weighting groups of terms. This would be independent of the individual term weightings, but the two weighting systems would combine in their effect. Bob Korfhage Department of Information Science 737 LIS Building University of Pittsburgh Pittsburgh, PA 15260 korfhage@lis.pitt.edu ------------------------------ From: coder@cgi.com (Dale Coder) Date: Wed, 16 Jun 93 19:07:31 EDT Subject: Variable-Length Genotype GA's I am looking for info on variable-length genotype genetic algorithms. I am aware of Harvey's work at the University of Sussex, and I was wondering what else might be out there. Source code would be appreciated. Dale Coder phone: (412) 642-6811 x275 email: coder@cgi.com ------------------------------ From: schraudo@cs.ucsd.edu (Nici Schraudolph) Date: Sat, 19 Jun 93 10:15:01 -0700 Subject: forwarded from comp.ai.genetic > Has anybody out there writen uniform crossover > or ranked based selection routines for GAucsd? > > If so, I'd enjoy a copy of your code! :-) > -- > Jim Frenzel Electrical Engineering > University of Idaho Moscow, ID 83844-1023 USA > 208-885-6045 jfrenzel@groucho.mrc.uidaho.edu Maybe this is a good opportunity to mention that in case you've written such or other GAucsd enhancements and would consider contributing them for future releases, I would also appreciate hearing from you... - Nici. Nicol N. Schraudolph, CSE Dept. | ``Understructured, overresourced, Univ. of California, San Diego | undermanaged, overinebriated. La Jolla, CA 92093-0114, U.S.A. | And that was just the editor.'' nici%cs@ucsd.{edu,bitnet,uucp} | - Douglas Adams, Mostly Harmless. ------------------------------ From: mm@santafe.edu Date: Thu, 10 Jun 93 15:04:27 MDT Subject: Paper available The following paper is available via public ftp. When Will a Genetic Algorithm Outperform Hill-Climbing? Melanie Mitchell John H. Holland Santa Fe Institute University of Michigan Santa Fe Institute Working Paper 93-06-037 Abstract In this paper we review some previously published experimental results in which a simple hill-climbing algorithm---Random Mutation Hill-Climbing (RMHC)---significantly outperforms a genetic algorithm on a simple ``Royal Road'' function. We present an analysis of RMHC followed by an analysis of an ``idealized'' genetic algorithm (IGA) that is in turn significantly faster than RMHC. We isolate the features of the IGA that allow for this speedup, and discuss how these features can be incorporated into a real GA and a fitness landscape, making the GA better approximate the IGA. We use these features to design a modified version of the previously published experiments, and give new experimental results comparing the GA and RMHC. A summary version of this paper will appear in the 1993 ICGA proceedings. To obtain an electronic copy: ftp santafe.edu login: anonymous password: cd /pub/Users/mm binary get ga-hillclimb.ps.Z quit Then at your system: uncompress ga-hillclimb.ps.Z lpr -P ga-hillclimb.ps To obtain a hard copy, send a request for SFI-93-06-037 to dlu@santafe.edu. ------------------------------ From: mm@santafe.edu Date: Fri, 18 Jun 93 12:37:30 MDT Subject: paper available The following paper is available by public ftp. Dynamics, Computation, and the ``Edge of Chaos'': A Re-Examination Melanie Mitchell James P. Crutchfield Peter T. Hraber Santa Fe Institute UC Berkeley Santa Fe Institute Santa Fe Institute Working Paper 93-06-040 Abstract In this paper we review previous work and present new work concerning the relationship between dynamical systems theory and computation. In particular, we review work by Langton (1990) and Packard (1988) on the relationship between dynamical behavior and computational capability in cellular automata (CA). We present results from an experiment similar to the one described in Packard (1988), that was cited there as evidence for the hypothesis that rules capable of performing complex computations are most likely to be found at a phase transition between ordered and chaotic behavioral regimes for CA (the "edge of chaos"). Our experiment produced very different results from the original experiment, and we suggest that the interpretation of the original results is not correct. We conclude by discussing general issues related to dynamics, computation, and the "edge of chaos" in cellular automata. To appear in G. Cowan, D. Pines, and D. Melzner (editors), _Integrative Themes_. Santa Fe Institute Stuides in the Sciences of Complexity, Proceedings Volume 19. Reading, MA: Addison-Wesley. Note: This paper is a much shorter version of our paper "Revisiting the Edge of Chaos" (SFI Working Paper 93-03-014, announced previously on this newsgroup). It contains an expanded review of previous work on relationships between dynamical systems theory and computation. To obtain an electronic copy: ftp santafe.edu login: anonymous password: cd /pub/Users/mm binary get sfi-93-06-040.ps.Z quit Then at your system: uncompress sfi-93-06-040.ps.Z lpr -P sfi-93-06-040.ps To obtain a hard copy (only if you cannot obtain an electronic copy), send a request to dlu@santafe.edu. ------------------------------ From: Robert Elliott Smith Date: Sat, 12 Jun 93 13:15:52 -0600 Subject: correction to TCGA report number 93001 Please note the following corrections to TCGA report #93001 "Adaptively Resizing Populations: An Algorithm and Analysis": The first equation on page 7 reads \[G = (1 - \gamma) + \frac{2 \gamma}{1+\exp{\left(\beta\left(\frac{\hat{L}}{L_t}-1\right)\right)}}\] However, it should read should be \[G = (1 - \gamma) + \frac{2 \gamma}{1+\exp{\left(-\beta\left(\frac{\hat{L}}{L_t}-1\right)\right)}}\] Also, the second and third equations currently read \[G_{1,2} = G_{1,2,3,4}\frac{f(H_{1,2})}{f(H_{1,2})+f(H_{3,4})} \] and \[G_{3,4} = G_{1,2,3,4}\frac{f(H_{3,4})}{f(H_{1,2})+f(H_{3,4})} \] They should read \[G_{1,2} = \left(1-\frac{f(H_{1,2})}{f(H_{1,2})+f(H_{3,4})}\right) + \left(G_{1,2,3,4} \frac{f(H_{1,2})}{f(H_{1,2})+f(H_{3,4})} \right) \] and \[G_{3,4} = \left(1-\frac{f(H_{3,4})}{f(H_{1,2})+f(H_{3,4})}\right) + \left(G_{1,2,3,4} \frac{f(H_{3,4})}{f(H_{1,2})+f(H_{3,4})} \right) \] The simulations in the paper are consistent with these equations. If you would like a copy of the report that incorporates these corrections, feel free to write me. Robert Elliott Smith Department of Engineering Science and Mechanics Room 210 Hardaway Hall The University of Alabama Box 870278 Tuscaloosa, Alabama 35487 <> rob@comec4.mh.ua.edu <> (205) 348-1618 <> (205) 348-6419 ------------------------------ From: mccainra@dunx1.ocs.drexel.edu (Roger A. McCain) Date: Thu, 10 Jun 93 12:15:40 EDT Subject: Call for abstracts Call for abstracts: Scholars working in applications of the following fields to economics and finance: chaos theory, self-organizing systems, genetic algorithms, fuzzy logic, neural networks, or in applications of related fields are invited to submit abstracts of research papers for a special issue of the journal Economic and Financial Computing. This is a developmental project and will be carried forward if there is sufficient interest. Please share this posting with interested colleagues, e-mail contacts or mail lists where you believe there may be interest in the issue. Abstracts may be sent by regular mail to Dr. Shawkat Hammoudeh Dept. of Economics Drexel University Philadelphia, PA, 19104-2875 or by electronic mail to Dr. Roger A. McCain Dept. of Economics Drexel University Philadelphia, PA, 19104-2875 mccainra@dunx1.ocs.drexel.edu Preliminary submissions are requested by 15 October 1993. Roger A. McCain Director, Honors Program and Professor, Economics 5016 MacAlister Hall Drexel University Philadelphia, PA, 19104 215-895-1267 mccainra@dunx1.ocs.drexel.edu ------------------------------ From: punch@cps.msu.edu Date: Fri, 11 Jun 93 11:50:35 EDT Subject: Pattern Recognition and GA's, a conference I'm the program coordinator for the Genetic Algorithms part of "Pattern Recognition in Practice IV", to be held in Vlieland, Neterlands, June 1-3, 1994. The CFP reads in part: "Pattern Recognition in Practice IV aims at the stimulation of interaction between experts in the field of Pattern Recognition and scientists from various areas in which Pattern Recognition techniques are applied..." "Proposed Topics: 1) Use of AI techniques in pattern recognition and image processing. 2) Principles and use of neural networks. 3) Principles and use of causal networks. 4) Genetic Algorithms. 5) Hybrid Systems. 6) Comparative Studies" I'm trying to gauge interest in the conference from the GA point of view. I'd appreciate hearing from any GA-List readers that would be interested. We can talk more about the conference, via email or perhaps at the upcoming ICGA-93. Thanks. >>>bill punch<<< A714 Wells Hall Computer Science Dept. Michigan State University East Lansing MI, 48824 punch@cps.msu.edu 517-353-3541 ------------------------------ From: econec@vax.ox.ac.uk Date: Fri, 11 Jun 1993 18:15:00 +0100 Subject: The Evolutionary Models In Soc Sci Mail/File Server ANNOUNCING THE EVOLUTIONARY MODELS IN SOCIAL SCIENCE (EMSS) LIST After 200 plus requests for my bibliography on Evolutionary Models in Social Science, I have managed to set up a species of mail/file server for people interested in this area. Anyone reading this message who STILL hasn't had the bibliography should email me again! The software is safe - you won't get millions of bounces if you join - but it is not polished! You can subscribe to the list by sending a message with the string "subs-list" in the subject line to ECONEC@BLACK.OX.AC.UK You will get a short message confirming your subscription and providing more information about the server. If you don't, mail me in person. In addition the latest copy of the EMSS bibliography and some accompanying notes can be retrieved from this site automatically. Please let me know if you need any help with these instructions or if my server is screwing anything up where you are. I am rapidly discovering that there are MANY sorts of mailer. I have only subscribed manually those people who explictly asked me to do so: Xiao Zhou, Soren Risbjerg Thomsen, Timothy Van Zandt, Leslie DeGroff, Michael Wellman, Jack Birner, Pradeep Philip, Graeme Faulkner, Howard Andrew Gutowitz, Peter Treloar, Scott E Page, Carl Schmertmann, Penio Penev, Sushil Louis, Jack Stecher, Philip Sharman, J J Merelo, Hadon Nash Now that this project looks like really getting off the ground - there has been far more interest than I envisaged - please feel free to pass on this message to anyone else you think will be interested. Many thanks to all those who have offered help and encouragement so far :) All the best, Edmund Chattoe SNAIL: Mr E Chattoe Lady Margaret Hall Oxford OXON OX2 6QA UK PERSONAL EMAIL: ECONEC@VAX.OX.AC.UK EMAIL FOR EMSS LIST: ECONEC@BLACK.OX.AC.UK ------------------------------ End of Genetic Algorithms Digest ******************************