Selection of Encoding Cardinality for a Class of Fitness Functions to Obtain Order-1 Building Blocks

Abstract

Encoding plays a key role in determining the optimization efficiency of a genetic algorithm. In the optimization of a continuous function, binary encodings are normally used due to their low coding-alphabet cardinalities. Nevertheless, from the viewpoint of building-block supply, it is remarked that a binary encoding is not necessarily the best choice to express a fitness function which is linearly combined of sinusoidal functions with frequencies exponential to a positive integer when is not equal to 2. It is proved that, if the frequencies are exponential to , an encoding of cardinality can provide a better supply of order-1 building blocks than the encodings of other cardinalities. Taking the advantage of building-block supplies, a genetic algorithm with an encoding of cardinality has higher chance to find fitter solutions. This assumption is verified via a number of randomly generated fitness functions, and encodings with different cardinalities are compared according to the optimization performance of corresponding genetic algorithms on these fitness functions. The simulation results support the assumption, and show in the statistical sense that the genetic algorithm with an encoding of cardinality outperforms those of the other cardinalities when the frequencies of the sinusoidal functions are exponential to .

Keywords

• Building block
• encoding
• genetic algorithm
• continuous optimization
• schema processing