Article

Integrating techniques from statistical ranking into evolutionary algorithms

Authors:

Christian Schmidt,

Jürgen Branke,

Stephen E. ChickAuthors Info & Claims

EuroGP'06: Proceedings of the 2006 international conference on Applications of Evolutionary Computing

Pages 752 - 763

https://doi.org/10.1007/11732242_73

Published: 10 April 2006 Publication History

Abstract

Many practical optimization problems are subject to uncertain fitness evaluations. One way to reduce the noise is to average over multiple samples of the fitness function in order to evaluate a single individual. This paper proposes a general way to integrate statistical ranking and selection procedures into evolutionary algorithms. The proposed procedure focuses sampling on those individuals that are crucial for the evolutionary algorithm, and distributes samples in a way that efficiently reduces uncertainty. The goal is to drastically reduce the number of evaluations required for a proper operation of the evolutionary algorithm in noisy environments.

References

[1]

D. V. Arnold and H.-G. Beyer. A comparison of evolution strategies with other direct search methods in the presence of noise. Computational Optimization and Applications, 24:135-159, 2003.

Digital Library

[2]

T. Bartz-Beielstein, D. Blum, and J. Branke. Particle swarm optimization and sequential sampling in noisy environments. In Metaheuristics International Conference, 2005.

[3]

H.-G. Beyer. Toward a theory of evolution strategies: Some asymptotical results from the (1 +, ?)-theory. Evolutionary Computation, 1(2):165-188, 1993.

Digital Library

[4]

J. Boesel. Search and Selection for Large-Scale Stochastic Optimization. PhD thesis, Northwestern University, Evanston, Illinois, USA, 1999.

Digital Library

[5]

J. Boesel, B. L. Nelson, and S. H. Kim. Usint ranking and selection to "clean up" after simulation optimization. Operations Research, 51:814-825, 2003.

Digital Library

[6]

J. Branke. Evolutionary Optimization in Dynamic Environments. Kluwer, 2001.

Digital Library

[7]

J. Branke, S. Chick, and C. Schmidt. New developments in ranking and selection: An empirical comparison of the three main approaches. In N.E. Kuhl, M. N. Steiger, F. B. Armstrong, and J. A. Joines, editors, Winter Simulation Conference, pages 708-717. IEEE, 2005.

Digital Library

[8]

J. Branke and C. Schmidt. Selection in the presence of noise. In E. Cantu-Paz, editor, Genetic and Evolutionary Computation Conference, volume 2723 of LNCS, pages 766-777. Springer, 2003.

Digital Library

[9]

J. Branke and C. Schmidt. Sequential sampling in noisy environments. In X. Yao et al., editor, Parallel Problem Solving from Nature, volume 3242 of LNCS, pages 202-211. Springer, 2004.

[10]

P. Buchholz and A. Thümmler. Enhancing evolutionary algorithms with statistical sselection procedures for simulation optimization. 2005.

[11]

E. Cantu-Paz. Adaptive sampling for noisy problems. In K. Deb et al., editors, Genetic and Evolutionary Computation Conference, volume 3102 of LNCS, pages 947-958. Springer, 2004.

[12]

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.

[13]

A. Di Pietro, L. While, and L. Barone. Applying evolutionary algorithms to problems with noisy, time-consuming fitness functions. In Congress on Evolutionary Computation, pages 1254-1261. IEEE, 2004.

[14]

U. Hammel and T. Bäck. Evolution strategies on noisy functions, how to improve convergence properties. In Y. Davidor, H. P. Schwefel, and R. Männer, editors, Parallel Problem Solving from Nature, volume 866 of LNCS. Springer, 1994.

Digital Library

[15]

H. E. Hedlund and M. Mollaghasemi. A genetic algorithm and an indifference-zone ranking and selection framework for simulation optimization. InWinter Simulation Conference, pages 417-421. IEEE, 2001.

Digital Library

[16]

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

Digital Library

[17]

P. Stagge. Averaging efficiently in the presence of noise. In A. E. Eiben, T. Bäck, M. Schoenauer, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature V, volume 1498 of LNCS, pages 188-197. Springer, 1998.

