Importance of finding a good basis in binary representation
Junghwan Lee, Yong-Hyuk Kim · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2018
In genetic algorithms, the importance of the basis for representation has been well known. In this paper, we studied the effect of a good basis in binary representation, and resultantly we could show that a good basis improves the performance of search algorithms. A complicated problem space may be transformed into a linearly-separable one via a change of basis. We had experiments on search performance. Finding a good basis from all the bases may not be practical, because it takes O(2n2) time, where n is the length of a chromosome. However, we used a genetic algorithm to find a good basis, to correctly investigate how a basis affects the problem space. We also conducted experiments on the NK-landscape model as a representative computationally hard problem. Experimental results showed that changing basis by the presented genetic algorithm always leads better search performance on the NK-landscape model.