A free lunch proof for Gray versus Binary encodings
Darrell Whitley · 1999
A measure of complexity is proposed that counts the number of local minima in any given problem representation. A special class of functions with the maximum possible number of optima is also defined. A proof is given showing that reflected Gray code induce more optima than Binary over this special class of functions; by the No Free Lunch principle, reflected Gray codes therefore induces fewer optima over all other remaining functions. 1 INTRODUCTION Over all possible functions, Gray codes and Standard Binary codes are equal in that they both cover the set of all possible bit representations [4]. In spite of this No Free Lunch result [5], applications oriented researchers have often argued for the use of Gray codes [1]. The debate as to whether Gray coding is better than Binary representations has been a classic example of where theory and practice clash. The results in this paper bring theory and practice closer together and yields new insights into the role of representati...