Sorting by swaps with noisy comparisons
Tomáš Gavenčiak, Barbara Geissmann, Johannes Lengler · Proceedings of the Genetic and Evolutionary Computation Conference · 2017
We study sorting of permutations by random swaps if the comparison operator is noisy. The noise is not associated with the underlying fitness but is inherent to the comparison operator. This type of fitness-independent noise has not been studied before in the community but is prototypical for comparison-based evolutionary algorithms, which often do not need to compute or approximate explicit fitness values. As quality measure, we compute the average fitness of the stationary distribution. To measure runtime, we compute the minimal number of steps after which the expected fitness approximates the average fitness of the stationary distribution.