Article

When Does Quasi-random Work?

Author:

Olivier TeytaudAuthors Info & Claims

Proceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 5199

Pages 325 - 336

Published: 13 September 2008 Publication History

Abstract

[10,22] presented various ways for introducing quasi-random numbers or derandomization in evolution strategies, with in some cases some spectacular claims on the fact that the proposed technique was always and for all criteria better than standard mutations. We here focus on the quasi-random trick and see to which extent this technique is efficient, by an in-depth analysis including convergence rates, local minima, plateaus, non-asymptotic behavior and noise. We conclude to the very stable, efficient and straightforward applicability of quasi-random numbers in continuous evolutionary algorithms.

References

[1]

Atanassov, E.I.: On the discrepancy of the halton sequences. Math. Balkanica 1812, 15---32 2004

[2]

Braaten, E., Weller, G.: An improved low-discrepancy sequence for multidimensional quasi-monte carlo integration. J. Comput. Phys. 33, 249---258 1979

[3]

Bratley, P., Fox, B.: Algorithm 659: Implementing sobol's quasirandom sequence generator. ACM Transactions on Mathematical Software 141, 88---100 1988

Digital Library

[4]

Cervellera, C., Muselli, M.: A deterministic learning approach based on discrepancy. In: Apolloni, B., Marinaro, M., Tagliaferri, R. eds. WIRN 2003. LNCS, vol. 2859, pp. 53---60. Springer, Heidelberg 2003

[5]

Cranley, R., Patterson, T.N.L.: Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 136, 904---914 1976

[6]

Faure, H.: Good permutations for extreme discrepancy. J. Number Theory 42, 47---56 1992

[7]

Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 111 2003

Digital Library

[8]

Hardy, G.H.: On double fourier series, and especially those which represent the double zeta-function with real and incommensurable parameters. Quart. J. Mathematics 37, 53---79 1905

[9]

Hickernell, F.J.: A generalized discrepancy and quadrature error bound. Math. Comp. 67, 299---322 1998

Digital Library

[10]

Kimura, S., Matsumura, K.: Genetic algorithms using low-discrepancy sequences. In: GECCO, pp. 1341---1346 2005

Digital Library

[11]

L'Ecuyer, P., Lemieux, C.: Recent Advances in Randomized Quasi-Monte Carlo Methods, pp. 419---474. Kluwer Academic Publishers, Dordrecht 2002

[12]

Mascagni, M., Chi, H.: On the scrambled halton sequence. Monte Carlo Methods Appl. 103, 435---442 2004

[13]

Morokoff, W.J., Caflish, R.E.: Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput. 156, 1251---1279 1994

Digital Library

[14]

Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods 1992

Digital Library

[15]

Okten, G., Srinivasan, A.: Parallel quasi-monte carlo methods on a heterogeneous cluster. In: Niederreiter, H., Fang, K.-T., Hickernell, F.J. eds. Monte Carlo and Quasi-Monte Carlo Methods 2000, pp. 406---421. Springer, Heidelberg 2002

[16]

Owen, A.B.: Quasi-Monte Carlo Sampling, A Chapter on QMC for a SIGGRAPH 2003 course 2003

[17]

Sarkar, P.K., Prasad, M.A.: A comparative study of pseudo and quasi random sequences for the solution of integral equations. J. Computational Physics 68, 66---88 1978

Digital Library

[18]

Sloan, I.H., Woźniakowski, H.: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? Journal of Complexity 141, 1---33 1998

Digital Library

[19]

Sobol, I.M.: On the systematic search in a hypercube. Siam journal on Numerical Analysis 165, 790---793 1979

[20]

Srinivasan, A.: Parallel and distributed computing issues in pricing financial derivatives through quasi-monte carlo. In: Proceedings of the 16th International Parallel and Distributed Processing Symposium 2002

Digital Library

[21]

Teytaud, O., Gelly, S., Mary, J.: Active learning in regression, with application to stochastic dynamic programming. In: Proceedings of ICINCO 2007, pp. 47---54 2007

[22]

Teytaud, O., Gelly, S.: Dcma: yet another derandomization in covariance-matrix-adaptation. In: GECCO 2007: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 955---963. ACM Press, New York 2007

Digital Library

[23]

Tuffin, B.: On the use of low discrepancy sequences in monte carlo methods 1996

[24]

