Genetic Algorithms Digest Wednesday, September 11, 1996 Volume 10 : Issue 36 - 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: - On the Futility of Blind Search (Re: v10n35) - Matrix Compression (Aggregation) Algorithms - "An Introduction to Genetic Algorithms" book - Request for std.test problems on Scheduling - ECAL97 CFP - Conference & Workshop - With Deadlines - An European Mirror for the Genetic Programming Notebook ---------------------------------------------------------------------- CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) 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 SAC97 Symp on Applied Comp (GAs track), San Jose,CA (v10n28) Feb 28-Mar 2, 97 ICCIN97 Comp Intelligence and Neuroscience, North Carolina (v10n16)Mar 2-5,97 FEA97 1st Intl Wrkshp on Frontiers in EAs, North Carolina (v10n21) Mar 2-5,97 ICANNGA97 Intl Conf on Artificial NNs and GAs, England (v10n16) Apr 1-4, 97 EP97 Conf on Evolutionary Programming, Indianapolis (v10n19) Apr 13-16, 97 ICEC97 Intl Conf Evolutionary Computation, Indianapolis(v10n27) Apr 13-16, 97 GP97 Genetic Programming Conference, Stanford, CA Jul 13-16, 97 ICGA97 Intl Conf on Genetic Algorithms, East Lansing MI(v10n35) Jul 19-23, 97 ECAL97 4th European Conf on Artificial Life, England (v10n36) Jul 28-31, 97 GALESIA97 Conf on GAs in Engineering Systems, Glasgow UK (v10n36) Sept 2-4,97 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ------------------------------ From: Emanuel Falkenauer Date: Tue, 10 Sep 96 19:52:22 +0200 Subject: On the Futility of Blind Search (Re: v10n35) Hi, I've read Joseph Culberson's above-mentioned paper and have to recommend it to everybody. Great paper! I'll indulge to a few comments of the paper. It's funny. I remember PPSN-2, the final session. One of the speakers said "Also, we are confident we'll soon find the ideal encoding, because Nature was able to do so." Having grown dissatisfied with the nearly complete absence of the subject of encoding at the conference, I couldn't resist to object "I don't buy that argument, because we have of course never seen the beautiful creatures Nature could have evolved had it used another encoding." Well, I got sort of flamed there... It's sort of sad that a similar argument has to be given five years later, but it's quite comforting to see that somebody else shares that point of view. Joseph illustrates quite nicely the importance of knowledge of the target function on the hoped-for performance of an algorithm by presenting five knowledge (or "blindness") classes. I was however a bit disappointed to see him jump from Full Knowledge (i.e. the algorithm is targetted to just that one graph it's trying to color - clearly a useless device as soon as it's applied to another graph) to a Partial Knowledge where the algorithm can take into account the evaluation of a *permutation* of the vertices (or, alternatively, the adversary is allowed to construct any graph which is consistent with the permutation given its previous answers). Graph Coloring is a prime example of what I call a Grouping Problem, and I have shown in [1] that ordering (permutation-based) GAs simply do not work on Grouping Problems. However, there is an encoding which is better suited for them (described ibidem), which will leave much less space for the Adversary. So the point is that the jump from Full Knowledge to Partial Knowledge seems too long to me for that particular example: there are ways to extract a much smarter partial knowledge from an Adversary than by using permutations (and still you don't need to target a particular graph). The comment might seem a bit far fetched, if it wasn't for this: the whole point of search for good encodings is minimizing the "playing ground" of the Adversary. The "Diskette TM" of Joseph is of course extremely smart, but I would like to insist, as I did in GA-List v10n22, that complexity issues are *extremely* relevant even with the limited memory of your favourite computer. Any develop- ment (e.g. the current version of NFL) that tries to sidestep those issues on the grounds that they only arise in "theoretical" devices like the TMs, is simply irrelevant in day-to-day life of the practitioner: today's computers *already* (i.e. even without infinite tapes, or diskettes) have enough memory to make you wait for an answer for ages of the Universe if your approach is bad. There is one example in Complexity Theory which illustrates a very important aspect of day-to-day life of the practitioner which (according to my knowledge) is not well covered be the Theory. While Linear Programming (LP) has recently been shown to be in P (i.e. deterministically solvable in polynomial time), ask any practitioner for a good algorithm for LP and they will reply "Simplex, of course!" Yet Simplex has exponential complexity! The point is that Simplex performs so well in such an overwhelming majority of cases that most people don't even know it can sometimes get "exponentially crazy". If all my GAs were as successful as Simplex, woah! So for instance, even if it's sure that no approximation algorithm (including GAs) will ever achieve a great performance on Graph Coloring (unless P=NP), there could still be exponential algorithms as successful as Simplex. Cheers, Emanuel. [1] Falkenauer E. - "A New Representation and Operators for GAs Applied to Grouping Problems", in Evolutionary Computation, Vol.2, Nr.2 (Summer 1994), MIT Press, pp. 123-144. ------------------------------ From: spears@AIC.NRL.Navy.Mil Date: Tue, 10 Sep 96 12:43:08 EDT Subject: Matrix Compression (Aggregation) Algorithms Some of my most recent work has involved Markov chain models of GAs (the Nix and Vose model). This requires the creation of large (huge!) probability transition matrices (in which the rows sum to 1.0, while the columns need not sum to 1.0). I have invented a simple algorithm for compressing a probability transition matrix to a much smaller probability transition matrix, which allows me to make various computations much faster, with minimal loss in numerical accuracy. Several people state that such "aggregation" work has been done in the past. Thus far I've been unable to locate any references, however. Do any of you know of any related work? Any help would be appreciated. Even one reference could start me on the right path. Thanks very much. Bill Spears@aic.nrl.navy.mil ------------------------------ From: mm@santafe.edu (Melanie Mitchell) Date: Sat, 7 Sep 1996 10:26:38 -0600 (MDT) Subject: "An Introduction to Genetic Algorithms" book Hi, I have posted solutions to selected thought exercises for my book "An Introduction to Genetic Algorithms" in postscript format on my web page: http://www.santafe.edu/~mm/books.html. Also on that page you can find a short list of corrections to errors that have been found in the book. Melanie Mitchell ------------------------------ From: Date: Tue, 10 Sep 96 0:55:29 IST Subject: Request for std.test problems on Scheduling Sir, I'm Arvind K Tripathi,graduate student in the deptt. of Mechanical Engg.at Indian Institute of Technology Kanpur India.I'm working in field of Optimization using Genetic Algorithms Presently,I'm working on scheduling kind of problems. In Genetic Algorithms the crossover operators available presently work very well on the problems of particular domain for which the operator has been developed. My aim is to develop a new crossover operator suitable for a wider class of problems. kindly send me few standard test benchmark problems of this field. I look forward for a favourable reply in this regard. Thanking you. Regards, Arvind K Tripathi CAD Project Northern Block-1 I.I.T.Kanpur Pin-208016 India. Email uday@iitk.ernet.in [ WMS: I'll be happy to provide pointers to any such test functions from my home page http://www.aic.nrl.navy.mil/~spears. Just send email to spears@aic.nrl.navy.mil with the relevant pointer(s). ] ------------------------------ From: inmanh@cogs.susx.ac.uk (Inman Harvey) Date: Thu, 5 Sep 96 16:42 BST Subject: ECAL97 CFP CONFERENCE ANNOUNCEMENT AND CALL FOR PAPERS 4th. EUROPEAN CONFERENCE ON ARTIFICIAL LIFE ECAL97 Brighton, UK, July 28-31 1997 This interdisciplinary conference aims to provoke new understandings of the relationships between the natural and the artificial. Artificial Life is often described as the endeavour to synthesize life-like phenomena in artificial media in an attempt to establish a formal and general understanding of life. In practice it is something much broader. At its core are exchanges of ideas and blurring of boundaries between disciplines traditionally constrained to just the natural or just the artificial. ECAL97 will foster further cross-fertilisation and hopes to extend the Artificial Life community by encouraging contributions from people involved in the Arts and Humanities. The conference will involve oral presentations, both invited and contributed, poster sessions, debates, exhibitions, demonstrations, installations and related activities. Scientific topics to be covered will include, but not be limited to, the list below. Contributions from biologists are particularly welcome. Self-organisation. Origins of Life. Prebiotic evolution. RNA Systems. Fitness Landscapes. Natural Selection. Sexual Selection. Ecosystem evolution. Evolutionary Optimisation. Evolutionary Computation. Immune Networks. Neural Networks. Multicellular Development. Natural and Artificial Morphogenesis. Learning and Development. Communication. Artificial Worlds. Simulations of Ecological and Evolving Systems. Mobile Agents. Autonomous Robots. Evolutionary Robotics. Software Agents. Collective Behaviour. Swarm Intelligence. Cooperation. Evolution of Social Behaviour. Philosophical Issues in Alife. Ethical problems. Papers should not be longer than 12 pages (including figures) in the Springer-Verlag llncs style (http://www.springer.de/tex/help-tex.html) with an abstract of 70-150 words. We encourage paper submissions via the Internet, though traditional paper is also acceptable (4 hard-copies). Demonstrations, Videos, and proposals for associated workshops are also welcomed. Official Language: English Publisher: Springer-Verlag IMPORTANT DATES Feb 28, 1997 -- Submission deadline Apr 28 -- Notification of acceptance May 16 -- Camera-ready due May 31 -- Early registration deadline July 28-31, 1997 -- Conference dates ECAL97 will be held in Brighton on the South Coast of England, just one hour by train from London and conveniently close to London Gatwick airport. Please PRE-REGISTER your interest by filling out a form via our WWW site. All new announcements will be emailed to those who have pre-registered, and will also be available on this site: http://www.cogs.susx.ac.uk/ecal97/ EMAIL: ecal97@cogs.susx.ac.uk Conference organizers: Phil Husbands and Inman Harvey Local organization: Medeni Fordham and Joseph Faith Conference Secretariat: Medeni Fordham
ECAL97 COGS, University of Sussex Brighton BN1 9QH, UK ------------------------------ From: GALESIA'97 Organizing Committee Date: Fri, 6 Sep 1996 09:12:27 +0100 Subject: Conference & Workshop - With Deadlines [ WMS: I have shortened this somewhat - please see the Web site below for more information ] (Updates on http://www.iee.org.uk/LSboard/Conf/Galesia/) GALESIA'97 2nd IEE/IEEE International Conference on Genetic ALgorithms in Engineering Systems: Innovations and Applications 2 - 4 September 1997, Glasgow, United Kingdom With a One-Day International Workshop on Evolutionary Computation: Theory and Applications Monday, 1 September 1997 This event, the Second in the GALESIA series of Conferences, aims to provide an international forum for the presentation of technical results and advances in Genetic Algorithms (GAs) theory and applications in engineering systems. GALESIA'97 will consider contributions from both academia and industry which emphasise the role of Evolutionary Computing and GAs in particular, in engineering systems although the general focus on theory and applications will be retained. SCOPE The scope of the Conference includes, but is not limited, to 1. Innovations and Theory scheduling genetic operators and representations parallel genetic algorithms genetic programming evolution strategies classifier systems evolutionary programming mathematical techniques and analysis surveys and reviews (GAs in Engineering and Computer Science) biological aspects of GAs intelligent agents hybrid methods artificial neural networks fuzzy logic Conventional optimizers 2. Applications aerospace automobiles marine rail telecommunications systems integration network industry systems energy systems robotics biomedical manufacturing decision support control systems process industry system identification and modelling signal image processing/coding civil engineering fault diagnosis The Conference targets those working in Engineering Systems or related fields such as Mathematics, Physics, Computer Science, Biology, Psychology and Medicine. CONTRIBUTIONS Authors wishing to contribute to the Conference should send an original plus four copies of each paper by 31 January 1997 to the GALESIA Secretariat. Papers should be submitted on A4 sheets with a 2-column format. Each column is 8.2 cm in width with a spacing of 0.8 cm between columns. Text should be typed in 10 point Times-Roman font with single line spacing. The first page should incorporate (first line) the title, (double line space) author(s), (double line space), and affiliations. Only six pages are allowed per paper (inclusive of figures, tables etc.), although further pages (maximum of 8 in total) may be considered, for an accepted paper, upon a charge of =FA20.00 per page. Please contact the GALESIA Secretariat should you require a sample of the required layout. If presented in good quality suitable for camera-ready copying, successful contributions may be published from the original copy submitted in the first instance. Otherwise, authors will be requested to re-submit. All contributions will be published as part of the IEE conference proceeding series and will be available to all delegates at the event. DEADLINES Today: Fill in the information request form 31 January 1997: Submission of 5 copies of paper May 1997: Notification of Acceptance to Authors 1 September 1997: Workshop 2-4 September 1997: Conference and Exhibition INVITED SESSIONS Proposals are invited for special Sessions on topics related to the general scope of the Conference. A special Session may contain 4 or 5 contributions. In addition to a one page description of the aims and objectives of the Session, the proposer is requested to take up the task of co-ordinating the submission of the papers for that Session. Please submit proposals to the GALESIA Secretariat. PANEL DISCUSSION A Panel Discussion will be held to discuss the definitions and the potential role of evolutionary computation in academic research and its industrial applications, thus attempting to present a formal overview from an engineering prospective. WORKING LANGUAGE The working language of the Conference will be English which will be used for all printed material, presentations and discussion. One-Day Workshop on Evolutionary Computation: Theory and Applications Monday, 1 September 1997 An International Workshop on "Evolutionary Computation: Theory and Applications" will precede the Conference on Monday, 1 September 1997. The Workshop is aimed at those from industry as well as academia and it aims to promote the successful implementation of evolutionary computation in engineering applications by introducing both the underlying theoretical concepts in addition to the industrial experience. The planned sessions include: 1. Principles for control optimisation and design (Professor Peter Fleming, University of Sheffield) 2. Applications in industrial automation (Dr. Ali Zalzala, University of Sheffield) 3. Fuzzy-genetic applications (Professor Derek Linkens, University of Sheffield) 4. Parallel genetic algorithms (Dr. Marco Tomassini, Swiss Federal Institute of Technology) 5. Industrial experience ( Dr Peter Cowley, Rolls Royce Applied Science Laboratories) 6. Industrial experience (Dr Bertrand Braunschweig, Institut Frangais du Pitrole) 7. Industrial experience (Dr Ken Hunt, Daimler-Benz AG) 8. Industrial experience (Dr Markus Hoefeld, Siemens AG) For further information, please contact the GALESIA Secretariat. GALESIA'97 Organizing Committee Contact Points: 1. MANAGEMENT AND TECHNICAL: Dr. Ali Zalzala (Chairman) Department of Automatic Control and Systems Engineering University of Sheffield Mappin Street, Sheffield S1 3JD, U.K. Tel: +44 (0)114 2825136; Fax: +44 (0)114 2731729 Email: galesia@sheffield.ac.uk 2. ORGANISATION: Mr. Jarlath O'Connell (GALESIA'97 Secretariat) Conference Services The Institution of Electrical Engineers Savoy Place, London WC2R 0BL, U.K. Tel: +44 (0)171 344 5477/2245; Fax: +44 (0)171 497 3633 Email: conference@iee.org.uk ------------------------------ From: Jaime Fernandez Date: Mon, 09 Sep 1996 20:49:59 -0500 Subject: An European Mirror for the Genetic Programming Notebook There is now an European Mirror for the Genetic Programming Notebook it is located at: http://www.lcc.uma.es/jjf/gp/ I want to thank Enrique Alba from the University of Malaga in Spain for providing the mirror. In addition to the European mirror the Genetic Programming Notebook has 5 mirrors in the USA and 2 in Asia at: USA Mirrors: http://www.jrabbit.com/~jjf/gp/ http://tommy.jsc.nasa.gov/~jjf/gp/ http://www.owlnet.rice.edu/~jjf/gp/ http://metricanet.com/people/jjf/gp/ http://www.mysite.com/jjf/gp Asia Mirrors: http://cair.kaist.ac.kr/gp/ http://monami.kaist.ac.kr/gp/ The GP Notebook contains information in the following categories: GENETIC PROGRAMMING GP Tutorial Software People Other Sites Research Groups Miscellaneous Bibliographies Papers Journals FAQ Calls for Papers Conferences Commercial GENETIC ALGORITHMS Genetic Algorithms Software People Other Sites Research Groups Miscellaneous Bibliographies Papers Journals FAQ Courses Parallel Repositories Tutorials ARTIFICIAL INTELLIGENCE & ROBOTICS Artificial Intelligence FAQs Newsgroups Machine Learning Artificial life Sites Fuzzy Logic Neural Nets Robots Financial Programming Jaime J. Fernandez Jr. | Email: jjf@jjf.com Metrica, Inc. | WWW: http://www.jjf.com ------------------------------ End of Genetic Algorithms Digest ******************************