Detecting Spin-Flip Symmetry in Optimization Problems

Abstract

The presence of symmetry in the representation of an optimization problem can cause the search algorithm to get stuck before reaching the global optimum. The traveling salesman problem and the graph coloring problem are some well-known NP-complete optimization problems containing symmetry in their usual representation. This paper describes a class of symmetry, called spin-flip symmetry, which one finds in functions like the one-dimensional nearest neighbor interaction functions. Spin-flip symmetry indicates that bit-complementary strings have the same function value. This notion can be generalized to substrings, called spin-flip blocks, in a canonical way. We distinguish two specific cases of spin-flip symmetry and introduce a spin-flip detection algorithm. The performance of the algorithm strongly depends on the initial sample the algorithm uses to detect the spin-flip blocks. The algorithm is designed to detect spin-flip symmetry in the whole search space, as well as in its hyperplanes. The difficulty with detection in hyperplanes is related to the detection of the correct hyperplane, which can be time consuming. Once the desired hyperplane is found, the spin-flip block can be detected using the normal detection procedure. The one-max problem shows that spin-flip symmetry in other types of subspaces, like the subspace in which the number of 1 s equals the number of Os, is not detected. For these kinds of subspaces the method needs to be extended.