{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T18:15:51Z","timestamp":1693678551257},"reference-count":37,"publisher":"MIT Press","issue":"3","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1162\/evco_a_00327","type":"journal-article","created":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T19:40:27Z","timestamp":1680810027000},"page":"309-335","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":0,"title":["Symmetry Breaking for Voting Mechanisms*"],"prefix":"10.1162","volume":"31","author":[{"given":"Preethi","family":"Sankineni","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA sanki002@d.umn.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Minnesota Duluth, Duluth, MN, USA amsutton@d.umn.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2023,9,1]]},"reference":[{"key":"2023090105043411700_B1","first-page":"1","article-title":"The query complexity of finding a hidden permutation","volume":"8066","author":"Afshani","year":"2013","journal-title":"Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday"},{"key":"2023090105043411700_B2","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-30217-9_4","article-title":"The Ising model: Simple evolutionary algorithms as adaptation schemes","volume":"3242","author":"Briest","year":"2004","journal-title":"Proceedings of the Eighth International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043411700_B3","first-page":"148","article-title":"Symmetry-breaking predicates for search problems","author":"Crawford","year":"1996","journal-title":"Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning"},{"key":"2023090105043411700_B4","author":"Culberson","year":"1992","journal-title":"Genetic invariance: A new paradigm for genetic algorithm design"},{"key":"2023090105043411700_B5","first-page":"53","article-title":"Sulla proseguibilit\u00e0 di processi aleatori scambiabili","volume":"1","author":"de Finetti","year":"1969","journal-title":"Rendiconti dell'Istituto di Matematica dell'Universit\u00e0 di Trieste"},{"key":"2023090105043411700_B6","volume-title":"Probability, induction and statistics. The art of guessing","author":"de Finetti","year":"1972"},{"issue":"2","key":"2023090105043411700_B7","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF00486116","article-title":"Finite forms of de Finetti's theorem on exchangeability","volume":"36","author":"Diaconis","year":"1977","journal-title":"Synthese"},{"issue":"5","key":"2023090105043411700_B8","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1109\/TEVC.2003.818192","article-title":"The analysis of a recombinative hill-climber on H-IFF","volume":"7","author":"Dietzfelbinger","year":"2003","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"4","key":"2023090105043411700_B9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1162\/EVCO_a_00158","article-title":"Unbiased black-box complexities of jump functions","volume":"23","author":"Doerr","year":"2015","journal-title":"Evolutionary Computation"},{"key":"2023090105043411700_B10","first-page":"163","article-title":"Faster black-box algorithms through higher arity operators","author":"Doerr","year":"2011","journal-title":"Proceedings of the Eleventh ACM Conference on Foundations of Genetic Algorithms"},{"issue":"1\u20132","key":"2023090105043411700_B11","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0304-3975(01)00182-7","article-title":"On the analysis of the (1+1) evolutionary algorithm","volume":"276","author":"Droste","year":"2002","journal-title":"Theoretical Computer Science"},{"key":"2023090105043411700_B12","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s00224-004-1177-z","article-title":"Upper and lower bounds for randomized search heuristics in black-box optimization","volume":"39","author":"Droste","year":"2006","journal-title":"Theory of Computing Systems"},{"key":"2023090105043411700_B13","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/3-540-58484-6_252","article-title":"Genetic algorithms with multi-parent recombination","volume":"866","author":"Eiben","year":"1994","journal-title":"Proceedings of the Third International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043411700_B14","first-page":"1100","article-title":"A polynomial upper bound for a mutation-based algorithm on the two-dimensional Ising model","volume":"3102","author":"Fischer","year":"2004","journal-title":"Proceedings of the Genetic and Evolutionary Computation (GECCO)"},{"issue":"2\u20133","key":"2023090105043411700_B15","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.tcs.2005.04.002","article-title":"The one-dimensional Ising model: Mutation versus recombination","volume":"344","author":"Fischer","year":"2005","journal-title":"Theoretical Computer Science"},{"key":"2023090105043411700_B16","first-page":"661","article-title":"Fast building block assembly by majority vote crossover","author":"Friedrich","year":"2016","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023090105043411700_B17","volume-title":"Genetic algorithms in search optimization and machine learning","author":"Goldberg","year":"1989"},{"key":"2023090105043411700_B18","first-page":"626","article-title":"From TwoMax to the Ising model: Easy and hard symmetrical problems","author":"Hoyweghen","year":"2002","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"4","key":"2023090105043411700_B19","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1162\/106365602760972749","article-title":"Spin-flip symmetry and synchronization","volume":"10","author":"Hoyweghen","year":"2002","journal-title":"Evolutionary Computation"},{"issue":"1","key":"2023090105043411700_B20","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1007\/BF02980577","article-title":"Beitrag zur theorie des ferromagnetismus","volume":"31","author":"Ising","year":"1925","journal-title":"Zeitschrift f\u00fcr Physik"},{"key":"2023090105043411700_B21","first-page":"16","article-title":"On the black-box complexity of example functions: The Real Jump function","author":"Jansen","year":"2015","journal-title":"Proceedings of the Thirteenth ACM Conference on Foundations of Genetic Algorithms"},{"issue":"4","key":"2023090105043411700_B22","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00453-012-9616-8","article-title":"Black-box search by unbiased variation","volume":"64","author":"Lehre","year":"2012","journal-title":"Algorithmica"},{"key":"2023090105043411700_B23","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001","author":"Moore","year":"2011","journal-title":"The nature of computation"},{"key":"2023090105043411700_B24","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BFb0056850","article-title":"The effect of spin-flip symmetry on the performance of the simple GA","volume":"1498","author":"Naudts","year":"1998","journal-title":"Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043411700_B25","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BFb0026602","article-title":"SGA search dynamics on second order functions","volume":"1363","author":"Naudts","year":"1997","journal-title":"Proceedings of the Third European Conference on Artificial Evolution"},{"key":"2023090105043411700_B26","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/3-540-45356-3_38","article-title":"Genetic algorithms, clustering, and the breaking of symmetry","volume":"1917","author":"Pelikan","year":"2000","journal-title":"Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043411700_B27","first-page":"273","article-title":"Symmetry breaking and local search spaces","volume":"3524","author":"Prestwich","year":"2005","journal-title":"Proceedings of the Second International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems"},{"issue":"1","key":"2023090105043411700_B28","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s10601-004-5306-8","article-title":"Symmetry breaking revisited","volume":"10","author":"Puget","year":"2005","journal-title":"Constraints"},{"key":"2023090105043411700_B29","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/3299904.3340305","article-title":"The benefits and limitations of voting mechanisms in evolutionary optimisation","author":"Rowe","year":"2019","journal-title":"Proceedings of the Fifteenth ACM\/SIGEVO Conference on Foundations of Genetic Algorithms"},{"key":"2023090105043411700_B30","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-030-72904-2_12","article-title":"Symmetry breaking for voting mechanisms","volume":"12692","author":"Sankineni","year":"2021","journal-title":"Proceedings of the Twenty-First European Conference on Evolutionary Computation in Combinatorial Optimization"},{"issue":"1","key":"2023090105043411700_B31","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1006\/jmaa.1999.6420","article-title":"Inequalities for binomial coefficients","volume":"236","author":"Sasv\u00e1ri","year":"1999","journal-title":"Journal of Mathematical Analysis and Applications"},{"issue":"12","key":"2023090105043411700_B32","doi-asserted-by":"publisher","first-page":"1539","DOI":"10.1016\/j.dam.2005.10.018","article-title":"Generating effective symmetry-breaking predicates for search problems","volume":"155","author":"Shlyakhter","year":"2007","journal-title":"Discrete Applied Mathematics"},{"key":"2023090105043411700_B33","first-page":"244","article-title":"Extending SAT solvers to cryptographic problems","volume":"5584","author":"Soos","year":"2009","journal-title":"Proceedings of the Twelfth International Conference on Theory and Applications of Satisfiability Testing"},{"key":"2023090105043411700_B34","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1145\/1068009.1068202","article-title":"Crossover is provably essential for the Ising model on trees","author":"Sudholt","year":"2005","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"issue":"3","key":"2023090105043411700_B35","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00453-015-0027-5","article-title":"Superpolynomial lower bounds for the (1+1) EA on some easy combinatorial problems","volume":"75","author":"Sutton","year":"2016","journal-title":"Algorithmica"},{"key":"2023090105043411700_B36","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-319-99259-4_5","article-title":"Exploration and exploitation without mutation: Solving the Jump function in \u03d1(n) time","volume":"11102","author":"Whitley","year":"2018","journal-title":"Proceedings of the Fifteenth International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043411700_B37","first-page":"2:1","article-title":"On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms","author":"Witt","year":"2021","journal-title":"Proceedings of the Sixteenth ACM Conference on Foundations of Genetic Algorithms"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/309\/2155628\/evco_a_00327.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/309\/2155628\/evco_a_00327.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T05:04:54Z","timestamp":1693544694000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/31\/3\/309\/115604\/Symmetry-Breaking-for-Voting-Mechanisms"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":37,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9,1]]},"published-print":{"date-parts":[[2023,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00327","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}