Symmetry Breaking for Voting Mechanisms*
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.
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)
Stichwörter der Autor:innen
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}
}
EUVIMED