Solving Symmetric Functions Using a Majority Vote Algorithm

Abstract

The Majority Vote Algorithm, introduced by Rowe and Aishwaryaprajna in 2019 in a previous research, uses a majority voting technique to effectively solve the OneMax benchmark function with large noise, the Jump function with large gaps and any monotonic function with a polynomial image size. The Voting mechanism has been used as an evolutionary operator for a long time but came into light recently in the community.In our research, we identified the presence of a pathological condition called spin flip symmetry for the algorithm. Spin flip symmetry is the invariance of a pseudo-Boolean function to its complement. We prove that the majority voting technique cannot solve spin flip symmetric functions with reasonable probability. To address this issue, this thesis introduces a simple symmetry breaking technique which allows the majority voting to succeed. We demonstrate its efficiency on TwoMax and a new function called the SymmetricJump function. We also prove that the algorithm fails to solve the one-dimensional Ising Model. We use the significant-bit voting algorithm to check if the ising model works well with it and find that this algorithm also fails to solve the problem. We perform an experimental study to explore the tightness of the run time bounds and algorithm performance.