Genetic Algorithms Digest Thursday, August 7, 1997 Volume 11 : Issue 27 - 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 [132.250.84.25] in /pub/galist. ****************************************************************************** Today's Topics: - Ph.D. thesis on linkage-friendly GAs available - A.K. Dewdney, core wars - Random number generators (Re: v11n26) - Final CFP: special issue on scheduling - Free EP97 Proceedings for new EPS members - Visiting post -urgent - Special issue on variable length representations and non-coding segments - Extended Deadline Autonomous Robots CFP ---------------------------------------------------------------------- CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) 3NWGA 3rd Nordic Workshop on GAs, Helsinki, Finland (v10n43) Aug 18-20, 97 PATAT97 Intl Conf on Automated Timetabling, Toronto (v11n6) Aug 20-22, 97 IJCAI97 Workshop on Evolvable Systems, Nagoya, Japan (v11n5,6) Aug 23, 97 IMACS97 Scientific Comp, Modelling & App Math, Germany (v10n42) Aug 24-29, 97 IMACS97 Evolutionary Computation, Berlin, Germany (v10n45) Aug 24-29, 97 SNAC97 School on Natural Computation, Turku, Finland (v11n12) Aug 25-29, 97 BCEC97 Bio-Computing and Emergent Computation, Sweden (v10n44) Sep 1-2, 97 GALESIA97 Conf on GAs in Engineering Systems, Glasgow UK (v10n36) Sep 2-4, 97 EUROMICRO97 Euromicro Wrkshp on Comp Intel, Hungary (v10n47) Sep 3-4, 97 EUFIT97 Intelligent Techniques & Soft Computing, Aachen (v10n41) Sep 8-12, 97 SOCO97 Intl ICSC Symposium on Soft Computing, France (v10n40) Sep 17-19, 97 EA97 Evolution Artificielle, EMA-EERIE, Nimes, France (v11n10), Oct 21-24, 97 Evol Computation for Industrial Applications,New Zealand (v11n3)Nov 24-28, 97 EuroGen97 Short course GAs & ESs / Comp Sci & Eng (v11n5) Nov 28 - Dec 5, 97 SAC98 GAs and Optimization Track, Atlanta, Georgia (v11n17) Feb 27- Mar 1, 98 EP98 7th Conf on Evolutionary Programming, San Diego (v11n18) Mar 25-27, 98 ACDM98 Adaptive Comp in Design & Manufacture, Plymouth (v11n3) Apr 21-23, 98 ICEC98 Intl Conf on Evol Computation, Anchorage, Alaska (v11n22) May 4-9, 98 ISORA98 Learning Cyclic Control/Behavior in Robots,Alaska(v11n8)May 10-14, 98 GP98 Genetic Programming Conference, Madison, WI (v11n23/25) Jul 22-25, 98 HIC98 Intl Conf on Hydroinformatics, Copenhagen, Denmark(v11n13)Aug 24-26, 98 ICES98 Intl Conf on Evolvable Systems, Lausanne, Switz (v11n11) Sep 24-26, 98 PPSN98 Parallel Problem Solving from Nature,Amsterdam(v11n16)Sep 27-Oct 1, 98 http://www.aic.nrl.navy.mil/galist/info/conferences/CONFERENCES.html has more information on the above conference activities. Send announcements of other activities to GA-List@aic.nrl.navy.mil. ------------------------------ From: Larry Merkle Date: Thu, 31 Jul 1997 13:41:20 -0600 (MDT) Subject: Ph.D. thesis on linkage-friendly GAs available My Ph.D thesis, "Analysis of Linkage-Friendly Genetic Algorithms" is available from my WWW page: http://www.thuntek.net/~lmerkle or via anonymous ftp: ftp://thuntek.net/pub/users/sub/lmerkle/dissertation.ps.gz Abstract Evolutionary algorithms (EAs) are stochastic population-based algorithms inspired by the natural processes of selection, mutation, and recombination. EAs are often employed as optimum seeking techniques. A formal framework for EAs is proposed, in which evolutionary operators are viewed as mappings from parameter spaces to spaces of random functions. Formal definitions within this framework capture the distinguishing characteristics of the classes of recombination, mutation, and selection operators. EAs which use strictly invariant selection operators and order invariant representation schemes comprise the class of linkage-friendly genetic algorithms (lfGAs). Fast messy genetic algorithms (fmGAs) are lfGAs which use binary tournament selection (BTS) with thresholding, periodic filtering of a fixed number of randomly selected genes from each individual, and generalized single-point crossover. Probabilistic variants of thresholding and filtering are proposed. EAs using the probabilistic operators are generalized fmGAs (gfmGAs). A dynamical systems model of lfGAs is developed which permits prediction of expected effectiveness. BTS with probabilistic thresholding is modeled at various levels of abstraction as a Markov chain. Transitions at the most detailed level involve decisions between classes of individuals. The probability of correct decision making is related to appropriate maximal order statistics, the distributions of which are obtained. Existing filtering models are extended to include probabilistic individual lengths. Sensitivity of lfGA effectiveness to exogenous parameters limits practical applications. The lfGA parameter selection problem is formally posed as a constrained optimization problem in which the cost functional is related to expected effectiveness. Kuhn-Tucker conditions for the optimality of gfmGA parameters are derived. Parameter selection techniques are proposed for fmGAs and gfmGAs. Sincerely, Larry Merkle Capt Laurence D. Merkle, Ph.D. Center for Plasma Theory and Computation PL/WSQA 3550 Aberdeen Ave SE Kirtland AFB, NM 87117-5776 voice: (505) 846-9101 FAX: (505) 846-9103 official e-mail: merklel@plk.af.mil official www: http://www.afit.af.mil:80/Schools/EN/ENG/LABS/PARALLEL/Students/lmerkle.htm personal e-mail: l.merkle@ieee.org personal www: http://thuntek.net/~lmerkle ------------------------------ From: Harold Eckstein Date: Mon, 28 Jul 1997 01:06:45 -0400 Subject: A.K. Dewdney, core wars Hi, Can you help me, please, with two searches? I'd like to find someone with a copy of the Core Wars document(s), which describe that computer game of the mid-eighties. I and a friend think it would be interesting to adapt it as a test bed for GP. I used to have at hand the documentation and a Redcode interpreter, but I can't find either any more. Can you help me find this material? If you are interested in our GP idea, please let me know. Thanks for your attention. Sincerely, Harold Eckstein ------------------------------ From: ds1@philabs.research.philips.com (Dave Schaffer) Date: Fri, 1 Aug 97 14:24:31 EDT Subject: Random number generators (Re: v11n26) In V11 issue 26 Konstam writes: > These researchers conclusions are that the quality of the Random Number > generator makes no difference to the outcome of the genetic algorithm runs. > This is a slight over-simplification of their conclusions but if they are > right it seems to me that the concern about the quality of random number > generation in GA is misplaced. I must strenuously disagree with drawing this over-general conclusion from the Meysenburg & Foster study. At least, readers should remember that the reported results were derived from: 1) a simple GA 2) online average performance 3) after 1000 generations for all problems 4) with popsize of 100 for all problems 5) with crossover probability = 0.6 for all problems 6) with mutation probability = 0.01 for all problems 7) for the test problems described (which looks like a good set to me, BTW) While working on our 1989 study of the effects of GA parameters on online performance, we had the same experience as did Ross et al. (GA-List v11 issue23): statistically significant, but very suspicious patterns in our results were traced to the weak pseudo random number generator (PRNG) we were using. These patterns vanished when a good PRNG was used. So I must ask, why didn't Meysenburg & Foster see it? I do not have a definitive answer, and cannot have one without doing some additional studies myself (which I cannot afford to do at this time), but I offer the following hypothesis for general consideration: H1: The performance measure used was too insensitive to observe the effect. When you use online average and you run your GA rather too long (i.e. the population diversity was all but lost in the early generations), you can end up looking at averages that contain mostly random walk data. In our 1989 study (ICGA89 p51) we did several things I wouldn't do today (like use a weak GA and online average on too small a problem set), but at least we tuned the length of each run to the difficulty of the problem. I think it's just irresponsible to suggest that you can do serious problem solving with an algorithm as exploitive as a (good) GA and get away with using a flawed PRNG. ------------------------------ From: David Montana Date: Fri, 01 Aug 1997 18:16:52 -0400 Subject: Final CFP: special issue on scheduling FINAL CALL FOR PAPERS Special Issue on Scheduling in the journal Evolutionary Computation Scheduling and timetabling are very important problems in a wide variety of domains including service (e.g., scheduling repair service calls or generating staffing plans), manufacturing (e.g., job shop or flow shop routings), transportation (e.g., vehicle routing), and the military (e.g., logistics planning). The large economic impact of scheduling has attracted a large amount of research into algorithms for automatic schedule generation. Recently, evolutionary algorithms have been applied to various scheduling and timetabling problems with notable success. However, many open questions still remain about genetic scheduling. This special issue will address some of these questions. Papers will be considered which accomplish at least one of the following: - provide example(s) of successful operation of genetic scheduling and document its performance - analyze the characteristics of problems that are well suited to genetic scheduling techniques and those which are not - compare different genetic techniques and representations and investigate the suitability to different problems of particular representations, operators, parameters, parent selection algorithms, etc. - compare genetic scheduling with other approaches (both traditional and recent) and characterize problems suited to particular techniques - define and investigate the big issues which prevent genetic scheduling techniques from being even more widely applicable (e.g., how to scale to very large problems) Please submit papers before September 1, 1997 to the guest editor: David J. Montana E-mail: dmontana@bbn.com BBN Corporation Phone: (617)-873-2719 70 Fawcett Street Fax: (617)-873-2616 Cambridge, MA 02138 USA Both electronic submissions (postscript, either uuencoded in an e-mail message or with an ftp or web address) and hardcopies (five copies) will be accepted. A longer version of this call for papers can be found on the web at http://asd.bbn.com/papers/EVCO/evco.htm ------------------------------ From: fogel@ece.ucsd.edu (Fogel) Date: Sat, 2 Aug 1997 10:46:34 -0700 (PDT) Subject: Free EP97 Proceedings for new EPS members Dear Colleagues, The Evolutionary Programming Society purchased several additional copies of "Evolutionary Programming VI: Proceedings of the 6th Annual Conference on Evolutionary Programming," edited by P.J. Angeline, R.G. Reynolds, J.R. McDonnell, and R. Eberhart, Lecture Notes in Computer Science 1213, Springer, Berlin, Germany, 1997 after our joint meeting with the 1997 IEEE Conference on Evolutionary Computation in April. While these supplies last, the EP Society would like to offer a complimentary copy (yes that means free) to all new members. Members enjoy the lowest registration rates at the annual EP conference, as well as discounted subscription rates to the journal BioSystems (Elsevier Science). For more information, please see www.natural-selection.com/eps Applications for membership should be sent to: Bill Porto, Treasurer Evolutionary Programming Society c/o 3333 N. Torrey Pines Ct., Suite 200 La Jolla, CA 92037 If you have any further questions please don't hesitate to contact me. Sincerely, David Fogel Secretary, EPS ------------------------------ From: janikow Date: Mon, 4 Aug 1997 13:34:11 -0500 (CDT) Subject: Visiting post -urgent As always, we have a last-minute opening for a visitor for 1997/98. Ph.Ds or advanced doctoral students are all welcome. Please contact me for more info if interested. Sincerely, Cezary Z. Janikow Department of Math and CS, CCB319 tel (314) 516-6352 UMSL fax (314) 516-5400 St. Louis, MO 63121 mailto:janikow@arch.cs.umsl.edu http://www.cs.umsl.edu/Faculty/janikow ftp://radom.cs.umsl.edu ------------------------------ From: aswu@AIC.NRL.Navy.Mil Date: Mon, 4 Aug 97 17:53:59 EDT Subject: Special issue on variable length representations and non-coding segments CALL FOR PAPERS Evolutionary Computation Journal Special Issue on Variable size representation and non-coding segments Submission deadline: December 1, 1997 A simple but significant difference between natural and computational evolutionary systems is the prevalence of variable size representations in natural systems. This variability and flexibility lead naturally to the appearance of non-coding or unexpressed segments in the genome. The result of this freedom of expression is that natural evolution is virtually unlimited in the types and complexity of the organisms that can be evolved. Extending such flexibility to evolutionary algorithms (EAs) greatly increases the scope and complexity of the problem solutions that may be generated by these algorithms and makes these algorithms much more challenging to understand. EAs that use variable size genomes have more expressive power and freedom to solve problems where the structure and size of a satisfactory solution is unknown in advance. Non-coding segments are thought to provide some protection from the disruptive effects of genetic operators as well as provide natural backups for coding regions. A better understanding of the origin, effects, and implications of variable length representations and non-coding segments on EAs would allow researchers to use these structures more effectively in practical applications. This special issue will focus on papers that address one or more of the following topics: -- The effect of these structures on the performance (e.g. speed, stability, adaptability) of EAs. In what situations are they desirable or undesirable? -- Issues that must be addressed when extending EAs to include these structures. -- The effect of such structures on the dynamics of EAs. -- Analysis of the interaction between variable complexity and evolution. -- Controlling genome length and/or the emergence of non-coding material. -- Innovative applications outlining tradeoffs or issues involving variable length representation or non-coding segments. Authors interested in submitting papers should contact one of the guest editors listed below. Both electronic and hardcopy submissions are acceptable. If hard copies are sent, please provide 5 copies (not faxes) for reviewing. Manuscripts should be approximately 8,000 to 12,000 words in length and formatted for 8 1/2 x 11 inch paper, single sided and double spaced. The first page should include the title, abstract, key words, and author information (name, affiliation, mail address, telephone number, and electronic mail address). The text of the paper should begin on the second page and continue on consecutively numbered pages. Wolfgang Banzhaf Department of Computer Science LS11 University of Dortmund D-44221 Dortmund, Germany +49-231-9700-953 banzhaf@tarantoga.informatik.uni-dortmund.de Annie S. Wu Naval Research Laboratory Code 5514 4555 Overlook Avenue, SW Washington, DC 20375, USA 202-404-4946 aswu@aic.nrl.navy.mil ------------------------------ From: Maja Mataric Date: Tue, 5 Aug 1997 11:34:02 -0400 (EDT) Subject: Extended Deadline Autonomous Robots CFP NOTE: Due to popular demand and unwieldy schedules, we have moved and *finalized* the submission deadline to Sep 1, 1997. CALL FOR PAPERS Autonomous Robots Journal Special Issue on Learning in Autonomous Robots http://www.cs.buffalo.edu/~hexmoor/autonomous-robots.html Guest editors: Henry Hexmoor and Maja Mataric Submission Deadline: September 1, 1997 Autonomous Robots is an international journal published by Kluwer Academic Publishers, Editor-in-Chief: George Bekey Current applications of machine learning in robotics explore learning behaviors such as obstacle avoidance, navigation, gaze control, pick and place operations, manipulating everyday objects, walking, foraging, herding, and delivering objects. It is hoped that these are first steps toward robots that will learn to perform complex operations ranging from folding clothes, cleaning up toxic waste and oil spills, picking up after the children, de-mining, look after a summer house, imitating a human teacher, or overseeing a factory or a space mission. As builders of autonomous embedded agents, researchers in robot learning deal with learning schemes in the context of physical embodiment. Strides are being made to design programs that change their initial encoding of know-how to include new concepts as well as improvements in the associations of sensing to acting. Driven by concerns about the quality and quantity of training data and real-time issues such as sparse and low-quality feedback from the environment, robot learning is undergoing a search for quantification and evaluation mechanisms, as well as for methods for scaling up the complexity of learning tasks. This special issue of Autonomous Robots will focus on novel robot learning applications and quantification of learning in autonomous robots. We are soliciting papers describing finished work preferably involving real manipulator or mobile robots. We invite submissions from all areas in AI and Machine Learning, Mobile Robotics, Machine Vision, Dexterous Manipulation, and Artificial Life that address robot learning. Submitted papers should be delivered by September 1, 1997. Potential authors intending to submit a manuscript can contact either guest editor for answer to any questions. Manuscripts should be typed or laser-printed in English (with American spelling preferred) and double-spaced. Both paper and electronic submission are possible, as described below. For paper submissions, send five (5) copies of submitted papers (hard-copy only) to: Dr. Henry Hexmoor Department of Computer Science State University of New York at Buffalo 226 Bell Hall Buffalo, NY 14260-2000 U.S.A. PHONE: 716-645-3197 FAX: 716-645-3464 For electronic submissions, use Postscript format, ftp the file to ftp.cs.buffalo.edu, and send an email notification to hexmoor@cs.buffalo.edu Detailed ftp instructions: compress your-paper (both Unix compress and gzip commands are ok) ftp ftp.cs.buffalo.edu (but check in case it has changed) give anonymous as your login name give your e-mail address as password set transmission to binary (just type the command BINARY) cd to users/hexmoor/ put your-paper send an email notification to hexmoor@cs.buffalo.edu to notify us that you transferred the paper Relevant Dates: September 1, 1997 submission deadline November 15, 1997 review deadline December 1, 1997 acceptance/rejection notifications to the authors ------------------------------ End of Genetic Algorithms Digest ******************************