EUVIMEDEUVIMED entdecken
Crossref

Symmetry Breaking for Voting Mechanisms*

Preethi Sankineni, Andrew M Sutton

Evolutionary Computation · 2023

DOI: 10.1162/evco_a_00327 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2023. Verfasst von Preethi Sankineni und 1 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA sanki002@d.umn.edu. Hauptthemen laut MEDLINE: Algorithms. Die Arbeit nennt 37 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsProbabilityPopulation Density

Stichwörter der Autor:innen

Runtime analysiscrossoversymmetry breaking

Autor:innen und Institutionen

  • Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA sanki002@d.umn.edu.
  • Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA amsutton@d.umn.edu.

Zitieren

APA

Sankineni, P., & Sutton, A. M. (2023). Symmetry Breaking for Voting Mechanisms*. Evolutionary Computation. https://doi.org/10.1162/evco_a_00327

Vancouver

Sankineni P, Sutton AM. Symmetry Breaking for Voting Mechanisms*. Evolutionary Computation. 2023. doi:10.1162/evco_a_00327

BibTeX
@article{Sankineni2023,
  author = {Sankineni, Preethi and Sutton, Andrew M},
  title = {Symmetry Breaking for Voting Mechanisms*},
  journal = {Evolutionary Computation},
  year = {2023},
  doi = {10.1162/evco_a_00327}
}
Kostenlos starten →