Genetic Algorithms Digest Wednesday, September 7, 1994 Volume 8 : Issue 34 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL - anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL [192.26.18.68] - (Info in /pub/galist/FTP) Today's Topics: - Multiple competing chromosomes - Applications of GA in Unit Commitment Problem - New IlliGAL papers (8/94) - Call for Papers for EA-book - EA-book available ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) TECOM AI Conference, Aberdeen Proving Ground, Maryland (v8n19) Sep 13-16, 94 Evolution Artificielle 94, Toulouse, France (v8n10) Sep 19-23, 94 COMPLEX94 2nd Australian National Conference, Australia (v7n34) Sep 26-28, 94 PPSN-94 Parallel Problem Solving from Nature, Israel (v7n32) Oct 9-14, 94 GAs in Image Processing and Vision Colloquium, Savoy Place (v8n16) Oct 20, 94 AI'94 Workshop on Evol Comp, Armidale, NSW, Australia (v8n15) Nov 22, 94 ACM SAC '95 Symposium on Applied Computing, Tennessee (v8n20) Feb 26-28, 95 EP95 4th Ann Conf on Evolutionary Programming, San Diego,CA(v8n6) Mar 1-4, 95 ICTS95 3rd Int'l Conf. on Telecommunications, Tennessee (v8n21) Mar 16-19, 95 ICANNGA95 Intl Conf on Artificial NNs and GAs, France (v8n10) Apr 18-21, 95 IAS-95 Intelligent Adaptive Systems, Melbourne Beach FL (v8n32), April 26, 95 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 95 ICGA-95 Sixth Int'l Conference on GAs, Pittsburgh PA (v8n32), July 15-20, 95 ASI-AA-95 Practice and Future of Autonomous Agents (v8n19) Sep 23 - Oct 1, 95 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: Raphael T. Haftka Date: Sun, 4 Sep 94 12:25:22 -0400 Subject: Multiple competing chromosomes I am working on the application of two-species genetic algorithm to a min-max problem from structural optimization (minimum weight design of beams). The resulting GA would appear to simulate a host-parasite relationship in biology. I would not like to reinvent the wheel if others have solved the problems associated with such an algorithm, such as how to evaluate the fitness of each one of the species. I assume that there is previous work on two-species GA either in game theory or in biological simulations, and I would appreciate information on such work. Raphael T. Haftka, Professor Tel: 703-231-4860 Department of Aerospace and Ocean Engineering Viriginia Tech email: haftka@vtvm1.cc.vt.edu Blacksburg, VA 24061-0203 ------------------------------ From: fabiano@gsc.ele.puc-rio.br (Fabiano S. G. de Oliveira [Marco 94.1]) Date: Thu, 1 Sep 94 16:03:31 EST Subject: Applications of GA in Unit Commitment Problem Please insert this message in the next Digest: Dear colleagues, I'm looking for papers about applications of Genetic Algorithms in Unit Commitment Problem and Economic Load Dispatch. Thank you for any help. Fabiano S.G. de Oliveira Fabiano@gsc.ele.puc-rio.br Oliveira@ele.puc-rio.br ------------------------------ From: jhorn@gal1.ge.uiuc.edu (Jeff Horn) Date: Mon, 29 Aug 94 10:28:27 CDT Subject: New IlliGAL papers (8/94) IlliGAL ANNOUNCEMENT 8/94 (Last Announcement, 7/94) The Illinois Genetic Algorithms Laboratory (IlliGAL) is pleased to announce the publication of several new technical reports and papers. Most IlliGAL technical reports, as well as reprints of other publications, are available in hardcopy and can be ordered from the IlliGAL librarian, (see below for ordering information). Those papers marked with an asterisk (*) are also available electronically on our ftp and WWW server (see below for ftp and WWW access instructions). (1) NEW 1994 IlliGAL REPORTS: IlliGAL Report No 94006* (17 pp.) Title: Genetic algorithm difficulty and the modality of fitness landscapes Authors: Jeffrey Horn and David E. Goldberg We assume that the modality (i.e., number of local optima) of a fitness landscape is related to the difficulty of finding the best point on that landscape by evolutionary computation (e.g., hillclimbers and genetic algorithms (GAs)). We first examine the limits of modality by constructing a unimodal function and a maximally multimodal function. At such extremes our intuition breaks down. A fitness landscape consisting entirely of a single hill leading to the global optimum proves to be hard for hillclimbers but apparently easy for GAs. A provably maximally multimodal function, in which half the points in the search space are local optima, can be easy for both hillclimbers and GAs. Exploring the more realistic intermediate range between the extremes of modality, we construct local optima with varying degrees of ``attraction'' to our evolutionary algorithms. Most work on optima and their basins of attraction has focused on hills and hillclimbers, while some research has explored attraction for the GA's crossover operator. We extend the latter results by defining and implementing "maximal" partial deception in problems with k arbitrarily placed global optima. This allows us to create functions with multiple local optima attractive to crossover. The resulting maximally deceptive function has several local optima, in addition to the global optima, each with various size basins of attraction for hillclimbers as well as attraction for GA crossover. This "minimum distance" function seems to be a powerful new tool for generalizing deception and relating hillclimbers (and Hamming space) to GAs and crossover. IlliGAL Report No 94005* (17 pp.) Title: Population Sizing for Sharing Methods Author: Samir W. Mahfoud Sharing methods promote the formation and maintenance of stable subpopulations or niches in genetic algorithms. This paper derives, for various models of sharing, lower bounds on the population size required to maintain, with probability gamma, a fixed number of niches. The first model assumes all niches are equivalent with respect to fitness and that crossover is minimally disruptive. The next two models allow niches to differ with respect to fitness. The final model takes into account the disruptive effects of crossover. GAs with sharing are run on seven test problems in optimization and classification, using population sizes derived from the models. IlliGAL Report No 94004* (33 pp.) Title: Decision Making In Genetic Algorithms: A Signal-To-Noise Perspective Authors: Hillol Kargupta and David E. Goldberg Signal detection in presence of noise is a decision problem, as addressed in the traditional signal processing literature. On the other hand, an arbitrary decision problem can also be posed in terms of signal and noise, corresponding to the inference to be tested. In this paper, we extend the previous efforts to analyze the decision making process in Genetic Algorithms(GAs) [Holland, 75] [Goldberg and Rudnick, 91] [Goldberg, Deb and Clark, 92] to a more general one for quantifying different aspects of difficulties that may lead GA towards a suboptimal solution. First we pose a decision problem in terms of multiple 2-armed bandits, which may be mutually dependent. This presents a theoretical framework for understanding stochastic search techniques in general. The deterministic and nondeterministic effects on the convolution kernel associated with the bandits are identified as signal and noise respectively. Next we discuss what these quantities mean in a GA. We also describe how they can be computed in GA and show that the population fitness variance may be used as an estimator. Next, we present a signal-to-noise perspective of GA hardness. It is noted that there are two fundamental modes of introducing difficulty into the decision making process: 1) sending a wrong signal and 2) increasing or decreasing noise depending on the direction of signal. We mostly focus on the second order interaction between partitions, namely the variance within the partitions and the cross-covariance between partitions. We also note that the difficulty due to crosstalk [Goldberg, 93a] can be quantified by these higher order components. A simple 18 bit problem is constructed to show the possible sources of increased noise during the late stages, when the population gets biased. Next, we experiment with Royal Road functions R1 & R2 [Forrest and Mitchell, 93] and explain their behavior in terms of the signal-to-noise characteristic of the convolution kernel. We show that the signal-to-noise ratio for R1 is significantly higher than that of R2. This clearly tells us that increasing signal in the right direction alone does not necessarily make a problem easy for GA, unless the noise does not increase. At the end we briefly discuss the possible underlying mechanism that makes deceptive problems hard to solve, from the framework of signal and noise. We also show that the partially deceptive function presented in [Grefenstate, 93] hardly share any of the fundamental characteristics of other traditional fully deceptive functions, rather stands as an instance of a simple linearization technique, in other words a reduction to a sequential decision making problem, as described in an earlier paper [Goldberg, 92b]. (2) NEW PUBLICATIONS: Horn, J., Goldberg, D.E., & Deb, K. (1994). Implicit niching in a learning classifier system: nature's way. Evolutionary Computation, 2(1). August, 1994, 37-66. (early version available as IlliGAL Report No. 94001) (ABSTRACT) We approach the difficult task of analyzing the complex behavior of even the simplest learning classifier system (LCS) by isolating one crucial subfunction in the LCS learning algorithm: covering through niching. The LCS must maintain a population of diverse rules that together solve a problem (e.g., classify examples). To maintain a diverse population while applying the GA's selection operator, the LCS must incorporate some kind of niching mechanism. The natural way to accomplish niching in an LCS is to force competing rules to share resources (i.e., rewards). This implicit LCS fitness sharing is similar to the explicit fitness sharing used in many niched GAs. Indeed, the LCS implicit sharing algorithm can be mapped onto explicit fitness sharing with a one-to-one correspondence between algorithm components. This mapping is important because several studies of explicit fitness sharing, and of niching in GAs generally, have produced key insights and analytical tools for understanding the interaction of the niching and selection forces. We can now bring those results to bear in understanding the fundamental type of cooperation (a.k.a. weak cooperation) that an LCS must promote. Goldberg, D.E. (1993). The Wright brothers, genetic algorithms, and the design of complex systems. In the proceedings of SYNAPSE '93 (Japan). Goldberg, D.E. (1993). A Wright brothers theory of genetic algorithm flight. iSCIe, 37(8) (Japan). The above IlliGAL reports, and others, are available electronically via FTP or WWW, or as hardcopy directly from us: FTP: ftp GAL4.GE.UIUC.EDU login: anonymous password: (your email address) cd /pub/papers/IlliGALs (for reports) or cd /pub/papers/Publications (for preprints) or cd /pub/src (for messy GA code) binary get 93005.ps.Z (for example) bye Then on your machine (for papers): uncompress 93005.ps.Z lpr -P(your postscript queue) 93005.ps Please look at the README files for explanations of what the file names mean. IlliGAL reports are all compressed postscript files. WWW: To access the IlliGAL home page, open URL (Uniform Resource Locator) http://GAL4.GE.UIUC.EDU/illigal.home.html (To get X binaries for Mosaic, ftp to ftp.ncsa.uiuc.edu, cd Mosaic, cd Mosaic-binaries, get the appropriate platform's binaries. For the Mac binaries, ftp to ftp.ncsa.uiuc.edu, cd Mac, cd Mosaic, go from there.) HARDCOPY: You can still order hardcopy versions of most IlliGAL publications (including, in particular, those not yet on the server!). See the IlliGAL order form (via WWW, below, or as file "orderform.ps" or "orderform.text" on the ftp server), or request them directly (by IlliGAL number or title) from the IlliGAL librarian: Internet: library@GAL1.GE.UIUC.EDU Phone: 217/333-2346 Surface mail: IlliGAL Librarian Department of General Engineering 117 Transportation Building 104 South Mathews Avenue Urbana, IL 61801-2996 USA When ordering hardcopy, please include your surface mail address! Note that the file "orderform.ps" in /pub/papers on the ftp server is the IlliGAL order form and contains a (nearly) complete listing of IlliGAL reports and other publications to date. Jeffrey Horn jeffhorn@uiuc.edu Illinois Genetic Algorithms Laboratory (jhorn@GAL1.GE.UIUC.EDU) University of Illinois at Urbana-Champaign 117 Transportation Building Day Phone: 217/333-2346 104 South Mathews Avenue Fax: 217/244-5705 Urbana, IL 61801-2996 USA ------------------------------ From: vnissen Date: Mon, 5 Sep 1994 16:06:28 +0200 (MET DST) Subject: Call for Papers for EA-book Call for Papers Evolutionary Algorithms in Management Applications Prof. Dr. Joerg Biethahn and I are editing a book on evolutionary algorithms (EA) in management applications. The purpose of this project is to give an overview of innovative applications of these promising search and optimization techniques in a field of primary importance. The book will consist of invited and contributed papers and group EA-applications in sections such as * Industry * Retailing * Financial Services * Energy * Traffic * Education * Health Care * Telecommunication We invite authors to contribute unpublished high quality papers describing management applications of genetic algorithms, genetic programming, evolution strategies, evolutionary programming , classifier systems or other evolutionary inspired metaphors. The contribution must describe a real-world application or have a clear potential for practical applications in the field of management. Prospective authors are requested to send an abstract (in English) of half a page to my adress below prior to 10th October 1994. The abstract should give a good idea of the type of application, whether it is a practical implementation in business or application-oriented research, and the methodology employed. Full papers are due 1st December. All contributed papers will be reviewed. We aim at publishing the book in mid-1995. More detailed information on the full paper will be sent to the authors of abstracts. Please do not forget your postal and e-mail adress when sending the abstracts. Abstracts should be directed to my following adress: Dr. Volker Nissen Universitaet Goettingen Institut fuer Wirtschaftsinformatik Abteilung I Platz der Goettinger Sieben 5 (MZG) D-37073 Goettingen Germany Fax: Germany-(0)551-39-9679 e-mail: vnissen@gwdg.de ------------------------------ From: vnissen Date: Mon, 5 Sep 1994 16:52:11 +0200 (MET DST) Subject: EA-book available The following book on evolutionary algorithms (written in GERMAN) is now available from DUV Deutscher Universitaets Verlag: Nissen, Volker: Evolutionaere Algorithmen. Darstellung, Beispiele, betriebswirtschaftliche Anwendungsmoeglichkeiten. 1994. XXVI, 488 pages, 88 fig., 43 tab. ISBN 3-8244-0217-3 In the first part of the book all mainstream EA-variants (genetic algorithms, evolution strategies, evolutionary programming, genetic programming) are described, including variants and important elements of theory. Then, implementations and experimental results with various EA-types and conventional optimization techniques are given for sample applications in facility layout and inventory. The third part is devoted to the general application potential of EA in the field of management. First, a survey of current management applications of EA is given and evaluated. Second, advantages and disadvantages of EA are discussed and inferences on their applicability in management are drawn. Third, combinations of EA with other problem-solving techniques and their application potential in management are highlighted, in particular neural nets, simulation, fuzzy set theory, conventional OR-methods and production systems (such as LCS). Finally, let me point out again that the book is written in German. Best wishes, Volker. ------------------------------ End of Genetic Algorithms Digest ******************************