François-Michel De Rainville
Skip Abstract Section
Skip Supplemental Material SectionAbstract
Low-discrepancy sequences provide a way to generate quasi-random numbers of high dimensionality with a very high level of uniformity. The nearly orthogonal Latin hypercube and the generalized Halton sequence are two popular methods when it comes to generate low-discrepancy sequences. In this article, we propose to use evolutionary algorithms in order to find optimized solutions to the combinatorial problem of configuring generators of these sequences. Experimental results show that the optimized sequence generators behave at least as well as generators from the literature for the Halton sequence and significantly better for the nearly orthogonal Latin hypercube.
Supplemental Material
Available for Download
zip
rainville.zip (3.6 MB)
Supplemental movie, appendix, image and software files for, Evolutionary optimization of low-discrepancy sequences
- Atanassov, E. I. 2004. On the discrepancy of the Halton sequences. Mathematica Balkanica 18, 15--32.Google Scholar
- Atanassov, E. I. and Durchova, M. K. 2003. Generating and testing the modified Halton sequences. In Proceedings of the Conference on Numerical Methods and Applications (NMA'02). Springer, Berlin, 91--98. Google ScholarDigital Library
- Auger, A., Jebalia, M., and Teytaud, O. 2006. Algorithms (X, sigma, eta): Quasi-random mutations for evolution strategies. In Proceedings of the Artificial Evolution Conference (EA'05). Springer, Berlin, 296--307. Google ScholarDigital Library
- Bates, S., Sienz, J., and Toropov, V. 2004. Formulation of the optimal Latin hypercube design of experiments using a permutation genetic algorithm. In Proceedings of the 5th ASMO-UK/ISSMO Conference on Engineering Design Optimization.Google Scholar
- Braaten, E. and Weller, G. 1979. An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integration. J. Comput. Phys. 33, 2, 249--258.Google ScholarCross Ref
- Caflisch, R. E., Morokoff, W. J., and Owen, A. B. 1997. Valuation of mortgage-backed securities using Brownian bridges to reduce effective dimension. J. Comput. Finance 1, 1, 27--46.Google ScholarCross Ref
- Cervellera, C. and Muselli, M. 2004. Deterministic design for neural network learning: An approach based on discrepancy. IEEE Trans. Neural Netw. 15, 3, 533--544. Google ScholarDigital Library
- Chi, H., Mascagni, M., and Warnock, T. T. 2005. On the optimal Halton sequence. ACM Trans. Model. Comput. Simul. 70, 1, 9--21. Google ScholarDigital Library
- Cicirello, V. A. and Smith, S. F. 2000. Modeling GA performance for control parameter optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO). AAAI, Menlo Park, 235--242.Google Scholar
- Cioppa, T. M. 2002. Efficient nearly orthogonal and space-filling experimental for high-dimensional complex models. Ph.D. thesis, Naval Postgraduate School, Monterey, CA.Google Scholar
- Cioppa, T. M. and Lucas, T. W. 2007. Efficient nearly orthogonal and space-filling Latin hypercubes. Technometrics 49, 1, 45--55.Google ScholarCross Ref
- Deb, K. 2000. Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester, UK. Google ScholarDigital Library
- Deb, K., Pratab, A., Agarwal, S., and Meyarivan, T. 2002. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. IEEE Trans. Evolut. Comput. 6, 2, 849--858. Google ScholarDigital Library
- Fang, K. T., Lin, D. K. J., Winker, P., and Zhang, Y. 2000. Uniform design: Theory and application. Technometrics 42, 3, 237--248.Google ScholarCross Ref
- Faure, H. 1982. Discrépance de suites associées à un système de numération (en dimension s). Acta Arithmetica 41, 337--351.Google ScholarCross Ref
- Faure, H. 2006. Selection criteria for (random) generation of digital (0,s)-sequences. In Proceedings of the Conference on Monte Carlo Methods and Quasi-Monte Methods. H. Niederreiter and D. Talay, Eds., Springer-Verlag, Berlin, 113--126.Google ScholarCross Ref
- Faure, H. and Lemieux, C. 2009. Generalized Halton sequences in 2008: A comparative study. ACM Trans. Model. Comput. Simul. 19, 4, 1--43. Google ScholarDigital Library
- Florian, A. 1992. An efficient sampling scheme: Updated Latin hypercube sampling. Probabil. Engin. Mechan. 7, 2, 123--130.Google ScholarCross Ref
- Glasserman, P. 2004. Monte Carlo Methods in Financial Enginerring. Springer-Verlag, New York.Google Scholar
- Halton, J. H. 1960. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik 2, 84--90.Google ScholarDigital Library
- Hammersley, J. M. 1960. Monte Carlo methods for solving multivariable problems. Ann. NY Acad. Sci. 86, 3, 844--874.Google ScholarCross Ref
- Hickernell, F. J. 1998. A generalized discrepancy and quadrature error bound. Math. Comput. 67, 221, 299--322. Google ScholarDigital Library
- Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI.Google Scholar
- Joe, S. and Kuo, F. Y. 2003. Remark on algorithm 659: Implementing Sobol's quasirandom sequence generator. ACM Trans. Math. Softw. 29, 49--57. Google ScholarDigital Library
- Johnson, M. E., Moore, L. M., and Ylvisaker, D. 1990. Minimax and maximin distance designs. J. Statist. Plann. Infer. 26, 131--148.Google ScholarCross Ref
- Kocis, L. and Whiten, W. J. 1997. Computational investigations of low-discrepancy sequences. ACM Trans. Math. Softw. 23, 2, 266--294. Google ScholarDigital Library
- Koza, J. R. 1991. Evolving a computer program to generate random numbers using the genetic programming paradigm. In Proceedings of the 4th International Conference on Genetic Algorithm. Morgan Kaufmann, 37--44.Google Scholar
- L'Ecuyer, P. 2009. Quasi-Monte carlo methods with applications in finance. Finance Stochast. 13, 307--349. 10.1007/s00780-009-0095-y.Google ScholarCross Ref
- L'Ecuyer, P. and Lemieux, C. 2000. Variance reduction via lattice rules. Manag. Sci. 46, 9, 1214--1235. Google ScholarDigital Library
- L'Ecuyer, P. and Lemieux, C. 2002. Recent advances in randomized quasi-Monte Carlo methods. In Proceedings of the Conference on Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications. P. L. M. Dror and F. Szidarovszki, Eds., Kluwer Academic Publishers, Chapter 20, 479--474.Google Scholar
- Lemieux, C. 2009. Monte Carlo and Quasi Monte Carlo Sampling. Springer, New York.Google Scholar
- Liefvendahl, M. and Stocki, R. 2006. A study on algorithms for optimization of Latin hypercubes. J. Statist. Plann. Infer. 136, 9, 3231--3247.Google ScholarCross Ref
- McKay, M. D., Beckman, R. J., and Conover, W. J. 1979. A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, 2, 239--245.Google Scholar
- Morokoff, W. J. and Caflisch, R. E. 1994. Quasi-random sequences and their discrepancies. SIAM J. Sci. Comput. 15, 6, 1251--1279. Google ScholarDigital Library
- Niederreiter, H. 1978. Quasi-Monte Carlo methods and pseudo-random numbers. Bull. Amer. Math. Soc. 84, 6, 957--1041.Google ScholarCross Ref
- Niederreiter, H. 1987. Point sets and sequences with small discrepancy. Monatshefte für Math. 104, 273--337.Google ScholarCross Ref
- Niederreiter, H. 1992. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Owen, A. B. 2003. The dimension distribution and quadrature test functions. Statistica Sinica 13, 1--17.Google Scholar
- Papageorgiou, A. and Traub, J. F. 1997. Faster evaluation of multidimensional integrals. Comput. Phys. 11, 6, 574--579. Google ScholarDigital Library
- Sipper, M. and Tomassini, M. 1996. Co-Evolving parallel random number generators. In Proceedings of the Conference on Parallel Problem Solving from Nature (PPSNIV). H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, Eds., Lecture Notes in Computer Science Series, vol. 1141, Springer, 950--959. Google ScholarDigital Library
- Sloan, I. H. and Woźniakowski, H. 1998. When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? J. Complex. 14, 1, 1--33. Google ScholarDigital Library
- Sobol', I. M. 1967. The distribution of points in a cube and the approximate evaluation of integrals. USSR Comput. Math. Math. Phys. 7, 4, 86--112.Google ScholarCross Ref
- Sobol', I. M. and Asostsky, D. I. 2003. One more experiment on estimating high-dimensional integrals by quasi-Monte Carlo methods. Math. Comput. Simul. 62, 3-6, 255--263. Google ScholarDigital Library
- Tuffin, B. 1998. A new permutation choice in halton sequences. In Proceedings of the Conference on Monte Carlo and Quasi-Monte Carlo Methods. P. Hellekalek, G. Larcher, H. Niederreiter, and P. Zinterhof, Eds., Lecture Notes in Statistics Series, vol. 127, Springer, Berlin, 427--435.Google ScholarCross Ref
- van der Corput, J. G. 1935. Verteilungsfunktionen. In Akademie van Wetenschappen. Vol. 38. KNAW, Amsterdam, 813--821.Google Scholar
- Vandewoestyne, B. and Cools, R. 2006. Good permutations for deterministic scrambled Halton sequences in terms of L2-discrepancy. Comput. Appl. Math. 189, 1,2, 341:361. Google ScholarDigital Library
- Wang, X. and Fang, K. T. 2003. The effective dimension and quasi-Monte Carlo integration. J. Complex. 19, 101--124. Google ScholarDigital Library
- Wang, X. and Hickernell, F. J. 2000. Randomized Halton sequences. Math. Comput. Modell. 32, 7, 887--899. Google ScholarDigital Library
- Wang, X. and Sloan, I. 2008. Low discrepancy sequences in high dimensions: How well are their projections distributed? J. Comput. Appl. Math. 213, 2, 366--386. Google ScholarDigital Library
- Warnock, T. T. 1972. Computational investigation of low discrepancy point sets. In Applications of Number Theory to Numerical Analysis. Academic Press, New York, 319--343.Google Scholar
- Ye, K. Q. 1998. Orthogonal column Latin hypercubes and their application in computer experiments. J. Amer. Statist. Assoc. 93, 1430--1439.Google ScholarCross Ref
Index Terms
- Evolutionary optimization of low-discrepancy sequences
Recommendations
Optimizing low-discrepancy sequences with an evolutionary algorithm
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationMany fields rely on some stochastic sampling of a given complex space. Low-discrepancy sequences are methods aiming at producing samples with better space-filling properties than uniformly distributed random numbers, hence allowing a more efficient ...
Genetic algorithms using low-discrepancy sequences
GECCO '05: Proceedings of the 7th annual conference on Genetic and evolutionary computationThe random number generator is one of the important components of evolutionary algorithms (EAs). Therefore, when we try to solve function optimization problems using EAs, we must carefully choose a good pseudo-random number generator. In EAs, the pseudo-...
Implementation and tests of low-discrepancy sequences
Low-discrepancy sequences are used for numerical integration, in simulation, and in related applications. Techniques for producing such sequences have been proposed by, among others, Halton, Sobol´, Faure, and Niederreiter. Niederreiter's sequences have ...
Comments