Genetic Algorithms Digest Thursday, May 2, 1996 Volume 10 : Issue 19 - 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: - EP97--Sixth Annual Conference on Evolutionary Programming - Graduate Research Assistantship at Los Alamos National Laboratory - who invented GP? ---------------------------------------------------------------------- CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) 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 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 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 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 ICANNGA97 Intl Conf on Artificial NNs and GAs, England (v10n16) Apr 1-4, 97 EP97 Conference 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: fogel@ece.ucsd.edu (Fogel) Date: Thu, 25 Apr 96 22:09:51 PDT Subject: EP97--Sixth Annual Conference on Evolutionary Programming Dear Colleagues, I'm posting this on behalf of John McDonnell. Please follow up with Pete Angeline (pja@lfs.loral.com), Bob Reynolds (reynolds@cs.wayne.edu), or John McDonnell (mcdonn@cod.nosc.mil) for further information. If I can be of any help just let me know. Regards, David === CALL FOR PAPERS EP97 -- THE SIXTH ANNUAL CONFERENCE ON EVOLUTIONARY PROGRAMMING SPONSORED BY THE EVOLUTIONARY PROGRAMMING SOCIETY April 13-16, 1997 University Palace Hotel and Conference Center Indianapolis, IN, USA Expected to be in Conjunction with IEEE ICEC'97 General Chairman: Peter J. Angeline, Lockheed Martin Federal Systems Technical Co-Chairmen: Robert G. Reynolds, Wayne State University John R. McDonnell, San Diego State University The Sixth Annual Conference on Evolutionary Programming will serve as a forum for researchers investigating applications and theory of evolutionary programming and other related areas in evolutionary and natural computation. Authors are invited to submit papers which describe original, unpublished research in evolutionary programming, evolution strategies, genetic algorithms, genetic programming, artificial life, cultural algorithms, and other models that rely on evolutionary principles. Specific topics include, but are not limited to, the use of evolutionary simulations in optimization, neural network and filter design, automatic control, image processing and computer graphics. Other topics of interest include mathematical theory or empirical analysis providing insight into the behavior of evolutionary algorithms. Of particular interest are applications of simulated evolution to problems in biology and operations research. Hard copies of manuscripts must be received by Sept. 15, 1996. Electronic submissions will not be accepted. Papers should be clear, concise, and written in English. Papers received after the deadline will be handled on a time- and space-available basis. Submissions should be single-spaced, 12-point font, and should not exceed 15 pages including figures and references. To encourage student participation, a $500 student prize will be awarded at the conference for the best student submission. In order to be considered for the student prize, the principle author must be a student in good standing and the paper must be clearly marked as a student submission. The notification of the program committee's review decisions will be mailed by Nov. 15, 1996. Camera-ready papers are due Jan. 6, 1997 for inclusion in the proceedings that will be distributed at the conference. Send five (5) copies of the complete paper to Robert G. Reynolds Dept. of Computer Science Wayne State University 431 State Hall Detroit, MI 48202 reynolds@cs.wayne.edu SUMMARY OF IMPORTANT DATES September 15, 1996 Submission of papers due November 15, 1996 Notification sent to authors January 6, 1997 Final submissions for published proceedings ------------------------------ From: Hillol Kargupta Date: Fri, 26 Apr 1996 01:02:29 -0600 Subject: Graduate Research Assistantship at Los Alamos National Laboratory I am looking for a graduate student to work on gene expression messy genetic algorithms, its parallel implementation and machine learning applications. The opening is immediate. The selected person will have to work at Los Alamos National Laboratory, NM, USA over the summer. However, ideally I would like him/her to stay for a longer period. Los Alamos is located in the mountains of New Mexico, surrounded by canyons and woods. We pay 25-32K/year for graduate research assistants. If interested please send me your resume as soon as possible. Hillol Kargupta Computational Methods Group X Division, Mail Stop F645 Los Alamos National Laboratory Los Alamos, NM 87545 (505) 667-8945 (505) 665-4479 (FAX.) email: hillol@lanl.gov ------------------------------ From: juergen@idsia.ch (Juergen Schmidhuber) Date: Wed, 1 May 96 19:30:38 +0200 Subject: who invented GP? A while ago, I asked: who ``invented'' Genetic Programming (GP)? I got quite a few responses. Some of them lead to additional, interesting questions. Below a somewhat redundant compendium. ======== Extracted from original message: From Juergen Schmidhuber juergen@idsia.ch @misc{DSW87, author = {D. Dickmanns and J. Schmidhuber and A. Winklhofer}, title = {{ Der genetische Algorithmus: Eine Implementierung in Prolog. Fortgeschrittenenpraktikum, Institut f\"{u}r Informatik, Lehrstuhl Prof. Radig, Technische Universit\"{a}t M\"{u}nchen}}, year = {1987}} The authors (all undergrads back then) used a GA to evolve general, assembler-like programs (with loops etc.). The system was implemented in PROLOG. It was applied to simple tasks, including the ``lawnmower problem'' (later also studied by J. Koza, 1994). ======== Moderator's note: Holland mentions using a GA to learn programs: (Adaptation in natural and artificial systems. The University of Michigan Press, 1975). Steve Smith learned simple variable length rule-based programs (I believe) in his LS-1 system: (Flexible learning of problem solving heuristics through adaptive search. Proceedings of the Eighth Int'l Joint Conf on AI, pp. 422 - 425, 1983). I believe that John Koza's GP was at least partially inspired by the work of Cory Fujiki and John Dickinson: (Using the Genetic Algorithm to Generate Lisp Source Code to Solve the Prisoner's Dilemma. 1987 Int'l Conf on GAs, pp. 236-240). Also see Cory's masters thesis: (An Evaluation of Holland's Genetic Operators Applied to a Program Generator, Dept of CS, Univ of Idaho, 1986). ======== Response to moderator's note: From: John Dickinson The work of Cory Fujiki was built upon the work of Joe Hicklin. (Application of the Genetic Algorithm to Automatic Program Generation, MSCS Thesis, Dept of CS, Univ of Idaho, 1986). The work of Hicklin and Fujiki both built Lisp Cond expressions. At the time some viewed these as simply classifier systems similar to those being built by Goldberg, but I think they were some of the first use of variable length, source code generating GAs. ========= From: Jeremy Fisher Jeremy_Fisher@sandwich.pfizer.com This is really vague BUT ... I _think_ that some work was done at IBM in the early 1960s (1964?) on trying to generate simple programs (eg sort) by a primitive technique using randomly generated programs. I don't know of any papers about it however. I seem to remember that the technique failed. Perhaps this was because there was no fitness function or the fitness function was too simple. (The views expressed are my own and do not necessarily reflect those of my employer). ======= From: Inman Harvey The earliest paper I am aware of which introduces the basic ideas later taken up in Koza's GP is: @inproceedings{Cramer:85, author = "Cramer, N. L.", title = "A Representation for the Adaptive Generation of Simple Sequential Programs", booktitle = "Proceedings of an International Conference on Genetic Algorithms and Their Applications", editor = "Grefenstette, J.J.", publisher = {Lawrence Erlbaum Associates}, address = {Hillsdale NJ}, year = "1985" } This paper from the very first 1985 GA Conference allows for the evolution of programs of arbitrary length. It utilises the tree-like nature of programs to introduce the sub-tree recombination operator later used by Koza. It also proposes the evaluation scheme of testing candidate programs against a suite of input/output pairs, with a time-out for functions that run for a long time without halting. Since hearing the rumour that some aspects of Koza's GP are patented, I have always been curious as to what claims were made there that were not predated by Cramer 1985. I understand that quite a few of the early pioneers of computing had an interest in evolutionary approaches to producing programs; including Alan Turing himself, e.g. in @article{Turing:50, author = {A. M. Turing}, title = {Computing Machinery and Intelligence}, journal = {Mind}, month = oct, number = {2236}, pages = {433--460}, volume = {LIX}, year = {1950} } However I get the impression that though there were early attempts in the 1950s, none were successful and hence no papers were published. It will be interesting if your survey does unearth some recorded early work. ====== Follow-up message by Inman Harvey: Spurred by your enquiry, a colleague and I just downloaded from the Internet the abstract of the relevant patent. It does indeed cite an explicit reference to Cramer 1985, among others. I append the relevant information. The abstract seems to cover the whole of GAs. My curiosity remains as to what was claimed that was not predated by other work, from before the filing date of May 20 1988. I am not sure yet if we can get the whole patent over the Internet. United States Patent 4,935,877 Koza Jun. 19, 1990 Non-linear genetic algorithms for solving problems Inventors: Koza; John R. (2961 Industrial Rd. - No. 612, Las Vegas, NV 89109). Appl. No.: 196,973 Filed: May 20, 1988 Intl. Cl.: G06F 15/18 U.S. Cl.: 364/513; 364/200; 364/274 Field of Search: 364/513, 200, 274; 382/14, 15 References Cited U.S. Patent Documents 4,479,241 Oct., 1984 Buekley 364/513 4,675,829 Jun., 1987 Clemenson 364/513 4,697,242 Sept., 1987 Holland et al. 364/513 4,821,333 Apr., 1989 Gillies 382/ 41 Other References Cramer, Nichael Lynn, "A Representation for the Adaptive Generation of Simple Sequential Programs", Grefenstette: Proceedings of First Internaional Conference on Genetic Algorithms, 1985. DeJong, Kenneth, "On Using Genetic Algorithms to Search Program Spaces", Grefenstette: Proceedings of Second International Conference on Genetic Algorithms, 1987. Fujiki, Cory and Dickinson, John, "Using the Genetic Algorithm to Generate Lisp Source Code to Solve the Prisoner's Dilemma", Grefenstette: Proceedings of Second International Conference on Genetic Algorithms, 1987. Dress, W. B., "Darwinian Optimization of Synthetic Neural Systems", IEEE First International Conference on Neural Networks, San Diego, Jun. 1987, vol. No. 3, pp. 769-775. Fujiki, C. and Dickinson, J., Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Cambridge, U.S.A., Jul. 1987, pp. 236-240. Sannier, A. V. and Goodman, E. D., Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, Cambridge, U.S.A., Jul. 1987, pp. 162-169. Grefenstette, John J. (Editor)-Proceedings of an International Conference on Genetic Algorithms and Their Applications, Pittsburgh 1985. Grefenstette, John J.(Editor)-Genetic Algorithms and Their Applications; Proceedings of the Second International Conference on Genetic Algorithms, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1987. Hicklin, Joseph F.-Application of the Genetic Algorithm to Automatic Program Generation, Master of Science Thesis, Department of Computer Science, University of Idaho, 1986. Holland, John H.-Adaptation in Natural and Artificial Systems; The University of Michigan Press, Ann Arbor, 1975. Holland, J. H., and Reitman, J. S. (1978), Cognitive Systems Based on Adaptive Algorithms, in D. A. Waterman and F. Hayes-Roth (Eds.), Pattern Directed Inference Systems (pp. 313-329), New York: Academic Press. Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D.B. The Traveling Salesman Problem, John Wiley & Sons, New York, 1986. Primary Examiner: Lastova; John R. Attorney, Agent or Firm: Blakely, Sokoloff, Taylor & Zafman Abstract The present invention is a non-linear genetic algorithm for problem solving. The iterative process of the present invention operates on a population of problem solving entities. First, the activated entities perform, producing results. Then the results are assigned values and associated with the producing entity. Next, entities having relatively high associated values are selected. The selected entities perform either crossover, reproduction, or permutation operations. Lastly, the newly created entities are added to the population. 44 Claims, 13 Drawing Figures ====== Similar information was provided by Patrik D'haeseleer patrik@cs.unm.edu For what it's worth, here's the list of references from Koza's patent application (available at http://patents.cnidr.org:4242/access/access.html): ....... ======= From: Stephen.Smith@ISL1.RI.CMU.EDU Juergen, In my PhD Thesis (1980) I developed a system that evolved simple rule-based programs that could consist of a variable number of rules. Programs were evolved (learned) to (1) perform a maze learning task and (2) make bet deciisions in a game of draw poker. Some theoretical work was also done here, confirming that the schema theorem continues to make sense in the case of variable length individuals, and clarifying tendencies for growth in the average length of individuals over time. To my knowledge, there was no earlier work in evolving variable length individuals. S.F. Smith, A Learning System Based on Genetic Adaptive Algorithms, Ph.D. Thesis, Computer Science Dept., University of Pittsburgh, Dec. 1980. summary paper: S.F. Smith, Flexible Learning of Problem Solving Heuristics Through Adaptive Search, Proceedings IJCAI 83, Karlsruhe, August, 1983. ======== From: "Peter J. Angeline" Juergen, There are two papers that are generally considered to be the origins of GP. The first by N. Cramer entitled "A representation for the adaptive generation of simple sequential programs" appears in the 1985 GA conference. The second, by C. Fujiko and J. Dickson entitled "Using the genetic algorithm to generate LISP source code to solve the prisoner's dilema" appears in the 1987 GA conference. There are a few others that are referenced in Koza's first book that you also might be interested in. Excerpt from Peter's follow-up message: And I should be clear. The Cramer and Fujiko&Dickson articles are not GP as defined by Koza, they are more basic efforts but together contain 95% of the ideas in Koza's GP. ======= From: Eric Siegel One crucial reference is missing from the previous message: it was Nichael Cramer who first applied a genetic algorithm to the tree representation (with the subtree-swapping crossover operation). Cramer, Nichael Lynn, 1985. A Representation for the Adpative Generation of Simple Sequential Programs International Conference on Genetic Algorithms and their Applications [ICGA95], CMU, Pittsburgh. -Eric Siegel ======== From: Jarmo Alander Our anonymous ftp-server (ftp.uwasa.fi) has directory cs/report94-1, which contains a set of indexed genetic algorithm bibliographies. The files are in compressed PostScript and updated every now and then. One of the files called gaGPbib.ps.Z contains references to genetic programming stating from year 1981. Do not hesitate to ask for further details. The directory has README-file containing some more info. ======= From: Dev Prabhu I think N. Cramer's research reported in ICGA-87 is (at the least, one of) the seminal contributions to "GP". He used a tree-structured chromosome and genetic operators suitable for such representation. I am sure there are many other previous contributions if you are looking for "variable-length chromosomes" rather than "tree-structured chromosomes". ========= SUMMARY: it seems that the earliest relevant papers are Smith's (1980, 1983), Cramer's (1985), and Hicklin's (1986). I should mention, however, that I haven't had time to obtain copies of these papers (the moderator encouraged me to send my compendium today). Perhaps there are subtle reasons why some people might consider some of these papers as ``real GP'' papers and others not. So I am still not sure who is the real creator of the field. I'd appreciate messages providing further insight, also concerning patent issues (see Inman Harvey's messages). Again, I'll compile a list and post it to this forum. Thanks to all who responded! Juergen Juergen Schmidhuber research director IDSIA, Corso Elvezia 36, 6900-Lugano, Switzerland juergen@idsia.ch http://www.idsia.ch/~juergen [ WMS: I encouraged the submission because I will be unable to do GA-List for a couple of weeks and I didn't want to delay the submissions from David and Hillol (sending out short GA-List issues is not efficient). I'll be happy to post any further information on this topic. ] ------------------------------ End of Genetic Algorithms Digest ******************************