Genetic Algorithms Digest Thursday, June 22, 1995 Volume 9 : 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: - simulated annealing refs. - GA-Archives (GA-List archives) update - GA solves Game Theory? - Boolean Satisfiability Problem - Re: Boolean Satisfiability Problem (SAT) ---------------------------------------------------------------------- ******************************************************************************* CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) ACAI95 Advanced Course on AI, Perros-Guirec, France (v9n34) Jun 29-Jul 6, 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 SOCONF95 Self-Organization of Complex Structure, Berlin (v9n30) Sep 24-28, 95 MENDEL95 130th Anniversary of Mendels Laws, Brno, Czech (v9n28) Sep 26-28, 95 Towards Evolvable Hardware Intl Wrkshp, Lausanne, Switz (v9n29) Oct 2-3, 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 WWW95 on Fuzzy Logic and NNs/Evol Comp, Nagoya, Japan (v9n6) Nov 14-15, 95 ICEC95 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 SAC96 Symposium on Applied Computing GA & Opt Track, PA (v9n33) Feb 17-19, 96 EP96 5th Conf on Evol Programming, San Diego, CA (v9n18) Feb 29-Mar 3, 96 ACEDC96 Adaptive Computing in Eng. Design & Control, UK (v9n28) Mar 26-28, 96 SOCO96 Intl Symposia w/ Workshops/Tutorials, Reading, UK (v9n35)Mar 26-28, 96 ICEC96 IEEE Intl Conf on Evol Comp, Nagoya, Japan (v9n18) May 20-22, 96 IPMU96 Granada, Spain (v9n31) Jul 1-5, 96 GP96 Genetic Programming Conference, Stanford, CA (v9n9) Jul 28-31, 96 SAB96 From Animals to Animats, Cape Cod, Massachusetts (v9n31) Sep 9-13, 96 PPSN96 Parallel Problem Solving from Nature, Berlin (v9n17) Sep 22-27, 96 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ******************************************************************************* ------------------------------ From: fogel@ece.ucsd.edu (Fogel) Date: Thu, 15 Jun 95 16:54:36 PTD Subject: simulated annealing refs. In response to Garry Greenwood's posting on 6/15/95: Dear Colleagues: In the ga-digest posted 6/15/95, Garry Greenwood asked for articles comparing GAs with simulated annealing in general. Two comparison papers that I am aware of are: WL Goffe, GD Ferrier, and J Rogers (1994) "Global optimization of statistical functions with simulated annealing," J. of Econometrics, 60, 65-99. L Ingber and B Rosen (1992) "Genetic algorithms and very fast simulated annealing -- a comparison," Math. and Comp. Model., 16, 87-100. Neither of these comparisons favor genetic algorithms. Garry Greenwood indicated that in all of the comparisons he has observed, evolutionary techniques (presumably speaking about GAs given the preceding paragraph of his text) have always performed at least as well if not better than simulated annealing, and with less computational effort. I think a bibliography of papers documenting such results would be appropriate given the above two papers in archive literature. I would appreciate receiving the citations for such papers. Regards, David [ WMS: And I'd be happy to post those citations, David. ] ------------------------------ From: schultz@AIC.NRL.Navy.Mil Date: Fri, 16 Jun 95 16:13:35 EDT Subject: GA-Archives (GA-List archives) update Hello, I have just completed making some changes to both the GA-List archive ftp site and the WWW pages. The most important change involves the archiving of back issues of the GA-List digests. Previously you could either retrieve a single issue, or the entire archive. You will now find additional files that contain sets of issues, and one that contains just the most recent volume. This will make it easier and more efficient for you to keep an up to date mirror of the archive. If you have not tried WWW access yet, you will find that it is an easier way to navigate around the information in the archives, and that it contains more information than the anonymous ftp access. To access our Web pages, look at URL http://www.aic.nrl.navy.mil/galist/ To access out ftp pages, anonymous ftp to ftp.aic.nrl.navy.mil and look in /pub/galist. --Alan C. Schultz, GA-Archive maintainer ------------------------------ From: tburns@uhunix.uhcc.Hawaii.Edu (T. David Burns) Date: Mon, 19 Jun 1995 09:51:00 -1000 Subject: GA solves Game Theory? I have some results on using the GA to solve simple game theory problems. Is anyone aware of anyone else having done something like this? I am not able to find anything in the library on it after a cursory search. Axelrod (1) set inquiries moving in this direction, with others following suit. Axelrod used a GA to evolve strategies that could beat Tit-For-Tat in an environment of "representative strategies" from his tournament. He also used it to see what sort of strategies evolve when IPD tournament scores are used as the GA's fitness function. Miller(2), several papers by Marks(3), and Stanley et al(4) are among the published work in this area. But none of them mention doing basic benchmarks to see whether a GA can solve "simple" game theory problems in an appropriate way, let alone the more ambitious and ambiguous iterated game problems to which they apply it. I performed several simple simulations to test whether a plain GA would converge upon the standard game theory solutions of the common 2x2 games discussed in the game theory literature (prisoner's dilemma, coordination, etc.) Unsurprisingly, the GA had no problem converging upon unique pure strategy equilibria, and even had little difficulty choosing among multiple pure strategy equilibria. But when faced with mixed strategy equilibria, the GA oscillates in a way that can hardly be characterized as convergence (though this too may not be surprising in the light of work by DeJong (5)). So, I wonder whether these questions have not been addressed more thoroughly already, in which case I would love to be able to cite them. If not, it may be worth my while to pursue this inquiry further in hope of publishing the results more formally. David Burns 1) Robert Axelrod, "The Evolution of Strategies in the Iterated Prisoner's Dilemma," in Lawrence Davis, ed., Genetic Algorithms and Simulated Annealing (Los Altos, California: Morgan Kaufman, 1987), pp. 32-42. 2) John H. Miller, "Coevolution of Automata in the Repeated Prisoner's Dilemma," Economic Behavior and Organizations (forthcoming). 3) Richard Marks, "Breeding Hybrid Strategies: Optimal Behaviour for Oligopolists," Journal of Evolutionary Economics (1992):17-38. Richard Marks, "Repeated Games and Finite Automata," in John Creedy, et al., eds., Recent Developments in Game Theory (Brookfield, VT: Edward Elgar, 1992), pp. 43-64. Richard Marks, "Niche Strategies: The Prisoner's Dilemma Computer Tournaments Revisited," Computational Economics (forthcoming). 4) E. Ann Stanley, et al., Iterated Prisoner's Dilemma with Choice and Refusal (working paper, Iowa State University, 1992). 5) Kenneth De Jong, "Are Genetic Algorithms Optimisers?," in Proceedings of Foundations of GAs - 2 (Morgan-Kaufmann, 1992-3). ------------------------------ From: shartley@mcs.drexel.edu (Stephen J. Hartley) Date: Tue, 20 Jun 95 14:38:40 EDT Subject: Boolean Satisfiability Problem I have decided to devote some time to using GAs to solve the boolean satisfiability problem (SAT), specifically ones in conjunctive normal form (CNF). The former are NP-hard and the latter are NP-complete. The only reference I have for using GAs to solve SATs is K. A. DeJong and W. M. Spears, "Using Genetic Algorithms to Solve NP-Complete Problems," Proceedings of the 3rd International Conference on Genetic Algorithms, San Mateo, CA, June 4-7, 1989, pp. 124-132. I would like to know of other papers on using GAs to solve SATs (and if they are available by anonymous ftp). One of my motivations is that Steiner Systems (GA-list v8n47, v8n50) can be translated into SATs and also into CNF. They are very difficult to solve with GAs. I want to develop general GA techniques that can be used on any CNF SAT, including the ones derived from Steiner Systems. Thank you. Steve Hartley Math and CS Drexel University shartley@mcs.drexel.edu ------------------------------ From: spears@aic.nrl.navy.mil (William M. Spears) Date: Wed, 21 Jun 95 Subject: Re: Boolean Satisfiability Problem (SAT) Steve, thanks for the posting. I have also received other email about GAs for SAT, so my reply will be a little more general than it would be otherwise... There has been a recent upsurge in interest in SAT, as evidenced by the recent DIMACS Challenge (Mike Trick, editor). However, I have not seen many papers using GAs for SAT. My ICGA'89 and Parallel Problem Solving From Nature (PPSN'90) papers with Ken De Jong do not assume CNF. These papers are available via anonymous ftp at ftp.aic.nrl.navy.mil under pub/spears or via the Web at http://www.aic.nrl.navy.mil/~spears. The problems themselves are under pub/spears/functs on the ftp site. In 1990 the following appeared (and I think it assumes CNF): "A hybrid genetic algorithm for a logic problem", by Young, R.A. and Reel, A., in ECAI 90. Proceedings of the 9th European Conference on Artificial Intelligence, pp.744-746, Editor: Aiello, L.C. Publisher: Pitman, London, UK c1990. ISBN: 0 273 08822 X Conference Date: 6-10 Aug. 1990 Conference Location: Stockholm, Sweden Jin-Kao Hao (hao@eerie.fr) indicates to me that "There are some very interesting work under way in France concerning SAT (both complete and incomplete procedures)." He gives the following references: J.K. Hao, A Clausal Genetic Representation and its Related Evolutionary Procedures for Satisfiability Problems. Proc. of Intl. Conf. on Artificial Neural Networks & Genetic Algorithms (ICANNGA'95). Ales, France, April 1995. Springer-Verlag, pp289-292. R. Dorne and J.K. Hao, presented at Evolution Artificielle'94, Toulouse, a French National Workshop on Artificial Evolution. "Nouveaux Operators Genetiques Appliques au SAT" (New Genetic Operators Applied to SAT) He also states that "I do know some researchers who just begin to work on GA/SAT in Europe. However, no significant progress has been done (so no published papers)." Finally, I should point out that the SAT problems presented in the ICGA'89 and PPSN'90 papers are quite simple. A lot of progress has been made in defining new, large, and hard problems (the DIMACS challenge). My "Simulated Annealing for Hard Satisfiability Problems" paper (to be published in the DIMACS proceedings) includes pointers to many of the problems that were defined in the challenge. It will also mention other algorithms that show good performance (i.e., the GSAT algorithm by Bart Selman, the old Davis-Putnam procedure, branch-and-bound techniques, etc...). It would be interesting to see how a GA would fare in comparison. Can we get better results? I of course would welcome the Steiner System set of problems (as defined by Steve in the above message) to a general test suite, and I would be happy to hear of any other GA approaches to SAT! I hope this helps. Bill ------------------------------ End of Genetic Algorithms Digest ******************************