by Wojciech Jaśkowski, Wojciech Kotłowski
Abstract:
In evolutionary algorithms, the typical post-processing phase involves selection of the best-of-run individual, which becomes the final outcome of the evolutionary run. Trivial for deterministic problems, this task can get computationally demanding in noisy environments. A typical naive procedure used in practice is to repeat the evaluation of each individual for the fixed number of times and select the one with the highest average. In this paper, we consider several algorithms that can adaptively choose individuals to evaluate basing on the results evaluations which have already been performed. The procedures are designed without any specific assumption about noise distribution. In the experimental part, we compare our algorithms with the naive and optimal procedures, and find out that the performance of typically used naive algorithm is poor even for relatively moderate noise. We also show that one of our algorithms is nearly optimal for most of the examined situations.
Reference:
On Selecting the Best Individual in Noisy Environments (Wojciech Jaśkowski, Wojciech Kotłowski), In GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation (Maarten Keijzer, Giuliano Antoniol, Clare Bates Congdon, Kalyanmoy Deb, Benjamin Doerr, Nikolaus Hansen, John H. Holmes, Gregory S. Hornby, Daniel Howard, James Kennedy, Sanjeev Kumar, Fernando G. Lobo, Julian Francis Miller, Jason Moore, Frank Neumann, Martin Pelikan, Jordan Pollack, Kumara Sastry, Kenneth Stanley, Adrian Stoica, El-Ghazali Talbi, Ingo Wegener, eds.), Association for Computing Machinery, 2008.
Bibtex Entry:
@InProceedings{Jaskowski2008selecting,
Title = {On Selecting the Best Individual in Noisy Environments},
Author = {Wojciech Jaśkowski and Wojciech Kot{ł}owski},
Booktitle = {GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation},
Year = {2008},
Address = {Atlanta, GA, USA},
Editor = {Maarten Keijzer and Giuliano Antoniol and Clare Bates Congdon and Kalyanmoy Deb and Benjamin Doerr and Nikolaus Hansen and John H. Holmes and Gregory S. Hornby and Daniel Howard and James Kennedy and Sanjeev Kumar and Fernando G. Lobo and Julian Francis Miller and Jason Moore and Frank Neumann and Martin Pelikan and Jordan Pollack and Kumara Sastry and Kenneth Stanley and Adrian Stoica and El-Ghazali Talbi and Ingo Wegener},
Month = {jul},
Organization = {Association for Computing Machinery},
Pages = {961--968},
Publisher = {Association for Computing Machinery},
Abstract = {In evolutionary algorithms, the typical post-processing phase involves selection of the best-of-run individual, which becomes the final outcome of the evolutionary run. Trivial for
deterministic problems, this task can get computationally
demanding in noisy environments. A typical naive procedure
used in practice is to repeat the evaluation of each
individual for the fixed number of times and select the one
with the highest average. In this paper, we consider several
algorithms that can adaptively choose individuals to evaluate
basing on the results evaluations which have already
been performed. The procedures are designed without any
specific assumption about noise distribution. In the experimental
part, we compare our algorithms with the naive and
optimal procedures, and find out that the performance of
typically used naive algorithm is poor even for relatively
moderate noise. We also show that one of our algorithms is
nearly optimal for most of the examined situations.},
Doi = {doi:10.1145/1389095.1389278},
Keywords = {approximation models, evolutionary algorithm, evolutionary computation, noise, robustness, uncertainty, genetic algorithms},
Url = {http://www.cs.put.poznan.pl/wkotlowski/research/2008GECCOBest.pdf}
}