Genetic Algorithms Digest Tuesday, May 10, 1994 Volume 8 : Issue 15 - 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 (Info in /pub/galist/FTP) Today's Topics: - Applications of GA to SPP/SCP problems (Re: v8n8) - 2 messages - Response to Evolver 2.0 Query (Re: v7n28) - 2D encoding query - info request - request: ga, TSP, and large numbers of cities ? - Postdoc - classifier systems and branch prediction? - evolutionary Fuzzy-systems - Bin Packing test cases & benchmarks - Long bit strings - AI'94 Workshop on Evolutionary Computation ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) The IEEE Conference on Evolutionary Computation, Orlando(v7n26) Jun 26-30, 94 FOGA94 Foundations of GAs Wkshop, Estes Park, Colorado(v7n26)Jul 30-Aug 3, 94 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 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 AI'94 Workshop on Evol Comp, Armidale, NSW, Australia (v8n15) Nov 22, 94 EP95 4th Ann Conf on Evolutionary Programming, San Diego,CA(v8n6) Mar 1-4, 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 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: nagar@server.uwindsor.ca (Nagar Amit) Date: Fri, 8 Apr 94 11:52:38 -0400 Subj: Applications of GA to SPP/SCP problems (Re: v8n8) In response to my query about the applications of GA to SPP/SCP problems, I received the following responses which I would like to share with the other readers. Thanks to everyone who responded. -Amit Nagar nagar@server.uwindsor.ca From: David Levine Date: Thu, 31 Mar 1994 18:17:54 -0600 Subject: set/spp I'm hoping to finish my PhD thesis at the end of next month: "A Parallel Genetic Algorithm for the Set Partitioning Problem". I have a short paper in ICGA #5. The following references all have something avout Set Covering in them. @inbook{LiHiRiPa, author = "G. Liepins and M. Hilliard and J. Richardson and M. Palmer", editor = "D. Brown and C. White", title = "{G}enetic {A}lgorithms {A}pplications to {S}et {C}overing and {T}raveling {S}alesman {P}roblems", year = "19XX", booktitle = "OR/AI: The Integration of Problem Solving Strategies", publisher= "XXXX", address = "XXXX", pages = "29--57" } @inproceedings{RiPaLiHi89, author = "J. Richardson and M. Palmer and G. Liepins and M. Hilliard", editor = "J. Schaffer", title = "Some {G}uidelines for {G}enetic {A}lgorithms with {P}enalty {F}unctions", booktitle = "Proceedings of the Third International Conference on Genetic Algorithms", year = "1989", publisher = "Morgan Kaufmann", Pages ="191--197" } @book{Da91, author = "L. Davis", title = "Handbook of Genetic Algorithms", publisher = "Van Nostrand Reinhold", address = "New York", year = "1991" } Finally, I don't recall it was GAs, but there is/was a Univ of Rochester tech report about parallel heuristics for SCP. regards --dave David Levine levine@mcs.anl.gov (708)-252-6735 Fax: (708)-252-5986 MCS 221 C-216 Argonne National Laboratory Argonne, Illinois 60439 From: potter@pollux.cs.uga.edu (Don Potter) Date: Fri, 1 Apr 1994 10:06:37 +0500 Subject: GA refs Hi, You should take a look at the papers by Liepins and papers by Potter (that's me) for GA set covering info. We actually address multiple fault diagnosis but it's really a set covering problem. See the Handbook of GAs , proceedings of the IEA/AIE conferences, and recent IEEE SMC journal (sept/Oct 93 vol 23 no 5, paper by Miller et. al), and the Applied Intelligence journal (vol 2, 1992). Also, please post or setup ftp access to your reference list. Thanks, Don Potter Graduate Coordinator, AI Programs and Associate Professor of Computer Science University of Georgia Athens, GA 30602-7405 potter@pollux.cs.uga.edu From: Tal Grossman Date: Fri, 1 Apr 1994 08:42:57 -0700 Subject: set covering Amit, I am currently working on Neural computation approach to the set covering problem (and on variations of the greedy algorithm). There are VERY few works on NNs for that problem and I know of know GA for purpose. There are many applications of GAs to related problems such as scheduling, general assignment, graph partitioning etc. I think GA is not a good approach for this type of problems as there is very little structure that allows the transfer of usefull information from one generation to the next. I tried all sorts of GA approaches on related problems, such as MaxClique. However, if you have a clever idea of how overcome this problem (e.g. by adding local search to the basic GA scheme) you should certainly try it. A similar approach for the MaxClique was presented at the DIMACS challenge by Fleurent and Ferland (they have found that even such a hybrid is outperformed in most cases by tabu search). You may also be interested in general approaches to such strategies like: "Hybrid Genetic Algorithms for Bin-Packing and related Problems" - Colin Reeves (preprint, contact crreeves@uk.ac.cov), or "Towards Solving Subset Selection Problems with the Aid of the Genetic Algorithm" - Lucasius and Kateman, in Parallel Problem Solving from Nature II, Manner and Manderick (Eds), Elsevier 1992. In any case, I would be very interested in what you find, both in your literature search and in your experiments with the problem. With a friend at the Weizmann Inst. we intend to make an experimental study of different algs. for the set covering (greedy, NNs, and other algs based on linear programming). It would be nice to add GAs to the party. We already have a set of benchmarks, and welcome any addition to our test suite - so if you have any such instances, I will also be interested. The situation so far is that the simple greedy heuristic (or simple variations of it) is doing very well on most of the problems... Other more sophisticated algorithms have very hard time trying to beat it. We keep on trying. Good Luck with your trials, yours - Tal Grossman From: rogerw@penguin.mcs.utulsa.edu (Roger Wainwright) Date: Fri, 1 Apr 94 11:52:11 cst Subject: GA set covering and Partition problems My students and have published several papers using GAs for solving the set covering and various partitioning problems. We do not have them available in electronic form as yet, but I will be happy to mail it to you by surface mail. Our work involves set covering, graph bisection, triangulation of a point set, and k-way graph bisection Give me your mailing address, and I wil send the papers to you. Roger L. Wainwright Associate Professor and Chairman of Computer Science Department of Mathematical and Computer Sciences University of Tulsa 600 South College Ave. Tulsa, OK 74104-3189 Ph: (918) 631-3143 Fax: (918) 631-3077 rogerw@penguin.mcs.utulsa.edu ------------------------------ From: Sandip Sen Date: Fri, 1 Apr 1994 14:25:28 -0600 Subject: Applications of GA to SPP/SCP problems (Re: v8n8) In v8n8 of GA Digest Amit Nagar (nagar@server.uwindsor.ca) inquires about applications of GA to set covering/partition problems. In the following paper, I have compared the performance of a simple GA and an automatic schedule simulated annealing algorithm on a class of randomly generated set covering problems: Sandip Sen, "Minimal cost set covering using probabilistic methods," Proc. 1993 ACM/SIGAPP Symposium on Applied Computing, pages 157-164, 1993. In the same proceedings, you will find the following paper which also uses the set covering problem for illustrating the usefulness of infeasible solutions in GA search: D. Ansa Sekharan and Roger L. Wainwright, "Manipulating Subpopulations of Feasible and Infeasible Solutions in Genetic Algorithms," Proc. ACM/SIGAPP Symposium on Applied Computing, pages 118-125, 1993. Sandip Sen Department of Mathematical & Computer Sciences, University of Tulsa, 600 South College Avenue, Tulsa, OK 74104-3189. ------------------------------ From: cscbp@knuth.mtsu.edu (Dr. Chris Pettey) Date: Fri, 15 Apr 1994 11:26:56 -0500 (CDT) Subject: Response to Evolver 2.0 Query Several months ago I posted a query for users of Evolver. I got two responses--both negative--so my colleague decided against buying. I am including both responses here in case anyone is interested. Chrisila Pettey (cscbp@knuth.mtsu.edu) Return-Path: From: Don Kummer Subject: Evolver 2.0 Chris, In response to your GA-list query regarding Evolver 2.0, I have used the product in a classroom setting as an illustration of a non-linear solution technique. Beyond setting the crossover and mutation rate there's not much one can do to alter the system. Even the population generation (ie number) is proprietary. I've spoken to the developers on a couple of occasions. In my area - Finance -- it provided an adequate illustration. But for someone in mgmt. science or interested in research, it would not be a good investment. Don Kummer School of Business University of Missouri - St. Louis 314-553-6270 voice Return-Path: From: William Fulkerson My Company is listed as a satisfied user of Evolver on their promotional literature. However, I have yet to meet anyone that has made a successful application. The range of people this includes is from VP of Finance, pension fund portfolio manager, ..., engineer. In my recent work, the Excel Solver add-in has been more than adequate and faster than Evolver. BILL ------------------------------ From: "Andrew Hall" Date: Fri, 15 Apr 94 14:09:25 BST Subject: 2D encoding query Has anyone considered encodings which are in more than one dimension? For instance, a real number is often encoded as a binary word, which is intrinsically a one dimensional encoding. What about problems where an encoding could be two dimensional, ie a grid of bits? I wonder how a GA could be adapted to cope with this, and whether there are problems that exist that are somehow more amenable to some kind of 2D encoding. Any ideas? Andy Hall andrewh@logcam.co.uk Logica Cambridge Ltd +44 223 66343 Ext. 4878 Betjeman House 104 Hills Road Cambridge CB2 1LQ. ------------------------------ From: greenwoo@lab.cc.wmich.edu (GREENWOOD GARRISON) Date: Wed, 6 Apr 94 21:46:44 EDT Subject: info request I am beginning to investigate the use of genetic algorithms or evolutionary strategies to solve the preventative maintenance (PM) scheduling problem. This problem is a variation of the time schedule problem which is NP-hard. Briefly, the PM problem is 1. There are N preventative maintenance tasks. Associated with each task is a list of the specific required skills (e.g., mechanic or electrician). 2. Tasks are not preemptable. 3. Only workers with the appropriate skills can be assigned to a task. 4. A worker cannot be assigned to more than one task at a time. Also, once assigned, the worker cannot be reassigned until the task is completed. 5. A list of workers (and their skills) is given. Objective: Find an appropriate assignment of workers to tasks such that all tasks can be completed in minimum time. I am interested in finding out if someone has done any work on this type of problem. I am particularly interested in knowing the chromosome definition and the genetic operators that were used. Thanks, Garry garry.greenwood@wmich.edu ------------------------------ From: thorsten@archsci.arch.su.EDU.AU Date: Fri, 8 Apr 1994 17:00:16 +1000 Subject: request: ga, TSP, and large numbers of cities ? In his book about genetic algorithms [1], Michalewicz dedicates a whole chapter to different ga approaches to the travelling salesman problem. All the papers he lists try to code every single point (or edge) into the genotytpe. For a large number of points, Michalewicz mentions applications with as many as 1.2 million cities, this clearly is not a useful approach. One way to deal with high numbers of cities is to use a divide-and-conquer algorithm. Litke [2] presented such an algorithm, using local optimization for clusters with up to 10 cities (or subclusters). I would like to know if someone has developed approaches to tsp's with large numbers of cities using combinations of ga's and divide-and-conquer algorithms (or is currently doing so). And what algorithms are currently used for applictions with high numbers of cities (i.e. what is 'state-of-the-art')? Thanks in advance Thorsten Schnier References: 1: Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs Springer Verlag Berlin Heidelberg 1992 2: Litke, J.D.: An Improved Solution to the travelling salesman problem with thousands of nodes, Communications of the ACM, Vol.27, No.12, pp1227-1236, 1984 Thorsten Schnier Key Centre of Design Computing University of Sydney NSW 2006 thorsten@archsci.arch.su.edu.au ------------------------------ From: Stewart Wilson Date: Thu, 21 Apr 94 14:42:21 EDT Subject: Postdoc I would be interested in communicating with anyone completing a PhD and interested in doing a postdoc combining classifier systems and genetic programming. Stewart Wilson ------------------------------ From: "Theodore C. Belding" Date: Thu, 21 Apr 1994 20:53:18 +0100 Subject: classifier systems and branch prediction? Does anyone know of any work done on implementing branch prediction (in computer architecture) using classifier systems? How about implementing classifier systems in hardware (e.g., multiplexers, etc.)? Thanks in advance! Ted Belding Ted.Belding@umich.edu or streak@engin.umich.edu 415 Lawrence, Apt. 6, Ann Arbor, MI 48104 USA Phone: +1 313 994 9573 "Modern computing is basically a glamour industry." - Bruce Sterling ------------------------------ From: vasseur@uni-muenster.de Date: Tue, 26 Apr 1994 13:10:18 +0200 (MES) Subject: evolutionary Fuzzy-systems As as a french student of economy at the Fachhochschule Muenster (Germany), I' ve started to take my diploma. The subjet of my dissertation is "the evolving of fuzzy-systems with help of genetic algorithms and evolution-strategys, the possible applications in management and business, perspectives and limits. While there exist no collected works in the german speaking area, I would be thankfull, if anybody could give me some information about scientific works or paper concerning my subject. Obviously, I will look for more information by myself and I' ll place my research to everybody disponal. Thanks Pierre-Andre Vasseur Email:vasseur@uni-muenster.de. ------------------------------ From: rhh@matilda.vut.edu.au (Robert Hinterding) Date: Sun, 17 Apr 94 16:16:23 EST Subject: Bin Packing test cases & benchmarks In my research in grouping GAs, I have come across a new way of solving the Bin Packing problem using GAs. I would like to know of any test cases or benchmarks for this problem. Also references for other GA methods to solve this problem would be welcome. I know of the work done by Emanuel Falkenauer and Kate Juliff. Robert Hinterding VICTORIA UNIVERSITY OF TECHNOLOGY Email: rhh@matilda.vut.edu.au P.O. Box 14428, Melb Mail Centre Fax: +61 3 688 4050 AUSTRALIA 3000 Phone: +61 3 688 4686 ------------------------------ From: David Levine Date: Tue, 19 Apr 1994 09:40:58 -0500 Subject: Long bit strings I'm looking for references to the longest bit strings that people have applied GAs to. I've been working on set partitioning problems which have a natural binary representation. Real world problems (primarily from airline crew scheduling) typically have hundreds to tens of thousands of columns (bits). Thanks --dave levine David Levine levine@mcs.anl.gov (708)-252-6735 Fax: (708)-252-5986 MCS 221 C-216 Argonne National Laboratory Argonne, Illinois 60439 ------------------------------ From: xin@cspyr0.cs.adfa.oz.au (Xin Yao) Subject: AI'94 Workshop on Evolutionary Computation Date: Fri, 8 Apr 1994 14:27:12 +1000 (EST) CALL FOR PAPERS AND PARTICIPATIONS AI'94 WORKSHOP ON EVOLUTIONARY COMPUTATION Armidale, NSW, Australia, 22 November 1994 SCOPE AI'94 Workshop on Evolutionary Computation will be held as part of AI'94 (The Seventh Australian Joint Conference on Artificial Intelligence) on 21--25 November 1994 in Armidale, NSW, Australia. People from all areas of evolutionary computation are encouraged to participate in and submit their papers to the workshop. The first such workshop was held on 16 November 1993 in Melbourne, Australia, as the AI'93 Workshop on Evolutionary Computation. Evolutionary computation is the study of computational systems which use ideas and get inspirations from natural evolution and adaptation. Topics of this workshop include, but are not limited to: + Classifier Systems and Other Evolutionary Learning Systems + Evolutionary Artificial Neural Networks + Hybrid Learning Systems + Comparisons Between Different Learning Systems + Evolutionary Optimisation + Self-Organisation + Collective Behaviour + Complexity in Evolutionary Systems + Artificial Life + Evolutionary Approach to Autonomous Robots + Theories of Evolutionary Computation + Parallel Implementations + Applications PAPER SUBMISSION AND PUBLICATION Authors are invited to submit original papers describing experimental and/or theoretical results from all areas of evolutionary computation. Four hard copies of the *full* paper with no more than 25 11pt single-spaced, single-column pages should be submitted to the following address before *8 August 1994*. Dr X. Yao Department of Computer Science University College, The University of New South Wales Australian Defence Force Academy, Canberra, ACT 2600, Australia Email: xin@csadfa.cs.adfa.oz.au Phone: +61 6 268 8819 Fax: +61 6 268 8581 Authors are strongly encouraged to prepared their manuscripts in LaTex. You may obtain the style file from the publisher's server svserv@vax.ntp.springer.de under directory /tex/latex. The file name is llncs.zip. All accepted papers will be published by Springer-Verlag as a volume in Lecture Notes in Artificial Intelligence. Authors of accepted papers are expected to present their papers at the workshop. Notification to authors will be sent out on *12 September 1994*. The revised final papers should be submitted before *17 October 1994* in order to be included in the proceedings. WORKSHOP ORGANISING COMMITTEE A/Prof D. Abramson Griffith University Dr E. Lewis University College, UNSW, ADFA Dr B. Marksj\"{o} CSIRO DBCE, Melbourne Dr H.B. Penfold University of Newcastle Dr X. Yao (Chair) University College, UNSW, ADFA IMPORTANT DATES 8 August 1994 Submission of full papers 12 September 1994 Notification of acceptance/rejection to authors 17 October 1994 Submission of revised final papers ------------------------------ End of Genetic Algorithms Digest ******************************