Genetic Algorithms Digest Thursday, August 4, 1994 Volume 8 : Issue 30 - 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: - Conservation of Moderator Energy - ** CMU Artificial Intelligence Repository ** - Looking for functions - Report Available - Packing problems or cutting stock problems - GA/EA-Tool? - Dynamic Hill Climbing papers available ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) SAB94 3rd Intl Conf on Sim of Adaptive Behavior, Brighton(v7n11) Aug 8-12, 94 ECAI-94, 11th European Conference on AI, Amsterdam (v7n23) Aug 8-12, 94 ECAI-94 Wkshp on Applied Genetic & Other Evol Algs, Amsterdam(v8n5) Aug 9, 94 IEEE/Nagoya Univ WW Wkshp on Fuzzy Logic & NNs/GAs, Japan(v7n33) Aug 9-10, 94 ISRAM94 Special Session on Robotics & GAs, Maui, Hawaii (v7n22) Aug 14-17, 94 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 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 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: William M. Spears (Moderator) Date: Wed, 3 Aug 94 Subject: Conservation of Moderator Energy Your moderator has used up his supply of energy for the year and will be taking a vacation during the middle of August. Thus, there may be a 2 week pause in issues. Keep the discussions going while I'm away! Bill ------------------------------ From: Mark Kantrowitz Date: Thu, 21 Jul 94 15:41:56 -0400 Subject: ** CMU Artificial Intelligence Repository ** [ WMS: Since I've been getting a lot of requests concerning the availability of GA+GP+EP+ES=EA software recently, I thought this might be of interest to many of you. Note the genetic/ subdirectory. ] ** ANNOUNCING ** ++++++++++++++++++++++++++++++++++++++++++ + CMU Artificial Intelligence Repository + + and + + Prime Time Freeware for AI + ++++++++++++++++++++++++++++++++++++++++++ July 1994 The CMU Artificial Intelligence Repository was established by Carnegie Mellon University to contain public domain and freely distributable software, publications, and other materials of interest to AI researchers, educators, students, and practitioners. The AI Repository currently contains more than a gigabyte of material and is growing steadily. The AI Repository is accessible for free by anonymous FTP, AFS, and WWW. A selection of materials from the AI Repository is also being published on CD-ROM by Prime Time Freeware and should be available for purchase at AAAI-94 or direct by mail or fax from Prime Time Freeware (see below). - ---------------------------- Accessing the AI Repository: - ---------------------------- To access the AI Repository by anonymous FTP, ftp to: ftp.cs.cmu.edu [128.2.206.173] and cd to the directory: /user/ai/ Use username "anonymous" (without the quotes) and type your email address (in the form "user@host") as the password. To access the AI Repository by AFS (Andrew File System), use the directory: /afs/cs.cmu.edu/project/ai-repository/ai/ To access the AI Repository by WWW, use the URL: http://www.cs.cmu.edu:8001/Web/Groups/AI/html/repository.html Be sure to read the files 0.doc and readme.txt in this directory. - ------------------------------ Contents of the AI Repository: - ------------------------------ The AI Programming Languages and the AI Software Packages sections of the repository are "complete". These can be accessed in the lang/ and areas/ subdirectories of the AI Repository. Compression and archiving utilities may be found in the util/ subdirectory. Other directories, which are in varying states of completion, are events/ (Calendar of Events, Conference Calls) and pubs/ (Publications, including technical reports, books, mail/news archives). The AI Programming Languages section includes directories for Common Lisp, Prolog, Scheme, Smalltalk, and other AI-related programming languages. The AI Software Packages section includes subdirectories for: agents/ Intelligent Agent Architectures alife/ Artificial Life and Complex Adaptive Systems anneal/ Simulated Annealing blackbrd/ Blackboard Architectures bookcode/ Code From AI Textbooks ca/ Cellular Automata classics/ Classical AI Programs constrnt/ Constraint Processing dai/ Distributed AI discover/ Discovery and Data-Mining doc/ Documentation edu/ Educational Tools expert/ Expert Systems/Production Systems faq/ Frequently Asked Questions fuzzy/ Fuzzy Logic games/ Game Playing genetic/ Genetic Algorithms, Genetic Programming, Evolutionary Programming icot/ ICOT Free Software kr/ Knowledge Representation, Semantic Nets, Frames, ... learning/ Machine Learning misc/ Miscellaneous AI music/ Music neural/ Neural Networks, Connectionist Systems, Neural Systems nlp/ Natural Language Processing (Natural Language Understanding, Natural Language Generation, Parsing, Morphology, Machine Translation) planning/ Planning, Plan Recognition reasonng/ Reasoning (Analogical Reasoning, Case Based Reasoning, Defeasible Reasoning, Legal Reasoning, Medical Reasoning, Probabilistic Reasoning, Qualitative Reasoning, Temporal Reasoning, Theorem Proving/Automated Reasoning, Truth Maintenance) robotics/ Robotics search/ Search speech/ Speech Recognition and Synthesis testbeds/ Planning/Agent Testbeds vision/ Computer Vision The repository has standardized on using 'tar' for producing archives of files and 'gzip' for compression. - ------------------------------------ Keyword Searching of the Repository: - ------------------------------------ To search the keyword index by mail, send a message to: ai+query@cs.cmu.edu with one or more lines containing calls to the keys command, such as: keys lisp iteration in the message body. You'll get a response by return mail. Do not include anything else in the Subject line of the message or in the message body. For help on the query mail server, include: help instead. A Mosaic interface to the keyword searching program is in the works. We also plan to make the source code (including indexes) to this program available, as soon as it is stable. - ----------------------------------------- Contributing Materials to the Repository: - ----------------------------------------- Contributions of software and other materials are always welcome, but must be accompanied by an unambiguous copyright statement that grants permission for free use, copying, and distribution, such as: - a declaration that the materials are in the public domain, or - a copyright notice that states that the materials are subject to the GNU General Public License (cite version), or - some other copyright notice (we will tell you if the copying permissions are too restrictive for us to include the materials in the repository) Inclusion of materials in the repository does not modify their copyright status in any way. Materials may be placed in: ftp.cs.cmu.edu:/user/ai/new/ When you put anything in this directory, please send mail to ai+contrib@cs.cmu.edu giving us permission to distribute the files, and state whether this permission is just for the AI Repository, or also includes publication on the CD-ROM version (Prime Time Freeware for AI). We would appreciate if you would include a 0.doc file for your package; see /user/ai/new/package.doc for a template. (If you don't have the time to write your own, we can write it for you based on the information in your package.) - ------------------------------------ Prime Time Freeware for AI (CD-ROM): - ------------------------------------ A portion of the contents of the repository is published annually by Prime Time Freeware. The first issue consists of two ISO-9660 CD-ROMs bound into a 224-page book. Each CD-ROM contains approximately 600 megabytes of gzipped archives (more than 2 gigabytes uncompressed and unpacked). Prime Time Freeware for AI is particularly useful for folks who do not have FTP access, but may also be useful as a way of saving disk space and avoiding annoying FTP searches and retrievals. Prime Time Freeware helped establish the CMU AI Repository, and sales of Prime Time Freeware for AI will continue to help support the maintenance and expansion of the repository. For further information on Prime Time Freeware for AI and other Prime Time Freeware products, please contact: Prime Time Freeware 370 Altair Way, Suite 150 Sunnyvale, CA 94086 USA Tel: +1 408-433-9662 Fax: +1 408-433-0727 E-mail: ptf@cfcl.com - ---------------------- Repository Maintainer: - ---------------------- The AI Repository was established by Mark Kantrowitz in 1993 as an outgrowth of the Lisp Utilities Repository (established 1990) and his work on the FAQ (Frequently Asked Questions) postings for the AI, Lisp, Scheme, and Prolog newsgroups. The Lisp Utilities Repository has been merged into the AI Repository. Bug reports, comments, questions and suggestions concerning the repository should be sent to Mark Kantrowitz . Bug reports, comments, questions and suggestions concerning a particular software package should be sent to the address indicated by the author. ------------------------------ From: mlevin@husc.harvard.edu Date: Wed, 27 Jul 94 21:18:03 -0400 Subject: Looking for functions I am looking for 2 functions of 10 (or so) variables, to use in a GA which will optimize (maximize or minimize, whichever) these functions. This will be part of an experiment, and I want these two functions to have the following properties: 1) both should not be too easy, but also should be GA-solvable (i.e., I am not looking for examples of GA-resistant functions, but I want the GA to spend a significant time on them - on the order of 100 to 1000 generations). 2) One of the functions should be straight-forward building-block stuff - that is, the goodness of fit of each of the variables should be independent of the others, so that each one can be tuned independently and good schemas can be recombined to form even better individuals. 3) the other function should be the opposite - is should have a highly "epigenetic" character, and the overall fitness should depend in a complex way on all of the variables, such that none of them has any fitness on its own (is dependent on all of the others). If anyone has any ideas, or knows of any "classic" functions that have these properties, please email to mlevin@husc7.harvard.edu. Thanks! ------------------------------ From: D.Savic@exeter.ac.uk Date: Tue, 2 Aug 1994 12:44:50 +0100 (BST) Subject: Report Available The following report No. 94/15 (Centre for Systems and Control Engineering, University of Exeter, U.K.) is available: AN EVOLUTION PROGRAM FOR PRESSURE REGULATION IN WATER DISTRIBUTION NETWORKS D.A. Savic and G.A. Walters University of Exeter United Kingdom ABSTRACT Leakage losses in a water distribution network increase significantly for higher pressures and an obvious way of reducing losses is by reducing network pressures. This report presents a methodology for pressure regulation in a water distribution network using an evolution program (EP), encompassing the principles of evolutionary design and genetic algorithms. The optimisation problem of minimising the pressure heads is formulated with the settings of isolating valves as decision variables and minimum allowable pressures as constraints. The problem is highly constrained both in terms of topology (i.e., it is difficult to generate feasible network layouts) and in terms of minimum pressure requirement. The EP uses integer coding and domain-specific operators to ensure creation of feasible (connected) networks and a penalty function to allow solutions infeasible with respect to the pressure constraint to guide the search. The algorithm developed incorporates a steady-state network analysis model based on the linear theory method. Computational results for two example networks demonstrating the effectiveness of the methodology are also presented. Total 42 pages Contact Address: D.Savic School of Engineering University of Exeter North Park Road, Exeter, EX4 4QF U.K. e-mail Address: D.Savic@exeter.ac.uk Tel: +44 0392 263637 Fax: +44 0392 217965 ------------------------------ From: kats@csd.sumikin.co.jp (Katsumi Hirayama) Date: Tue, 26 Jul 94 15:16:03 JST Subject: Packing problems or cutting stock problems Nice to meet you. My name is katsumi Hirayama. I work on SMI(Sumitomo Metal Industory)in Japan. I wanna get some information,study,or report that GA was aplaied to 'Packing problem or cutting stock problem'. Thank you. ************************************************************************ Mathmatical Science Section Open System Dept System Engineering Divition Sumitomo Metal Industries.LTD. Phone : 06-942-8113 or 8114 (Dial-In) FAX : 06-942-8115 E-mail : kats@osa.sumikin.co.jp ************************************************************************ ------------------------------ From: Dagmar Mack Date: Wed, 27 Jul 1994 09:32:17 +0100 Subject: GA/EA-Tool? Hello anonymous! Could anybody give me a hint where I can get a GA-Tool with emphasis on economic applications (the best would be for free)? We still got a tool 'GENESIS' which is written in C. We need a tool which runs on a PC (386) and it should be written in PASCAL (for all of our students learn PASCAL and not C). The tool is for academic use only! Thank's in advance to anybody who is going to answer! Bye Dagmar Universitaet Dortmund Telefon 0049 (0)231 7553112 Fakultaet WiSo Telefax 0049 (0)231 7553158 Lehrstuhl Wirtschaftsinformatik Street: Vogelpothsweg 87 Dipl. Wirt.-Ing. Dagmar Mack D-44227 Dortmund D-44221 Dortmund ------------------------------ From: mdlm@ai.mit.edu (Michael de la Maza) Date: Wed, 3 Aug 94 16:31:18 EDT Subject: Dynamic Hill Climbing papers available Dynamic hill climbing is an optimization algorithm that has outperformed the standard genetic algorithm, Ingber & Rosen's adaptive simulated annealing, and Powell's method on several problems, both artificial and real-world. A packet of three papers that describe dynamic hill climbing is available by sending a physical mail address to: dhc@ai.mit.edu. The abstract of one of those papers reads: The work described began as an inquiry into the nature and use of optimization programs based on "genetic algorithms." That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent. These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data. ------------------------------ End of Genetic Algorithms Digest ******************************