Genetic Algorithms Digest Monday, 26 March 1990 Volume 4 : Issue 5 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - TCGA - GA for a pursuit game - Clarification of deadlines for Workshop on Foundations of GAs - Class-room scheduling via GA - Call for Papers -- Dortmund Workshop ****************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) Double Auction Tournament - Sante Fe Institute (v3n12) Mar 1990 Workshop on GAs, Sim. Anneal., Neural Nets - Glasgow (v3n15) May 9, 1990 7th Intl. Conference on Machine Learning (submissions 2/1/90) Jun 21-23, 1990 Workshop Foundations of GAs (v3n19) Jul 15-18, 1990 Conference on Simulation of Adaptive Behavior, Paris (v3n21) Sep 24-28, 1990 Workshop Parallel Prob Solving from Nature, W Germany (v4n5) Oct 1-3, 1990 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ****************************************************************************** -------------------------------- Date: Wed, 7 Mar 90 15:34:59 PST From: mdeale@vega.ACS.CalPoly.EDU (Myron Deale) Subject: TCGA Hello, I've seen this term before, "The Clearinghouse for Genetic Algorithms." I've read Goldberg's book and understand the use of clearinghouse's in classifier systems. However, TCGA is attributed as having published papers, how would I go about contacting them? -Myron -------------------------------- Date: Mon, 19 Mar 90 10:29:10 EST From: jrv@sdimax2.mitre.org Subject: GA for a pursuit game I am designing a GA for the mutual optimization of kinetic-kill interceptors (like the "brilliant pebbles" proposed recently by Livermore) and their targets (ICBMs which maneuver in an attempt to avoid the interceptors). The target has no sensor, so it cannot change its behavior in response to the observed behavior of the interceptor. It must choose its avoidance strategy before the engagement. The interceptor does have a sensor, so it could conceivably change its guidance law in mid-flight. I want to treat the problem as a pursuit game in which both the interceptors and their targets evolve. Conceivably, there is more than one good strategy for each group, so I would also like to encourage the formation of species. I am looking at sharing functions for this [1]. As with other two-person games, a pure strategy (a fixed sequence of maneuvers for the target, or a fixed guidance law for the interceptor) may quite possibly be inferior to a mixed strategy (a stochastic mixture of pure strategies). Should the appropriate mixture be determined by the GA, or separately? I am planning to encode for each target a sequence of maneuvers. An inversion operator would seem appropriate to permute this sequence. Holland discusses inversion operators in ANAS, but they seem to have been unpopular in recent implementations. For example, inversion is not included in GENESIS. Why is this? Does anyone have suggestions on how to set up the GA for two populations competing in an asymmetric game? Suppose there are I interceptors and T targets. I would prefer not having to perform all IT possible comparisons in order to establish fitness. I expect the comparisons to be much more expensive than the overhead of even an elaborate GA. I have looked at Ping-Chung Chi's work on games [2]. My case is easier than his in that I can compute a relative fitness (actually two of them: divert delta velocity for a successful intercept, or miss distance for a failed one). However, his work suggests that the number of comparisons can be limited. Unlike the repeated Prisoner's Dilemma studied by Axelrod [3] and Marks [4], this game is not repeated -- each booster and interceptor will meet only once, so they will have no opportunity to exploit knowledge of their opponent's past behavior. Also, of course, there is no hope of cooperation here. Any suggestions would be greatly appreciated. - Jim Van Zandt --------- [1] K. Deb and D. E. Goldberg, "An Investigation of Niche and Species Formation in Ginetic Function Optimization", 3rd ICGA. [2] P. C. Chi, "Genetic Search with Proportion Estimations", 3rd ICGA. [3] R. Axelrod, "The Evolution of Strategies in the iterated Prisoner's Dilemma", Genetic Algorithms and Simulated Annealing, 1987. [4] R. E. Marks, "Breeding Hybrid Strategies: Optimal Behavior for Oligopolists", 3rd ICGA. -------------------------------- Date: Mon, 19 Mar 90 15:39:01 -0500 From: Gregory J. E. Rawlins Subject: Clarification of deadlines for Workshop on Foundations of GAs Hello, it seems that there is some confusion about the deadlines for the workshop on the foundations of genetic algorithms and classifier systems to be held in Bloomington in July 15th-18th, 1990. This letter is intended to clarify the issues; please phone, or send me mail if you have further questions. We have extended one of the deadlines (see below) because of all of the confusion. Thanks for your time, gregory. -- 812-855-2136; rawlins@iuvax.cs.indiana.edu ========================================================================== Format: ======= The intent of the workshop is to collect those people interested in the foundations of genetic algorithms and classifier systems and hammer out the basic assumptions and theories of the field. The format is designed to make the workshop a very low stress affair. In pursuit of this aim attendance is being kept to less than forty, and deadlines and publication are arranged so that possible contributors have a lot of leeway. There is no publisher pressure prior to the workshop, and there is no pressure to have results completely polished before the workshop. The workshop is mostly by invitation. We accepted abstracts (with a March 1st deadline) to review. Authors of acceptable abstracts are then invited. Several people sent abstracts and they are under review. The workshop is being kept to a small number to encourage as much discussion as possible and to reduce ``conference burnout.'' As of this writing, about 30 people have already agreed to attend and so there are only a few slots left open. The March 1st deadline has now been extended to May 1st. (NOTE: if you are already invited you DO NOT have to send abstracts by May 1st.) The proceedings are almost completely separate. Papers are to be submitted to be reviewed by us *after* the workshop. If these papers can be edited to make a collection of rigourous papers with a common theme (foundational aspects of genetic algorithms/classifier systems) then the papers will be published in a proceedings volume. The publisher, as of this writing, is Morgan Kaufmann. The deadline for submission of papers intended for possible inclusion in the proceedings is September 1 (to give everyone a chance to polish their results and also to bound the time that they have to do it in so that the proceedings appear within a year and not three years from now). ========================================================================== Deadlines: ========== Deadline for submission of abstracts March 1st 1990 [now extended: May 1] Registration information mailed April 1st 1990 Letter asking for specifics of topic of talk mailed May 1st 1990 Registration period ends May 15th 1990 Workshop July 15th-18th 1990 Deadline for submission of papers for proceedings September 1st 1990 Publication of proceedings Spring 1991 ========================================================================== Abbreviated Call for Abstracts: =============================== A Workshop on The Foundations of Genetic Algorithms and Classifier Systems July 15th-18th, 1990 Bloomington, Indiana, USA The main thrust of this workshop will be towards rigorous approaches to understanding the foundations of genetic algorithms and classifier systems. Experimental results are acceptable, but they should have a defensibly (and preferably explicit) theoretical basis. Acceptable topics include but are not limited to: -convergence properties of genetic algorithms -structure theory for GA-hard problems -properties of the schema theorem -coding functions and representation -genetic algorithms as combinatorial optimizers -parallelizing evolutionary systems -sustaining long rule sequences in classifier systems -modularizing classifier systems -relations between evolutionary systems and neuromorphic systems -search space assumptions of distributed search procedures A program committee consisting of Kenneth De Jong, David Goldberg, Gregory Rawlins, and Dirk Van Gucht will review submitted abstracts. Abstracts should be no more than 15 pages long (excluding figures and tables), double-spaced, and set in 11pt or better. Authors will be notified of the committees decision by April 2nd, 1990. Please send four copies to: Gregory Rawlins Department of Computer Science 101 Lindley Hall Indiana University Bloomington, Indiana 47405, USA ========================================================================== Tentative Attendance: ===================== Currently the following people are attending: R. Belew University of California San Diego L. Booker Naval Research Laboratory C. Bridges Carnegie-Mellon University P.-C. Chi Catholic University of America M. Conrad Wayne State University J. Culberson University of Alberta Y. Davidor Weizmann Institute K. De Jong George Mason University L. Eshelman Philips Laboratories T. Fogarty Bristol Polytechnic S. Forrest Los Alamos National Laboratory D. Goldberg University of Alabama J. Grefenstette Naval Research Laboratory P. Jog CADEX J. Koza Stanford University G. Liepins Oak Ridge National Laboratory S. Louis Indiana University H. Muehlenbein GMD D. Offutt Philips Laboratories G. Rawlins Indiana University J. Richardson University of Tenessee R. Riolo University of Michigan J. Schaeffer University of Alberta D. Schaffer Philips Laboratories L. Shu University of Alberta R. Smith University of Alabama W. Spears Naval Research Laboratory J. Suh Indiana University D. Van Gucht Indiana University T. Westerdale University of London D. Whitley Colorado State University S. Wilson Rowland Institute for Science -------------------------------- Date: Mon, 19 Mar 90 14:46 N From: DORI%IPMEL1.POLIMI.IT@CUNYVM.CUNY.EDU Subject: Class-room scheduling via GA Milano, 19 March 1990 Is there anybody that can give me some informations about people trying to solve the time-table problem (classroom scheduling) using Genetic Algorithms? I need names and addresses or articles. If anyone has got some articles and is so nice to send them to me I'll appreciate this a lot. My address is: Marco Dorigo Dipartimento di Elettronica Politecnico di Milano Via Ponzio 34/5 20133 Milano Italia Tel. +39-2-2399-3622 e-mail: dori%ipmel1.polimi.it@iboinfn.bitnet dorigo@tumult.informatik.tu-muenchen.de Thank you to everybody that is going to help me, Marco -------------------------------- Date: Thu, 22 Mar 90 06:55:07 CST From: Dave Goldberg Subject: Call for Papers -- Dortmund Workshop The following Call for Papers should be of interest to genetic algorithmists. Note that the workshop is the week following Stewart Wilson's Paris conference, permitting overseas travelers to get two conferences for the price of one. I hope to see many of you there. Dave G. ----------------------------------------------------------------------------- FIRST ANNOUNCEMENT and CALL FOR PAPERS International Workshop Parallel Problem Solving from Nature (PPSN) October 1 - 3, 1990 University of Dortmund, Germany F.R. Scope With the appearance of massively parallel computers increased attention has been paid to algorithms which rely upon analogies to natural processes. The workshop scope includes but is not limited to the following topics: - Darwinian methods such as Evolution Strategies and Genetic Algorithms - Boltzmann methods such as Simulated Annealing - Classifier systems and Neural Networks insofar as problem solving predominates - Transfer of other natural metaphors to artificial problem solving The objectives of this workshop are - to bring together scientists and practitioners working on and with such strategies. - to gather theoretical results about as well as experimental comparisons between these algorithms. - to discuss various implementations on different parallel computer architectures (e.g. SIMD, MIMD, LAN). - to look for current and future applications in science, technology, and administration. - to summarize the state of the art in this field which up to now has been scattered so widely among disciplines as well as geographically. Submission of papers, Proceedings Prospective authors are invited to submit 4 copies of an extended abstract of two pages to the conference chair before June 1, 1990. All contributions will be reviewed by the programme committee and up to about 30 papers will be selected for presentation. Authors will get notice about acceptance or rejection of their papers by July 15, 1990. Full papers will be due on September 1, 1990. They will be delivered to all participants at the conference as a prepublication volume. Final papers for the proceedings of the workshop should be finished immediately after the workshop. Details about the format of the camera-ready final papers will be distributed later. Language The official language for papers and presentations is English. Conference Chair: H. Muehlenbein and H.-P. Schwefel Gesellschaft fuer Mathematik University of Dortmund und Datenverarbeitung (GMD) -Z1- Dept. of Computer Science P. O. Box 12 40, Schloss Birlinghoven P. O. Box 50 05 00 D-5205 St. Augustin 1 D-4600 Dortmund 50 F. R. Germany F. R. Germany Tel. +49-2241-142405 Tel. +49-231-755-4590 Fax +49-2241-142889 Fax +49-231-755-2047 bitnet grzia0@dbngmd21 bitnet uin005@ddohrz11 Programme Committee: (chair) D.E. Goldberg Univ. of Alabama, Tuscaloosa, USA (chair) R. Maenner Univ. of Heidelberg, FRG Institute of Physics Philosophenweg 12 D-6900 Heidelberg 1 Tel. +49-6221-569363 Fax +49-6221-475733 bitnet maen@dhdmpi50 E.M.L. Aarts Philips Res.Lab. Eindhoven, NL P. Bock Univ. of Washington DC, USA V. Cerny Univ. of Bratislava, CSSR Y. Davidor Weizmann Inst. Rehovot, Israel G. Dueck IBM Heidelberg, FRG J.J. Grefenstette Naval Res.Lab. Washington DC, USA A.W.J. Kolen Univ. of Limburg, Maastricht, NL B. Manderick Univ. of Brussels, Belgium H. Roeck Univ. of Bielefeld, FRG H. Schwaertzel Siemens AG Munich, FRG B. Soucek Univ. of Zagreb, YU H.-M. Voigt Academy of Sciences Berlin, GDR Organization Committee: J. Becker, H. Bracklo, H.-P. Schwefel, E. Speckenmeyer, A. Ultsch Sponsors: Parsytec GmbH and Paracom GmbH, IBM Deutschland GmbH, Siemens AG Deadlines: Abstracts (2 pages) June 1, 1990 Notification of acceptance July 15, 1990 Full papers (for preprints) September 1, 1990 Workshop October 1-3, 1990 Final papers November 1, 1990 Reply Form International Workhop Parallel Problem Solving from Nature (PPSN) Dortmund, October 1-3, 1990 c/o Prof. Dr. H.-P. Schwefel Dept. of Computer Science Tel. +49-2 31/7 55/45 90 P. O. Box 50 05 00 Fax +49-2 31/7 55/20 47 D-4600 Dortmund 50 bitnet uin005@ddohrz11 F. R. Germany Title First Name Middle Initials Last Name ................................................................. Institution ..................................................... Address ......................................................... ................................................................. ................................................................. ( ) Please send further information ( ) I intend to attend the workhop ( ) I intend to submit an abstract: Title of paper to be presented ................................................................. ................................................................. Category: ( ) theory ( ) implementation ( ) application -------------------------------- End of Genetic Algorithms Digest ********************************