Genetic Algorithms Digest Thursday, December 15, 1994 Volume 8 : Issue 49 - Do NOT reply to or send email to gadistr@aic.nrl.navy.mil - 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 - For GA code, papers, conference announcements, GA-List back issues, etc., please use our anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL [192.26.18.68] Information is in /pub/galist/FTP Today's Topics: - Test functions (2 Messages - Re: v8n47) - How 2 classify (Re: v8n47) - Info request - CFP: 4th Int'l Golden West Conference on Intelligent systems ---------------------------------------------------------------------- **************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) 1NWGA The 1st Nordic Wrkshp on GAs & their Appl, Finland (v8n41) Jan 9-13, 95 EAs in Management Applications, Univ of Goettingen, Germany (v8n45)Feb 23, 95 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 Intl Conf on Telecommunications, Tennessee (v8n21) Mar 16-19, 95 CAD95 Computer Aided Design / "GA Day", Yalta City, CIS (v8n46) May 4-13, 95 CSCS10 10th Intl Conf on CONTROL SYSTEMS & CS, Romania (v8n37) May 24-26, 95 AISB Wrkshp on Evol Comp, Univ of Sheffield, UK (v8n45) April 3-4, 95 ICANNGA95 Intl Conf on Artificial NNs and GAs, France (v8n10) Apr 18-21, 95 IAS-95 Intelligent Adaptive Systems, Melbourne Beach FL (v8n32) April 26, 95 ECAL95 3rd European Conf on Artificial Life, Granada, Spain(v8n5) Jun 4-6, 95 GWIC95 Golden West Intl Conf on Intell Systems, San Fran(v8n49) Jun 12-14, 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) July 15-20, 95 PASE95 Wrkshp Parallel Appl in Stat and Econ, Trier (v8n39) Aug 29-Sep 2, 95 GALESIA'95 GAs in Eng Systems, Univ of Sheffield, UK (v8n45) Sept 12-14, 95 AIPetro95 AI in the Petroleum Ind, Lillehammer, Norway (v8n48) Sept 13-15, 95 ASI-AA-95 Practice and Future of Autonomous Agents (v8n19) Sep 23-Oct 1, 95 AAAI GP Symposium (Fall Series), Cambridge, MA (v8n43) Nov 10-12, 95 ICEC '95 IEEE Intl Conf on Evol. Computing, Perth (v8n36) Nov 29-Dec 1, 95 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) **************************************************************************** ------------------------------ From: shartley@mcs.drexel.edu (Stephen J. Hartley) Date: Fri, 9 Dec 94 07:43:49 EST Subject: Test functions (Re: v8n47) [ WMS: I have received personal responses from Karoly Pal and Darrell Whitley to my request for test functions. I think the following would be a nice addition as well. Starting next year I will ask people for code, in some format which will have to be decided in advance. Thanks! ] > One task I'd like to accomplish next year is to create a very > large test suite of problems for GAs. Functions F1 - F5 are clearly > showing signs of wear. Some of the newer functions have almost no > epistasis (interactions between variables). I will be able to provide > some hard problems from the boolean satisfiability community - but I'm ^^^^^^^^^^^^^^^^^^^^^^ > hoping that some of you can provide other problems of interest. The > hope is to help explain GA behaviour through a better choice of > test problems, and to help facilitate comparisons. I would like to nominate the Steiner System problem as a hard instance of the boolean satisfiability problem. (Steiner Systems are not related to Steiner trees or Steiner graphs.) The following is an excerpt from a 1993 paper on genetic algorithms and Steiner Triple Systems. S. J. Hartley and A. H. Konstam, "Using Genetic Algorithms to Generate Steiner Triple Systems," Proceedings of the 21st Annual ACM Computer Science Conference, February 16-18, 1993, pp. 366-371. For three integers $t$, $k$, $v$, where $2 \leq t < k < v$, a {\em Steiner system} $S ( t , k , v )$ is a pair $( S , V )$ where $S$ is a set of $v$ elements and $V$ is a collection of subsets of $S$, each of size $k$, such that any subset of $S$ of size $t$ is contained in exactly one member of $V$. A Steiner {\em triple} system $S ( 2 , 3 , v )$ is a set of triples (order not important in a triple) of elements from a set $S$ of $v$ elements such that each pair of elements from $S$ is contained in exactly one triple. For the set $S = \{\rm A, \rm B, \rm C, \rm D, \rm E, \rm F, \rm G, \rm H, \rm I \}$ of nine elements, an example Steiner triple system $S ( 2 , 3 , 9 )$ is \{(A,B,C), (A,D,E), (A,F,G), (A,H,I), (B,D,F), (B,E,H), (B,G,I), (C,D,I), (C,E,G), (C,F,H), (D,G,H), (E,F,I)\}. Since the problem of generating Steiner triples is NP but not P, it seemed worthwhile to take note of how genetic algorithms were used to solve NP problems in general \cite{de:usi} and the n-queens problem in particular \cite{cr:sol}. The approach used in these two papers was to treat the problem as a boolean satisfiability problem. The boolean satisfiability problem, which itself is NP-complete, consists of an arbitrary boolean expression of $n$ variables. The problem is to find an assignment to these $n$ variables which will result in the boolean expression being true. De Jong and Spears \cite{de:usi} have given a rather complete analysis of appropriate fitness functions and we describe our fitness function more fully in light of their work in a subsequent section. Each chromosome is a bit string of length equal to the total number of $k$-tuples over the set $S$ of $v$ elements. Each bit encodes whether or not the corresponding $k$-tuple is in the potential Steiner system represented by the chromosome. The fitness function is patterned on the fitness function used in genetic algorithm programs solving the satisfiability problem \cite{cr:sol,de:usi}. It works as follows. In a chromosome being evaluated, the bits set to 1 represent $k$-tuples in the candidate solution encoded by the chromosome. The evaluation function determines how many times each $t$-tuple is ``covered'' or included in any $k$-tuple in the chromosome. If the chromosome were actually a valid solution Steiner system, then this count would be exactly 1 for each $t$-tuple. For each $t$-tuple over $S$, the fitness function counts how many times that $t$-tuple is contained in any of the $k$-tuples in the chromosome. The counts are then adjusted by setting to 0 all those counts that are not exactly 1. Then the fitness value is set equal to the square of the average of all the counts. This is equivalent to the fitness function used in \cite{de:usi} for the satisfiability problem, where the boolean equation represents the logical value of the statement that each $t$-tuple occurs exactly once in the set of $k$-tuples represented by the chromosome. \bibitem{cr:sol} K. D. Crawford, ``Solving the n-Queens Problem Using Genetic Algorithms,'' Proceedings of the 1992 ACM/SIGAPP Symp. on Applied Computing, Kansas City, MO, March 1-3, 1992, pp.\ 1039-1047. \bibitem{de:usi} 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. ------------------------------ From: shartley@mcs.drexel.edu (Stephen J. Hartley) Date: Fri, 9 Dec 94 11:44:10 EST Subject: more on Steiner Systems Translating a Steiner System S(x,y,z) into a boolean satisfiability problem. First note that overall there are $z \choose x$ x-tuples and $z \choose y$ y-tuples. A Steiner System is some subset of the $z \choose y$ y-tuples so that each of the $z \choose x$ x-tuples is in exactly one of the y-tuples in S(x,y,z). The number of y-tuples in S(x,y,z) is |S(x,y,z)| = ${z \choose x} \over {y \choose x}$. Let each of the $z \choose y$ y-tuples corresponds to a boolean variable y_i, i=1 to $z \choose y$, where y_i = \true if y_i \elem S(x,y,z) and y_i = \false if not. We are going to construct a boolean equation in y_i that will be true for some assignment of \true and \false to y_i if and only if the set of y_i that are \true form a Steiner System S(x,y,z). Each of the $z \choose x$ x-tuples is to be contained in exactly one y-tuple in S(x,y,z). So we need to construct a boolean expression for each x-tuple that evaluates to \true if that x-tuple is in exactly one y-tuple in S(x,y,z) and is \false otherwise. Then we \and together all the expressions for the x-tuples. Each x-tuple corresponds to the following boolean expression. Each y-tuple "contains" or "covers" $y \choose x$ x-tuples. Each x-tuple "overlaps" or is "contained in" ${z-x} \choose {y-x}$ y-tuples. For each x-tuple, construct a term involving the ${z-x} \choose {y-x}$ y-tuples that overlap it. The term is \true if and only if the x-tuple is in exactly one of the ${z-x} \choose {y-x}$ y-tuples overlapping it that have y_i = \true, i.e., that are in S(x,y,z). Suppose we number the $z \choose x$ x-tuples 1, 2, ..., $z \choose \x$. Now suppose x-tuple j is contained in y-tuples y_{j_1}, y_{j_2}, ..., y_{j_l}, where l = ${z-x} \choose {y-x}$. Then the boolean term for each x-tuple is y_{j_1} \and \not y_{j_2} \and \not y_{j_3} \and \not ... \and \not y_{j_l} \or \not y_{j_1} \and y_{j_2} \and \not y_{j_3} \and \not ... \and \not y_{j_l} \or \not y_{j_1} \and \not y_{j_2} \and y_{j_3} \and \not ... \and \not y_{j_l} \or ... \or \not y_{j_1} \and \not y_{j_2} \and \not y_{j_3} \and \not ... \and y_{j_l} This will be \true if and only if the x-tuple is in exactly one y-tuple in S(x,y,z). Now take the \and of all the above terms for each x-tuple and we get a boolean expression that is \true if and only if all $z \choose x$ x-tuples are in exactly one of the y-tuples in S(x,y,z). An example. For the set $S = \{A, B, C, D, E, F, G, H, I \}$ of nine elements. The number of x-tuples is 36, the number of y-tuples is 84, and |S(2,3,9)| is 12. An example Steiner triple system $S ( 2 , 3 , 9 )$ is \{(A,B,C), (A,D,E), (A,F,G), (A,H,I), (B,D,F), (B,E,H), (B,G,I), (C,D,I), (C,E,G), (C,F,H), (D,G,H), (E,F,I)\}. The x-tuple AB is contained in 6 y-tuples: ABC, ABD, ABE, ABF, ABG, ABH, ABI. Suppose these 6 y-tuples are represented by y_1, y_2, ..., y_6. Then the equation for the x-tuple AB is (where _ means negation and | means or): _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 | _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 | _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 | _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 | _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 | _ _ _ _ _ y_1 y_2 y_3 y_4 y_5 y_6 ------------------------------ From: goodman@egr.msu.edu Date: Mon, 12 Dec 1994 15:11:29 -0500 (EST) Subject: How 2 classify (Re: v8n47) We have done some work on classification of data such as you are considering, using both single-population GA's and micro-grained parallel GA's (which allows only larger, panmictic populations, not the "island parallel" subpopulations such as we've used for many other applications). We've even used some of the "classical" datasets from the medical community for testing our approach, and done pretty well. Here's the response Prof. Pei, a Visiting Professor in our Genetic Algorithm Research and Applications Group (GARAGe) prepared to your question: We have developed an approach which uses Genetic Algorithms to carry out supervised learning from known training samples for selecting a best subset of characteristic features,i.e., identifying those features that discriminate, and/or for weighting the relative importance of the features for the classification task; and uses a generalized KNN classifier as a part of evaluation function during the process of optimization of the feature weightings. We have applied this approach to the classfication of microbial samples, among other things. The results show that the GA/KNN performs significantly better than the unmodified KNN on high-dimensionality pattern problems. You may try to apply this approach to classify your medical data. We have published a paper on this approach, entitled "Further Research on Feature Selection and Classification Using Genetic Algorithms." Proc. 5th ICGA, 1993. That paper, and some others as well, are available on our web server, at //isl.msu.edu/GA, under subdirectory papers. As to Classifier Systems, I am currently working on a project to classify High-Dimensionality Biological Binary Patterns. Using Genetic Classifier Learning, we can seek to find the best rule for performing a classification task. The preliminary results show that the correctness rate of classification can reach about the same level as with our GA/KNN method. We will publish all of these results in the next ICGA, or somewhere else. If you are interested, we can discuss this further, and provide you some of our test results, etc. ---Pei, Min--- **************************************************************************** Visiting Professor Genetic Algorithms Research and Application Group (GARAGe) Case Center for Computer-Aided Engineering and Manufacturing Engineering Building Michigan State University Phone: (517)353-4973(O), (517)355-7888(H) FAX: (517)355-7516 E-mail addr: pei@egr.msu.edu **************************************************************************** Thus, I'm afraid that you may still face a dilemma as to which approach is better -- either can work pretty well. The good news is that if you like, you need not start from scratch with either approach. -- Erik D. Goodman, Director, Case Center for Comp.-Aided Engr. and Mfg. Director, MSU Manufacturing Research Consortium Co-Director, Genetic Algorithms Research and Applications Group (GARAGe) Prof., EE, ME; Michigan State University; goodman@egr.msu.edu Snail mail: 112 Engrg. Bldg. Phone: (517)355-6453 or 353-9695 E. Lansing, MI 48824 FAX: (517)355-7516 ------------------------------ From: cheaw.yee-soon Date: Thu, 8 Dec 1994 16:59:31 +0000 (GMT) Subject: Info request Currently i am doing my final year project in university of sunderland my project title is " Frequncy domain identification for Genetic Tuning for PI controller". So please send me some info that related my subject or any info that regard my subject area. Thank You. ------------------------------ From: sushil%cs.unr.edu@mailroute.UNR.EDU (Sushil Louis) Date: Mon, 12 Dec 94 16:51:11 PDT Subject: CFP - 4th Int'l Golden West Conference on Intelligent systems THE INTERNATIONAL SOCIETY FOR COMPUTERS AND THEIR APPLICATIONS Presents +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ __________ ___ ___ ___________ ___________ / _______/| / /| / /| /___ ___/| / ________/| / /|_____|/ / / / / / / / /|__|/ / /|_______|/ / / / ____ / / / / / / / / / / / / / / / /_ /| / / / /\ / / / / / / / / / / /_/___/ / / / /_/__/ \__/ / / ___/ /_/__ / /_/______ /__________/ / /_________/\_____/ / /___________/| /___________/| |__________|/ |_________/\_____|/ |___________|/ |___________|/ +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ THE FOURTH GOLDEN WEST INTERNATIONAL CONFERENCE ON INTELLIGENT SYSTEMS CALL FOR PAPERS Mon. - Wed., June 12, 13, and 14, 1995, San Francisco. The Fourth Golden West International Conference on Intelligent Systems seeks quality international submissions in all areas of intelligent systems including, but not limited to: =============================================================================== REASONING KNOWLEDGE-BASED SYSTEMS LOGIC AND INFERENCE MACHINE LEARNING AND ADAPTIVE SYSTEMS NON-MONOTONIC REASONING RECOGNITION AND CLASSIFICATION VISION, IMAGE PROCESSING/INTERPRETATION FUZZY SYSTEMS ARTIFICIAL NEURAL NETWORKS ROBOTICS, CONTROL, PLANNING CASE-BASED REASONING MULTIMEDIA AND HUMAN COMPUTER INTERFACES DISTRIBUTED INTELLIGENT SYSTEMS EVOLUTIONARY COMPUTATION(GA,GP,ES,EP) CELLULAR AUTOMATA ARTIFICIAL LIFE COGNITIVE SCIENCE AUTONOMOUS AGENTS =============================================================================== LOCATION & TRAVEL CONNECTIONS: The conference is being held in the Sir Francis Drake Hotel near Nob Hill in downtown San Francisco. One of the world's most exciting cities, San Francisco has many attractions including the Golden Gate Bridge and Park, Nob Hill, Chinatown, and nearby Silicon Valley. The second week in June usually has warm days and cool nights (bring warm jackets). San Francisco can be reached by airline from anywhere in the world. =============================================================================== GUIDELINES * Authors must submit 5 copies of an extended abstract (at least 4 pages) or complete paper (no more than 10 double spaced pages). Please include one separate cover page containing title, author's name(s), affiliation, EMAIL ADDRESS, telephone number, and TOPIC AREA. To help us assign reviewers to papers use the topics in the list above as a guide. In cases of multiple authors all correspondence will be sent to the first author unless otherwise requested. Send submissions to Sushil J. Louis, Dept. of Computer Science/171, University of Nevada, Reno, NV 89557. * Papers/abstracts must be received by February 15, 1995. --------------------- * Notice of acceptance will be mailed by April 10, 1995, after refereeing. Information on formatting, and hotel reservations etc., will also be included. All accepted papers will appear in the conference proceedings and MUST be presented at the conference by an author. * We will solicit expanded versions of selected papers for review toward possible Journal publication. For information on submissions, the conference program, and other technical matters contact: Sushil J. Louis, Email:gwics95@cs.unr.edu, Tel:(702)784-4315, Fax:(702)784-1766 A POSTSCRIPT VERSION of this call for papers is available for anonymous ftp from mammoth.cs.unr.edu in /sushil/gwics.ps For information on local arrangements contact: Mary Ann Sullivan, Email:sullivan@unity.ncsu.edu, Tel: (919) 847-3747. ------------------------------ End of Genetic Algorithms Digest ******************************