Genetic Algorithms Digest Monday, April 24, 1995 Volume 9 : Issue 24 - 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: - CFP: special issue of Evolutionary Computation - ASI-AA-95 - Call for Participation - References for GAs in high-level synthesis - looking for classifier system example - Genetic Based machine Learning - ES Demos available - Inversion (Re: v9n21) - TR available ---------------------------------------------------------------------- ******************************************************************************* CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) IAS-95 Intelligent Adaptive Systems, Melbourne Beach FL (v8n32) Apr 26, 95 CAD95 Computer Aided Design / "GA Day", Yalta City, CIS (v8n46) May 4-13, 95 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 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 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: peter@ai.iit.nrc.ca (Peter Turney) Date: Thu, 13 Apr 1995 09:05:18 +0500 Subject: CFP: special issue of Evolutionary Computation Special Issue on EVOLUTION, LEARNING, AND INSTINCT: 100 YEARS OF THE BALDWIN EFFECT In 1896, James Mark Baldwin proposed that individual learning can explain evolutionary phenomena that appear to require Lamarckian inheritance of acquired characteristics. The ability of individuals to learn can guide the evolutionary process. In effect, learning smoothes the fitness landscape, thus facilitating evolution. This first aspect of the Baldwin effect has recently received much attention, especially for its applications to computational problem solving. In evolutionary algorithms, local search is analogous to individual learning. Improvements found via local search change the fitness of an individual without changing the actual genotype. Baldwin further proposed that abilities that initially require learning are eventually replaced by the evolution of genetically determined systems that do not require learning. Thus learned behaviours may become instinctive behaviours in subsequent generations, without appealing to Lamarckian inheritance. This aspect of the Baldwin effect deserves more attention. Recent work suggests that intuitive abilities in human language, physics, biology, and arithmetic may be largely instinctive. The Baldwin effect can help us understand the relationship between learning and instinct. Furthermore, increased understanding of this second aspect of the Baldwin effect may enable us to improve the performance of computational problem solving by hybrids of genetic algorithms and local search algorithms. A special issue of Evolutionary Computation is planned for 1996, the 100th anniversary of Baldwin's paper. Evolutionary Computation provides an international forum for facilitating and enhancing the exchange of information among researchers involved in both the theoretical and practical aspects of computational systems of an evolutionary nature. Papers are solicited that address both theoretical and computational work related to evolution, learning, instinct and the Baldwin Effect. Examples of topics of interest include: * When is learning advantageous? Learning can facilitate evolution by allowing individuals to more quickly adapt to fitness landscapes that would otherwise be difficult to exploit; however, the ability to learn weakens the selective forces acting on an individual, which can slow evolutionary change. * When is instinctive behaviour advantageous? Instincts can be fast and dependable in a static environment, although they may not be able to cope with radical environmental change. Thus the trade off between instinctual and learned responses may have implications for search and learning in dynamic computational environments. * From a design perspective, what parts of an individual's cognitive machinery should be modifiable by experience (local search) and what parts should be determined by evolution (genetic search)? For example, in a typical hybrid of a genetic algorithm and a neural network, the genetic algorithm determines the network architecture and back propagation determines the network weights. Is there a Baldwinian justification for this division of labour? * How does learned behaviour become instinctive? It seems plausible that, for some learned behaviours, there is no evolutionary path that leads to an instinctive replacement for the behaviour. For computational problem solving with hybrid genetic algorithms, what techniques can we use to encourage learned behaviours to evolve into instinctive behaviours? Further Information For more information, see "http://ai.iit.nrc.ca/baldwin/cfp.html" on the World Wide Web or send a message to the contact address listed below. Instructions for Submitting Papers Papers should describe mature work that is original in nature and has not been published elsewhere. Manuscripts should be approximately 8,000 to 12,000 words in length and formatted for 8 1/2 x 11-inch paper, single-sided and double-spaced. The first page should include the title, abstract, key words, and author information (name, affiliation, mailing address, telephone number, and e-mail address). The text of the paper should begin on the second page and continue on consecutively numbered pages. For more information on the format, consult the inside back cover of a recent issue of Evolutionary Computation. Send five hard copies (not faxes) to the contact address listed below. Electronic submissions in PostScript are also acceptable. Important Dates Manuscripts due: February 1, 1996 Acceptance notification: May 1, 1996 Final manuscript due: August 1, 1996 Planned Publication date of issue: December 1996 Guest Editors Peter D. Turney, National Research Council, Canada Darrell Whitley, Colorado State University, USA Russell W. Anderson, University of California, USA Contact Address Dr. Peter Turney Knowledge Systems Laboratory Institute for Information Technology National Research Council Canada Ottawa, Ontario, Canada K1A 0R6 (613) 993-8564 (office) (613) 952-7151 (fax) peter@ai.iit.nrc.ca ------------------------------ From: maris@ifi.unizh.ch (Marinus Maris) Date: Thu, 13 Apr 1995 16:04:30 +0100 Subject: ASI-AA-95 Here is the final announcement for the Advanced Study Institute on Autonomous Agentsto be held in Ascona, Switzerland, from September 23rd to October 1st, 1995. Please find enclosed: -- Description of the program for ASI-AA-95 -- Timetable of ASI-AA-95 -- Application form for ASI-AA-95 Please note that the application deadline is April 29th, 1995. All applications will be considered, however, the available positions are limited. The documents mentioned above can be found in the following WWW page: http://www.ifi.unizh.ch/asi-aa.html. The documents are in postcript format for enabling appropriate printing. We hope to see at the Study Institute: Sincerely Yours, Daniel Meier and Marinus Maris [ WMS: The full announcement is also on our anonymous FTP site under pub/galist/info/conferences/ASI-AA-95.info. ] ------------------------------ From: David Levine Date: Thu, 13 Apr 1995 11:37:52 -0500 Subject: Call for Participation ICGA-95 Workshop on Parallel Genetic Algorithms at the 1995 International Conference on Genetic Algorithms (ICGA-95) 15-19 July, 1995 University of Pittsburgh Pittsburgh, PA USA Workshop organizers: David Levine levine@mcs.anl.gov Jayshree Sarma jsarma@cs.gmu.edu To some people, a parallel genetic algorithm is a model of evolution that is independent of hardware and software considerations. To others, a parallel genetic algorithm is a style of programming that takes advantage of parallel computers to reduce the time to solve a problem. Finally, for still others, a parallel genetic algorithm is both of the above. This workshop aims to bring together those interested in the above topics to discuss common and contrasting points of view. Topics of interest include, but are not limited to: * Parallel genetic algorithm models * Parameter choices for different models * Theory of parallel genetic algorithms * Computational results * Performance metrics * Interesting/Novel applications. * Hardware and software considerations The format of the workshop will consist of short presentations and informal discussions. If you are interested in participating please send a short description of your proposed topic to one of the workshop organizers by May 31. An attempt will be made to accomodate all interested speakers. Work already accepted for ICGA-95 is not appropriate for this workshop. ------------------------------ From: rsm@doe.carleton.ca (Raul San Martin) Date: Fri, 14 Apr 1995 14:59:18 -0400 (EDT) Subject: References for GAs in high-level synthesis A couple of issues back someone asked for references of applications of GAs in the high-level synthesis of ICs. Here are some: N. Wehn, M. Held, and M. Glesner, "A Novel Scheduling/Allocation Approach for Datapath Synthesis Based on Genetic Paradigms,", Proc. of the IFIP TC10/WG10.5 Workshop on Logic and Architecture Synthesis, pp. 47-56, Paris, France, May 1990. R. San Martin and J.P. Knight, "Genetic Algorithms for Optimization of Integrated Circuit Synthesis," in Proc. of the Fifth Int. Conf. on Genetic Algorithms and their Applications, pp. 432-438, Morgan Kaufman, San Mateo, CA, July 1993. S. Ali, S.M. Sait, and M.S.T. Benten, "GSA: Scheduling and Allocation using Genetic Algorithm," Proc. of the 1994 Eurodac, pp. 84-89, 1994. R. San Martin and J.P. Knight, "PASSOS, a Different Approach for Assignment and Scheduling in High-Level Synthesis," Proc. of the 37th Midwest Symposium of Circuits and Systems, pp. 339-342, Lafayette, LA, August 1994. R. San Martin and J.P. Knight, "Power-Profiler: Optimizing ASICs Power Consumption at the Behavioral Level," Proc. of the 32nd ACM/IEEE Design Automation Conference, San Francisco, CA, June 1995 (to appear). (This system is also available on the World Wide Web: http://www.doe.carleton.ca/~rsm/Power/power/html) Hope this helps. Raul San Martin rsm@doe.carleton.ca ------------------------------ From: Juan Ramon Velasco Perez Date: Mon, 17 Apr 1995 15:58:40 +0200 Subject: looking for classifier system example Hello, I'm looking for an easy-to-understand example of classifier system. It is for a sort-first course on GA's. Could anybody give me some pointers (references, http pages, ftp, software packages, etc... are wellcome)? Thanks in advance, Juan R. Velasco Dr. Juan R. Velasco tel: +34 1 5495700 (ext. 440) Dpt. Ing. Sist. Telematicos fax: +34 1 5432077 E.T.S.I Telecomunicacion Ciudad Universitaria s/n e-mail: jvelasco@dit.upm.es E-28040 MADRID (SPAIN) ------------------------------ From: Student 2 (D. Wienke) Date: Tue, 18 Apr 1995 20:56:34 +0200 Subject: Genetic Based machine Learning Hello everybody, I'm writing a report about genetic based machine learning and I have one difficulty. I can't find any applications which have a chemical background. If you know such an application please mail me, i'll be grateful. Greetings Kees. dwstud2@sci.kun.nl ------------------------------ From: "I.SANTIBANEZ-KOREF" Date: Tue, 18 Apr 95 12:56:50 +0200 Subject: ES Demos available Three Demonstration-Programs for the application of the Evolution Strategy to different technical problems are now available from ftp://ftp-bionik.fb10.tu-berlin.de/pub/BIONIK/DEMOS/demovga.exe or ftp://ftp-bionik.fb10.tu-berlin.de/pub/BIONIK/DEMOS/demoega.exe Also available is the technical report ftp://ftp-bionik.fb10.tu-berlin.de/pub/BIONIK/PAPERS/tr-05-94.ps.Z which gives some explanations to the examples. The report describes 10 different examples for the use of the Evolution Strategy. In the moment the three programs Poly94, Lens94 and Brach94 are available: Lens94: By means of Evolution Strategy the shape of an initially cuboid light transmissive body is to be changed in such a way, that parallel falling rays of light are refracted into a single point P on a projection surface. Poly94: To a set of data points in the two-dimensional plane a polynomial is to be find in such a way, that all points are described by the polynomial with minimal error. The coefficients of the polynomial are to be found with the Evolution Strategy. Brach94: This classical problem was posed by Johann Bernoulli to his professional colleagues in 1696. He asked for the track between the two points A and B, on which a movable point P slides frictionless in shortest time by means of his own gravity. The optimal track is to be found with the Evolution Strategy. Michael Herdy TU-Berlin Ackerstr. 71-76, Sekr. ACK1 D-13355 Berlin Germany ftp-server: ftp-bionik.fb10.tu-berlin.de (130.149.192.50) email: herdy@fb10.tu-berlin.de fon : +49 30 31472663 fax : +49 30 31472658 ------------------------------ From: jan@riks.nl (Jan Paredis) Date: Thu, 20 Apr 95 10:32:54 +0200 Subject: Inversion (Re: v9n21) In response to Philipp Djang (GA-List v9n21, "Random Keys GA"). Philipp asked: > Has anybody ever built a GA with more than the "standard" > genetic operators ( standard = {crossover, mutation} )? Holland's > seminal book describes an inversion operator, but nobody seems > to use it. I believe that early experiments compared different > operators (applying a fairly rigorous design), and concluded > that inversion was not effective for the test problems. As was already mentioned in the reply of Mr. Falkenauer, inversion is useful for attacking the representation problem (putting functionally related genes near each other on the gene string, unrelated genes should be far apart on the string). Obviously inversion will only work well in combination with a crossover with high positional bias (for a definition of positional bias see (Eshelman et al ICGA-89)). Hence it might be worth to use inversion in combination with one-point crossover. One would expect less from the use of inversion with two-point crossover. In combination with uniform crossover , inversion is not going to be of any help. But - according to me - there is another problem with inversion: its random non-accumulative nature! It would obviously be better that during the run, a GA learns to find a good representation (combining multiple inversions). A GA-type knowledge free estimator of a good representation (inversion if you want) would be the relation between the fitness of the parents and the fitness of the child which was created using that representation/ inversion. My upcoming ICGA paper exactly does this (throught the symbiotic coevolution of solutions and representation). For the people interested, below you find the abstract of this paper: Title: The Symbiotic Evolution of Solutions and their Representation Author: Jan Paredis (jan@riks.nl) ICGA-95 Abstract: This paper studies the use of co-operating populations of individuals to boost evolutionary search. More specifically, techniques originating from previous work on artificial predator-prey systems are evaluated within the context of symbiosis. The use of life-time fitness evaluation (LTFE) is particularly effective. Besides being applicable in symbiotic as well as predator-prey systems, LTFE is also robust when confronted with noisy environments and/or noisy fitness evaluations. It is shown how the search for a good genetic representation can speed up the search for a solution to a difficult deceptive problem. This through the symbiotic coevolution of solu- tions and representations. Cheers, Jan ------------------------------ From: chiva@biologie.ens.fr (Emmanuel CHIVA) Date: Thu, 20 Apr 1995 12:20:33 +0200 Subject: TR available ftp-host: ftp.ens.fr ftp-filename: /pub/reports/biologie/liverpool.ps.Z (215 kB compressed, 18 pages) *** DO NOT FORWARD TO ANY OTHER LISTS *** The following report (Submitted to IPCT'95) is available by ftp from our ftp-server (Ecole Normale Superieure, Paris, France) (a WWW page will be available soon). "Modelling the emergence of coregulated proteins in biological regulation networks" Emmanuel Chiva and Philippe Tarroux Ecole Normale Superieure Groupe de BioInformatique 46 rue d'Ulm, 75230 Paris Cedex 05, FRANCE The organization of gene and protein regulation networks adresses fundamental questions in biology. In this work, we show that the emergence of particular hierarchized structures allows the cell to respond in an adapted way to significant environmental inducers. Using multivariate analysis techniques, we demonstrate that the constraint to exhibit as many different responses as possible results in the individualization of functionally correlated units, related to the coregulated protein groups previously observed in actual regulation systems. ------------------------------ End of Genetic Algorithms Digest ******************************