Symmetry Breaking for Voting Mechanisms

Preethi Sankineni, Andrew M. Sutton

Research output: Contribution to journalArticlepeer-review

Abstract

Recently, Rowe and Aishwaryaprajna (2019) introduced a simple majority vote technique that efficiently solves Jump with large gaps, OneMax with large noise, and any monotone function with a polynomial-size image. In this paper, we identify a pathological condition for this algorithm: the presence of spin-flip symmetry in the problem instance. Spin-flip symmetry is the invariance of a pseudo-Boolean function to complementation. Many important combinatorial optimization problems admit objective functions that exhibit this pathology, such as graph problems, Ising models, and variants of propositional satisfiability. We prove that no population size exists that allows the majority vote technique to solve spin-flip symmetric functions of unitation with reasonable probability. To remedy this, we introduce a symmetry-breaking technique that allows the majority vote algorithm to overcome this issue for many landscapes. This technique requires only a minor modification to the original majority vote algorithm to force it to sample strings in {0, 1}n from a dimension n − 1 hyperplane. We prove a sufficient condition for a spin-flip symmetric function to possess in order for the symmetry-breaking voting algorithm to succeed, and prove its efficiency on generalized TwoMax, a spin-flip symmetric variant of Jump, and families of constructed 3-NAE-SAT and 2-XOR-SAT formulas. We also prove that the algorithm fails on the one-dimensional Ising model, and suggest different techniques for overcoming this. Finally, we present empirical results that explore the tightness of the runtime bounds and the performance of the technique on randomized satisfiability variants.

Original languageEnglish (US)
Pages (from-to)309-335
Number of pages27
JournalEvolutionary Computation
Volume31
Issue number3
DOIs
StatePublished - Sep 2023

Bibliographical note

Publisher Copyright:
© 2023 Massachusetts Institute of Technology.

Keywords

  • Runtime analysis
  • crossover
  • symmetry breaking

PubMed: MeSH publication types

  • Journal Article

Fingerprint

Dive into the research topics of 'Symmetry Breaking for Voting Mechanisms'. Together they form a unique fingerprint.

Cite this