Genetic Algorithms Digest Wednesday, June 28, 1995 Volume 9 : Issue 37 - 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: - New GA Library Available - GA solves Game Theory? (Re: v9n36) - Game Theory (Re: v9n36) - Bin-Packing and GA - Boolean Satisfiability Problem (SAT) (Re: v9n36) - IlliGAL Announcement (6-26-95) - GAs/simulated annealing comparisons (Re: v9n36) ---------------------------------------------------------------------- ******************************************************************************* 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: David Levine Date: Thu, 22 Jun 1995 18:26:49 -0500 Subject: New GA Library Available PGAPack is a general-purpose, data-structure-neutral, parallel genetic algorithm library being developed at Argonne National Laboratory. PGAPack V0.2, a sequential beta version that runs on many 32-bit workstations, is being made available for early access and comment. This version has the following features: * Callable from Fortran or C. * Binary-, integer-, and real-valued native data types * Object-oriented data structure neutral design. * Parameterized population replacement. * Multiple choices for selection, crossover, and mutation operators * Easy integration of hill-climbing heuristics. * Black-box interface for novice and application users. * Access to all library calls for expert users. * Fully extensibile to support custom operators and new data types. * Extensive debugging facilities * A large set of example programs. * A users guide. PGAPack is available via anonymous ftp from info.mcs.anl.gov in the file pub/pgapack/pgapack.tar.Z. (Be sure to ftp it in binary mode.) As an example, below is a simple PGAPack program to solve the Maxbit problem. #include "pgapack.h" double evaluate ( PGAContext *ctx, int p, int pop ); int main( int argc, char **argv ) { PGAContext *ctx; ctx = PGACreate (&argc, argv, PGA_DATATYPE_BINARY, 100, PGA_MAXIMIZE); PGASetUp (ctx); PGARun (ctx, evaluate); PGADestroy (ctx); } double evaluate ( PGAContext *ctx, int p, int pop ) { int i, nbits=0, stringlen; stringlen = PGAGetStringLen(ctx); for ( i=0; i Date: Fri, 23 Jun 1995 09:14:25 -0600 (MDT) Subject: Game Theory (Re: v9n36) Concerning David Burns posting on game theory. There is a game theory literature about "fictitious play", which is an iterative process whose dynamics are related to the Nash equilibrium(a). I am not sure, but I think that the long run frequency distribution of fictitious play is related to a mixed strategy equilibrium. If so, one would not expect a GA to converge if there is a unique Nash equilibrium, which is in mixed strategies. Mark B. Cronshaw, Dept. of Economics Tel. (303) 492-6310 University of Colorado Fax (303) 492-8960 Boulder, CO 80309-0256 ------------------------------ From: kats@osa.sumikin.co.jp Date: Sat, 24 Jun 1995 18:12:59 +0900 Subject: Bin-Packing and GA Hi to everyone, I am new at the GA Digest List. I am warking on SUMITOMO METAL INDUSTRIES, LTD. Thesis on writting a paper, which title is A Genetic Algorithm for Applying SlabDesign problem. Slab Design is a kind of Bin-packing Problem. Then, I try to seach the paper applied Bin-packing problem to GA. My GA is the Hybrid from GA and heuristics. Slab Design is a part of real production system at steel works. This problem is to solve the combination of given Order plates, and to decide the slabs size and the total number of Slabs. And, we could get the better solution than past method(B&B + Heuristics) by using GA. If you know of any such an approach or a reference where the problem is discussed or would like to comment of the previous options or all of the above, please send me e-mail(kats@osa.sumikin.co.jp). I'm sorry I can't write in English well. Sincerely, Katsumi Hirayama Mathmatical Science Section Open System Dept System Engineering Divition Sumitomo Metal Industries.LTD. ------------------------------ From: fleurent@IRO.UMontreal.CA (Charles Fleurent) Date: Mon, 26 Jun 1995 10:35:54 -0400 Subject: Boolean Satisfiability Problem (SAT) (Re: v9n36) Steve, Bill, I just want to mention the following paper that deals with GAs and SAT. The paper will appear in the second DIMACS Challenge special issue, edited by M. A. Trick and D. S. Johnson. TITLE: Object-Oriented Implementation of Heuristic Search Methods for Graph Coloring, Maximum Clique, and Satisfiability AUTHORS: Charles Fleurent and Jacques A. Ferland ABSTRACT: Using object-oriented design and the C++ programming language, generic operators are developed for tabu search and genetic algorithms. These operators are used for the graph coloring, maximum clique and satisfiability problems. The availability of all methods for each problem allows us to consider hybrid schemes. This paper is available by anonymous ftp at: ftp.iro.umontreal.ca in the directory: pub/optim/fleurent/papers/dimacs Charles |Charles Fleurent | Telephone: (514) 343-6111 # 3549 | |Universite de Montreal, Dep. I.R.O. | Fax: (514) 343-5834 | |C.P. 6128, Succursale Centre-Ville | E-mail: fleurent@iro.umontreal.ca | |Montreal (Quebec) H3C 3J7. | | ------------------------------ From: jhorn@gal11.ge.uiuc.edu (Jeff Horn) Date: Mon, 26 Jun 95 13:13:52 CDT Subject: IlliGAL Announcement (6-26-95) IlliGAL ANNOUNCEMENT 6/26/95 (Last Announcement, 4/22/95) The Illinois Genetic Algorithms Laboratory (IlliGAL) is pleased to announce the publication of new technical reports and papers, and the recent availability, on our server, of an older technical report. Most IlliGAL technical reports, as well as reprints of other publications, are available in hardcopy and can be ordered from the IlliGAL librarian, (see below for ordering information). Those papers marked with an asterisk (*) are also available electronically on our ftp and WWW server (see the end of this announcement for ftp and WWW access instructions). (1) NEW 1995 IlliGAL REPORTS: IlliGAL Report No 95003* (91 pp.) TITLE: Organizational Learning Within a Learning Classifier System AUTHOR: Jason R. Wilcox ABSTRACT: This thesis recasts the debate between Michigan-style and Pitt-style classifier systems to a debate on appropriately sizing organizations within a learning classifier system. Motivated by the economic study of transaction costs, an organizational classifier system (OCS) combining explicit use of multiple reputation values and organization sizing operators better distinguishes parasitic (less than optimal) classifiers than a simple classifier system (SCS). The results show that by building a system that autonomously adjusts the degree of individual to collective behavior, it is possible for it to be both efficient and resilient to problem difficulty. (a masters thesis from the University of Illinois) (anonymous ftp: GAL4.GE.UIUC.EDU/pub/papers/IlliGALs/95003.ps.Z) (WWW URL: http://GAL4.GE.UIUC.EDU/orderform.html) IlliGAL Report No 95002* (24 pp.) TITLE: Critical Deme Size for Serial and Parallel Genetic Algorithms AUTHOR: David E. Goldberg, Hillol Kargupta, Jeffrey Horn, and Erick Cantu-Paz ABSTRACT: This paper investigates the possibility of gaining any computational benefit from multiple deme, small population GAs compared to a single large population GA. Our framework is based on an earlier decision theoretic framework developed by Goldberg, Deb and Clark (1992) for population sizing. Our analysis and empirical results for different bounding cases of multiple deme GAs, reveal a critical population size below which the computational cost (of good performance) goes up very sharply. However this critical size turns out to be less than the baseline population size (Goldberg, Deb, and Clark, 1992) by a moderate factor. We therefore recommend only a moderate reduction of population size from a base line population size. Our analysis also presents a methodology for optimizing GA experimental setups for different machine architectures, from serial to coarse and fine-grain parallelization. This paper also shows that linear speed up for parallel machines can be accomplished without sacrificing the solution quality even for isolated demes (i.e., no migration). (anonymous ftp: GAL4.GE.UIUC.EDU:/pub/papers/IlliGALs/95002.ps.Z) (WWW URL: http://GAL4.GE.UIUC.EDU/orderform.html) IlliGAL Report No 95001* (251 pp.) TITLE: Niching Methods for Genetic Algorithms AUTHOR: Samir W. Mahfoud ABSTRACT: - Abstract included in last IlliGAL announcement (4/22/95) - (a PhD dissertation from the University of Illinois) (anonymous ftp: GAL4.GE.UIUC.EDU:/pub/papers/IlliGALs/95001.ps.Z) (WWW URL: http://GAL4.GE.UIUC.EDU/orderform.html) (2) NEW PUBLICATIONS: Mahfoud, S. W., & Goldberg, D. E. (1995). Parallel recombinative simulated annealing: a genetic algorithm. Parallel Computing 21. 1-28. (reprints available as hardcopy only, but earlier version available online as IlliGAL 93006*) This paper introduces and analyzes a parallel method of simulated annealing. Borrowing from genetic algorithms, an effective combination of simulated annealing and genetic algorithms, called {\em parallel recombinative simulated annealing}, is developed. This new algorithm strives to retain the desirable asymptotic convergence properties of simulated annealing, while adding the populations approach and recombinative power of genetic algorithms. The algorithm iterates a population of solutions rather than a single solution, employing a binary recombination operator as well as a unary neighborhood operator. Proofs of global convergence are given for two variations of the algorithm. Convergence behavior is examined, and empirical distributions are compared to Boltzmann distributions. Parallel recombinative simulated annealing is amenable to straightforward implementation on SIMD, MIMD, or shared-memory machines. The algorithm, implemented on the CM-5, is run repeatedly on two {\em deceptive} problems to demonstrate the added {\em implicit parallelism} and faster convergence which can result from larger population sizes. Deb, K., & Goldberg, D. E. (1994). Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence 10. 385-408. (reprints available as hardcopy only, but earlier version available online as IlliGAL Report No. 92001*.) This paper finds sufficient conditions for fully or partially deceptive binary functions by calculating schema average fitness values. Deception conditions are first derived for functions of unitation (functions that depend only on the number of 1s in the string) and then extended for any binary function. The analysis is also extended to find a set of sufficient conditions for fully easy binary functions. It is found that the computational effort required to investigate full or partial deception in a problem of size l using these sufficient conditions is O(2^l) and using all necessary conditions of deception is O(4^l). This calculation suggests that these sufficient conditions can be used to quickly test deception in a function. Furthermore, it is found that these conditions may also be systematically used to design a fully deceptive function by performing only O(l^2) comparisons and to design a partially deceptive function to order k by performing only O(kl) comparisons. The analysis shows that in the class of functions of unitation satisfying these conditions of deception, an order-k partially deceptive function is also partially deceptive to any lower order. Finally, these sufficient conditions are used to investigate deception in a number of currently-used deceptive problems. (3) NEWLY AVAILABLE "Old" IlliGAL REPORT: IlliGAL Report No 90001* (18 pp.) Title: Real-coded Genetic Algorithms, Virtual Alphabets, and Blocking Author: David E. Goldberg (Figures and cover page are missing from electronic version but are included in hardcopy version. Final version available as publication [1] on IlliGAL orderform.) (anonymous ftp: GAL4.GE.UIUC.EDU:/pub/papers/IlliGALs/90001.ps.Z) RETRIEVAL/ORDERING: The above IlliGAL reports and publications, along with other publications and source code, are available electronically via FTP or WWW, or as hardcopy directly from us: FTP: ftp GAL4.GE.UIUC.EDU login: anonymous password: (your email address) cd /pub/papers/IlliGALs (for reports) or cd /pub/papers/Publications (for preprints) or cd /pub/src (for GA and classifier system source code) binary get 95003.ps.Z (for example) bye Then on your machine (for papers): uncompress 95003.ps.Z lpr -P(your postscript queue) 95003.ps Please look at the README files for explanations of what the file names mean. IlliGAL reports are all compressed postscript files. WWW: To access the IlliGAL home page, open URL (Uniform Resource Locator) http://GAL4.GE.UIUC.EDU/illigal.home.html (To get X binaries for Mosaic, ftp to ftp.ncsa.uiuc.edu, cd Mosaic, cd Mosaic-binaries, get the appropriate platform's binaries. For the Mac binaries, ftp to ftp.ncsa.uiuc.edu, cd Mac, cd Mosaic, go from there.) HARDCOPY: You can still order hardcopy versions of most IlliGAL publications (including, in particular, those not yet on the server!). See the IlliGAL order form (via WWW, below, or as file "orderform.ps" or "orderform.text" on the ftp server), or request them directly (by IlliGAL number or title) from the IlliGAL librarian: Internet: library@GAL1.GE.UIUC.EDU Phone: 217/333-2346 Surface mail: IlliGAL Librarian Department of General Engineering 117 Transportation Building 104 South Mathews Avenue Urbana, IL 61801-2996 USA When ordering hardcopy, please include your surface mail address! Note that the file "orderform.ps" in /pub/papers on the ftp server is the IlliGAL order form and contains a (nearly) complete listing of IlliGAL reports and other publications to date. Jeffrey Horn jeffhorn@uiuc.edu Illinois Genetic Algorithms Laboratory (jhorn@GAL1.GE.UIUC.EDU) University of Illinois at Urbana-Champaign 117 Transportation Building Day Phone: 217/333-2346 104 South Mathews Avenue Fax: 217/244-5705 Urbana, IL 61801-2996 USA ------------------------------ From: Jarmo Alander Date: Sat, 24 Jun 1995 10:26:31 +0300 Subject: GAs/simulated annealing comparisons (Re: v9n36) Dear All, Our Indexed GA Bibliographies Collection now includes "An Indexed Bibliography of Genetic Algorithms and Simulated Annealing: Hybrids and Comparisons" containing over 90 references. The file is compressed PostScript and available via anonymous ftp (ftp.uwasa.fi) directory: cs/report94-1 file: gaSAbib.ps.Z. Yours, Jarmo Alander University of Vaasa, Finland PS. The directory also contain a few other such bibs. [ WMS: Thanks, Jarmo! Jarmo also sent me a list of pubs, but it was quite long - I have placed it on ftp.aic.nrl.navy.mil under pub/galist/info/GA-SA.comparison.refs. Now, who is going to read all these papers and summarize the results? Volunteers? ;-) ] ------------------------------ End of Genetic Algorithms Digest ******************************