Linear transformation in Pseudo-Boolean functions
Yong-Hyuk Kim · 2008
Traditional approaches dealing with pseudo-boolean function mostly use the inherent standard basis. When we consider another basis instead of the standard one, the linkage structure between basis elements and the ruggedness of the problem space can be completely different from original ones. Through a change of basis, a complex/difficult problem may be changed into a simple/easy one and vice versa. Chryssomalakos and Stephens [4] theoretically dealt with the bases of function space on Zn2 . In this paper, we investigate bases of more fundamental space, i.e., those of the vector space Zn2 = ({0, 1} ,⊕). Gene reordering [3, 8] can be considered as a special case of the change of basis. If T is just a permutation matrix, a change of basis means a reordering of gene positions in encoding. The concept of changing basis is much more general than that of gene reordering. Coordinate changes based on eigenspace and orthogonalization have been studied [10, 11]. But, they focused on realcode representation. These results cannot apply to pseudoboolean functions using binary representation because of the following proposition.