Genetic Algorithms Digest Thursday, February 3, 1994 Volume 8 : Issue 3 - 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: - Rate of convergence (Re: v7n34) - paper available (2 messages) - Abstract of paper that will appear in J. Chem. Inf. Comp. Sci. - GA/GP software - 3rd Ann. Conf. on Evolutionary Programming ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) EP94 3rd Ann Conf on Evolutionary Programming, San Diego (v7n7) Feb 24-25, 94 IEE94 Colloquium on Molecular Bioinformatics, London, UK (v7n21) Feb 28, 94 SPIE, Neural & Stoch. Methods in Image & Sig Proc, Orlando(v7n18) Apr 5-8, 94 FLAIRS-94 Workshop on Artif Life and AI, Pensacola Beach, FL(v7n23) May 4, 94 The IEEE Conference on Evolutionary Computation, Orlando(v7n26) Jun 26-30, 94 FOGA94 Foundations of GAs Wkshop, Estes Park, Colorado(v7n26)Jul 30-Aug 3, 94 SAB94 3rd Intl Conf on Sim of Adaptive Behavior, Brighton(v7n11) Aug 8-12, 94 ECAI-94, 11th European Conference on AI, Amsterdam (v7n23) Aug 8-12, 94 IEEE/Nagoya Univ WW Wkshp on Fuzzy Logic & NNs/GAs, Japan(v7n33) Aug 9-10, 94 ISRAM94 Special Session on Robotics & GAs, Maui, Hawaii (v7n22) Aug 14-17, 94 COMPLEX94 2nd Australian National Conference, Australia (v7n34) Sep 26-28, 94 PPSN-94 Parallel Problem Solving from Nature, Israel (v7n32) Oct 9-14, 94 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: vose@cs.utk.edu Date: Mon, 3 Jan 94 12:38:22 -0500 Subject: Rate of convergence This is in response to Edmund Chattoe's request in Volume 7 : Issue 34. Theory has not much to offer at this point. However, in the limit as either (take your pick, as they are equivalent) 1) population size grows, 2) the deviation of sampling from expectation diminishes there are some *qualitative* results that can be proved. Subject to technical conditions about generic behavior (which one should regard as satisfied except in contrived situations) and assuming that convergence to "x" takes place, then evolving to within "d" from "x" happens in "k log(1/d)" generations. In other words, the GA is getting within "d" of wherever its going in time "O(log (1/d)". The proof is nonconstructive -- it relies on compactness -- and so "k" must be determined by curve fitting. This looks like some previous results about takeover time, but it is far more profound. The result pertains to the simple GA in it's complete and gory detail. Crossover and mutation are incorporated as well as selection. The weakness of course is that "k" is not given explicitly, and the result holds asymptotically (i.e., in the limit) with either condition 1 or 2 above. At the last GA conference, I seem to recall a poster presentation reporting a similar phenomenon on the basis of empirical observations. Best wishes, Michael Vose ------------------------------ From: Dirk Schlierkamp-Voosen Date: Wed, 29 Dec 1993 11:19:49 +0100 Subject: paper available The following paper is available via anonymous ftp. The science of breeding and its application to the breeder genetic algorithm BGA Heinz M\"uhlenbein, Dirk Schlierkamp-Voosen \begin{abstract} The Breeder Genetic Algorithm BGA models artificial selection as done by human breeders. The science of breeding is based on advanced statistical methods. In this paper a connection of genetic algorithm theory and the science of breeding is done. We show how the response to selection equation and the concept of heritability can be applied to predict the behavior of the BGA. Selection, recombination and mutation are analyzed within this framework. It is shown that recombination and mutation are complementary search operators. The theoretical results are obtained under the assumption of additive gene effects. For general fitness landscapes advanced statistical techniques for estimating the heritability are used to analyse and control the BGA. \end{abstract} To obtain an electronic copy of this paper: ftp ftp.gmd.de login: anonymous password: cd /gmd/as/paper binary get msv_breeder_genetic_algorithm.ps.Z quit Then at your system: uncompress msv_breeder_genetic_algorithm.ps.Z lpr -P msv_breeder_genetic_algorithm.ps Dirk Schlierkamp-Voosen, dirk.schlierkamp-voosen@gmd.de, (++49 2241) 14-2466 German National Research Center for Computer Science (GMD) Research Division Artificial Intelligence D-53 757 Sankt Augustin, FRG ------------------------------ From: aris@isosun.ariadne-t.gr Date: Fri, 7 JAN 94 00:51 GMT Subject: Paper available The following paper is available: Hatjimihail AT. Genetic algorithms based design and optimization of statistical quality control procedures. Clin Chem 1993;39:1972-8. ABSTRACT In general, we can not use algebraic or enumerative methods to optimize a quality control (QC) procedure so as to detect the total allowable analytical error with a stated probability, while the probability for false rejection is minimum. Genetic algorithms (GAs) offer an alternative, as they do not require knowledge of the objective function to be optimized and search through large parameter spaces quickly. To explore the application of GAs in statistical QC, I have developed two interactive computer programs, based on the deterministic crowding genetic algorithm. Given an analytical process, the program "Optimize" optimizes a user defined QC procedure, while the program "Design" designs a novel optimized QC procedure. The programs search through the parameter space and find the optimal or a near-optimal solution. The possible solutions of the optimization problem are evaluated using computer simulation. Please ask for hard copies from: Aristides T. Hatjimihail, Hellenic Complex Systems Laboratory, P.O. Box 56, GR-661 00 Drama, Greece. aris@isosun.ariadne-t.gr ------------------------------ From: drogers@MSI.COM Date: Fri, 7 Jan 94 00:27:37 -0500 Subject: Abstract of paper that will appear in J. Chem. Inf. Comp. Sci. Application of Genetic Function Approximation (GFA) to Quantitative Structure-Activity Relationships (QSAR) and Quantitative Structure-Property Relationships (QSPR). David Rogers* Molecular Simulations Incorporated 16 New England Executive Park Burlington, MA 01803-5297 drogers@msi.com A. J. Hopfinger University of Illinois at Chicago Department of Medicinal Chemistry and Pharmacognosy College of Pharmacy, Box 6998, Chicago, IL 60680 (Paper accepted into the Journal of Chemical Information and Computer Science) Abstract: The Genetic Function Approximation (GFA) algorithm offers a new approach to the problem of building Quantitative Structure Activity Relationship (QSAR) and Quantitative Structure-Property Relationship (QSPR) models. Replacing regression analysis with the GFA algorithm allows the construction of models competitive with, or superior to, standard techniques, and makes available additional information not provided by other techniques. Unlike most other analysis algorithms, GFA provides the user with multiple models; where the populations of the models are created by evolving random initial models using a genetic algorithm. GFA can build models using not only linear polynomials, but also higher-order polynomials, splines, and gaussians. By using spline-based terms, GFA can perform a form of automatic outlier removal and classification. The GFA algorithm has been applied to three published data sets to demonstrate it is an effective tool for doing both QSAR and QSPR. ------------------------------ From: Herve LUGA Date: Fri, 7 Jan 1994 10:01:34 GMT Subject: GA/GP software I am actually working on a parallel(or sequential) GA/GP system implemented in C++. In this system, problem must be representation independant and representations (LISP trees, bitstrings, charstrings, real valued,...) could act like species in the SAME population to solve the SAME problem. I want to make it run on a 36 transputer-based machine with 144 Megs of RAM If anybody is interested I could send Him an article about this system (in a few days....) Herve LUGA IRIT / Universite Paul Sabatier II RRRRR II TTTTTT 118 Rte de Narbonne 31062 TOULOUSE RR RR TT FRANCE II RRRRR II TT II RR RR II TT Tel : (+33) 61 55 63 13 II RR RR II TT Fax : (+33) 61 55 62 58 II * RR RR * II * TT E-Mail : luga@irit.fr ------------------------------ From: fogel@ece.UCSD.EDU (Fogel) Date: Tue, 4 Jan 94 18:36:38 PST Subject: 3rd Ann. Conf. on Evolutionary Programming Dear Colleagues: I'm sending along a registration form for EP94 followed by the preliminary program. If you want to register by email, please send your registration to Bill Porto, finance chair, at porto@orincon.com and then follow it up with regular mail. If you have any questions regarding the conference, please either send them to me, or to Bill Porto as you deem appropriate. Best wishes, David REGISTRATION FORM FOR THE THIRD ANNUAL CONFERENCE ON EVOLUTIONARY PROGRAMMING (EP94) February 24-26, 1994 Sheraton Harbor Island Hotel San Diego, CA, USA Sponsored by the Evolutionary Programming Society In Cooperation with the IEEE Neural Networks Council Please Indicate Your Form of Registration: Full Registration: (All three days/proceedings/banquet) EP Society or IEEE Member: Before Jan. 15, 1994: $225 After Jan. 15, 1994: $275 Non-Member: Before Jan. 15, 1994: $275 After Jan. 15, 1994: $325 Single Day Registration: (Includes proceedings but not banquet) Before Jan. 15, 1994: $100 After Jan. 15, 1994: $150 Student Registration: (No proceedings/no banquet/ID require) EP Society or IEEE Member: Before Jan. 15, 1994: $20/day After Jan. 15, 1994: $30/day Non-Member: Before Jan. 15, 1994: $30/day After Jan. 15, 1994: $40/day Tickets for the banquet can be purchased at the conference on a space available basis. The banquet speaker will be Dr. Gerald Joyce of Scripps Clinic and Research Institute. Papers are due at the conference and the proceedings will be published by World Scientific and distributed within four months. Total Registration in US$:______________ Please Indicate Form of Payment: Check in US$ (make payable to "EP94") VISA/MC __________________________________ Signature ________________________________ Date _____________________________________ Name _____________________________________ Affiliation ______________________________ Address __________________________________ City/State/Zip ___________________________ Country __________________________________ Mail to: Evolutionary Programming Society EP94 - Registration 9363 Towne Centre Dr. San Diego, CA 92121 Attn: Bill Porto, Finance Chair Preliminary Program for The Third Annual Conference on Evolutionary Programming February 24-26, 1994 Sheraton Harbor Island Hotel San Diego, CA, USA Sponsored by the Evolutionary Programming Society In Cooperation with the IEEE Neural Networks Council General Chairman: A.V. Sebald, U.C.S.D. Technical Program Chairman: L.J. Fogel, Natural Selection, Inc. Thursday, February 24, 1994 Registration: 8:00 a.m. - 5:00 p.m. 8:30 a.m. - 9:15 a.m. Plenary Talk: "An Introduction to Simulated Evolution" D.B. Fogel, Natural Selection, Inc. 9:15 a.m. - 9:30 a.m. -- Break 9:30 a.m. - 11:00 a.m. Evolving Neural Networks Session Chair: V.W. Porto, ORINCON Corporation "Evolving Neural Networks" - P.J. Angeline, IBM - G.M Saunders, J.B. Pollack, The Ohio State Univ. "Neural Network Construction using Evolutionary Programming" - J.R. McDonnell, W.C. Page, NCCOSC - D. Waagen, TRW "Growing Universal Neural Networks using GESA" - P.P.C. Yip, Y.-H. Pao, Case Western Res. "Generalization in Populations of Recurrent Neural Networks" - T.M. English, Texas Tech. Univ. 11:00 a.m. - 11:15 a.m. -- Break 11:15 a.m. - 12:00 noon Evolution Strategies Session Chair: H.-P. Schwefel, Univ. Dortmund "Improved Global Convergence by Means of Collective Learning" - R. Salomon, R. Pfeifer, Tech. Univ. Berlin "Neighborhood Model Evolution Strategies" - J. Sprave, Univ. Dortmund 12:00 noon - 1:15 p.m. -- Lunch 1:15 p.m. - 3:00 p.m. Evolutionary Image Processing and Clustering Session Chairman: M.A. Zmuda, Wright Laboratories "Evolving Wavelet Compression Strategies" - D. Waagen, J. Argast, TRW - J.R. McDonnell, NCCOSC "E-MORPH: A Two-Phased Learning System for Evolving Morphological Classificatio" - M.M. Rizki, Wright State Univ. - L.A. Tamburino, M.A. Zmuda, Wright Lab. "Classifier Design using Evolutionary Programming" - T.W. Brotherton, D.B. Fogel, P.K. Simpson, T. Pollard, ORINCON Corp. "An EP Clustering Algorithm for Short and Long Term Memory Paradigms" - M. Bower, Martin Marrietta "Automatic Control of Physically Realistic Animated Figures using Evolutionary Programming" - A. Fukunaga, J.T. Ngo, Harvard Univ. - J. Marks, Digital Equipment Corp. 3:00 p.m. - 3:15 p.m. -- Break 3:15 p.m. - 4:00 p.m. Hybrid Evolutionary Computation Session Chairman: Z. Michalewicz, Univ. North Carolina "Evolutionary Operators for Continuous Convex Parameter Spaces" - Z. Michalewicz, T.D. Logan, S. Swaminathan, U.N.C.C. "Evolutionary Optimization of Constrained Problems" - Z. Michalewicz, U.N.C.C. - N.F. Attia, Johnson Smith Univ. 4:00 p.m. - 4:10 p.m. -- Break 4:10 p.m. - 5:00 p.m. Biological Application of Simulated Evolution Session Chairman: G.B. Fogel, U.C.L.A. "Application of Evolutionary Algorithm to the Structure-Activity Relationship" - I.V. Tetko, V.Y. Tanchuk, A.I. Luik Inst. Bioorganic Petro. Chemistry "Evolving Continuous Behaviors in the Iterated Prisoner's Dilemma" - D.B. Fogel, Natural Selection, Inc. - P.G. Harrald, Simon Fraser Univ. 7:00 p.m. Banquet Banquet Speaker: "A Massively Parallel Analog System for Evolutionary Optimization: The Wetware Approach" G.F. Joyce, Scripps Clin. Res. Inst. Friday, February 25, 1994 Registration: 8:00 a.m. - 5:00 p.m. 8:30 a.m. - 10:30 a.m. Cultural Algorithms Session Chairman: R.G. Reynolds, Wayne State Univ. "An Introduction to Cultural Algorithms," -R.G. Reynolds, Wayne State Univ. "Modelling the Evolution of Cooperation Using Cultural Algorithms" - R.G. Reynolds, Wayne State Univ. "Learning to Understand Software using Cultural Algorithms" - R. Posner and R.G. Reynolds, Wayne State Univ. "A Region-Growing Approach to Edge Detection Based Upon Cultulral Algorithms" - W. Sverdlik, Lawrence Tech. Univ. - R.G. Reynolds, Wayne State Univ. "Optimal Rate Concept Acquisition using Cultural Algorithms" - W.G. Brown, Jackson State Univ. - R.G. Reynolds, Wayne State Univ. 10:30 a.m. - 10:45 a.m. -- Break 10:45 a.m. - 12:30 p.m. Evolutionary Control and Identification Session Chairman: J.R. McDonnell, NCCOSC "Reinforcement Learning using Evolutionary Programming" - N. Saravanan, Florida Atlantic Univ. "Behavior-Based Control for Autonomous Systems" - J.B. Watson, Columbus Research Lab. "Evolving Neural Networks to Control Unstable Dynamical Systems" - P. Pratt, Imperial College Sci. Tech. Med. "Evolution of Neural Networks by Implicit Specification" - A.S. Austin, Beckman Instruments Inc. "Evolutionary Optimization of State Space Representation of Experimental Data" - J.L. Breeden, Prediction Company 12:30 p.m. - 1:45 -- Lunch 1:45 p.m. - 3:45 p.m. Genetic Programming Session Chairman: P.J. Angeline, IBM "Genetic Programming: Myths and Facts" - P.J. Angeline, IBM "Scalability and Generalization in Genetic Programs: The Donut Problem" - W. Tackett, Hughes Missile Syst. Comp. "The Evolution of Evolvability in Genetic Programming" - L. Altenberg, Duke University "Scalable Learning in Genetic Programming Using Automatic Function Definition" - J. Koza, Stanford University 3:45p.m. - 4:00 p.m. -- Break 4:00 p.m. - 5:15 p.m. Panel Discussion: The Fundamental Questions of Evolutionary Design: An Open Discussion Panelists: -W. Atmar, AICS Research, Inc. -M.E. Gilpin, U.C.S.D. -G.F. Joyce, Scripps Clin. Res. Inst. -P. Mabee, San Diego State Univ. Saturday, February 26, 1994 Registration: 8:00 a.m. - 12:00 noon 8:30 a.m. - 10:00 a.m. Foundations of Evolutionary Algorithms Session Chairman: A.V. Sebald, U.C.S.D. "An Empirical Evaluation of the Gaussian Mutation Function in Evolutionary Programming" - M. Davis, New Mexico State Univ. "Controlled Offspring Generation in Evolutionary Programming" - G.P. Babu, M. Murty, Indian Inst. Science "Evolution of Two: An Example of Space of States Approach" - R. Galar, I. Karcz-Duleba. Tech. Univ. Wroclaw "Learning of Strategy Parameters in Evolutionary Programming: An Empirical Study" - N. Saravanan, Florida Atlantic Univ. 10:00 a.m. - 10:15 a.m. -- Break 10:15 a.m. - 11:45 noon Genetic Algorithms Session Chairman: W.M. Spears, Navy Research Lab. "Population Structure and GA Performance" - B. Manderick, EUR - P. Spiessens, VUB "An Evolutionary Algorithm for Syntax Parsing" - J.L. Johnson, Western Washington Univ. "Simple Subpopulation Schemes" - W.M. Spears, Navy Research Lab. "Evolving Cooperative Communicating Classifier Systems" - L. Bull, T.C. Fogarty, Univ. West England 11:45 a.m. - 1:00 p.m. -- Lunch 1:00 p.m. - 2:00 pm. Evolutionary Computing Session Chair: R. Freund, NCCOSC "Tuning Computer CPU Scheduling Algorithms using Evolutionary Programming" - B. Andersen, NCCOSC "Function Optimization and Parallel Evolutionary Programming on the MasPar MP-1" - K.M. Nelson, Florida Atlantic Univ. 2:00 p.m. - 2:15 p.m. -- Break 2:15 p.m. - 3:45 p.m. Speculations Session Chair: D.B. Fogel, Natural Selection, Inc. "Growing an Artificial Brain: The Genetic Programming of Million-Neural-Net-Module Artificial Brains with Trillion Cell Cellular Automata Machines" - H. de Garis, ATR Hum. Info. Proc. Res. "Exploratory Modeling: Search Through Spaces of Computational Experiments" - S. Bankes, RAND "Remarks on Progress Inspired by Evolutionary Simulations" - R. Galar, Tech. Univ. of Wroclaw "Evolutionary Algorithms in Economics: A View" - P.G. Harrald, Simon Fraser Univ. 3:45 p.m. - 4:00 p.m. -- Break 4:00 p.m. - 5:00 p.m. Panel Discussion: The Future of Evolutionary Computation Moderator: - A.V. Sebald, U.C.S.D. Panelists: - K.A. De Jong, George Mason Univ. - L.J. Fogel, Natural Selection, Inc. - H.-P. Schwefel, Univ. Dortmund - C. Taylor, U.C.L.A. ------------------------------ End of Genetic Algorithms Digest ******************************