Tuffin, B.: A new permutation choice in halton sequences. Monte Carlo and Quasi-Monte Carlo 127, 427---435 1997

[25]

van der Corput, J.G.: Verteilungsfunktionen. Proc. Ned. Akad. v. Wet. 38, 813---821 1935

[26]

Vandewoestyne, B., Cools, R.: Good permutations for deterministic scrambled halton sequences in terms of l2-discrepancy. Computational and Applied Mathematics 1891,2, 341---361 2006

Digital Library

[27]

Wang, X., Hickernell, F.: Randomized halton sequences. Math. Comput. Modelling 32, 887---899 2000

Digital Library

[28]

Warnock, T.T.: Computational investigations of low-discrepancy point sets. In: Zaremba, S.K. ed. Applications of Number Theory to Numerical Analysis Proceedings of the Symposium. University of Montreal, pp. 319---343 1972

[29]

Warnock, T.T.: Computational investigations of low-discrepancy point sets ii. In: Niederreiter, H., Shiue, P.J.-S. eds. Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing. Springer, Berlin 1995

Cited By

Teytaud FTeytaud ONeumann FSutton A(2016)QR Mutations Improve Many Evolution StrategiesProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2909060(35-36)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2909060
Schoenauer MTeytaud FTeytaud O(2011)A rigorous runtime analysis for quasi-random restarts and decreasing stepsizeProceedings of the 10th international conference on Artificial Evolution10.1007/978-3-642-35533-2_4(37-48)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1007/978-3-642-35533-2_4
Teytaud FTeytaud O(2010)Log(λ) modifications for optimal parallelismProceedings of the 11th international conference on Parallel problem solving from nature: Part I10.5555/1885031.1885059(254-263)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.5555/1885031.1885059
Show More Cited By

Recommendations

Mirrored orthogonal sampling with pairwise selection in evolution strategies
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied Computing

In this paper, an improvement of the mirrored sampling method, called mirrored orthogonal sampling, is propsed. The convergence rates on the sphere function are estimated. It is also applied to Covariance Matrix Adaptation Evolution Strategy (CMA-ES). ...
On three new approaches to handle constraints within evolution strategies

Evolutionary algorithms with a self-adaptive step control mechanism like evolution strategies (ES) often suffer from premature fitness stagnation on constrained numerical optimization problems. When the optimum lies on the constraint boundary or even in ...
A hybrid evolution strategy for the open vehicle routing problem

This paper presents a hybrid evolution strategy (ES) for solving the open vehicle routing problem (OVRP), which is a well-known combinatorial optimization problem that addresses the service of a set of customers using a homogeneous fleet of non-depot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the 10th International Conference on Parallel Problem Solving from Nature --- PPSN X - Volume 5199

September 2008

1159 pages

ISBN:9783540876991

Editors:
Günter Rudolph
Fakultät für Informatik, Technische Universität Dortmund, Dortmund, Germany
,
Thomas Jansen
Fakultät für Informatik, Technische Universität Dortmund, Dortmund, Germany
,
Nicola Beume
Fakultät für Informatik, Technische Universität Dortmund, Dortmund, Germany
,
Simon Lucas
Department of Computing and Electronic Systems, University of Essex, Colchester, UK
,
Carlo Poloni
Dipartimento di Ingegneria Meccanica, Universití degli Studi di Trieste, Trieste, Italy

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 13 September 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Teytaud FTeytaud ONeumann FSutton A(2016)QR Mutations Improve Many Evolution StrategiesProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2909060(35-36)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908961.2909060
Schoenauer MTeytaud FTeytaud O(2011)A rigorous runtime analysis for quasi-random restarts and decreasing stepsizeProceedings of the 10th international conference on Artificial Evolution10.1007/978-3-642-35533-2_4(37-48)Online publication date: 24-Oct-2011
https://dl.acm.org/doi/10.1007/978-3-642-35533-2_4
Teytaud FTeytaud O(2010)Log(λ) modifications for optimal parallelismProceedings of the 11th international conference on Parallel problem solving from nature: Part I10.5555/1885031.1885059(254-263)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.5555/1885031.1885059
Knowles J(2009)Closed-loop evolutionary multiobjective optimizationIEEE Computational Intelligence Magazine10.1109/MCI.2009.9330954:3(77-91)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1109/MCI.2009.933095

View Options

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

Media

Figures

Other

Tables

View Table of Contents