Digital Library

Cited By

Branke JAuger AStützle T(2019)Simulation optimisationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323385(862-889)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323385
Görder BKolonko M(2019)Ranking and SelectionACM Transactions on Modeling and Computer Simulation10.1145/324104229:1(1-24)Online publication date: 24-Jan-2019
https://dl.acm.org/doi/10.1145/3241042
Branke JTakadama K(2018)Simulation optimisationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207887(745-772)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207887
Show More Cited By

Recommendations

Using holey fitness landscapes to counteract premature convergence in evolutionary algorithms
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computation

Premature convergence is a persisting problem in evolutionary optimisation, in particular - genetic algorithms. While a number of methods exist to approach this issue, they usually require problem specific calibration or only partially resolve the issue,...
Fast non-elitist evolutionary algorithms with power-law ranking selection
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Theoretical evidence suggests that non-elitist evolutionary algorithms (EAs) with non-linear selection mechanisms can efficiently overcome broad classes of local optima where elitist EAs fail. However, the analysis assumes a weak selective pressure and ...
Towards the right amount of randomness in quantum-inspired evolutionary algorithms

Quantum-inspired evolutionary algorithms (QIEAs) combine the advantages of quantum-inspired bit (Q-bit), representation and operators with evolutionary algorithms for better performance. Using quantum-inspired representation the complete binary search ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EuroGP'06: Proceedings of the 2006 international conference on Applications of Evolutionary Computing

April 2006

809 pages

ISBN:3540332375

Editors:
Franz Rothlauf
Johannes Gutenberg University, Mainz, Germany
,
Jürgen Branke
Institute AIFB, University of Karlsruhe, Karlsruhe, Germany
,
Stefano Cagnoni
Dipartimento di Ingegneria dell'Informazione, Università di Parma, Karlsruhe
,
Ernesto Costa
Dipartimento di Ingegneria dell'Informazione, Centre of Informatics and Systems of the University of Coimbra, Karlsruhe
,
Carlos Cotta
Dept. LCC, Universidad de Málaga, Karlsruhe, Spain

Sponsors

EvoNet
Artpool Art Research Center, Budapest, Hungary: Artpool Art Research Center, Budapest, Hungary

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 10 April 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Branke JAuger AStützle T(2019)Simulation optimisationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323385(862-889)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323385
Görder BKolonko M(2019)Ranking and SelectionACM Transactions on Modeling and Computer Simulation10.1145/324104229:1(1-24)Online publication date: 24-Jan-2019
https://dl.acm.org/doi/10.1145/3241042
Branke JTakadama K(2018)Simulation optimisationProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3205651.3207887(745-772)Online publication date: 6-Jul-2018
https://dl.acm.org/doi/10.1145/3205651.3207887
Groves MBranke JTakadama K(2018)Sequential sampling for noisy optimisation with CMA-ESProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205559(1023-1030)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205559
Branke JAsafuddoula MBhattacharjee KRay T(2017)Efficient Use of Partially Converged Simulations in Evolutionary OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2016.256901821:1(52-64)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1109/TEVC.2016.2569018
Liu MCramer A(2016)Genetic algorithm with integrated computing budget allocation for stochastic problemsInternational Journal of Metaheuristics10.1504/IJMHEUR.2016.0802575:2(115-135)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJMHEUR.2016.080257
Branke JNeumann FSutton A(2016)Simulation OptimisationProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2926995(663-686)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2926995
Berkhout J(2015)An accelerated stopping rule for the Nested Partition Hybrid Algorithm for discrete stochastic optimizationDiscrete Event Dynamic Systems10.1007/s10626-014-0191-925:3(441-452)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s10626-014-0191-9
Piperagkas GGeorgoulas GParsopoulos KStylios CLikas AMoore J(2012)Integrating particle swarm optimization with reinforcement learning in noisy problemsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330173(65-72)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330173
Boumaza A(2011)Reducing the learning time of tetris in evolution strategiesProceedings of the 10th international conference on Artificial Evolution10.1007/978-3-642-35533-2_17(193-204)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1007/978-3-642-35533-2_17
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents