Genetic Algorithms Digest Wednesday, March 13, 1996 Volume 10 : Issue 12 - 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: - Bandit Paper - Announcement and Call for Papers ISFL'97 - giraffes (Re: v10n10) - More giraffes (Re: v10n10) - NFL and the Optimal Universal Search - New Genetic Programming Web Site - One Dimensional Cutting Stock - AID'96 Workshop on Evolutionary Systems in Design ---------------------------------------------------------------------- CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) WEC2 2nd Online Workshop on EC, on the Internet WWW (v10n8) Mar 4-22, 96 CIFEr96 Comp Intelligence for Financial Eng, NY City (v9n53) Mar 24-26, 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 AISB96 Workshop on Evolutionary Computing, Sussex, UK (v9n54) Apr 1-2, 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 ROSYCS Romanian Symposium on Computer Science, Romania (v10n4)May 30-Jun 1,96 EvCA96 Evol Comp and Its Applications, Moscow, Russia (v9n59) Jun 24-27, 96 MENDEL96 2nd Intl Mendel Conference 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 Conference, 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 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: Fri, 1 Mar 96 09:26:10 MST Subject: Bandit Paper I would like to announce a paper that readers of GA-List might find of interest On 2-armed Gaussian Bandits and Optimization W.G. Macready, D.H. Wolpert We explore the 2-armed bandit with Gaussian payoffs as a theoretical model for optimization. We formulate the problem from a Bayesian perspective, and provide the optimal strategy for both 1 and 2 pulls. We present regions of parameter space where a greedy strategy is provably optimal and compare the optimal strategy to a genetic-algorithm-based strategy. In doing so we correct a previous error in the literature concerning the Gaussian bandit problem and the supposed optimality of genetic algorithms for this problem. Finally, we provide an analytically simple bandit model that is more directly applicable to optimization theory than the traditional bandit problem, and determine a near-optimal strategy for that model. This paper is available from http://www.santafe.edu/~wgm/papers.html ------------------------------ From: icsc@freenet.edmonton.ab.ca Date: Tue, 5 Mar 1996 09:48:06 -0700 (MST) Subject: Announcement and Call for Papers ISFL'97 Announcement and Call for Papers Second International ICSC Symposium on FUZZY LOGIC AND APPLICATIONS ISFL'97 To be held at the Swiss Federal Institute of Technology (ETH), Zurich, Switzerland February 12 - 14, 1997 Applications of fuzzy logic have played a significant role in industry, notably in the field of process and plant control, especially in applications where accurate modelling is difficult. The organisers hope that contributions will come not only from this field, but also from newer applications areas, perhaps in business, financial planning management, damage assessment, security, and so on. TOPICS Contributions are sought in areas based on the list below, which is indicative only. Contributions from new application areas will be particularly welcome. - Basic concepts such as various kinds of Fuzzy Sets, Fuzzy Relations, Possibility Theory - Neuro-Fuzzy Systems and Learning - Fuzzy Decision Analysis - Image Analysis with Fuzzy Techniques - Mathematical Aspects such as non-classical logics, Category Theory, Algebra, Topology, Chaos Theory - Modeling, Identification, Control - Robotics - Fuzzy Reasoning, Methodology and Applications, for example in Artificial Intelligence, Expert Systems, Image Processing and Pattern Recognition, Cluster Analysis, Game Theory, Mathematical Programming, Neural Networks, Genetic Algorithms and Evolutionary Computing - Implementation, for example in Engineering, Process Control, Production, Medicine - Design - Damage Assessment - Security - Business, Finance, Management DEADLINES AND REGISTRATION It is the intention of the organisers to have the conference proceedings available for the delegates. Consequently, the deadlines below are to be strictly respected: - Submission of Abstracts: May 31, 1996 - Notification of Acceptance: August 31, 1996 - Delivery of full papers: October 31, 1996 INFORMATION For further information please contact either of the following: - ICSC Canada, P.O. Box 279, Millet, Alberta T0C 1Z0, Canada E-mail: icsc@freenet.edmonton.ab.ca Fax: +1-403-387-4329 Phone: +1-403-387-3546 - ICSC Switzerland, P.O. Box 657, CH-8055 Zurich, Switzerland Fax: +41-1-761-9627 - Prof. Nigel Steele, Chairman ISFL'97, Coventry University, U.K. E-mail: nsteele@coventry.ac.uk Fax: +44-1203-838585 Phone: +44-1203-838568 ------------------------------ From: "Raymond N. Greenwell" Date: Wed, 06 Mar 1996 13:33:04 -0500 Subject: giraffes (Re: v10n10) I gave Paul Darwen's question on giraffe's vocal nerve (GA-List v10n10) to my wife, Karla Harby, a freelance science writer. Her reply is attached below. ************************************************************* Raymond N. Greenwell matrng@hofstra.edu Professor of Mathematics http://www.hofstra.edu/~matrng 103 Hofstra University (516) 463-5573 Hempstead, NY 11550-1090 ************************************************************* This person might be able to get an answer about the giraffe's anatomy by calling his local zoo. I wouldn't assume his giraffe anatomy is correct; it might be, might not be. Even if he's right about the anatomy, it's a big leap from the length of the nerve and the voice box response time/vocal behavior of the animal. After all, giraffes run really, really fast, and their feet are even further away from their brains than their larynxes, and somehow they can do it. How? Nerve signals are chemical and electrical in nature, not mechanical, which makes them very, very fast. Many species with short necks are relatively or completely silent. And I especially question his assumption that this is an example of an inefficiency in evolution. There may be some advantage to this long nerve that we humans have yet to discover. What other functions does this nerve control? Is it better shielded from attacks by lions than it otherwise would be? Such questions deserve consideration before drawing conclusions. ------------------------------ From: rogoldthwaite@ucdavis.edu (Ron Goldthwaite) Date: Wed, 6 Mar 1996 20:36:24 -0800 Subject: More giraffes (Re: v10n10) I've no direct citation for the recurrent laryngeal nerve in giraffes but it's basic vetebrate anatomy as noted by a couple of trustworthy tertiary sources: 1. Mark Ridley's 1993 text, EVOLUTION, pages 50 and 343, mentions it as an example of ancient homology. In modern fish (and presumably in the ancestral form which led to fish and then mammals, tho I don't know if anyone's looked at the "living fossil" lungfish and Port Jackson shark) the cranial nerve involved also goes around the dorsal aorta, but this is clearly the most direct route to their fifth gill slit. This topology has been preserved in all mammals tho the nerve (still identifiable as the fourth vagus) now serves the larynx, and in giraffes (and camels, et al) results in the clearly non-optimal loop about the extended neck. Ridley gives diagrams (p.344). 2. Richard Dawkins' 1982 EXTENDED PHENOTYPE mentions it as a 'historical constraint' with similar examples. Dawkins notes his familiarity with the giraffe example as due to Prof. J. D. Currey, but no citation is provided nor could I find one using Melvyl's journal databases. Dawkins also mentions as examples of historical constraint the krufty way in which flatfish eyes are twisted about to their new orientation, and the retinal organization of mammalian eyes generally (with the photocell layer _under_ the semi-transparent wiring layer). Of course both Dawkins and Ridley were once grad students (as was I), but Dawkins studied under Niko Tinbergen and Ridley under Dawkins, so there you go. I also found further examples of historical constraint at this web page: http://wcl-l.bham.ac.uk/origins/faqs/jury-rigged.html In a shameless bit of puffery, I'll note there's a discussion of historical constraints in neural organization in Coss & Goldthwaite 1995, "The Persistence of Old Designs for Perception", pps 83-148 of PERSPECTIVES IN ETHOLOGY, Volume 11, with several other chapters on the theme of behavioral design and its constraints. Hopefully helpfully, Ron G ====== Evidence for Jury-Rigged Design in Nature Chris Colby and others (colby@bu-bio.bu.edu) This is a post that presents evidence to back up my claim that there is evidence of jury-rigged design in nature. The first part is mine, the rest is assembled from contributions of others. This is extremely long, but interesting (IMHO). I just sort of collected all the posts below mine and I don't have the others permission to post them. But, I would suspect they don't mind (or they wouldn't have posted it in the first place. In any case, I'd like to thank all the contributors to this almost Meritt-like gargantuan post. (Loren Petrich, Matt Wiener, Herb Huston, Paul Keck and Keith Doyle) Many organisms show features of appallingly bad design. This is because evolution via natural selection cannot construct traits from scratch; new traits must be modifications of previously existing traits. This is called historical constraint. A few examples of bad design imposed by historical constraint: In parthenogenetic lizards of the genus Cnenidophorus, only females exist. Fertility in these lizards is increased when another lizard engages in pseudo male behavior and attempts to copulate with the first lizard. These lizards evolved from a sexual species so this behaviour makes some sense. The hormones for reproduction were likely originally stimulated by sexual behaviour. Now, although they are parthenogenetic, simulated sexual behaviour increases fertility. Fake sex in a parthenogenetic species doesn't sound like good design to me. In African locust, the nerve cells that connect to the wings originate in the abdomen, even though the wings are in the thorax. This strange "wiring" is the result of the abdomen nerves being co-opted for use in flight. A good designer would not have flight nerves travel down the ventral nerve cord past their target, then backtrack through the organism to where they are needed. Using more materials than necessary is not good design. In human males, the urethra passes right through the prostate gland, a gland very prone to infection and subsequent enlargement. This blocks the urethra and is a very common medical problem in males. Putting a collapsible tube through an organ that is very likely to expand and block flow in this tube is not good design. Any moron with half a brain (or less) could design male "plumbing" better. Perhaps one of the most famous examples of how evolution does not produced designed, but "jury-rigged" traits is the panda's thumb. If you count the digits on a panda's paw you will count six. Five curl around and the "thumb" is an opposable digit. The five fingers are made of the same bones our (humans and most other vertebrates) fingers are made of. The thumb is constructed by enlarging a few bones that form the wrist in other species. The muscles that operate it are "rerouted" muscles present in the hand of vertebrates (see S.J. Gould book "The Panda's Thumb" for an engaging discussion of this case). Again, this is not good design. R. Goldthwaite, PhD Psychology and Ethology | Career trajectory: from Dept. Psychology, U.California |Artifical Intelligence (AI), Davis, CA 95616 (916) 752 5655/1880 |to Natural Stupidities (NS). rogoldthwaite@ucdavis.edu ------------------------------ From: G Bilchev Date: Fri, 8 Mar 1996 22:32:37 GMT Subject: NFL and the Optimal Universal Search Previous discussions on the NFL topic reached several deadlocks. The purpose of this posting is to attempt to "resolve" one of them: Deadlock: Recall that initially the NFL theorem was rigorously proved for uniform distribution P(f) of fitness functions. The reason why a uniform distribution was selected, was said to be that it was a "typical" distribution. Such a (mis)justification caused much debate and most of the objections were resolved, as far as I am concerned, by the authors. Most, except one. This objection (produced by J. Kingdon) was that the so called "holy grail" is actually forbidden by the NFL theorem, because any such super search algorithm for uniform P(f) is equal on average to random search (or any other search) by the NFLT. So far, I am not aware of an explanation by the authors which satisfactory resolves this contradiction (i.e. the existence of the super search algorithm). At first glance it seems that the Optimal Universal Search Algorithm (OUSA) is forbidden by the NFLT. The Optimal Universal Search Algorithm (OUSA): About 25 years ago the OUSA was defined by Levin. It was defined w.r.t. the so called a priori distribution (defined in terms of Kolmogorov complexity). The algorithm basically works by generating solutions in increasing order of their Kolmogorov complexity. The rationale behind this algorithm is that the probability to guess any program that produces a given solution and stops is essentially equal to the probability to guess the shortest such program. Unfortunately, due to the uncomputability of the Kolmogorov complexity the OUSA is not computable. According to the NFLT the only way to make an algorithm faster on a given set of functions is to make it slower on others. This is exactly what the OUSA does: it specializes to problems with low Kolmogorov complexity and has slower performance for problems with high Kolmogorov complexity. Therefore, there is no contradiction in both results. Conclusions: The current interpretation of the "practical" implications of the NFLT shifted attention towards the question which are the distributions for which the NFLT holds. At the same time the issues of how the NFL result fits into complexity theory were completely disregarded. I hope to have convinced at least some of you that complexity issues are actually very important. Best regards, George Bilchev ------------------------------ From: jjf@mickey.jsc.nasa.gov Date: Sun, 10 Mar 1996 12:27:55 -0600 Subject: New Genetic Programming Web Site I have created a new genetic programming web site. Its address is: http://tommy.jsc.nasa.gov/~jjf/gp/ If you have any problems with that URL you can also try: http://www.owlnet.rice.edu/~jjf/gp/ http://www.ecisa.com/users/jjf/www/gp/ Originally this site started as my own hotlist of GP related sites. But, lately word got out and I have received a lot email about it so I have decided to make it public. This site contains every URL related to GP that I know. Most of the URLs come for the GP-mail-list and other mail lists, and the rest come from searching the different web search engines. It is divided in the following categories: Other GP Related Sites People Working on GP Research Groups Working on GP GP Related Conferences GP Related Calls for Papers GP Related Papers GP Software GP Bibliographies GP Miscellaneous URLs Genetic Algorithms Artificial Intelligence Happy surfing, Jaime Fernandez Jaime Fernandez Jr. NASA Robotics & AI Scientist Metrica, Inc. Personal mail: jjf@caesar.rice.edu Work mail: jjf@mickey.jsc.nasa.gov Mail alias: j.j.fernandez@ieee.org Personal WWW Pages: http://www.owlnet.rice.edu/~jjf/ http://www.ecisa.com/users/jjf/www/ Castles WWW Pages: http://www.ecisa.com/users/jjf/www/castles/ http://www.owlnet.rice.edu/~jjf/castles/ Genetic Programming: http://tommy.jsc.nasa.gov/~jjf/gp/ http://www.owlnet.rice.edu/~jjf/gp/ http://www.ecisa.com/users/jjf/www/gp/ ------------------------------ From: osman alp Date: Tue, 12 Mar 1996 11:19:14 +0300 (MEST) Subject: One Dimensional Cutting Stock Hi everybody, we are studying on the solution of one dimensional cutting stock problem by genetic algorithms. we need some test problems to analyze the performance of our formulation. we would be very thankful if anyone can help us? Osman Alp Tolga Tufekci alpo@rorqual.cc.metu.edu.tr atol@rorqual.cc.metu.edu.tr ------------------------------ From: Walter Hower Date: Tue, 12 Mar 1996 13:20:10 GMT Subject: AID'96 Workshop on Evolutionary Systems in Design Cfp via: http://www.arch.su.edu.au/~josiah/ESinD.html Kind regards - Walter Hower Department of Computer Science University College Cork National University of Ireland Western Rd Cork Republic of Ireland ------------------------------ End of Genetic Algorithms Digest ******************************