Genetic Algorithms Digest Thursday, May 11, 1995 Volume 9 : Issue 29 - 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: - GA's and Distributed Decision Making - Maximum Likelihood Estimators - distributed GA paper available - Adaptive Recombination Paper Available - ICGA95 papers available - Technical Reports Available for ftp. - Dissertation available for ftp - Info request - workshop announcement ---------------------------------------------------------------------- ******************************************************************************* CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) CSCS10 10th Intl Conf on CONTROL SYSTEMS & CS, Romania (v8n37) May 24-26, 95 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 95 GWIC95 Golden West Intl Conf on Intell Systems, San Fran(v8n49) Jun 12-14, 95 ML95 GP Workshop: Theory to real-world applications, CA (v9n8) Jul 9, 95 AAICG95 Symposium on Appl of AI in Geophysics, Boulder, CO (v8n39) Jul 12, 95 ICGA-95 Sixth Intl Conference on GAs, Pittsburgh PA (v8n32) Jul 15-20, 95 PASE95 Wrkshp Parallel Appl in Stat and Econ, Trier (v8n39) Aug 29-Sep 2, 95 EA95 Evolution Artificielle, Telecom Bretagne, Brest, Fr (v9n1) Sep 4-8, 95 GALESIA'95 GAs in Eng Systems, Univ of Sheffield, UK (v8n45) Sep 12-14, 95 AIPetro95 AI in the Petroleum Ind, Lillehammer, Norway (v8n48) Sep 13-15, 95 ASI-AA-95 Practice and Future of Autonomous Agents (v8n19) Sep 23-Oct 1, 95 MENDEL95 130th Anniversary of Mendels Laws, Brno, Czech (v9n28) Sep 26-28, 95 Towards Evolvable Hardware Intl Wrkshp, Lausanne, Switz (v9n29) Oct 2-3, 95 SOCO95 Soft Computing Fuzzy Logic, NNs and GAs, Rochester(v9n5) Oct 24-27, 95 Genetic Methods for Routing & Scheduling, New Orleans(v8n50) Oct 29-Nov 1, 95 AAAI GP Symposium (Fall Series), Cambridge, MA (v8n43) Nov 10-12, 95 IEEE Wrkshp on Natural Algorithms in Signal Proc, Essex (v9n7) Nov 12-14, 95 WWW'95 on Fuzzy Logic and NNs/Evol Comp, Nagoya, Japan (v9n6) Nov 14-15, 95 ICEC'95 IEEE Intl Conf on Evol. Computing, Perth (v8n36) Nov 29-Dec 1, 95 EUROGEN95 GAs and ESs in Computational Sci & Eng, Spain (v9n15) Dec 4-8, 95 EP96 5th Conf on Evol Programming, San Diego, CA (v9n18) Feb 29-Mar 3, 96 ACEDC96 Adaptive Computing in Eng. Design & Control, UK (v9n28) Mar 26-28, 96 ICEC'96 IEEE Intl Conf on Evol Comp, Nagoya, Japan (v9n18) May 20-22, 96 GP96 Genetic Programming Conference, Stanford, CA (v9n9) Jul 28-31, 96 PPSN 96 Parallel Problem Solving from Nature, Berlin (v9n17) Sep 22-27, 96 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ******************************************************************************* ------------------------------ From: Ioannis Androulakis Date: Mon, 8 May 1995 00:13:13 -0500 (EDT) Subject: GA's and Distributed Decision Making Greetings ! I am looking for references on GA's and Distributed Decision Making. Some time ago I came across a paper entitled "Applications of GA's for distributed decision making" All I remember is that it was presented some time in 1992, at a Control Systems Conference of the American Society of Mechanical Engineers - Dynamic Systems Control Division. The help of any one out there knows where I could get a preprint of this, or of any related paper, would be greatly appreiated. Thank you, yannis Yannis P. Androulakis androula@titan.princeton.edu ------------------------------ From: Alan Olinsky Date: Mon, 8 May 1995 15:15:33 -0400 (EDT) Subject: Maximum Likelihood Estimators I would appreciate any information or references that may be available regarding the use of genetic algorithms in the convergence of maximum likelihood estimators. Thank you. Alan Alan Olinsky Bryant College Smithfield, RI 02917 (401) 232-6266 ------------------------------ From: Ted.Belding@umich.edu (Theodore C. Belding) Date: Fri, 5 May 1995 13:32:19 -0400 Subject: distributed GA paper available The following paper is available over WWW, ftp, email, or AFS: The Distributed Genetic Algorithm Revisited Theodore C. Belding Division of Computer Science and Engineering University of Michigan To appear in: Eshelman, D. (Ed.) (1995). Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, CA: Morgan Kaufmann. Abstract This paper extends previous work done by Tanese on the distributed genetic algorithm (DGA). Tanese found that the DGA outperformed the canonical serial genetic algorithm (CGA) on a class of difficult, randomly-generated Walsh polynomials. This left open the question of whether the DGA would have similar success on functions that were more amenable to optimization by the CGA. In this work, experiments were done to compare the DGA's performance on the Royal Road class of fitness functions to that of the CGA. Besides achieving superlinear speedup on KSR parallel computers, the DGA again outperformed the CGA on the functions R3 and R4 with regard to the metrics of best fitness, average fitness, and number of times the optimum was reached. Its performance on R1 and R2 was comparable to that of the CGA. The effect of varying the DGA's migration parameters was also investigated. The results of the experiments are presented and discussed, and suggestions for future research are made. WWW: http://www.engin.umich.edu/~streak/dga.html (8 pp, 3.1 MB) or http://xyz.lanl.gov/ (uuencoded, gnuzipped PostScript, 914 KB) ftp (uuencoded, gnuzipped PostScript): ftp://xyz.lanl.gov/nlin-sys/adap-org/papers/9504/9504007 (914 KB) AFS: /afs/umich.edu/user/s/t/streak/Public/dga-revisited.ps.Z (1 MB) or /afs/umich.edu/user/s/t/streak/Public/dga-revisited.ps.gz (660 KB) email (uuencoded, gnuzipped PostScript, 914 KB): send mail to with the subject: get 9504007 or with the subject: cget 9504007 (the second command will chop the file into 100 KB blocks) -- Ted Belding Ted.Belding@umich.edu or streak@engin.umich.edu University of Michigan Division of Computer Science and Engineering "And the dance goes on regardless till/You're carried from the floor" - Fish ------------------------------ From: spears@AIC.NRL.Navy.Mil (William M. Spears) Date: Mon, 8 May 95 17:10:17 EDT Subject: Adaptive Recombination Paper Available Hello. Given that there is increased interest in adaptive operators (especially adaptive recombination) in EAs lately, I thought some of you might be interested in the following paper by myself, presented at the 1995 Evolutionary Programming Conference: Title: Adapting Crossover in Evolutionary Algorithms Abstract: One of the issues in evolutionary algorithms (EAs) is the relative importance of two search operators: mutation and crossover. Genetic algorithms (GAs) and genetic programming (GP) stress the role of crossover, while evolutionary programming (EP) and evolution strategies (ESs) stress the role of mutation. The existence of many different forms of crossover further complicates the issue. Despite theoretical analysis, it appears difficult to decide a priori which form of crossover to use, or even if crossover should be used at all. One possible solution to this difficulty is to have the EA be self-adaptive, i.e., to have the EA dynamically modify which forms of crossover to use and how often to use them, as it solves a problem. This paper describes an adaptive mechanism for controlling the use of crossover in an EA and explores the behavior of this mechanism in a number of different situations. An improvement to the adaptive mechanism is then presented. Surprisingly this improvement can also be used to enhance performance in a non-adaptive EA. The paper is available from ftp.aic.nrl.navy.mil under pub/spears/ep95.ps or from http://www.aic.nrl.navy.mil/~spears The FTP site should work ok - let me know if the Web link gives you a problem. Thanks. Bill ------------------------------ From: terry@santafe.edu Date: Wed, 10 May 95 08:09:36 MDT Subject: ICGA95 papers available These papers will be presented in July at the Sixth International Conference on Genetic Algorithms in Pittsburgh. They are available for ftp from ftp.santafe.edu in pub/terry/fdc.ps.gz and pub/terry/ch.ps.gz. Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms Terry Jones Stephanie Forrest Santa Fe Institute Department of Computer Science 1399 Hyde Park Road University of New Mexico Santa Fe, NM 87501, USA Albuquerque, NM 87131, USA terry@santafe.edu forrest@cs.unm.edu ABSTRACT A measure of search difficulty, fitness distance correlation (FDC), is introduced and examined in relation to genetic algorithm (GA) performance. In many cases, this correlation can be used to predict the performance of a GA on problems with known global maxima. It correctly classifies easy deceptive problems as easy and difficult non-deceptive problems as difficult, indicates when Gray coding will prove better than binary coding, and is consistent with the surprises encountered when GAs were used on the Tanese and royal road functions. The FDC measure is a consequence of an investigation into the connection between GAs and heuristic search. === Crossover, Macromutation, and Population-based Search Terry Jones Santa Fe Institute 1399 Hyde Park Road Santa Fe, NM 87501, USA terry@santafe.edu ABSTRACT A major reason for the maintenance of a population in a Genetic Algorithm (GA) is the hope of increased performance via direct communication of information between individuals. This communication is achieved through the use of a crossover operator. If crossover is not a useful method for this exchange, the GA may not, on average, perform any better than a variety of simpler algorithms that are not population-based. A simple method for testing the usefulness of crossover for a particular problem instance is presented. This allows the identification of situations in which crossover is apparently useful but is actually only producing gains that could be obtained, or exceeded, with macromutation and no population. Terry Jones (terry@santafe.edu). ------------------------------ From: terry@santafe.edu Date: Wed, 10 May 95 08:11:22 MDT Subject: Technical Reports Available for ftp. The following technical reports are now available via anonymous ftp. Both of these were rejected by conferences (ML and IJCAI respectively). Caveat Emptor. These can also be obtained by sending mail to mat@santafe.edu. Terry Jones (terry@santafe.edu). ================= One Operator, One Landscape Terry Jones Santa Fe Institute 1399 Hyde Park Road Santa Fe, NM 87501, USA terry@santafe.edu ABSTRACT The use of the term "landscape" is increasing rapidly in the field of evolutionary computation, yet in many cases it remains poorly, if at all, defined. This situation has perhaps developed because everyone grasps the imagery immediately, and the questions that would be asked of a less evocative term do not get asked. This paper presents an important consequence of a new model of landscapes. The model is general enough to encompass most of what computer scientists would call search, though it is not restricted to either the field or the viewpoint. The consequence is a "one-operator, one-landscape" view of search algorithms that is particularly relevant for algorithms that search via the use of multiple operators, and hence to genetic algorithms and other members of the evolutionary computing family. Crossover and selection landscapes are presented as siblings of the traditional mutation landscape. The model encourages a perspective on search algorithms that makes a clear division between landscape structures and navigation upon them. The model also establishes a strong connection with the heuristic state space search algorithms of Artificial Intelligence. 15 pages. FTP: ftp.santafe.edu:pub/terry/oool.ps.gz ================== Genetic Algorithms and Heuristic Search Terry Jones Stephanie Forrest Santa Fe Institute Department of Computer Science 1399 Hyde Park Road University of New Mexico Santa Fe, NM 87501, USA Albuquerque, NM 87131, USA terry@santafe.edu forrest@cs.unm.edu ABSTRACT Genetic algorithms (GAs) and heuristic search are shown to be structurally similar. The strength of the correspondence and its practical consequences are demonstrated by considering the relationship between fitness functions in GAs and the heuristic functions of AI. By examining the extent to which fitness functions approximate an AI ideal, a measure of GA search difficulty is defined and applied to previously studied problems. The success of the measure in predicting GA performance (1) illustrates the potential advantages of viewing evolutionary search from a heuristic search perspective and (2) appears to be an important step towards answering a question that has been the subject of much research in the GAs community: what makes search hard (or easy) for a GA? 19 pages. FTP: ftp.santafe.edu:pub/terry/gahs.ps.gz ------------------------------ From: terry@santafe.edu (Terry Jones) Date: Wed, 10 May 95 09:56:33 MDT Subject: Dissertation available for ftp Evolutionary Algorithms, Fitness Landscapes and Search by Terry Jones Department of Computer Science University of New Mexico Albuquerque NM 87131 terry@santafe.edu A postscript version of my dissertation is now available for ftp from ftp.santafe.edu in the directory pub/terry/phd. The entire dissertation is in the file phd.ps.gz. When uncompressed (using gunzip), the postscript file is over 5MB. If you are on UNIX, you may want to print this using "lpr -s phd.ps" which will cause the printer software to make a symbolic link to the file rather than copying it (if you use -s you cannot remove phd.ps until the printing is done). If your printer cannot deal with a 5MB postscript file, you can ftp the dissertation in smaller pieces: part00.ps.gz (25 pages) Title, Abstract, Lists, Abbreviations etc. part01.ps.gz (12 pages) Introduction part02.ps.gz (34 pages) A Model of Landscapes part03.ps.gz (38 pages) Crossover, Macromutation & Population-based Search part04.ps.gz (36 pages) Reverse Hillclimbing part05.ps.gz (41 pages) Evolutionary Algorithms and Heuristic Search part06.ps.gz (19 pages) Related Work & Conclusions part07.ps.gz (44 pages) Appendices & Bibliography Mail me if you don't have gunzip, or don't know how to use anonymous ftp. If you do not have access to a postscript printer, you can get a hardcopy of the dissertation by requesting SFI TR 95-05-048 from mat@santafe.edu. These were just sent to be spiral bound, and will be available early next week. ABSTRACT -------- A new model of fitness landscapes suitable for the consideration of evolutionary and other search algorithms is developed and its consequences are investigated. Answers to the questions "What is a landscape?" "Are landscapes useful?" and "What makes a landscape difficult to search?" are provided. The model makes it possible to construct landscapes for algorithms that employ multiple operators, including operators that act on or produce multiple individuals. It also incorporates operator transition probabilities. The consequences of adopting the model include a "one operator, one landscape" view of algorithms that search with multiple operators. An investigation into crossover landscapes and hillclimbing algorithms on them illustrates the dual role played by crossover in genetic algorithms. This leads to the "headless chicken" test for the usefulness of crossover to a given genetic algorithm and to serious questions about the usefulness of maintaining a population. A "reverse hillclimbing" algorithm is presented that allows the determination of details of the basin of attraction of points on a landscape. These details can be used to directly compare members of a class of hillclimbing algorithms and to accurately predict how long a particular hillclimber will take to discover a given point. A connection between evolutionary algorithms and the heuristic search algorithms of Artificial Intelligence and Operations Research is established. One aspect of this correspondence is investigated in detail: the relationship between fitness functions and heuristic functions. By considering how closely fitness functions approximate the ideal for heuristic functions, a measure of search difficulty is obtained. This measure, fitness distance correlation, is a remarkably reliable indicator of problem difficulty for a genetic algorithm on many problems taken from the genetic algorithms literature, even though the measure incorporates no knowledge of the operation of a genetic algorithm. This leads to one answer to the question "What makes a problem hard (or easy) for a genetic algorithm?" The answer is perfectly in keeping with what has been well known in Artificial Intelligence for over thirty years. Terry Jones (terry@santafe.edu). ------------------------------ From: Ronei J Poppi Date: Mon, 8 May 1995 09:04:56 -0300 (EST) Subject: Genetic Algorithms I would like informations about genetic algorithms. I am researcher in the Chemical Institute of Campinas State University - Brazil, and my interests include the utilization of mathematical mthods for optimization (chemometrics). In a paper in Computer & Chemistry, Lacasius and Kateman comments about this e-mail. If you can help me I am appreciate very well. Sincerely, Dr. Ronei J. Poppi Prof. Dr. Ronei Jesus Poppi Universidade Estadual de Campinas Instituto de Quimica C. P. 6154 - Campinas - SP - Brazil e-mail : ronei@iqm.unicamp.br ------------------------------ From: Marco.Tomassini@di.epfl.ch (Marco Tomassini) Date: Mon, 8 May 1995 16:26:50 +0200 Subject: workshop announcement TOWARDS EVOLVABLE HARDWARE: AN INTERNATIONAL WORKSHOP October 2-3, 1995 Swiss Federal Institute of Technology, Lausanne (EPFL) Logic Systems Laboratory (LSL) Lausanne, Switzerland Purpose ======= In the last few years the idea of producing hardware in a biological-like manner, that is by using concepts derived from natural evolution in place of traditional design methods, has received an increasing amount of attention. There are few advanced groups in the world doing promising research in the field and, to date, contributions have been appearing in a scattered way at evolutionary algorithms and artificial life conferences. We believe that time is ripe to determine the current state of the art in evolvable hardware research through a dedicated forum. This will facilitate communication of current research in the field and foster collaboration between active groups. [ WMS: The full announcement is available from ftp.aic.nrl.navy.mil under pub/galist/info/conferences/EVOLVE95 ] ------------------------------ End of Genetic Algorithms Digest ******************************