Genetic Algorithms Digest Tuesday, 14 August 1990 Volume 4 : Issue 15 - Send submissions to GA-List@AIC.NRL.NAVY.MIL - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL Today's Topics: - Visualization in a High Dimension Parameter Space - Inexpensive Sharing Functions in a High Dimension Parameter Space - TR announcement (ftp only) - Info an books - CFP - Annals of Math and AI special issue on GAs - Special Session on AI in Communications - '91 Phoenix Conference ****************************************************************************** CALENDAR OF GA-RELATED ACTIVITIES: (with GA-List issue reference) Conference on Simulation of Adaptive Behavior, Paris (v3n21) Sep 24-28, 1990 Workshop Parallel Prob Solving from Nature, W Germany (v4n5) Oct 1-3, 1990 2nd Intl Conf on Tools for AI, Washington, DC (v4n6) Nov 6-9, 1990 4th Intl. Conference on Genetic Algorithms (v4n9) Jul 14-17, 1991 (Send announcements of other activities to GA-List@aic.nrl.navy.mil) ****************************************************************************** Date: Thu, 02 Aug 90 07:36:41 EDT From: jrv@sdimax2.mitre.org Subject: Visualization in a High Dimension Parameter Space % (TeX users may wish to run the following through plain TeX and use a % previewer. Others should disregard the $s.) When using GAs to optimize a single parameter function, it is usual to plot the members of a given generation with the parameter on the abscissa and the corresponding fitness (function value) on the ordinate. When the function has more than one parameter, this is not feasible. It may not be the actual values of the parameters that are of interest, so much as their distribution: whether they are well scattered, or clustered, or confined to one or two small regions of the parameter space. For this purpose, it is convenient to map each point in parameter space to a point on the real line using a spacefilling curve as suggested by Patrick et al. [1]. This mapping makes it possible to use the parameter-versus-fitness display format even for functions of several variables. A spacefilling curve $\phi$ is a continuous mapping from the unit interval to a higher dimensional region, for example the unit $k$-cube. Such a mapping tends to preserve nearness. More precisely, if two points are nearby spacefilling curve, then they are nearby in $k$-space. If they are nearby in $k$-space, then they are likely to be nearby along the interval. To use this technique, a pseudoinverse of the spacefilling curve is needed. For each point $x$ in $k$-space to be displayed, one must find a value $\theta$ in the unit interval such that $\phi(\theta) = x$. The utility of the technique depends on an efficient means of calculating $\theta$. In a previous message, I posted a program which maps the unit square to the unit interval. Platzman and Bartholdi have described a pseudoinverse of a similar curve which maps a unit hypercube of arbitrary dimension to the unit interval [2]. A C program implementing their procedure is appended. Although this method is easiest to apply to isolated points, it is possible to display a continuous function as follows: Generate a large number of points, either on a regular lattice or at random within the parameter space. Evaluate the function value $ y $ at each point, and calculate for each point the corresponding $\theta$. Sort these pairs by their $\theta$ value and plot a continuous line joining the $ (\theta, y) $ pairs. [1] E. A. Patrick, D. R. Anderson, and F. K. Bechtel, "Mapping Multidimensional Space to One Dimension for Computer Output Display,", IEEE Transactions on Computers, vol C-17, No. 10, October 1968. [2] L. K. Platzman and J. J. Bartholdi III, "Spacefilling Curves and Routing Problems in the Plane", AD-A126309, PDRC-83-02, Georgia Institute of Technology, February 1983. \end ============= CODE FOLLOWS =============>> /* Multidimensional spacefilling curve */ #include int degray(int g) { int dg = 0; while(g) {dg ^= g; g >>= 1;} return dg; } /* Find a k-bit inverse mapping for a spacefilling curve (from vector x in the unit d-cube to the unit interval) */ double thetad(double x[], int d, int k) { int i, v, n; double t, alphad, y[16], twod; if(k == 0) return 0.; v = 0; for (i = 0; i < d; i++) { v <<= 1; if(x[i] > .5) /* x[i] must be in the unit interval [0,1] */ {v++; y[i] = 1. - 2*(1. - x[i]); } else y[i] = 1. - 2.*x[i]; } t = thetad(y, d, k-1); n = degray(v); if((n & 1)) t = 1. - t; twod = 1./(1 << d); if(d & 1) alphad = 2./3.; else alphad = 2./3.*(1. - twod); t = fmod((n + t - alphad)*twod + 10., 1.); return t; /* result t is in the interval [0,1] */ } ----------------------------------------- Date: Thu, 02 Aug 90 07:41:01 EDT From: jrv@sdimax2.mitre.org Subject: Inexpensive Sharing Functions in a High Dimension Parameter Space % (I suggest that TeX users run the following through plain TeX and use a % previewer. Others should disregard the $s.) In a previous note I suggested an exponential sharing function which could be calculated in two passes over the sorted members (i.e. in $O(n \log n)$ time). That method applied only to a function of a single variable. Here, I extend the method to the multivariable case. Each member is represented by a point in parameter space. My approach is as follows: First find a path through the points which approximately minimizes the total path length (a Euclidean Traveling Salesman Problem). Imagine connecting the points in order with a string, tying it to each point in turn. Stretch the string out straight, then apply the single parameter exponential filter algorithm to calculate niche counts. In the following, I will assume without loss of generality that the parameter space is the unit hypercube. (Otherwise, as in the previous method, it is necessary to scale points in parameter space into the unit hypercube.) A spacefilling curve $\phi$ can be used to specify the order in which the points are visited, as mentioned in a previous note. For each point $x$ in parameter space, a value $\theta$ is determined such that $\phi(\theta) = x$. The points are then visited in order of increasing $\theta$. The exponential filter algorithm requires a distance between successive points. The natural metric is the Euclidean one. However, the relative distance along the spacefilling curve can also be used... I have already mentioned that the spacefilling curve tends to preserve nearness -- points nearby in parameter space tend to be mapped to nearby points in the interval. This can be formalized as follows. In the parameter space, we will use the Euclidean metric. The spacefilling curves we are using are closed, so the natural metric $D(\theta_1, \theta_2)$ is the smaller of $|\theta_1 - \theta_2|$ and $|\theta_1 - \theta_2 - 1|$. For the two dimensional spacefilling curve given earlier (Sierpinski's curve), $$ |x_1 - x_2| \le 2 \sqrt{D(\theta_1, \theta_2)}. $$ Note the inequality: if the two $\theta$s are nearby, the the two $x$s are nearby, but the converse does not necessarily hold. In two dimensions, we may use the less biased estimate of the Euclidean metric $$ |x_1 - x_2| \approx \sqrt{D(\theta_1, \theta_2)}, $$ and for $d$-space we may use the estimate $$ |x_1 - x_2| \approx D(\theta_1, \theta_2)^{1/d}. $$ The spacefilling curve will tend to connect nearest neighbors, in which case their contribution to the niche count will be reasonably accurate. However, this method will generally underestimate the niche count because the distance to more distant neighbors is measured along a bent path rather than a straight line. In addition, it is possible for nearby points to be visited on different loops of the spacefilling curve, therefore to be mapped to distant values of $\theta$. One can compensate for the underestimation by increasing the characteristic distance $\sigma$ in the formula for the niche count. I used this technique while minimizing the function $$ f_5(x_1,x_2) = \left[ {1 \over 500} + \sum_{j=1}^{25} {1 \over {j + {\sum_{i=1}^2 \left(x_i - a_{ij} \right)^6}}} \right]^{-1}, $$ which is ``a plateau with 25 deep perforations centered at $(a_{1j}, a_{2j})$'' [1], and I believe is also known as Sheckle's Foxholes. A GA with a total population of 200 was able to keep stable populations on 12 of the 25 minima. Note that for sharing functions as used here, function values are expected to be positive. My GA was set up to maximize so I initially tried to maximize $-f_5$. I found that the sharing function was actually encouraging clustering rather than suppressing it. In addition to negating the function, it was necessary to add an offset so the values were positive. I published spacefilling curve programs in two and more dimensions in previous messages. I also published a program which calculated niche counts for a function of one variable. I am appending to this message a program which calculates niche counts for a function of two variables, using a spacefilling curve. (Genetic algorithms and spacefilling curves are both new additions to my collection of tools. It has surprised me to find this many ways to combine them. I hope these notes prove interesting, and perhaps stimulate some technical discussion. Lately, the GA-list seems to have concentrated on things like meeting announcements. :-) [1] L. Booker, ``Improving Search in Genetic Algorithms,'' {\it Genetic Algorithms and Simulated Annealing}, Morgan Kaufmann Publishers, Inc., Los Altos, Cal., 1987. \end ============= CODE FOLLOWS ====>> share_scores(int num) { int i; double density, dist, x0, x1; char *cp; for (i = 0; i < num; i++) {cp = (char *)¤t[i].code; /* scale each parameter to the unit interval */ x0 = ldegray(extract(cp, 0, 17))/131072.; x1 = ldegray(extract(cp, 17, 17))/131072.; /* calculate a single value for sorting */ current[i].order = theta1(x0, x1, 20); } qsort(current, num, sizeof(MEMBER_T), phenotypic_compare); density = 0.; current[0].niche = 1.; for (i = 1; i < num; i++) {diff = fabs(current[i].order-current[i-1].order); dist = 131.072*2.*sqrt(diff); current[i].niche = density = density*exp(-fabs(dist/sigma)) + 1.; } density = 0.; for (i = num-2; i >= 0; i--) {diff = fabs(current[i].order-current[i+1].order); dist = 131.072*2.*sqrt(diff); current[i].niche += density *= exp(-fabs(dist/sigma)); density += 1.; } } ----------------------------------- Date: Thu, 19 Jul 90 22:24:00 PDT From: schraudo%cs@ucsd.edu (Nici Schraudolph) Subject: TR announcement (ftp only) The following technical report is available via anonymous ftp from the Artificial Life archive server: Dynamic Parameter Encoding for Genetic Algorithms ------------------------------------------------- Nicol N. Schraudolph Richard K. Belew The selection of fixed binary gene representations for real-valued parameters of the phenotype required by Holland's genetic algorithm (GA) forces either the sacrifice of representational precision for efficiency of search or vice versa. Dynamic Parameter Encoding (DPE) is a mechanism that avoids this dilemma by using convergence statistics derived from the GA population to adaptively control the mapping from fixed-length binary genes to real values. By reducing the length of genes DPE causes the GA to focus its search on the interactions between genes rather than the details of allele selection within individual genes. DPE also highlights the general importance of the problem of premature convergence in GAs, explored here through two convergence models. ======== To obtain a copy use the following procedure: $ ftp iuvax.cs.indiana.edu % (or 129.79.254.192) login: anonymous password: ftp> cd pub/alife/papers ftp> binary ftp> get schrau90-dpe.ps.Z ftp> quit $ uncompress schrau90-dpe.ps.Z $ lpr schrau90-dpe.ps ======== Hardcopies will be available shortly; I will send out another announcement then. The DPE algorithm will be an option in the GENESIS 1.1ucsd GA simu- lator, which should be ready for distribution soon - please hold back the requests until you see 1.1ucsd announced on this list. Nici Schraudolph, C-014 nschraudolph@ucsd.edu University of California, San Diego nschraudolph@ucsd.bitnet La Jolla, CA 92093 ...!ucsd!nschraudolph ---------------------------------- Date: Fri, 3 Aug 90 13:13:16 MDT From: steph%cardinal@LANL.GOV (Stephanie Forrest) Subject: Info an books Several people have asked me to post the following information to these mailing lists: 1. The book "Emergent Computation" on self-organizing, collective, and cooperative phenomena in natural and artificial computing networks (edited by me) can be ordered from MIT Press. It is to be published sometime this fall, so any orders sent now will be "back ordered" and sent out right when the book is published. Orders may be placed by phone (800-356-0343), fax (617-625-6660), or by traditional mail (The MIT Press, Order Dept., 55 Hayward St., Cambridge, MA 02142) . Price is expected to be: $32.50 . 2. The book "Parallelism and Programming in Classifier Systems" (also by me) can be ordered in the U.S. from Morgan Kaufmann, Order Dept. 2929 Campus Dr., Suite 260 San Mateo, CA 94403 (415) 578-9911 Price is $29.95 plus $3.50 shipping and handling Orders from outside the U.S. should be sent to Ms. Soraya Romano Pitman Publishing 128 Long Acre London WC2E 9AN ENGLAND I hope that this isn't too much self promotion for the GA community to handle. Any of you who would like more details about abstracts, table of contents, etc., please email me directly: steph@cardinal.lanl.gov Finally, I will have a new address as of Aug. 13 : Dept. of Computer Science Farris Engineering Center, 307 The University of New Mexico Albuquerque, N.M. 87131 My LANL email address and phone numbers will be valid for at least a year and I don't have new ones at UNM yet. ------------------------------------- Date: Fri, 20 Jul 90 17:05:43 EDT From: spears@AIC.NRL.Navy.Mil Subject: CFP - Annals of Math and AI special issue on GAs Call for Papers Annals of Mathematics and Artificial Intelligence A special issue of the Annals of Mathematics and Artificial Intelligence devoted to genetic algorithms and classifier systems is planned for 1992. Papers with significant mathematical content addressing central genetic algorithm and classifier system properties and behavior are being solicited for consideration. Full length versions of selected papers will be published. All submissions will be refereed. Topics of interest include, but are not limited to: * Extensions to schema analysis * Computational complexity * Convergence proofs for GAs * Characterization of GAs in terms of fixed points and their stability * Analysis of GA Hard problems * Comparative analysis of different recombination operators * Approaches to constrained optimization * GA approaches to multiobjective problems * Population distributional properties * Dynamics of credit assignment The deadline for submissions is February 4, 1991. Please send four (4) copies of all submissions to: Dr. Gunar E. Liepins MS 6360 Bldg. 6025 Oak Ridge National Laboratory PO Box 2008 Oak Ridge, TN 37831-6360 Further inquiries can be sent to: liepins@utkuxl.utk.edu or gxl@msr.epm.ornl.gov ------------------------------------ Date: 2 Aug 90 10:56:00 EDT From: "Doug Bigwood" Subject: Special Session on AI in Communications - '91 Phoenix Conference I am organizing a special session on Artificial Intelligence Applications in Communications for the 10th Annual IEEE Phoenix Conference on Computers and Communications to be held March 27- 30, 1991 in Scottsdale, Arizona. I am in the process of gathering a list of potential contributors to this session. Anyone interested in contributing a paper to this session should contact me (preferably via e-mail) by the middle of August or so (or ASAP). All I need at this time is the title of the proposed submission, the author's names, and an address (again, preferably an e-mail address). The draft manuscripts will need to be submitted in September. I will provide further details to those who express interest. Note that the term "Artificial Intelligence" as used here is being interpreted in its loosest sense; i.e. topics may include expert systems, neural networks, robotics, genetic algorithms, etc. Thank you for your time. Dr. Douglas W. Bigwood B.E. Technologies 12906 Old Chapel Place Bowie, MD 20720 Internet: dbigwood@umdars.umd.edu Bitnet: dbigwood@umdars -------------------------------- End of Genetic Algorithms Digest ********************************