The benefits and limitations of voting mechanisms in evolutionary optimisation

Jon Rowe; null Aishwaryaprajna

doi:10.1145/3299904.3340305

The benefits and limitations of voting mechanisms in evolutionary optimisation

Jon Rowe, Aishwaryaprajna

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

252 Downloads (Pure)

Abstract

We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX andJUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ² = O(n) and in O(σ² log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

Original language	English
Title of host publication	FOGA '19 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Publisher	Association for Computing Machinery
Pages	34-42
Number of pages	9
ISBN (Print)	978-1-4503-6254-2
DOIs	https://doi.org/10.1145/3299904.3340305
Publication status	Published - 27 Aug 2019
Event	15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV) - Hasso Plattner Institute, Potsdam, Germany Duration: 27 Aug 2019 → 29 Aug 2019

Conference

Conference	15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)
Abbreviated title	FOGA 2019
Country/Territory	Germany
City	Potsdam
Period	27/08/19 → 29/08/19

Keywords

crossover
noise handling
voting

Access to Document

10.1145/3299904.3340305Licence: None: All rights reserved

Jon_Rowe_&_A_Aishwaryaprajna_The_benefits_and_limitations_of_voting_mechanisms_in_evolutionary_optimisation_FOGA_XV_2019
© ACM, 2019. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in FOGA '19 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, (27/08/2019) http://doi.acm.org/10.1145/3299904.3340305
Accepted author manuscript, 730 KBLicence: None: All rights reserved

https://dl.acm.org/citation.cfm?id=3340305Licence: None: All rights reserved

Cite this

@inproceedings{a736e98271184cb1992aa1a31e59c35c,

title = "The benefits and limitations of voting mechanisms in evolutionary optimisation",

abstract = "We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX andJUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ2 = O(n) and in O(σ2 log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.",

keywords = "crossover, noise handling, voting",

author = "Jon Rowe and Aishwaryaprajna",

year = "2019",

month = aug,

day = "27",

doi = "10.1145/3299904.3340305",

language = "English",

isbn = "978-1-4503-6254-2",

pages = "34--42",

booktitle = "FOGA '19 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms",

publisher = "Association for Computing Machinery ",

note = "15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), FOGA 2019 ; Conference date: 27-08-2019 Through 29-08-2019",

}

Rowe, J & Aishwaryaprajna 2019, The benefits and limitations of voting mechanisms in evolutionary optimisation. in FOGA '19 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms. Association for Computing Machinery , pp. 34-42, 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Potsdam, Germany, 27/08/19. https://doi.org/10.1145/3299904.3340305

TY - GEN

T1 - The benefits and limitations of voting mechanisms in evolutionary optimisation

AU - Rowe, Jon

AU - Aishwaryaprajna, null

PY - 2019/8/27

Y1 - 2019/8/27

N2 - We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX andJUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ2 = O(n) and in O(σ2 log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

AB - We study the use of voting mechanisms in populations, and introduce a new Voting algorithm which can solve ONEMAX andJUMP in O(n log n), even for gaps as large as O(n). More significantly, the algorithm solves ONEMAX with added posterior noise in O(n log n), when the variance of the noise distribution is σ2 = O(n) and in O(σ2 log n) when the noise variance is greater than this. We assume only that the noise distribution has finite mean and variance and (for the larger noise case) that it is unimodal. We also examine the performance on arbitrary linear and monotonic functions. The Voting algorithm fails on LEADINGONES but we give a variant which can solve the problem in O(n log n). We empirically study the use of voting in population based algorithms (UMDA, PCEA and cGA) and show that this can be effective for large population sizes.

KW - crossover

KW - noise handling

KW - voting

UR - http://www.scopus.com/inward/record.url?scp=85076401629&partnerID=8YFLogxK

U2 - 10.1145/3299904.3340305

DO - 10.1145/3299904.3340305

M3 - Conference contribution

SN - 978-1-4503-6254-2

SP - 34

EP - 42

BT - FOGA '19 Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms

PB - Association for Computing Machinery

T2 - 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV)

Y2 - 27 August 2019 through 29 August 2019

ER -

The benefits and limitations of voting mechanisms in evolutionary optimisation

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this