%0 Conference Paper %1 DBLP:conf/foga/0001KQS17 %A Friedrich, Tobias %A Kötzing, Timo %A Quinzan, Francesco %A Sutton, Andrew Michael %B Foundations of Genetic Algorithms (FOGA) %D 2017 %I ACM Press %K testing typo3 %P 25-35 %T Resampling vs Recombination: a Statistical Run Time Estimation %X Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.

@inproceedings{DBLP:conf/foga/0001KQS17, abstract = {Noise is pervasive in real-world optimization, but there is still little understanding of the interplay between the operators of randomized search heuristics and explicit noise-handling techniques, such as statistical resampling. In this paper, we report on several statistical models and theoretical results that help to clarify this reciprocal relationship for a collection of randomized search heuristics on noisy functions. We consider the optimization of pseudo-Boolean functions under additive posterior Gaussian noise and explore the trade-o between noise reduction and the computational cost of resampling. We first perform experiments to find the optimal parameters at a given noise intensity for a mutation-only evolutionary algorithm, a genetic algorithm employing recombination, an estimation of distribution algorithm (EDA), and an ant colony optimization algorithm. We then observe how the optimal parameter depends on the noise intensity for the different algorithms. Finally, we locate the point where statistical resampling costs more than it is worth in terms of run time. We find that the EA requires the highest number of resamples to obtain the best speed-up, whereas crossover reduces both the run time and the number of resamples required. Most surprisingly, we find that EDA-like algorithms require no resampling, and can handle noise implicitly.}, added-at = {2017-09-19T19:30:21.000+0200}, author = {Friedrich, Tobias and Kötzing, Timo and Quinzan, Francesco and Sutton, Andrew Michael}, biburl = {https://www.bibsonomy.org/bibtex/21d08887612b798c123137238316a654f/typo3tester}, booktitle = {Foundations of Genetic Algorithms (FOGA)}, interhash = {3e97e17a9101752c5c9944aa265e80da}, intrahash = {1d08887612b798c123137238316a654f}, keywords = {testing typo3}, pages = {25-35}, publisher = {ACM Press}, timestamp = {2017-09-19T20:37:23.000+0200}, title = {Resampling vs Recombination: a Statistical Run Time Estimation}, year = 2017 }