Encoding selection for a class of fitness functions based on locus interdependency

摘要

The feasible solutions are usually represented with a binary encoding when a genetic algorithm is applied to a continuous optimization problem. However, it has been remarked that a binary encoding was not always the best choice, and it was suggested to use a base-m encoding for a class of fitness functions linearly combined of sine functions whose frequencies were exponential to a positive integer m. In this paper, this suggestion is explained based on locus interdependency. It is shown that, for these fitness functions, the Euclidean distances from a considerable part of the highly fit strings to the objective strings are negative powers of m. Thus, the Hamming distances from the highly fit strings to the objective strings when the feasible solutions of these fitness functions are represented with a base-m encoding are much smaller than those when the fitness functions are expressed with an encoding of another cardinality. And as a result, locus interdependency of the former is much lower than that of the latter, which indicates that the fitness functions are likely to be much easier when expressed with the former encoding. The suggestion is then tested on a number of fitness functions randomly generated, in which encodings with different bases are compared according to locus interdependency and optimization performance. The results of the test substantiate the suggestion.