Top Document: FAQ: comp.ai.genetic part 6/6 (A Guide to Frequently Asked Questions) Previous Document: News Headers Next Document: Q22: What test data is available? See reader questions & answers on this topic!  Help others by sharing your knowledge The correct spelling is "Gray"not "gray", "Grey", or "grey" since Gray codes are named after the Frank Gray who patented their use for shaft encoders in 1953 [1]. Gray codes actually have a longer history, and the inquisitive reader may want to look up the August, 1972, issue of Scientific American, which contains two articles of interest: one on the origin of binary codes [2], and another by Martin Gardner on some entertaining aspects of Gray codes [3]. Other references containing descriptions of Gray codes and more modern, nonGA, applications include the second edition of Numerical Recipes [4], Horowitz and Hill [5], Kozen [6], and Reingold [7]. A Gray code represents each number in the sequence of integers {0...2^N1} as a binary string of length N in an order such that adjacent integers have Gray code representations that differ in only one bit position. Marching through the integer sequence therefore requires flipping just one bit at a time. Some call this defining property of Gray codes the "adjacency property" [8]. Example (N=3): The binary coding of {0...7} is {000, 001, 010, 011, 100, 101, 110, 111}, while one Gray coding is {000, 001, 011, 010, 110, 111, 101, 100}. In essence, a Gray code takes a binary sequence and shuffles it to form some new sequence with the adjacency property. There exist, therefore, multiple Gray codings for any given N. The example shown here belongs to a class of Gray codes that goes by the fancy name "binaryreflected Gray codes". These are the most commonly seen Gray codes, and one simple scheme for generationg such a Gray code sequence says, "start with all bits zero and successively flip the rightmost bit that produces a new string." Hollstien [9] investigated the use of GAs for optimizing functions of two variables and claimed that a Gray code representation worked slightly better than the binary representation. He attributed this difference to the adjacency property of Gray codes. Notice in the above example that the step from three to four requires the flipping of all the bits in the binary representation. In general, adjacent integers in the binary representaion often lie many bit flips apart. This fact makes it less likely that a MUTATION operator can effect small changes for a binarycoded INDIVIDUAL. A Gray code representation seems to improve a mutation operator's chances of making incremental improvements, and a close examination suggests why. In a binarycoded string of length N, a single mutation in the most significant bit (MSB) alters the number by 2^(N1). In a Graycoded string, fewer mutations lead to a change this large. The user of Gray codes does, however, pay a price for this feature: those "fewer mutations" lead to much larger changes. In the Gray code illustrated above, for example, a single mutation of the leftmost bit changes a zero to a seven and viceversa, while the largest change a single mutation can make to a corresponding binary coded individual is always four. One might still view this aspect of Gray codes with some favor: most mutations will make only small changes, while the occasional mutation that effects a truly big change may initiate EXPLORATION of an entirely new region in the space of CHROMOSOMEs. The algorithm for converting between the binaryreflected Gray code described above and the standard binary code turns out to be surprisingly simple to state. First label the bits of a binarycoded string B[i], where larger i's represent more significant bits, and similarly label the corresponding Graycoded string G[i]. We convert one to the other as follows: Copy the most significant bit. Then for each smaller i do either G[i] = XOR(B[i+1], B[i])to convert binary to Grayor B[i] = XOR(B[i+1], G[i])to convert Gray to binary. One may easily implement the above algorithm in C. Imagine you do something like typedef unsigned short ALLELE; and then use type "allele" for each bit in your chromosome, then the following two functions will convert between binary and Gray code representations. You must pass them the address of the highorder bits for each of the two strings as well as the length of each string. (See the comment statements for examples.) NB: These functions assume a chromosome arranged as shown in the following illustration. index: C[9] C[0] ** Char C:  1  1  0  0  1  0  1  0  0  0  ** ^^^^^ ^^^^^ highorder bit loworder bit C CODE /* Gray <==> binary conversion routines */ /* written by Dan T. Abell, 7 October 1993 */ /* please send any comments or suggestions */ /* to dabell@quark.umd.edu */ void gray_to_binary (Cg, Cb, n) /* convert chromosome of length n+1 */ /* from Gray code Cg[0...n] */ /* to binary code Cb[0...n] */ allele *Cg,*Cb; int n; { int j; *Cb = *Cg; /* copy the highorder bit */ for (j = 0; j < n; j++) { Cb; Cg; /* for the remaining bits */ *Cb= *(Cb+1)^*Cg; /* do the appropriate XOR */ } } void binary_to_gray(Cb, Cg, n) /* convert chromosome of length n+1 */ /* from binary code Cb[0...n] */ /* to Gray code Cg[0...n] */ allele *Cb, *Cg; int n; { int j; *Cg = *Cb; /* copy the highorder bit */ for (j = 0; j < n; j++) { Cg; Cb; /* for the remaining bits */ *Cg= *(Cb+1)^*Cb; /* do the appropriate XOR */ } } References [1] F. Gray, "Pulse Code Communication", U. S. Patent 2 632 058, March 17, 1953. [2] F. G. Heath, "Origins of the Binary Code", Scientific American v.227,n.2 (August, 1972) p.76. [3] Martin Gardner, "Mathematical Games", Scientific American v.227,n.2 (August, 1972) p.106. [4] William H. Press, et al., Numerical Recipes in C, Second Edition (Cambridge University Press, 1992). [5] Paul Horowitz and Winfield Hill, The Art of Electronics, Second Edition (Cambridge University Press, 1989). [6] Dexter Kozen, The Design and Analysis of Algorithms (Springer Verlag, New York, NY, 1992). [7] Edward M. Reingold, et al., Combinatorial Algorithms (Prentice Hall, Englewood Cliffs, NJ, 1977). [8] David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning (AddisonWesley, Reading, MA, 1989). [9] R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems (PhD thesis, University of Michigan, 1971). [10] Albert Nijenhuis and Herbert S. Wilf, Combinatorial Algorithms, (Academic Press, Inc., New York, San Francisco, London 1975). User Contributions:Comment about this article, ask questions, or add new information about this topic:Top Document: FAQ: comp.ai.genetic part 6/6 (A Guide to Frequently Asked Questions) Previous Document: News Headers Next Document: Q22: What test data is available? Part1  Part2  Part3  Part4  Part5  Part6  Single Page [ Usenet FAQs  Web FAQs  Documents  RFC Index ] Send corrections/additions to the FAQ Maintainer: David.Beasley@cs.cf.ac.uk (David Beasley)
Last Update March 27 2014 @ 02:11 PM
