Genetic Algorithms Digest Tuesday, March 7, 1995 Volume 9 : Issue 11 - Do NOT send email or reply to gadistr@aic.nrl.navy.mil (GA List Moderator) - Send submissions (articles) to GA-List@AIC.NRL.NAVY.MIL - Send administrative (subscribe, unsubscribe, change of address, etc.,) requests to GA-List-Request@AIC.NRL.NAVY.MIL ****************************************************************************** - You can access back issues, GA code, conference announcements, etc., either through the WWW at URL http://www.aic.nrl.navy.mil/galist/ or through anonymous ftp at ftp.aic.nrl.navy.mil [192.26.18.68] in /pub/galist. ****************************************************************************** Today's Topics: - Comments on NFL... - Super-Linear Speedup when Parallelizing GAs (3 messages) - GA's for grouping - EA Workshop Proceedings - Free software - University Courses in Genetic Algorithms - A visiting position - GAs vs Tabu Search? - GA without Crossover ---------------------------------------------------------------------- ******************************************************************************* CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) ICTS95 3rd Intl Conf on Telecommunications, Tennessee (v8n21) Mar 16-19, 95 AISB Wrkshp on Evol Comp, Univ of Sheffield, UK (v8n45) April 3-4, 95 ICANNGA95 Intl Conf on Artificial NNs and GAs, France (v8n10) Apr 18-21, 95 IAS-95 Intelligent Adaptive Systems, Melbourne Beach FL (v8n32) April 26, 95 CAD95 Computer Aided Design / "GA Day", Yalta City, CIS (v8n46) May 4-13, 95 CSCS10 10th Intl Conf on CONTROL SYSTEMS & CS, Romania (v8n37) May 24-26, 95 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 95 GWIC95 Golden West Intl Conf on Intell Systems, San Fran(v8n49) Jun 12-14, 95 ML95 GP Workshop: Theory to real-world applications, CA (v9n8) July 9, 95 AAICG95 Symposium on Appl of AI in Geophysics, Boulder, CO (v8n39) Jul 12, 95 ICGA-95 Sixth Intl Conference on GAs, Pittsburgh PA (v8n32) July 15-20, 95 PASE95 Wrkshp Parallel Appl in Stat and Econ, Trier (v8n39) Aug 29-Sep 2, 95 EA95 Evolution Artificielle, Telecom Bretagne, Brest, Fr (v9n1) Sept 4-8, 95 GALESIA'95 GAs in Eng Systems, Univ of Sheffield, UK (v8n45) Sept 12-14, 95 AIPetro95 AI in the Petroleum Ind, Lillehammer, Norway (v8n48) Sept 13-15, 95 ASI-AA-95 Practice and Future of Autonomous Agents (v8n19) Sep 23-Oct 1, 95 SOCO95 Soft Computing Fuzzy Logic, NNs and GAs, Rochester(v9n5) Oct 24-27, 95 Genetic Methods for Routing & Scheduling, New Orleans(v8n50) Oct 29-Nov 1, 95 AAAI GP Symposium (Fall Series), Cambridge, MA (v8n43) Nov 10-12, 95 IEEE Wrkshp on Natural Algorithms in Signal Proc, Essex (v9n7) Nov 12-14, 95 WWW'95 on Fuzzy Logic and NNs/Evol Comp, Nagoya, Japan (v9n6) Nov 14-15, 95 ICEC '95 IEEE Intl Conf on Evol. Computing, Perth (v8n36) Nov 29-Dec 1, 95 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ******************************************************************************* ------------------------------ From: vose@cs.utk.edu Date: Wed, 1 Mar 1995 10:47:13 -0500 Subject: Comments on NFL... Kihong Park made several interesting comments about the NFL theorem. He is no doubt aware that his statement "It is like trying to say something about the property of rational numbers but formulating a theorem that has the reals as its sample space. The reals swamp out the rationals, thus yielding useless results since rationals have measure 0 in this probability space." is, strictly speaking, false. Though what was *intended* is quite true -- and given the context of his surounding remarks, the intent shines through -- I still feel it is important, if possible, that potential misunderstanding concerning his statement be forestalled. In the seductive simplicity, generality, and intuitive "rightness" of his statement, there is a great danger for truth to be harmed by way of reasoning from a false premise. For example, suppose one wanted to show every rational number in the interval [0,1] has a square which is not more than 1. This conclusion does in fact follow from the truth of the following: THEOREM: If / 2 | t if t is *not* a rational. f(t) = | | arbitrary otherwise \ (i.e., if t *is* rational, define f(t) anyway you like!) then 2 / 1 \ p | / 2 | | | 1 / p | lim | | f(t) dt | = 1 p --> 0 | | | \ / / 0 Please note: a) This theorem does have the reals as its "sample space" (consider [0,1] as a probability space with the probability measure given by Lebesgue measure; the integral is the expectation of a random variable). b) Nevertheless, the theorem yields useful information about the rationals, namely, every rational number in the interval [0,1] has a square which is not more than 1 (easy exercise!). I will concede that this example is a bit on the trivial side, but there are other more interesting examples, like the Riemann zeta function for instance, where PROPERTIES OF REAL OR COMPLEX VALUED FUNCTIONS ON CONTINUOUS SPACES MAY SPEAK VERY MUCH TO WHAT IS TRUE ABOUT SETS OF ZERO MEASURE, even if the properties concern behavior in the *complement* of the measure zero sets about which one is interested! I apologize to Kihong Park for any appearance that I am criticizing him, for that is not the case. As pointed out above, he is no doubt aware of the truth, and besides, I am guilty of misinterpreting his statement (by taking it out of context) in order to make a point. I do hope to limit the application of a faulty principle however. There is already way too much of that going around (sigh). Michael. ------------------------------ From: John Koza Date: Mon, 27 Feb 95 8:04:55 PST Subject: Super-Linear Speedup when Parallelizing GAs It is well known that genetic algorithms are amenable to parallelization in several different ways. It has also been repeatedly established that parallel GAs deliver, in actual practice, nearly linear speedup (relative to the number of processors) and nearly 100% efficiency. These comparisons are based on doing the SAME NUMBER of fitness evaluations and running the same number of generations with subpopulations than without them. From time to time, I have heard it mentioned that GAs may deliver SUPER-LINEAR SPEEDUP in the sense that the parallel GA solves (at least for some problems) faster when semi-isolated sub-populations (Sewell Wright's demes) are used. In other words, the problem SOLVES IN FEWER GENERATIONS with subpopulations than without them. (Of course, subpopulations can be easily simulated on a serial machine; however, this observation is usually made in connection with large problems that require large populations, and hence, in practice require a parallel machine). We have observed just this in connection with runs of genetic programming on the problem of symbolic regression of the even-5-parity function. Is anyone aware of any published results in this area? John Koza Stanford University ------------------------------ From: "Dr. Robert J. Collins" Date: Mon, 27 Feb 1995 10:00:14 PST Subject: Re: Super-Linear Speedup when Parallelizing GAs > From time to time, I have heard it mentioned that GAs may > deliver SUPER-LINEAR SPEEDUP in the sense that the > parallel GA solves (at least for some problems) faster when > semi-isolated sub-populations (Sewell Wright's demes) are > used. In other words, the problem SOLVES IN FEWER > GENERATIONS with subpopulations than without them. > > Is anyone aware of any published results in this area? > > John Koza > Stanford University Check out Chapter 7 of my dissertation. Basically I designed a graph partitioning problem (based on Ackley's) that has scalable difficulty. I did ridiculously expensive parametric studies to determine how hard of a problem various GAs and parameter settings could solve. In addition, I instrumented for various things to try to determine exactly how spatially-structured GAs differ from panmictic GAs. The basic conclusion is that spatial structure completely changes the dynamics of evolution, and in a very positive way with large populations applied to very hard problems. Also, parametric studies can slow down the quest for a PhD :-) I think my dissertation is available via anonymous ftp from ftp.cognet.ucla.edu:/pub/alife/papers/collins-phd?.ps.gz. Let me know if you have questions/comments/problems getting/printing it. rob ------------------------------ From: "Mike J. Keith" Date: Mon, 27 Feb 1995 14:58:25 -0500 Subject: Re: Super-Linear Speedup when Parallelizing GAs Another interesting aspect to DEMES is that they can be multi-dimensional. That is, you can have a 1 dimensional setup, a 2 dimensional setup, or even an N dimensional setup. The different dimensional setup effects the genetic drift. For example, in a deme implementation of dimension=1 and radius=1, each individual can spread his material to 2 others. In a dimension of 2/radius=1, each individual can spread to 9 others - the higher the dimension the more channels you have for genetic material to spread. A lot of this can be accomplished by increasing the radius, but its a bit different. Also, unless I was drunk or something, when I read Robs paper, I noted that his results seemed to indicate that 3 dimensional demes worked a bit better than 2-Ds, and 2-Ds worked a bit better than 1 Ds. Not that big of a deal but it seems somewhat interesting... Mike ------------------------------ From: sivri%TRBOUN.BITNET@vm3090.ege.edu.tr Date: Tue, 28 Feb 1995 10:47:06 +0200 Subject: GA's for grouping Dear subscribers, I would appreciate if anyone would be willing to send me any papers he/she has collected/written on the theory and/or applications of GA's for grouping problems. My efforts to access Falkenauer's papers through the ftp sites he has given in one of the GA-Digest issues and to reach him personally through his e-mail address has remained fruitless. I hope some of you have those papers and/or others and can send me a copy. If anyone is interested I can share whatever I receive. Regards, Funda. Name: Funda Sivrikaya-Serifoglu, Address: Serifoglu Agac San.,E:80 No:88, 14600 Duzce, TURKEY. Fax: 90-374-5142898. e-mail: sivri@trboun.bitnet. ------------------------------ From: vnissen Date: Wed, 1 Mar 1995 11:15:03 +0100 (MET) Subject: EA Workshop Proceedings On Feb. 23rd 1995 a very successful workshop on Evolutionary Algorithms in Management Applications took place at the University of Goettingen, Germany, attracting over 50 participants, a quarter of them from industry. Remaining copies of the proceedings volume are now being sold: ============================================================= Most contributions are in German, one is in English. Publication title: Evolutionaere Algorithmen in Management-Anwendungen Editors: J. Kuhl; V. Nissen Price: DM 25,- within Germany, DM 30,- within Europe, DM 40 elsewhere (price includes packaging and air mail postage) Table of Contents: V. Nissen Evolutionaere Algorithmen in Management-Anwendungen - ein Ueberblick M. Schwehm Optimierung der Partitionierung und Kanban-Zuordnung bei JIT-Fertigungsstrassen J. Branke; U. Kohlmorgen; H. Schmeck; H. Veith Steuerung einer Heuristik zur Losgroessenplanung unter Kapazitaetsrestriktionen mit Hilfe eines parallelen Genetischen Algorithmus Rob Broekmeulen Facility Management of Distribution Centres for Vegetables and Fruits G. Schuetz Parallele Suche zur Loesung mehrstufiger Standortprobleme (extended abstract) K. Nachtigall; S. Voget Optimierung von periodischen Netzplaenen mit GA D. Mack GAK - ein Genetischer Algorithmus zur Loesung des Klassifikationsproblems G. Sieg Genetische Algorithmen zum Design erfolgreicher Wettbewerbs- strategien N. Vojdani; C. Maiworm Automatische Generierung von Fuzzy-Regeln und -mengen in hierarchischen Fuzzy-Systemen mit Hilfe von GA Please order from (include Euro-cheque or money order): Dr. Volker Nissen Universitaet Goettingen Abteilung Wirtschaftsinformatik I Platz der Goettinger Sieben 5 D-37073 Goettingen Germany ------------------------------ From: cs0ahu@isis.sund.ac.uk (Andy.Hunter) Date: Wed, 1 Mar 1995 10:41:56 +0000 Subject: free software New GA software package available! SUGAL (SUnderland Genetic Algorithms Library) is a new, free software package designed to support research in Genetic Algorithms. SUGAL has novel design features to make extension and customisation of the algorithm possible - without having to rewrite the supplied source code. The major features are: * Written in ANSI C. * Tested on SUN SOLARIS 2 and PC BORLAND C++ 3.0. * Supports multiple datatypes seamlessly: bit strings, integers, real numbers, symbols (from arbitrarily sized alphabets). * A powerful and general Genetic Algorithm (includes rank-based and non-rank based fitness and replacement options, various forms of fitness function normalisation, elitism, various forms of mutation and crossover). Includes GENESYS and GENITOR algorithms as a subset. * Parameters can be set in a configuration file, and overruled by command-line options and/or hard-coded program statements. * Users can add their own configuration file parameters and/or add additional options to existing parameters. * Virtually all major actions in the GA can be overridden by the user. * A comprehensive User Manual (available in postscript and on-line as HTML). The SUGAL source code and manual are available by anonymous ftp or via the World Wide Web. The ftp address is "osiris@sund.ac.uk" ; the SUGAL files are stored in directory /pub/sugal. On the World Wide Web, the SUGAL home page is at: http://osiris.sund.ac.uk/ahu/sugal/home.html Any comments to cs0ahu@sund.ac.uk Dr. Andrew Hunter, University of Sunderland, England. ------------------------------ From: John Koza Date: Wed, 1 Mar 95 8:26:08 PST Subject: University Courses in Genetic Algorithms RE: University Courses in Genetic Algorithms I think it would be useful to find out what courses are currently being taught at universities on genetic algorithms (and also artificial life). I have to say, I have no idea how many such courses there are (half dozen? dozen? several dozen?). I recently had some visitors from Sweden who visited Stanford and collected a bunch of stuff from me to start up a GA course there. I think it would be useful to publicize a short list of these courses in the GA list and other newsletters (for possible use by students and others) and also for the instructors to exchange some of their course materials (so they can recombine genetic material from many places). I am willing to implement this and propose the following approach. (1) Let the instructors identify themselves by sending me a message. I'm talking about courses that spend, say half of their time on GAs (not general AI or ML courses that mention GAs for 1 or 2 lectures). (2) I'll prepare a short half-page summary form and circulate it to the instructors and combine this summary information into a short report for the GA list and other newsletters. (3) I'll also ask the instructors to submit to me a larger pile of their interesting stufflettes, such as syllabus, reading lists, problem sets, important handouts, project guidance instructions, etc. I will then get these printed into a thick book and distribute this book to all of the submitting instructors. I'll also keep some extras of the book so that if someone is contemplating starting such as course in the future, they can refer to this book as a starting point. John Koza Stanford University ------------------------------ From: janikow@radom.umsl.edu (Cezary Janikow) Date: Wed, 1 Mar 95 14:20:51 CST Subject: a visiting position We have a visiting position (pending financial approval) for 1995/96. Unfortunately, it may require up to 9hrs/wk of teaching, but quite possibly 6hrs/wk. I would be most happy if anyone interested in collaborating on some GA-related research would be interested. Sabbatical, other Ph.D.s, and even doctorate students are welcome to apply. If interested, or for more info, please contact me directly. Sincerely, Cezary Z. Janikow Department of Math and CS, CCB319 tel (314) 516-6352 UMSL fax (314) 516-5400 St. Louis, MO 63121 ------------------------------ From: ieshan@unix1.sncc.lsu.edu (Shantanu S Deo) Date: Thu, 2 Mar 1995 12:46:55 -0600 Subject: GAs vs Tabu Search? Hi, I would be interested to know if there is anyone out there who has also applied Tabu Search as proposed by Glover, to any search / combinatorial optimization type problem. If so I would be interested to hear about your results and any performance highlights/comparisions vis-a-vis the GA's. Thanks in advance. Regards, Shantanu S. Deo (Dept. of Indusrtrial Engg. Louisiana State University) P.S: Please send responses to me directly, I will summarize them and post a compiled version later. My email addr. is (ieshan@unix1.sncc.lsu.edu). ^^^^^^^^^^^^^^^^^^^^^^^^^ ------------------------------ From: keenan@redmont1.cis.uab.edu (Mikal Keenan) Date: Fri, 3 Mar 1995 11:00:38 -0600 Subject: GA without Crossover During my candidacy meeting a member of the committee asked me about the use of GAs that do not include crossover in theri operations, i.e. mutation-only. He later stated that Fogel had written a book which describes their use and asserts that crossover is unnecessary. I am wondering if there is some confu- sion in the committee members mind re: GA/Mutation-Only and Evolution Strate- gies. Does anyone know anything about ^^^^^^^^^^^^^^^^? I basically want to cover the topic because it's liable to show up again during my dissertation defense. Regards, Mick Mikal Keenan Internet....: keenan@cis.uab.edu CompuServe..: 71167,1033 U.S.P.S.....: Dept of Computer & Info Sci, UAB - Campbell Hall University Station, Birmingham, AL 35294-1170 Phone.......: (205) 934-2213; (205) 879-9345 Fax.........: (205) 934-5473 ------------------------------ End of Genetic Algorithms Digest ******************************