Abstract
A simple Voting algorithm has been shown to be effective at solving the ONEMAX problem in the presence of high levels of posterior noise in our previous research. In this paper, we extend this analysis to several different noise models, and show that the Voting algorithm remains robust in all of them. We consider the prior noise model and the partial evaluation of randomly selected bits. The Voting algorithm has superior runtime bounds on these problems compared to other published algorithms. We also introduce a new variant of partial evaluation, and further consider the simple model when a comparison-based oracle produces incorrect results with a fixed probability.
Original language | English |
---|---|
Article number | 113844 |
Number of pages | 14 |
Journal | Theoretical Computer Science |
Volume | 957 |
Early online date | 29 Mar 2023 |
DOIs | |
Publication status | Published - 12 May 2023 |
Bibliographical note
Publisher Copyright:© 2023 The Author(s)
Keywords
- Noise
- Recombination
- Voting
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science