---joke[Editors note: For the refs cited here, you will have to go to: {ga faq}.]

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, non-GA, 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^N-1} 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 or any given N. The example shown here belongs to a class of Gray codes that goes by the fancy name "binary-reflected 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 right-most 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 attrributed 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 binary-coded 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 binary-coded string of length N, a single mutation in the most significant bit (MSB) alters the number by 2^(N-1). In a Gray-coded 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 left-most bit changes a zero to a seven and vice-versa, while the largest change a single mutation can make to a corresponding binarycoded 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 binary-reflected Gray code described above and the standard binary code turns out to be surprisingly simple to state. First label the bits of a binary-coded string B[i], where larger i's represent more significant bits, and similarly label the corresponding Gray-coded 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 Gray---or 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 high-order 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 | *-----------------------------------------------------------* ^^^^^ ^^^^^ high-order bit low-order bitC 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 from */ /* Gray code to binary representation */ allele *Cg,*Cb; int n; { int j;*Cb = *Cg; /* copy the high-order 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 from */ /* binary to Gray code representation */ allele *Cb, *Cg; int n; { int j;*Cg = *Cb; /* copy the high-order bit */

for (j = 0; j < n; j++) { Cg--; Cb--; /* for the remaining bits */ *Cg= *(Cb+1)^*Cb; /* do the appropriate XOR */ }

} References

- F. Gray, "Pulse Code Communication", U. S. Patent 2 632 058, March 17, 1953.

- F. G. Heath, "Origins of the Binary Code", Scientific American
v.227,n.2 (August, 1972) p.76.
- Martin Gardner, "Mathematical Games", Scientific American v.227,n.2 (August, 1972) p.106.

- William H. Press, et al., Numerical Recipes in C, Second Edition
(Cambridge University Press, 1992).
- Paul Horowitz and Winfield Hill, The Art of Electronics, Second Edition (Cambridge University Press, 1989).

- Dexter Kozen, The Design and Analysis of Algorithms (Springer-
Verlag, New York, NY, 1992).
- Edward M. Reingold, et al., Combinatorial Algorithms (Prentice Hall, Englewood Cliffs, NJ, 1977).

- David E. Goldberg, GENETIC ALGORITHMs in Search, OPTIMIZATION,
and Machine Learning (Addison-Wesley, Reading, MA, 1989).
- R. B. Hollstien, Artificial Genetic Adaptation in Computer Control Systems (PhD thesis, University of Michigan, 1971).

Hope this helps,Paul Holmes email: bsc0123@uk.ac.napier.dcs Computer Studies Department Napier University Edinburgh

Scotland

From genetic-programming-owner@list.Stanford.EDU Fri Dec 9 06:29 MET 1994

(1.38.193.4/16.2) id AA26570; Fri, 9 Dec 1994 06:29:34 +0100 id AA06986; Fri, 9 Dec 1994 06:32:51 +0100 id AA13908; Thu, 8 Dec 94 22:27:30 MST Errors-To: mail-errors@list.Stanford.EDU Errors-To: mail-errors@list.Stanford.EDU via Fnet-EUnet id AA16477; Fri, 9 Dec 1994 05:23:28 +0100 (MET) From: mgix@jpn.thomson-di.fr (Emmanuel Mogenet) To: bru@kosice.upjs.sk Cc: genetic-programming@cs.stanford.edu Reply-To: mgix@jpn.thomson-di.fr X-Mailer: ELM [version 2.4 PL21] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 5980Branislav Brutovsky writes:

>Hi everybody,>Would you send me the formula for construction decimal number from its >Gray counterpart, please. I would really appreciate it. >Thanks in advance.

>Branislav BrutovskyFind my personal brew attached.

Remarks:

- It's C++, but easyly downgraded to C.
- I've been using it for 6 month. It seems to work but I never bothered to
check its correctness for real.
- It's built to run on a 32 bit machines. As far as I can tell, endian-ness
shouldn't matter, except maybe for the test routine at the end.
- It has the advantage over most implementations I've seen to let you
choose between two modes:
a) Either your genetic code is seen has a collection of 32 bits chunks over which the gray coding is applied as many times as they are chunks b) Either your genetic code is seen has one long bit string representing one single binary number over which gray coding is applied once.

- It should be rather fast.

- Mgix!

Emmanuel Mogenet <mgix@thomson-di.fr> PGP Key on Request. MIME Groked.

- Copyright (C) 1994 Emmanuel MOGENET
- This file falls under the terms of the GNU General Public License
- Comments and Suggestions | mail mgix@thomson-di.fr

- $Revision: 1.1 $

- Library : Genetic
- Description : Gray Coding
- Author : E. Mogenet

\******************************************************************************/

#include <stdio.h> #include <stdlib.h>

