Genetic Algorithms Digest Thursday, 10 November 1988 Volume 2 : Issue 23 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - Administrivia - GAs for control systems - AI genealogy - GAs for game tree search - Apportionment of credit -------------------------------- Date: Thu, 13 Oct 88 13:34:21 EDT From: GA-List Moderator Subject: Administrivia Two items concerning the administration of GA-List: 1. The list has grown quite large (over 300 addresses). This presents no immediate problem -- in fact, the growth is extremely welcomed -- but it does slow down the process of sending issues out. It would help if organizations that had several members could form local bulletin boards to which I could send a single message. The larger organizations are listed below. If anyone wants to volunteer to organize local bulletin boards, let me know the new address, and who I should remove from my list. domain members --------- -------- bbn.com 15 umich.edu 12 cs.ucla.edu 10 cmu.edu 7 arc.nasa.gov 7 2. Many sites have adopted new names in the process of switching to domain style addresses. If it appears that GA-List is not being sent to the current preferred address, please let me know and I will update our list. A comment: Many of the postings consist of questions about GAs or classifier systems to which the author hopes the community will respond. I notice that answers to these questions are rarely offered, despite the presense of many active researchers on the list. Please take the time to share your experiences with the rest of us, and keep the discussion bi-directional. Thanks. -- John -------------------------------- Date: 13 Oct 88 12:40 EST From: POWELL DAVID J Subject: GAs for control systems I have been working on a program where the user can attach any program (with run times from 1 second to 30 minutes), specify inputs allowed to vary, outputs to be optimized on, parameter constraints, and rules of thumb on which parameters to vary to influence the optimization variables. My program will run the users program to an iterative solution. To date, I have attached a DC-MOTOR program, a turbine design program and a compressor program with mixed results. It is safe to assume that these programs provide a non linear, discontinuous and multi-dimensional domain. The intent of allowing rules of thumb to be added is to quickly prune the design domain. Typically, the designer has a limited deadline ( 2 - 14 days ) and the program cannot exhaust all possibilties. I will follow the experts advice first before trying other types of heuristics. This works very well if the user understands the design domain as I get a lot of gain in optimization quickly. However, it has some severe drawbacks: 1. It does not guarantee a global optimum. 2. It does not learn. It uses the simple rules of thumb of the user but does not combine them into more complex or general rules to speed up the search or to escape a corner that it has forced itself into. Furthermore, the rules are usually based on an understanding of the domain from previous experience with different constraints. Therefore, the experience may or may not be valid for different portions of the domain. 3. If the user has little knowledge then my current heuristics,hill climbing and random search are very inefficient. Inefficiency on day 1 is tolerable if the program can become smarter so that following application runs can be performed more quickly. Recently, I have read about genetic algorithms and Classifier systems. They both seem to have applicability to my problem. John Grefenstette was very kind and sent me a copy of his GENESIS package which I am currently experimenting with and trying to learn about your exciting field of genetics. Two initial questions that I am facing is: 1. How to speed up GA if I have some rules of thumb without forcing the GA to a local optimum? 2. Proper selection of population size and parameter settings. I have also recently read about Classifier systems as described by Holland in Machine Learning and his book on Induction. He seems to address the solution to my problems with his classifier system. Before spending a great deal of time to try an implement a classifier system which may or may not prove successfull, I have asked the computer science community (ARPANET) if there were any classifier systems available for me to try out in order to learn and see if they are as successfull as I hope them to be. One recommendation from Arpanet was to post a mail message on this bulletin board. I realize that the description of my problem is very brief but I would appreciate any suggestions as to possible directions or pitfalls that I may experience before I delve too deeply into this area. If anyone has a Classifier system or other system that addresses my problem or may lead to better insights on a method of solution then I would really appreciate it if you can send it to me. Hopefully, there will be a good response so that I can learn quite a bit and reply back to the genetic community with some better questions and possibly some initial results. My mail address is powell@crd.ge.com. Thank You Dave Powell -------------------------------- Date: Thu, 20 Oct 88 14:15:34 PDT From: rik%cs@ucsd.edu (Rik Belew) Subject: AI genealogy AI GENEALOGY Building an AI family tree Over the past several years we have been developing a collection of bibliographic references to the literature of artificial intelligence and cognitive science. We are also in the process of developing a system, called BIBLIO, to make this information available to researchers over Internet. My initial work was aimed at developing INDEXING methods which would allow access to these citations by appropriate keywords. More recently, we have explored the use of inter-document CITATIONS, made by the author of one document to previous articles, and TAXONOMIC CLASSIFICATIONS, developed by editors and librarians to describe the entire literature. We would now like to augment this database of bibliographic information with "cultural" information, specifically a family tree of the intellectual lineage of the authors. I propose to operationalize this tree in terms of each author's THESIS ADVISOR and COMMITTEE MEMBERS, and also the RESEARCH INSTITUTIONS where they work. It is our thesis that this factual information, in conjuction with bibliographic information about the AI literature, can be used to characterize important intellectual developments within AI, and thereby provide evidence about general processes of scientific discovery. A nice practical consequence is that it will help to make information retrievals from bibliographic databases, using BIBLIO, smarter. I am sending a query out to several EMail lists to ask for your help in this enterprise. If you have a Ph.D. and consider yourself a researcher in AI, I would like you to send me information about where you got your degree, who your advisor and committee members were, and where you have worked since then. Also, please forward this query to any of your colleagues that may not see this mailing list. The specific questions are contained in a brief questionnaire below, and this is followed by an example. I would appreciate it if you could "snip" this (soft copy) questionnaire, fill it in and send back to me intact because this will make my parsing job easier. Also, if you know some of these facts about your advisor (committee members), and their advisors, etc., I would appreciate it if you could send me that information as well. One of my goals is to trace the genealogy of today's researchers back as far as possible, to (for example) participants in the Dartmouth conference of 1956, as well as connections to other disciplines. If you do have any of this information, simply duplicate the questionnaire and fill in a separate copy for each person. Let me anticipate some concerns you may have. First, I apologize for the Ph.D. bias. It is most certainly not meant to suggest that only Ph.D.'s are involved in AI research. Rather, it is a simplification designed to make the notion of "lineage" more precise. Also, be advised that this is very much a not-for-profit operation. The results of this query will be combined (into an "AI family tree") and made publically available as part of our BIBLIO system. If you have any questions, or suggestions, please let me know. Thank you for your help. Richard K. Belew Asst. Professor Computer Science & Engr. Dept. (C-014) Univ. Calif. - San Diego La Jolla, CA 92093 619/534-2601 619/534-5948 (messages) rik%cs@ucsd.edu -------------------------------------------------------------- AI Genealogy questionnaire Please complete and return to: rik%cs@ucsd.edu NAME: Ph.D. year: Ph.D. thesis title: Department: University: Univ. location: Thesis advisor: Advisor's department: Committee member: Member's department: Committee member: Member's department: Committee member: Member's department: Committee member: Member's department: Committee member: Member's department: Committee member: Member's department: Research institution: Inst. location: Dates: Research institution: Inst. location: Dates: Research institution: Inst. location: Dates: -------------------------------------------------------------- AI Genealogy questionnaire EXAMPLE NAME: Richard K. Belew Ph.D. year: 1986 Ph.D. thesis title: Adaptive information retrieval: machine learning in associative networks Department: Computer & Communication Sciences (CCS) University: University of Michigan Univ. location: Ann Arbor, Michigan Thesis advisor: Stephen Kaplan Advisor's department: Psychology Thesis advisor: Paul D. Scott Advisor's department: CCS Committee member: Michael D. Gordon Member's department: Mgmt. Info. Systems - Business School Committee member: John H. Holland Member's department: CCS Committee member: Robert K. Lindsay Member's department: Psychology Research institution: Univ. California - San Diego Computer Science & Engr. Dept. Inst. location La Jolla, CA Dates: 9/1/86 - present -------------------------------- From: pixar!cc@ucbvax.Berkeley.EDU (Charlie Conklin) Received: by golden; 26 OCT 88 13:16:00 PDT Subject: GAs for game tree search I am currently doing some experimentation with different methods of game tree search, and am looking into genetic algorithms as methods to pre-select nodes of the tree. I would like to join the gla mailing list so that I main gain more information about GA's, and maybe come across someone using them in an application similar to my own. My address is below. Charlie Conklin ...!{ucbvax,sun}!pixar!cc -------------------------------- Date: Thu, 27 Oct 88 13:29:49 +0100 From: jvelasco@dit.upm.es (Juan Ramon Velasco Perez) Subject: Apportionment of credit I am a student in the Department of Telematic Engineering at the Madrid University of Technology. I am doing a research in Apportionment of Credit for Genetic Algorithms applied to Machine Learning, and I would like to be added to the "GA-LIST". I would be very please if you can send me some references about Apportionment of Credit (or the name of people who work in this area). With thanks in advance, I remain, Yours sincerely, Juan R. Velasco -------------------------------- End of Genetic Algorithms Digest ********************************