François-Michel De Rainville
ABSTRACT
Many 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 sampling of that space. State-of-the-art methods like nearly orthogonal Latin hypercubes and scrambled Halton sequences are configured by permutations of internal parameters, where permutations are commonly done randomly. This paper proposes the use of evolutionary algorithms to evolve these permutations, in order to optimize a discrepancy measure. Results show that an evolutionary method is able to generate low-discrepancy sequences of significantly better space-filling properties compared to sequences configured with purely random permutations.
- A. Auger, M. Jebalia, and O. Teytaud. XSE: quasi-random mutations for evolution strategies. In Proceedings of Evolutionary Algorithms, page 12, 2005.Google Scholar
- S.J. Bates, J. Sienz, and V.V. Toropov. Formulation of the optimal Latin hypercube design of experiments using a permutation genetic algorithm. In 5th ASMO-UK/ISSMO Conference on Engineering Design Optimization, 2004.Google ScholarCross Ref
- C. Cervellera and M. Muselli. Deterministic design for neural network learning: an approach based on discrepancy. IEEE Transactions on Neural Networks, 15(3):533--544, 2004. Google ScholarDigital Library
- C. Chlier. Error trends in quasi-Monte Carlo integration. Comp. Phys. Comm., 193:93--105, 2004.Google ScholarCross Ref
- K.-L. Chung. An estimate concerning the Kolmogoroff limit distribution. Transactions of the American Mathematical Society, 67:36--50, 1949.Google Scholar
- T.M. Cioppa and T.W. Lucas. Efficient nearly orthogonal and space-filling latin hypercubes. Technometrics, 49(1):45--55, February 2007.Google ScholarCross Ref
- T.J.G. Davies, R.R. Martin, and A. Bowyer. Computing volume properties using low-discrepancy sequences. In Geometric Modelling, pages 55--72, 1999. Google ScholarDigital Library
- K.T. Fang, D.K.J. Lin, P. Winker, and Y. Zhang. Uniform design: Theory and application. Technometrics, 42(3):237--248, August 2000.Google ScholarCross Ref
- K.T. Fang and Y. Wang. Number-theoretic Methods in Statistics. Chapman and Hall, 1994.Google ScholarCross Ref
- A. Florian. An efficient sampling scheme: updated Latin hypercube sampling. Probabilistic engineering mechanics, 7(2):123--130, 1992.Google Scholar
- C. Gagné and M. Parizeau. Genericity in evolutionary computation software tools: Principles and case study. International Journal on Artificial Intelligence Tools, 15(2):173--194, Apr. 2006.Google ScholarCross Ref
- F.J. Hickernell. A generalized discrepancy and quadrature error bound. Mathematics of Computation, 67(221):299--322, 1998. Google ScholarDigital Library
- M. Liefvendahl and R. Stocki. A study on algorithms for optimization of Latin hypercubes. Journal of Statistical Planning and Inference, 136(9):3231--3247, 2006.Google ScholarCross Ref
- M. Lizotte, D. Poussart, F. Bernier, M. Mokhtari, E . Boivin, and M. DuCharme. IMAGE: Simulation for understanding complex situations and increasing future force agility. In Proceedings of the 26th Army Science Conference, page 7, 2008.Google Scholar
- M.D. McKay, R.J. Beckman, and W.J. Conover. 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, May 1979.Google Scholar
- H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. SIAM, 1992. Google ScholarDigital Library
- A.B. Owen. Quasi-Monte Carlo sampling. In H.W. Jensen, editor, Monte Carlo Ray Tracing: Siggraph 2003 Course 44, pages 69--88. SIGGRAPH, 2003.Google Scholar
- I.H. Sloan and H. Wozniakowski. When are quasi-Monte Carlo algorithms efficient for high dimensional integrals? Journal of Complexity, 14(1):1--33, 1998. Google ScholarDigital Library
- K.S. Tan and P.P. Boyle. Applications of randomized low discrepancy sequences to the valuation of complex securities. Journal of Economic Dynamics and Control, 24:1747--1782, October 2000.Google ScholarCross Ref
- B. Vandewoestyne and R. Cools. Good permutations for deterministic scrambled Halton sequences in terms of l2-discrepancy. Computational and Applied Mathematics, 189(1,2):341:361, 2006. Google ScholarDigital Library
- G. Wasilkowski and H. Wozniakowski. The exponent of discrepancy is at most 1.4778. Math. Comp, 66:1125--1132, 1997. Google ScholarDigital Library
- K.Q. Ye. Orthogonal column Latin hypercubes and their application in computer experiments. Journal Association Statistical Analysis, Theory and Methods, 93:1430--1439, 1998.Google Scholar
Index Terms
- Optimizing low-discrepancy sequences with an evolutionary algorithm
Recommendations
Evolutionary optimization of low-discrepancy sequences
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 ...
Computational investigations of low-discrepancy sequences
The Halton, Sobol, and Faure sequences and the Braaten-Weller construction of the generalized Halton sequence are studied in order to assess their applicability for the quasi Monte Carlo integration with large number of variates. A modification of the ...
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-...
Comments