On Selecting the Best Individual in Noisy Environments

On Selecting the Best Individual in Noisy Environments. Jaśkowski, W., Kotłowski, W., Keijzer, M., Antoniol, G., Congdon, C. B., Deb, K., Doerr, B., Hansen, N., Holmes, J. H., Hornby, G. S., Howard, D., Kennedy, J., Kumar, S., Lobo, F. G., Miller, J. F., Moore, J., Neumann, F., Pelikan, M., Pollack, J., Sastry, K., Stanley, K., Stoica, A., Talbi, E. G., & Wegener, I. In GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 961--968, jul, 2008. Association for Computing Machinery.

Paper abstract bibtex

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.

@inproceedings{ jaskowski08selecting,
  author    = {Wojciech Jaśkowski and Wojciech Kotłowski and 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},
  title     = {On Selecting the Best Individual in Noisy Environments}, 
  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.},
  booktitle   = {GECCO &#39;08: Proceedings of the 10th annual conference on Genetic and evolutionary computation},
  month   = {jul},
  organization   = {Association for Computing Machinery},
  pages   = {961--968},
  url   = {http://www.cs.put.poznan.pl/wkotlowski/research/2008GECCOBest.pdf} ,
  year   = {2008}
}

Downloads: 0