Genetic Algorithms Digest Tuesday, June 18, 1996 Volume 10 : Issue 25 - 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: - End of discussion on NFL and related topics. - dropping optimal - drift bibliography - New Post Doctoral Position - Advanced MSc in Neural & Evolutionary Systems (London) ---------------------------------------------------------------------- CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) AID96 Artificial Intelligence in Design, Stanford Univ (v10n14) Jun 22, 96 EvCA96 Evol Comp and Its Applications, Moscow, Russia (v9n59) Jun 24-27, 96 MENDEL96 2nd Intl Mendel Conf on GAs, Brno, Czech (v9n61) Jun 26-28, 96 IPMU96 Granada, Spain (v9n31) Jul 1-5, 96 ICML96 Intl Conf on Machine Learning, Bari, Italy (v9n54) Jul 3-6, 96 GP96 Genetic Programming Conf, Stanford, CA (v9n9) Jul 28-31, 96 FOGA4 Foundations of Genetic Algorithms, San Diego, CA (v9n47) Aug 3-5, 96 AAAI96 Intl Wrkshp Intelligent Adaptive Agents, Portland (v10n4) Aug 4-8, 96 2NWGA 2nd Nordic Wrkshp on Genetic Algorithms, Finland (v9n56) Aug 19-25, 96 EUFIT96 Intelligent Techniques and Soft Computing, Germany (v9n60)Sep 2-5, 96 SAB96 From Animals to Animats, Cape Cod, Massachusetts (v9n31) Sep 9-13, 96 WCNN96 Session on Evolutionary Algorithms, San Diego (v9n62) Sep 15-20, 96 PPSN96 Parallel Problem Solving from Nature, Berlin (v9n17) Sep 22-27, 96 ICGI96 Colloquium on Grammatical Inference, Montpellier (v9n45) Sep 25-27, 96 ICES96 Conf on Evol Sys from Biology to Hardware, Tsukuba (v10n7) Oct 7-8, 96 SEAL96 Asia-Pacific Conf on Sim Evol And Learning, Korea (v10n13)Nov 9-12, 96 ICCIN97 Comp Intelligence and Neuroscience, North Carolina (v10n16)Mar 2-5,97 FEA97 1st Intl Wrkshp on Frontiers in EAs, North Carolina (v10n21) Mar 2-5,97 ICANNGA97 Intl Conf on Artificial NNs and GAs, England (v10n16) Apr 1-4, 97 EP97 Conf on Evolutionary Programming, Indianapolis (v10n19) Apr 13-16,97 ECAL97 4th European Conf on Artificial Life, England (v10n8) Jul 28-31, 97 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ------------------------------ From: Bill Macready Date: Thu, 13 Jun 96 11:53:47 MDT Subject: End of discussion on NFL and related topics. It appears the current nfl discussion involves only a few individuals and is no longer of interest to the broader community. For our part, we feel that we have said everything we can say about the issue. Consequently we will no longer be cluttering up the ga-list with our nfl related replies. We remind readers interested in these issues that our results are clearly explained in our most recent papers available at http://www.santafe.edu/~wgm/papers.html We thank all participants for a lively debate. Bill Macready and David Wolpert ------------------------------ From: TOBIAS PEGGS Date: Fri, 14 Jun 1996 10:17:16 GMT Subject: dropping optimal >From: GREENWOOD GARRISON >Maybe its about time we consider dropping the term "optimal" solution >and approach it from a more practical standpoint. >If a user finds that algorithm A gives a good enough answer in an >acceptable amount of time, is there really any reason to switch to >algorithm B? are you an engineer? :) I am, and I've been harping on about adopting this approach right the way through my PhD research (Classifier Systems in deriving operational control policies for multi-purpose reservoirs). I guess this 'thumb in the dyke' philosophy (sort of 'phew! this works, I know there's probably a more comfortable or complete solution, but what I've found is better than it was before - so let's go with it') upsets the Evolutionary Computing purists - but do these people have industrial sponsors breathing down their necks for the answers?!? In my (admittedly limited) experience, industry judges a technique by its affect on the bottom line of a balance sheet. So, of course, there's a strong argument for the 'academic' field to refine techniques in order such that, one day, they might produce 'optimal' (cost-saving) solutions, but sometimes industry can't wait that long. As an engineer, I have to use what's available to save money NOW whilst keeping an eye on developments that might save even more money in the future. I'd like to think I'm stating the obvious, but after following, say, the NFL debate for months before someone popped their head up and asked: 'what's the practical relevance here then, guys?' I'm not to sure. BTW: I have dropped the term "optimal" solution in favour of the fuzzy word 'better'. This brings a satisfied smile to the face of my industrial sponsors - the width of which I can use as a crude fitness function to assess my work... ___ http://www.cf.ac.uk/uwcc/engin/Civil&Struct/dss/dss_home.html ------------------------------ From: Ted.Belding@umich.edu (Theodore C. Belding) Date: Wed, 12 Jun 1996 16:39:57 -0400 Subject: drift bibliography (A copy of this message has also been posted to the following newsgroups: comp.ai.genetic) Here is what I've found so far on the topic of random genetic drift in genetic algorithms, in BibTeX format. Thanks to everyone who helped me compile this bibliography! Some of the entries do little more than mention the concept of drift; others go into far more detail. The chapters by Sewall Wright address drift in real populations, not GAs. -Ted @mastersthesis{syed:1995, author = {Omar Syed}, title = {Applying genetic algorithms to recurrent neural networks for learning network parameters and architecture}, school = {Case Western Reserve University}, address = {Cleveland}, month = {May}, year = {1995}, url = {http://www.lerc.nasa.gov/people/OmarSyed/homepage/MSThesis/}, note = {See especially Appendix A} } @phdthesis{dejong:1975, author = {Kenneth A. {De Jong}}, title = {An analysis of the behavior of a class of genetic adaptive systems}, school = {University of Michigan}, address = {Ann Arbor}, year = {1995}, note = {Dissertation Abstracts International 36(10), 5140B; UMI 76-9381} } @phdthesis{mahfoud:1995a, author = {Samir W. Mahfoud}, title = {Niching methods for genetic algorithms}, school = {University of Illinois at Urbana-Champaign}, address = {Urbana, IL, USA}, note = {IlliGAL Report 95001}, month = {May}, year = {1995}, url = {ftp://ftp-illigal.ge.uiuc.edu/pub/papers/IlliGALs/95001.ps.Z} } @phdthesis{wong:1995, author = {Hermean Wong}, title = {Performance Analysis of Genetic Algorithm}, school = {New Jersey Institute of Technology}, year = {1995}, note = {As of June, 1996 this is not listed in Dissertation Abstracts International. The copy in the NJIT library is non--circulating, and it is not available by ftp.} } @inproceedings{menczer:parisi:1992, author = {Filippo Menczer and Domenico Parisi}, title = {A model for the emergence of sex in evolving networks: adaptive advantage or drift?}, booktitle = {Toward a practice of autonomous systems: Proceedings of the first european conference on artificial life}, pages = {337--345}, editor = {Francisco J. Varela and Paul Bourgine}, publisher = {MIT Press}, address = {Cambridge, MA, USA}, year = {1992} } @inproceedings{asoh:muehlenbein:1994a, author = {Hideki Asoh and Heinz M\"{u}hlenbein}, title = {On the mean convergence time of evolutionary algorithms without selection and mutation}, booktitle = {Parallel problem solving from nature: PPSN III}, pages = {88--97}, editor = {Yuval Davidor and Hans--Paul Schwefel and Reinhard M\"{a}nner}, publisher = {Springer--Verlag}, address = {Berlin}, year = {1994}, note = {GMD Technical Report GMD-AS-TR-94-12}, url = {http://borneo.gmd.de/AS/ga/publi/gmd_as_ga-94_12.html} } @inproceedings{goldberg:segrest:1987, author = {David E. Goldberg and Phillip Segrest}, title = {Finite Markov chain analysis of genetic algorithms}, booktitle = {Genetic algorithms and their applications: Proceedings of the second international conference on genetic algorithms}, pages = {1--8}, editor = {John J. Grefenstette}, publisher = {Lawrence Erlbaum}, address = {Hillsdale, NJ, USA}, year = {1987} } @inproceedings{louis:rawlins:1993, author = {Sushil J. Louis and Gregory J. E. Rawlins}, title = {Syntactic analysis of convergence in genetic algorithms}, booktitle = {Foundations of genetic algorithms 2}, pages = {141--151}, editor = {L. Darrell Whitley}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA}, year = {1993} } @inproceedings{mahfoud:1995b, author = {Samir W. Mahfoud}, title = {Population size and genetic drift in fitness sharing}, booktitle = {Foundations of genetic algorithms 3}, pages = {185--224}, editor = {L. Darrell Whitley and Michael D. Vose}, publisher = {Morgan Kaufmann}, address = {San Francisco}, year = {1995}, url = {ftp://ftp-illigal.ge.uiuc.edu/pub/papers/Publications/Mahfoud/popsize.ps.Z} } @inbook{wright:1969, author = {Sewall Wright}, title = {Evolution and the genetics of populations}, volume = {2}, chapter = {13 and 14}, pages = {345--416}, publisher = {University of Chicago Press}, year = {1969}, address = {Chicago} } @article{muehlenbein:schlierkamp-voosen:1993, author = {Heinz M\"{u}hlenbein and Dirk Schlierkamp--Voosen}, title = {The science of breeding and its application to the breeder genetic algorithm ({BGA})}, journal = {Evolutionary Computation}, year = {1993}, volume = {1}, number = {4}, pages = {335--360} } @inproceedings{kubota:etal:1994, author = {Naoyuki Kubota and Toshio Fukuda and Fumiho Arai and Koji Shimojima}, title = {Genetic algorithm with age structure and its application to self-organizing manufacturing system}, booktitle = {Proceedings of the 1994 IEEE Symposium on Emerging Technologies and Factory Automation}, pages = {472--477}, year = {1994} } @inproceedings{lin:etal:1994, author = {Shyh--Chang Lin and William F. Punch and Erik D. Goodman}, title = {Coarse-grain parallel genetic algorithms: Categorization and new approach}, booktitle = {Proceeedings of the Sixth IEEE Symposium on Parallel and Distributed Processing}, year = {1994}, pages = {28--37}, url = {http://isl.cps.msu.edu/GA/papers/GARAGe94-1.ps} } @inproceedings{kargupta:1992, author = {Hillol Kargupta}, title = {Drift, diffusion and {Boltzmann} distribution in simple genetic algorithm}, booktitle = {Proceedings of the workshop on physics and computation}, year = {1992}, publisher = {IEEE Computer Society Press}, address = {Los Alamitos, CA, USA}, pages = {137--145}, url = {ftp://ftp-illigal.ge.uiuc.edu/pub/papers/Publications/Kargupta/drift_diffusion_boltzman.ps.Z} } @inproceedings{mahfoud:1994, author = {Samir Mahfoud}, booktitle = {Proceedings of the first {IEEE} conference on evolutionary computation}, pages = {67--72}, title = {Genetic drift in sharing methods}, year = {1994}, url = {ftp://ftp-illigal.ge.uiuc.edu/pub/papers/Publications/Mahfoud/share.ps.Z} } @inproceedings{harvey:93, author = {Inman Harvey}, booktitle = {Proceedings of the fifth international conference on genetic algorithms}, editor = {Stephanie Forrest}, pages = {15--22}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA, USA}, title = {The Puzzle of the Persistent Question Marks: A Case Study of Genetic Drift}, year = {1993}, url = {ftp://ftp.cogs.susx.ac.uk/pub/reports/csrp/csrp278.ps.Z} } @techreport{asoh:muehlenbein:1994b, author = {H. Asoh and Heinz M\"{u}hlenbein}, title = {On the mean convergence time of genetic populations without selection}, institution = {GMD}, year = {1994}, type = {Technical Report}, number = {94--02--13}, address = {Schloss Birlinghoven, D-53754 Sankt Augustin, Germany}, url = {mailto:muehlen@gmd.de} } @techreport{harvey:etal:1993a, author = {I. Harvey and P. Husbands and D. Cliff}, title = {Genetic Convergence in a Species of Evolved Robot Control Architectures}, institution = {University of Sussex}, year = {1993}, type = {Cognitive Science Research Paper}, number = {278}, address = {School of Cognitive and Computing Sciences, Falmer Brighton BN1 9QH, England, UK}, month = {January}, note = {A poster version of this paper was published as \cite{harvey:etal:1993b}}, url = {ftp://ftp.cogs.susx.ac.uk/pub/reports/csrp/csrp278.ps.Z}, size = {14 pages} } @inproceedings{harvey:etal:1993b, author = {I.~Harvey and P.~Husbands and D.~T.~Cliff}, title = {Genetic Convergence in a Species of Evolved Robot Control Architectures}, booktitle = {Proceedings of the fifth international conference on genetic algorithms}, editor = {Stephanie Forrest}, pages = {636}, publisher = {Morgan Kaufmann}, address = {San Mateo, CA, USA}, year = {1993}, note = {Poster version of \cite{harvey:etal:1993a}} } @techreport{langdon:1995:ppp, author = {William B. Langdon}, title = {Pareto, Population Partitioning, Price and Genetic Programming}, institution = {University College London}, year = {1995}, type = {Research Note}, number = {RN/95/29}, address = {Gower Street, London WC1E 6BT, UK}, month = {April}, note = {Submitted to AAAI Fall 1995 Genetic Programming Symposium}, keywords = {Automatic Programming, Machine Learning, Genetic Programming, Genetic Algorithms, Artificial Evolution, Pareto fitness, Demes}, url = {ftp://cs.ucl.ac.uk/genetic/papers/WBL_aaai-pppGP.ps}, abstract = { A description of a use of Pareto optimality in genetic programming is given and an analogy with Genetic Algorithm fitness niches is drawn. Techniques to either spread the population across many pareto optimal fitness values or to reduce the spread are described. It is speculated that a wide spread may not aid Genetic Programming. It is suggested that this might give useful insight into many GPs whose fitness is composed of several sub-objectives. The successful use of demic populations in GP leads to speculation that smaller evolutionary steps might aid GP in the long run. An example is given where Price's covariance theorem helped when designing a GP fitness function. }, size = {11 pages} } Ted Belding Ted.Belding@umich.edu or streak@engin.umich.edu University of Michigan Program for the Study of Complex Systems http://www-personal.engin.umich.edu/~streak/ ------------------------------ From: Andy.Keane@soton.ac.uk Date: Fri, 14 Jun 1996 09:47:30 +0100 Subject: New Post Doctoral Position We have a new position for a post-doctoral research fellow for three years to work on a project entitled The Integration of Multi-level, Multi-discipline Design Methods with Modern Stochastic Global Optimizers The main goals of the work are :- To assess the practicality of using a variety of different design analysis methods simultaneously with modern stochastic optimizers so as to achieve faster, more reliable and more innovative optimizations of designs. To study prototype tools based on this approach in collaboration with practising design staff (n.b., it is not the intention of this study to produce a commercially viable code, rather the aim is to provide inputs to enable suitable specifications for such software to be developed as the subject of other projects). To assess which optimization strategies best deal with this kind of approach and how to use clusters of workstations to implement them. This research project aims to investigate how multi-level, multi-discipline design methods could be used more efficiently by modern stochastic global optimizers. Key to the proposed approach is the idea of using generational optimization methods where individual members of each generation are calculated using a variety of different design codes in parallel on networks of computers. This would allow the use of stochastic optimizers which require many hundreds of design evaluations on problems where fully detailed analyses can take significant amounts of computer time to evaluate each design, but where simplified, but less accurate, calculations can be performed more readily. The post pays up to 21,500 UK pounds and is funded jointly by the UK EPSRC and British Aerospace. Andy Keane (We also have a studentship available to assist in this area for a suitably qualified graduate.) ------------------------------ From: Dimitris Dracopoulos Date: Fri, 14 Jun 1996 14:19:16 -0600 Subject: Advanced MSc in Neural & Evolutionary Systems (London) The Department of Computer Science, Brunel University, London will run a new advanced MSc in Neural & Evolutionary Systems in 1996/1997. The MSc covers introductory and more advanced material in the areas of neural networks, genetic algorithms, genetic programming, artificial life, parallel computing, etc. The MSc in Neural and Evolutionary Systems is supported by the Centre of Neural and Evolutionary Systems (CNES), in the Department of Computer Science and Information Systems. More information about this MSc can be found in: http://http2.brunel.ac.uk:8080/~csstdcd/NES_Msc.html Applications will be considered until late June (or the latest beginning of July). For application forms please contact: Admissions Secretary Department of Computer Science and Information Systems Brunel University London Uxbridge Middlesex UB8 3PH United Kingdom Telephone: +44 (0)1895 274000 ext. 2394 Fax: +44 (0)1895 251686 Email: cs-msc-courses@brunel.ac.uk Dr Dimitris C. Dracopoulos Department of Computer Science Brunel University Telephone: +44 1895 274000 ext. 2120 London Fax: +44 1895 251686 Uxbridge E-mail: Dimitris.Dracopoulos@brunel.ac.uk Middlesex UB8 3PH United Kingdom ------------------------------ End of Genetic Algorithms Digest ******************************