Optimizing low-discrepancy sequences with an evolutionary algorithm

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.

REFERENCES

• 1: A. Auger, M. Jebalia, and O. Teytaud. XSE: quasi-random mutations for evolution strategies. In Proceedings of Evolutionary Algorithms, page 12, 2005.
• 2: 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.
• 3: 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.
• 4: C. Chlier. Error trends in quasi-Monte Carlo integration. Comp. Phys. Comm., 193:93--105, 2004.
• 5: K.-L. Chung. An estimate concerning the Kolmogoroff limit distribution. Transactions of the American Mathematical Society, 67:36--50, 1949.
• 6: T.M. Cioppa and T.W. Lucas. Efficient nearly orthogonal and space-filling latin hypercubes. Technometrics, 49(1):45--55, February 2007.
• 7: T. J. G. Davies , Ralph R. Martin , Adrian Bowyer, Computing Volume Properties Using Low-Discrepancy Sequences, Geometric Modelling, p.55-72, May 01, 1999
• 8: K.T. Fang, D.K.J. Lin, P. Winker, and Y. Zhang. Uniform design: Theory and application. Technometrics, 42(3):237--248, August 2000.
• 9: K.T. Fang and Y. Wang. Number-theoretic Methods in Statistics. Chapman and Hall, 1994.
• 10: A. Florian. An efficient sampling scheme: updated Latin hypercube sampling. Probabilistic engineering mechanics, 7(2):123--130, 1992.
• 11: 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.
• 12: Fred J. Hickernell, A generalized discrepancy and quadrature error bound, Mathematics of Computation, v.67 n.221, p.299-322, Jan. 1998 [doi>10.1090/S0025-5718-98-00894-1]
• 13: 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.
• 14: 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.
• 15: 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.
• 16: Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 17: 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.
• 18: Ian H. Sloan , Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, Journal of Complexity, v.14 n.1, p.1-33, March 1998 [doi>10.1006/jcom.1997.0463]
• 19: 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.
• 20: Bart Vandewoestyne , Ronald Cools, Good permutations for deterministic scrambled Halton sequences in terms of L2-discrepancy, Journal of Computational and Applied Mathematics, v.189 n.1, p.341-361, 1 May 2006 [doi>10.1016/j.cam.2005.05.022]
• 21: Grzegorz W. Wasilkowski , Henryk Woźniakowski, The exponent of discrepancy is at most 1.4778…, Mathematics of Computation, v.66 n.219, p.1125-1132, July 1997 [doi>10.1090/S0025-5718-97-00824-7]
• 22: K.Q. Ye. Orthogonal column Latin hypercubes and their application in computer experiments. Journal Association Statistical Analysis, Theory and Methods, 93:1430--1439, 1998.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Performance

Keywords:
combinatorial optimization, discrepancy, evolutionary algorithms, orthogonal latin hypercube, quasi-random, scrambled halton