typedef int reg; typedef unsigned int uint32; typedef unsigned short uint16; typedef unsigned char uint8;

/*

- DESCRIPTION: Build The Gray Code Lookup
**----------------------------------------------------------------------------*/
static void BuildLookup() { for( reg i=0; i<2; ++i ) { for( reg j=0; j<256; ++j ) { uint16 last= (i<<8); lookup[i][j]=j; for( reg k=7; k>=0; --k ) { last>>=1; lookup[i][j] ^= last; last= lookup[i][j]&(1<<k); } lookup[i][j] |= (last<<8); } }

} /*

- DESCRIPTION: Binary Code --> Gray Code
**----------------------------------------------------------------------------*/
void Gray( uint32 *gray, // (O) Gray Code uint32 *binary, // (I) Binary Code

reg length, // (I) Length of the binary code (in 32 bit chunks) reg prop // (I) Propagate on the whole string of bits ?) { uint32 last=0; for( reg i=length-1; i>=0; --i ) { gray[i]= binary[i] ^ (last|(binary[i]>>1)); last= prop ? binary[i]<<31 :0; }

} /*

- DESCRIPTION: Gray Code --> Binary Code
**----------------------------------------------------------------------------*/
void Ungray( uint32 *binary, // (O) Binary Code uint32 *gray, // (I) Gray Code

reg length, // (I) Length of the gray code (in 32 bit chunks) reg prop // (I) Propagate on the whole string of bits ?) { if( !initDone ) { initDone=1; BuildLookup(); } uint16 last=0; for( reg i=length-1; i>=0; --i ) { uint8 *s=(uint8*)(gray+i); uint8 *d=(uint8*)(binary+i); uint16 z; z= lookup[last][ s[0] ]; d[0]= z&0xFF; last= z>>8; z= lookup[last][ s[1] ]; d[1]= z&0xFF; last= z>>8; z= lookup[last][ s[2] ]; d[2]= z&0xFF; last= z>>8;

z= lookup[last][ s[3] ]; d[3]= z&0xFF; last= prop ? z>>8 : 0; } }

static uint8 uniq[65535]; static char *bindump[]= { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111", }; /*

- DESCRIPTION: Hamming Distance between 2 32-bit vectors
**----------------------------------------------------------------------------*/
reg Hamming( uint32 a, uint32 b ) { reg res=0; for( reg i=0; i<32; ++i,a>>=1,b>>=1 ) res+= ((a&0x1) != (b&0x1)); return res;

} /*

- DESCRIPTION: Check if the thing behaves
**----------------------------------------------------------------------------*/
main() { reg i; uint32 bin; uint32 gray; /* Visual Check ----------------*/ for( i=0; i<256; ++i ) { bin=i; Gray( &gray, &bin, 1, 0 ); Ungray( &bin, &gray, 1, 0 ); printf( "%d: %s%s --> %s%s --> %s%s\n", i, bindump[ i>>4 ], bindump[ i&0xF ], bindump[ gray>>4 ], bindump[ gray&0xF ], bindump[ bin>>4 ], bindump[ bin&0xF ] ); }

/* Check the first 64k -----------------------*/ uint32 last=1; for( i=0; i<65536; ++i ) { bin=i; Gray( &gray, &bin, 1, 0 ); Ungray( &bin, &gray, 1, 0 ); uniq[gray]++; if( bin!=i || Hamming(last,gray)!=1 ) { printf( "Failure at %d\n", i ); exit(1); } last=gray; } for( i=0; i<65536; ++i ) { if( uniq[i]!=1 ) { printf( "Mapping not 1 to 1\n" ); exit(1); } } exit(0); } /*

// $Log: gcode.c++,v $

From: David_vun_Kannon_at_NY-RES@resgate.rch.gs.comI wrote some c code for this when I did GA work a couple of years ago.

However, I convinced myself that it wasn't really helpful to GA onbitstrings. The basic argument for using Gray coded bits is that single bit mutations in a Gray coded number will only change the value by a little bit also, as opposed to the usual power of 2 code, where changing one bit might change the value by as much as 2^(n-1) for n its. Unfortunately, this arguement ignores the wraparound that occurs between the first and last encoded values, which in Gray code are always 000... and 100.... A mutation between these two strings is still just a single bit, but it produces a value jump of 2^n. What has happened in effect is that Gray code has saved up the possible accumulated error and put it all in one place. put another way, I think that total error over all one bit changes in any representation is constant, all you can do is change the distribution of the error weight over the set of changes. I didn't find the bimodal distribution of error produced by Gray codes particularly more compelling than the approximately Gaussian distribution of the binary representation, and I couldn't come up with a representation that had uniform distribution without resorting to a hash table. So I gave up on Gray codes.