Sorting by Swaps with Noisy Comparisons
OPEN ACCESS
Author / Producer
Date
2019-02-15
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study sorting of permutations by random swaps if each comparison
gives the wrong result with some fixed probability p < 1/2. We use this process as
prototype for the behaviour of randomized, comparison-based optimization heuristics
in the presence of noisy comparisons. As quality measure, we compute the expected
fitness of the stationary distribution. To measure the runtime, we compute the minimal
number of steps after which the average fitness approximates the expected fitness of
the stationary distribution. We study the process where in each round a random pair
of elements at distance at most r are compared. We give theoretical results for the
extreme cases r = 1 and r = n, and experimental results for the intermediate cases.
We find a trade-off between faster convergence (for large r) and better quality of the
solution after convergence (for small r).
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
81 (2)
Pages / Article No.
796 - 827
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Sorting; Random swaps; Evolutionary algorithms; Comparison-based; Noise; Optimization heuristics
Organisational unit
03672 - Steger, Angelika / Steger, Angelika
03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
Notes
Published in the Special Issue on "Theory of Genetic and Evolutionary Computation".
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.
Funding
165524 - Energy-Tunable Combinatorial Algorithms (SNF)