Genetic Algorithms Digest Wednesday, September 20, 1995 Volume 9 : Issue 47 - 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: - CFP - New book announcement - Caching Evaluation Results - bibliography available - NFL Practical Implications - EUROGEN95, Detailed Timetable - Request Information - GA application - FOGA96 CFP ---------------------------------------------------------------------- ******************************************************************************* CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) ASI-AA-95 Practice and Future of Autonomous Agents (v8n19) Sep 23-Oct 1, 95 SOCONF95 Self-Organization of Complex Structure, Berlin (v9n30) Sep 24-28, 95 MENDEL95 130th Anniversary of Mendels Laws, Brno, Czech (v9n28) Sep 26-28, 95 Towards Evolvable Hardware Intl Wrkshp, Lausanne, Switz (v9n29) Oct 2-3, 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 WWW95 on Fuzzy Logic and NNs/Evol Comp, Nagoya, Japan (v9n6) Nov 14-15, 95 CALMA95 Combinatorial Algs for Military Appl, Scheveningen (v9n43) Nov 24, 95 ICEC95 IEEE Intl Conf on Evol. Computing, Perth (v8n36) Nov 29-Dec 1, 95 EUROGEN95 GAs and ESs in Computational Sci & Eng, Spain (v9n15) Dec 4-8, 95 SAC96 Symposium on Applied Computing GA & Opt Track, PA (v9n33) Feb 17-19, 96 EP96 5th Conf on Evol Programming, San Diego, CA (v9n18) Feb 29-Mar 3, 96 AAAI-96 Spring Symposium Series, Stanford University, CA (v9n44)Mar 25-27, 96 ACEDC96 Adaptive Computing in Eng. Design & Control, UK (v9n28) Mar 26-28, 96 SOCO96 Intl Symposia w/ Workshops/Tutorials, Reading, UK (v9n35)Mar 26-28, 96 SECTAM96 AI Techniques in Eng and Mechanics, Tuscaloosa (v9n46) Apr 14-16, 96 ALifeV Artificial Life Conference, Nara, Japan (v9n45) May 16-18, 96 ICEC96 IEEE Intl Conf on Evol Comp, Nagoya, Japan (v9n18) May 20-22, 96 ISRAM96 Session on Evol Algs in Robotics, Montpellier (v9n46) May 27-30, 96 IPMU96 Granada, Spain (v9n31) Jul 1-5, 96 GP96 Genetic Programming Conference, Stanford, CA (v9n9) Jul 28-31, 96 SAB96 From Animals to Animats, Cape Cod, Massachusetts (v9n31) Sep 9-13, 96 PPSN96 Parallel Problem Solving from Nature, Berlin (v9n17) Sep 22-27, 96 ICGI96 Colluquium on Grammatical Inference, Montpellier (v9n45) Sep 25-27, 96 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ******************************************************************************* ------------------------------ From: jim@anolis.bnr.usu.edu (James W. Haefner) Date: Tue, 12 Sep 95 Subject: CFP !!!!!!!! CORRECTION TO !!!!!!!!!!!!! * * * * CALL FOR PAPERS * * * * INTERNATIONAL JOURNAL IN COMPUTER SIMULATION announces a SPECIAL ISSUE scheduled for 1996 on NEW TECHNIQUES OF COMPUTER SIMULATION IN THE NATURAL SCIENCES The OLD deadline was 1 OCT 1995. The NEW DEADLINE is 1 NOV 1995. All submissions welcomed. This is a good opportunity to publish the computational details of models that other journals tend to curtail. More details below. Contact: Jim Haefner: jim@anolis.bnr.usu.edu Virtually all traditional disciplines in the natural sciences (physics, chemistry, biology, environmental sciences) use computer simulation and numerical analysis in the development of theories and models. Most of these applications are computationally hard, requiring the use of high-performance computer hardware and software. New algorithms and simulation techniques have been developed in the separate sub-disciplines that are not communicated effectively to colleqgues in other areas of science. This special issue is being planned to report the results of state-of-the-art research on new simulation techniques applicable to the natural sciences. This is an opportunity for modelers in the physical and biological sciences to relate details of their computational approaches to a diverse audience of simulation specialists for the purpose of cross-fertilization. Specific topics of interest include, but are not limited to: o Object-oriented simulation applied to continuous system dynamics o New algorithms and simulation techniques applied to particle-based and Lagrangian systems o Genetic algorithms and evolutionary programming approaches to simulation in the physcial and biological sciences o New approaches to simulation and model visualization, analysis, and performance evaluation o Innovative approaches to parallel and distributed simulation of continuous and particle-based systems Prospective authors are invited to submit five copies of previously unpublished, archival-quality research contributions by *1 Nov 1995* (new deadline) to Dr. James W. Haefner, Guest Editor Department of Biology Utah State University Logan, UT 84322-5305 Email: jim@anolis.bnr.usu.edu Phone: 801-797-3553 FAX: 801-797-1575 International Journal in Computer Simulation was established in 1989 and is published quarterly by Ablex Publishing Corporation (Norwood NJ). It welcomes papers concerning any area of computer simulation used in industry, military, engineering or the natural sciences. ------------------------------ From: "Stan Franklin" Date: Wed, 13 Sep 1995 Subject: New book Taking the position that minds are control structures for autonomous agents (see http://www.msci.memphis.edu/~franklin/aagents.html), *Artificial Minds* by Stan Franklin MIT Press A Bradford Book September 1995 ISBN 0-262-06178-3 464 pp., 95 illus. is concerned implicitely, and sometimes explictedly, with control architectures for autonomous agents. A brief description can be found at http://www-mitpress.mit.edu/mitp/recent-books/cog/fraah.html. [ WMS: Chapter 8 is titled: "Evolution, Natural and Artificial" ] Stan Franklin (901) 678-3142 phone Math Sciences (901) 678-2480 fax Univ of Memphis stan.franklin@memphis.edu Memphis, TN 38152 http://www.msci.memphis.edu/~franklin/ ------------------------------ From: jim@btc.uwe.ac.uk Date: Thu, 14 Sep 95 Subject: Caching Evaluation Results Hi, I'm currently working on a problem with a really time-consuming evaluation function, and so thought I'd speed this up by building a cache of previous evaluations to save time re-evaluating previously seen strings. Does anyone know of any previous work on the use of memory caching techniques with ga's e.g. best replacement policy, optimal size, access technique etc. If people could reply to me I'll post a summary Thanks Jim Smith Evolutionary Computing Group University of West of England [ WMS: My GAC code uses a partial cache to prevent re-evaluation of unchanged individuals from generation to generation - the assumption, of course, is that the evaluation function is not stochastic. However, I always assumed that a full cache might not be reasonable, because it seemed unlikely I would get many "hits" if the search space was even moderately large. Perhaps this assumption was wrong. If you do cache everything, this raises the interesting notion of actually using that information to direct search - you can consider this to be an ever expanding population. ] ------------------------------ From: Ted.Belding@umich.edu (Theodore C. Belding) Date: Fri, 15 Sep 1995 Subject: bibliography available (A copy of this message has also been posted to the following newsgroups: comp.ai.genetic, comp.ai.alife) While setting up a complex systems reading group here at Michigan, I've compiled a bibliography of readings on complex adaptive systems, emergent computation, modeling and simulation, and related topics. It's at: http://www-personal.engin.umich.edu/~streak/bib/ It's hardly complete, but someone may find it useful. Many thanks to Stephanie Forrest, Melanie Mitchell, Jim Crutchfield, and John Laird for syllabi and suggestions that went into this. Any mistakes and omissions are of course my own. -Ted Ted Belding Ted.Belding@umich.edu or streak@engin.umich.edu University of Michigan Division of Computer Science and Engineering http://www-personal.engin.umich.edu/~streak/ ------------------------------ From: G Bilchev Date: Fri, 15 Sep 1995 Subject: NFL Practical Implications Please find below my explanation to the question why the NFL paper invoked so mush controversy in the GA community? There are two different and *incompatible* scenario. The first is the NFL scenario in which the NFL paper was developed and the second is the practical scenario in which many people work in real world situations. Therefore, many of us could not accept the NFL scenario as practical (i.e. real world). The main message of this posting is to prove that the two scenario are *incompatible*: Initial NFL theorem scenario: 1) algorithms that contain all points sampled so far are considered 2) the cost is set by the number of distinct evaluations f(x) Let's draw some initial inferences about the scenario: a) if we ralax 1) then we could not guarantee the completeness of the compacting procedure, i.e. if we consider an algorithm which does not remember all the points sampled so far it is not guaranteed in general that it will generate m distinct samples. b)The only way to guarantee completeness of the compacting procedure is in general to modify the algorithm to work with constantly increasing populations (i.e. with all points sampled so far). This could cause possibly huge computational overhead due to: 1) checking againts all points met so far (log time), 2) there could be operations in the algorithm that involve the whole population (like sorting) with computational complexity depending on the particular operation, and c) let's define the computational complexity to generate a distinct point after m calls as C(m); then depending on the operators of the particular algorithm it could happen that C(m) is a very fast growing function. c) the way the NFL scenario solves all of the problems mentioned in b) is to accept 2) as real-world cost, i.e. adopt a cost measure that disregards all of the computational overhead. Please also note that this cost also disregards the possibility for f to have different computational complexity at different points of the search space (this issue is very important in real world situations when f is a simulation model). Then for algorithms that comply with the NFL scenario it is proved that P(c|f,m,a) is independent of a. The proof is rigorous. Now let's define a second scenario: 1) algorithms do not work with all points; 2) the cost is wall-clock time T For algorithms that comply with this scenario the completeness of the compacting procedure is not guaranteed. Therefore they do not comply with the first scenario (in which the NFL was proved) and therefore we could NOT compare such algorithms by the NFL theorem. If we know use the trick to gurantee completeness by modifying them to work with all the points sampled so far then point 2) from the second scenario catches this situation and the equation of the NFL becomes: sum P(c|f,m1,a1)= sum P(c|f,m2,a2) where in general m1 is NOT equal to m2 (different algorithms would produce in general different number of samples for the same time T). Because the NFL theorem was NOT rigorously proved when m1 is not equal to m2 then we again could NOT compare such algorithms by the NFL theorem. Real world algorithms like GA's, simulated annealing, hill-climbing, etc. do NOT comply with the first scenario. However, they comply with scenario 2.) Therefore we could *not* compare such algorithms by the NFL theorem. All subsecuent results in the paper are based on the NFL scenario, therefore all results *do not hold* for algorithms that do not comply with the initial scenario. In my experience (engineering design) the practical scenario is the second scenario. I would be interested to get information about which scenario is accepted as practical in which area. I will summerise. George Bilchev Plymouth Engineering Design Centre UK ------------------------------ From: "Manuel J. Galan-Moreno" Date: Fri, 15 Sep 1995 Subject: EUROGEN95, Detailed Timetable Mon, Dec. 4 08:15-09:00 Registration 09:00-10:00 Welcome 10:00-11:00 Goldberg D. "What Should Genetic Algorithmists Do?" 11:00-11:30 Coffee Break 11:30-12:30 Krishnakumar K. "Genetic Algorithm Modules in Matlab: Design and Implementation using Software Engineering practices". 12:30-13:30 Fogarty T. "Evolving multi-agent systems" 13:30-15:30 Lunch 15:30-16:30 Schwefel H.-P. "Evolution Strategies II Theoretical aspects" 16:30-17:30 Schoenauer M. "Representations for Evolutionary Optimization and Identification in Structural Mechanics" 17:30-18:30 Krishnakumar K. "Evolutionary Fuzzy Modeling (EFM) with Clustered Niches and its application to an aircraft control problem" Tue, Dec. 5 09:00-10:00 Goldberg D. "Limits and Horizons of Artificial Genetic Search" 10:00-11:00 Goldberg D. "From Competence to Efficiency: An Illinois Perspective on Genetic Algorithms" 11:00-11:30 Coffee Break 11:30-12:30 Krishnakumar K. "Solving large optimization problems using a genetic algorithm with stochastic coding" 12:30-13:30 Fogarty T. "GAs for load balancing in the process industries". 13:30-15:30 Lunch 15:30-16:30 Baeck T. "Evolution Strategies I Variants and their computational implementation" 16:30-17:30 Velasco J.R. "Genetic Algorithms in Fuzzy Control Systems" 17:30-18:30 Quagliarella D. "Genetic Algorithms Applications in Computational Fluid Dynamics" Wed, Dec. 6 09:00-10:00 Moreno R. "Neural Nets, Natural and Artificial" 10:00-11:00 Winter G. "Genetic Algorithms: A Stochastic Improvement Technique. Tools, Skills, Pitfalls and Examples" 11:00 Excursion Thu, Dec. 7 09:00-10:00 Periaux J. "Robust Genetic Algorithms for Optimization Problems of Aerodynamic Design" 10:00-11:00 Whitley D. "Modeling Hybrid Genetic Algorithms" 11:00-11:30 Coffee Break 11:30-12:30 Muhlenbein H. "The science of breeding as a theoretical foundation of genetic algorithms" 12:30-13:30 Doorly D. "Parallel GA's for optimization in Computational Fluid Dynamics" 13:30-15:30 Lunch 15:30-16:30 Herrera F. "A General Study for Genetic Fuzzy Systems" 16:30-17:30 Poloni C. "Multi objective aerodynamic shape design by means of Hybrid Genetic Algorithm" Fri, Dec. 8 09:00-10:00 Verdegay J.L. "Tackling Fuzzy Genetic Algorithms" 10:00-11:00 Whitley D. "Genetic Algorithms and Neural Networks: An Update" 11:00-11:30 Coffee Break 11:30-12:30 Muhlenbein H."PeGaSuS a programming environment for genetic algorithms" 12:30-13:30 Michielssen E. "Electromagnetic system design using Genetic Algorithms." -- Prof. Dr. Manuel J. Galan Universidad de Las Palmas de Gran Canaria Campus de Tafira Baja 35017 Las Palmas de G.C. -Espa~na- E-mail: manolo@aries.dma.ulpgc.es [ WMS: More info can be found on ftp.aic.nrl.navy.mil under pub/galist/info/conferences/EUROGEN95.info ] ------------------------------ From: rbarron@ccr.dsi.uanl.mx Date: Fri, 15 Sep 1995 17:51:08 EDT Subject: Request Information. Hi everybody. I am study Computer Science in the Universidad Autonoma de Nuevo Leon in Monterrey, Nuevo Leon, Mexico. I am working in GA's as a part of my thesis of undergraduate and I am very interested in the works of GA'a and CS's in Robotics. I would like to know if there exist some works using GA'a and CS's in robotics ( Path planning, programming of robots, etc.) If you more about this I will appreciate your comments and e-mails. Thanks, sincerely. Ramon Barron-Vazquez A.P. # 75-F Ciudad Universitaria. C.P. 66450 San Nicolas de los Garza, N.L. Mexico e-mail: rbarron@ccr.dsi.uanl.mx [ WMS: "Genetic Algorithms and Robotics: A Heuristic Strategy for Optimization" by Yuval Davidor, is one work that I know of. ISBN #9810202172 ] ------------------------------ From: cghan@nms.kyunghee.ac.kr (Han Chi-Geun) Date: Mon, 18 Sep 95 18:36:11 KDT Subject: GA application Hi! I am looking forward applications of GA in steal industry. If you have any information about research that uses GA for solving any problem in steal industry, please send me a message. Thanks in advance. Chi-Geun Han Kyung Hee University Korea cghan@nms.kyunghee.ac.kr [ WMS: I really hope that this is about the STEEL industry! ;-) ] ------------------------------ From: belew@cs.wisc.edu (Rik Belew) Date: Mon, 18 Sep 95 11:36:21 -0500 Subject: FOGA96 CFP FOGA4 August 3-5, 1996 San Diego, California The 1996 Foundations of Genetic Algorithms (FOGA4) workshop will be the fourth biennial meeting of a workshop designed to explore theoretical issues relevant to genetic algorithms (GAs) and evolutionary compuation generally. FOGA4 will held Saturday August 3 through Monday, August 5, 199 at the Unviersity of San Diego in San Diego, California. A reception will be held Friday evening August 2, with regular workshop activities beginning August 3. Attendance at the workshop will be limited; the goal is to create a small forum with close interaction among all the participants. Individuals submitting papers will be given priority for attendance, and some slots will be reserved for students. All individuals interested in attending must indicate this by either submitting a paper or requesting attendance. Extended abstracts as well as requests for attendance must be received by February 1, 1996. Submissions should address theoretical issues in GAs or evolutionary computation. Papers which make use of empirical data should ensure that the experimental results are well-connected to foundational issues. Work describing the application of GAs to engineering problems is not appropriate for this meeting unless it clearly illuminates a larger theoretical concern. Extended abstracts should be no longer than 10 pages (11 point font). Electronic submission of problem-free Postscript files is encouraged. Four copies of hardcopy manuscripts must be postmarked no later than February 1, 1996. Authors of accepted papers will be notified by April 15, 1996. Drafts of the full paper are due by July 15, 1996 and will be distributed as part of a preprint to participants at the FOGA4 meeting. Authors of papers presented at the FOGA4 workshop will be asked to contribute final versions of their papers (based on discussion/feedback at the meeting) as part a volume to be published in book form. Important dates: 1 Feb 96 Extended abstract due 15 Apr 96 Authors notified of acceptance 15 Jul 96 Drafts of full paper due 3-5 Aug 96 FOGA4, San Diego, CA Paper submissions and inquires may be directed to: Richard K. Belew Computer Science & Engr. Dept. (0114) Univ. California -- San Diego La Jolla, CA 92093-0114 rik@cs.ucsd.edu Michael D. Vose C.S. Dept., 107 Ayres Hall The University of Tennessee Knoxville, TN 37996 vose@cs.utk.edu [ WMS: A PostScript version of the full call is on ftp.aic.nrl.navy.mil under pub/galist/info/conferences/FOGA96.ps ] ------------------------------ End of Genetic Algorithms Digest ******************************