Properties of Gray and Binary Representations
研究了格雷码与二进制编码的性质，证明在特定单峰函数上，使用反射格雷码的爬山算法能在线性步数内达到全局最优，并提出了动态切换格雷码的移位机制以逃离局部最优。
January 01 2004 Properties of Gray and Binary Representations Jonathan Rowe, Jonathan Rowe Computer Science Department, University of Birmingham, Birmingham B15 2TT, UK, J.E.Rowe@cs.bham.ac.uk Search for other works by this author on: This Site Google Scholar Darrell Whitley, Darrell Whitley Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, whitley@cs.colostate.edu Search for other works by this author on: This Site Google Scholar Laura Barbulescu, Laura Barbulescu Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, laura@cs.colostate.edu Search for other works by this author on: This Site Google Scholar Jean-Paul Watson Jean-Paul Watson Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, watsonj@cs.colostate.edu Search for other works by this author on: This Site Google Scholar Author and Article Information Jonathan Rowe Computer Science Department, University of Birmingham, Birmingham B15 2TT, UK, J.E.Rowe@cs.bham.ac.uk Darrell Whitley Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, whitley@cs.colostate.edu Laura Barbulescu Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, laura@cs.colostate.edu Jean-Paul Watson Department of Computer Science, Colorado State University, Fort Collins, Colorado 80523, USA, watsonj@cs.colostate.edu Online Issn: 1530-9304 Print Issn: 1063-6560 © 2004 Massachusetts Institute of Technology2004 Evolutionary Computation (2004) 12 (1): 47–76. https://doi.org/10.1162/evco.2004.12.1.47 Cite Icon Cite Permissions Share Icon Share Twitter LinkedIn Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation Jonathan Rowe, Darrell Whitley, Laura Barbulescu, Jean-Paul Watson; Properties of Gray and Binary Representations. Evol Comput 2004; 12 (1): 47–76. doi: https://doi.org/10.1162/evco.2004.12.1.47 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search nav search search input Search input auto suggest search filter All ContentAll JournalsEvolutionary Computation Search Advanced Search Abstract Representations are formalized as encodings that map the search space to the vertex set of a graph. We define the notion of bit equivalent encodings and show that for such encodings the corresponding Walsh coefficients are also conserved. We focus on Gray codes as particular types of encoding and present a review of properties related to the use of Gray codes. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new convergence proofs for a special class of unimodal functions; the proofs show that a steepest ascent bit climber using any reflected Gray code representation reaches the global optimum in a number of steps that is linear with respect to the encoding size. There are in fact many different Gray codes.Shifting is defined as a mechanism for dynamically switching from one Gray code representation to another in order to escape local optima. Theoretical results that substantially improve our understanding of the Gray codes and the shifting mechanism are presented. New proofs also shed light on the number of unique Gray code neighborhoods accessible via shifting and on how neighborhood structure changes during shifting. We show that shifting can improve the performance of both a local search algorithm as well as one of the best genetic algorithms currently available. This content is only available as a PDF. © 2004 Massachusetts Institute of Technology2004 You do not currently have access to this content.