research-article

On selecting the best individual in noisy environments

Authors:

Wojciech Jaskowski,

Wojciech KotlowskiAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 961 - 968

https://doi.org/10.1145/1389095.1389278

Published: 12 July 2008 Publication History

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.

References

[1]

R. E. Bechhofer, T. J. Santner, and D. M. Goldsman. Design and Analysis for Statistical Selection, Screening, and Multiple Comparisons. John Wiley & Sons, Inc., New York, 1995.

[2]

James O. Berger. Statistical Decision Theory and Bayesian Analysis. Springer, 2nd edition, 1993.

[3]

Hans-Georg Beyer and Bernhard Sendhoff. Evolutionary algorithms in the presence of noise: To sample or not to sample. In FOCI, pages 17--24. IEEE, 2007.

[4]

Jürgen Branke, Stephen E. Chick, and Christian Schmidt. Selecting a selection procedure. Management Science, 53(12):1916--1932, 2007.

Digital Library

[5]

Jürgen Branke and Christian Schmidt. Sequential sampling in noisy environments. In Xin Yao et. al., editor, Parallel Problem Solving from Nature - PPSN VIII, volume 3242 of LNCS, pages 202--211, Birmingham, UK, 18-22 September 2004. Springer-Verlag.

[6]

Kathryn Chaloner and Isabella Verdinelli. Bayesian experimental design: A review. Statistical Science, 10(3):273--304, 1995.

[7]

C.-H. Chen. A lower bound for the correct subset-selection probability and its application to discrete event simulations. IEEE Transactions on Automatic Control, 41(8):1227--1231, 1996.

[8]

Stephen E. Chick and Koichiro Inoue. New two-stage and sequential procedures for selecting the best simulated system. Operations Research, 59(5):732--743, 2001.

Digital Library

[9]

Shanti S. Gupta and Klaus J. Miescke. Bayesian look ahead one-stage sampling allocations for selection of the best population. Journal of Statistical Planning and Inference, 54:229--244, 1996.

[10]

Koichiro Inoue, Stephen E. Chick, and Chun-Hung Chen. An empirical evaluation of several methods to select the best system. ACM Transactions on Modeling and Computer Simulation, 9(4):381--407, 1999.

Digital Library

[11]

Yaochu Jin and J. Branke. Evolutionary optimization in uncertain environments-a survey. Evolutionary Computation, IEEE Transactions on, 9(3):303--317, June 2005. Survey of noisy environments.

Digital Library

[12]

Dennis V. Lindley. Bayesian Statistics -- a Review. SIAM, Philadelphia, 1972.

[13]

O. Maron and A.W. Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. Advances in Neural Information Processing Systems, 6:59--66, 1994.

[14]

B.L. Miller. Noise, Sampling, and Efficient Genetic Algorithms. PhD thesis, University of Illinois at Urbana-Champaign, 1997.

Digital Library

[15]

B.L. Miller and D.E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Technical Report 95006, Dept. of General Engineering, University of Illinois at Urbana-Champaign, July 1995.

[16]

B.L. Miller and D.E. Goldberg. Optimal sampling for genetic algorithms. Technical Report 96005, Dept. of General Engineering, University of Illinois at Urbana-Champaign, 1996.

[17]

B. Yuan and M. Gallagher. Statistical racing techniques for improved empirical evaluation of evolutionary algorithms. In PPSN VIII, volume 3242 of LNCS, pages 172--181, 2004.

Cited By

Glenn J(2013)Evaluation scheduling in noisy environments2013 IEEE Symposium on Foundations of Computational Intelligence (FOCI)10.1109/FOCI.2013.6602457(68-75)Online publication date: Apr-2013
https://doi.org/10.1109/FOCI.2013.6602457
Stonedahl FStonedahl SPelikan MBranke J(2010)Heuristics for sampling repetitions in noisy landscapes with fitness cachingProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830532(273-280)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830532

Index Terms

On selecting the best individual in noisy environments
1. Mathematics of computing
  1. Mathematical software
  2. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods

Recommendations

Evolutionary optimization in uncertain environments-a survey

Evolutionary algorithms often have to solve optimization problems in the presence of a wide range of uncertainties. Generally, uncertainties in evolutionary computation can be divided into the following four categories. First, the fitness function is ...
Heuristics for sampling repetitions in noisy landscapes with fitness caching
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

For many large-scale combinatorial search/optimization problems, meta-heuristic algorithms face noisy objective functions, coupled with computationally expensive evaluation times. In this work, we consider the interaction between the technique of "...
Differential evolution with individual-dependent and dynamic parameter adjustment

Differential evolution (DE) is a powerful and versatile evolutionary algorithm for global optimization over continuous search space, whose performance is significantly influenced by its mutation operator and control parameters (population size, scaling ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Glenn J(2013)Evaluation scheduling in noisy environments2013 IEEE Symposium on Foundations of Computational Intelligence (FOCI)10.1109/FOCI.2013.6602457(68-75)Online publication date: Apr-2013
https://doi.org/10.1109/FOCI.2013.6602457
Stonedahl FStonedahl SPelikan MBranke J(2010)Heuristics for sampling repetitions in noisy landscapes with fitness cachingProceedings of the 12th annual conference on Genetic and evolutionary computation10.1145/1830483.1830532(273-280)Online publication date: 7-Jul-2010
https://dl.acm.org/doi/10.1145/1830483.1830532

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten