Carola Doerr
ABSTRACT
Geometric discrepancies are standard measures to quantify the irregularity of distributions. They are an important notion in numerical integration. One of the most important discrepancy notions is the so-called star discrepancy. Roughly speaking, a point set of low star discrepancy value allows for a small approximation error in quasi-Monte Carlo integration. It is thus the most studied discrepancy notion.
In this work we present a new algorithm to compute point sets of low star discrepancy. The two components of the algorithm (for the optimization and the evaluation, respectively) are based on evolutionary principles. Our algorithm clearly outperforms existing approaches. To the best of our knowledge, it is also the first algorithm which can be adapted easily to optimize inverse star discrepancies.
- E. Braaten and G. Weller. An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integration. J. of Comput. Phys., 33(2):249--258, 1979.Google Scholar
Cross Ref
- F.-M. De Rainville, C. Gagné, O. Teytaud, and D. Laurendeau. Optimizing low-discrepancy sequences with an evolutionary algorithm. In Proc. of GECCO'09, pages 1491--1498. ACM, 2009. Google ScholarDigital Library
- F.-M. De Rainville, C. Gagné, O. Teytaud, and D. Laurendeau. Evolutionary optimization of low-discrepancy sequences. ACM Trans. Model. Comput. Simul., 22(2):9:1--9:25, 2012. Google ScholarDigital Library
- K. Deb, A. Pratab, S. Agarwal, and T. Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. IEEE Trans. Evolut. Comput., 6(2):849--858, 2002. Google ScholarDigital Library
- J. Dick and F. Pillichshammer. Digital Nets and Sequences. Cambridge University Press, 2010.Google ScholarDigital Library
- D. P. Dobkin, D. Eppstein, and D. P. Mitchell. Computing the discrepancy with applications to supersampling patterns. ACM Trans. Graph., 15:354--376, 1996. Google ScholarDigital Library
- B. Doerr, M. Gnewuch, and M. Wahlström. Algorithmic construction of low-discrepancy point sets via dependent randomized rounding. J. Complexity, 26:490--507, 2010. Google ScholarDigital Library
- C. Doerr, F.-M. De Rainville, and C. Gagné. A database for low star discrepancy point sets and sequences. Available at http://qrand.gel.ulaval.ca.Google Scholar
- C. Doerr, M. Gnewuch, and M. Wahlström. Calculation of discrepancy measures and applications. Preprint, 2013. Available online on http://www.mpi-inf.mpg.de/ winzen/publications.html.Google Scholar
- P. Giannopoulus, C. Knauer, M. Wahlström, and D. Werner. Hardness of discrepancy computation and epsilon-net verification in high dimensions. J. Complexity, 28:162--176, 2012. Google ScholarDigital Library
- M. Gnewuch. Entropy, randomization, derandomization, and discrepancy. In L. Plaskota and H. Woźniakowski, editors, Monte Carlo and Quasi-Monte Carlo Methods 2010, pages 43--78. Springer-Verlag, 2012.Google ScholarCross Ref
- M. Gnewuch, A. Srivastav, and C. Winzen. Finding optimal volume subintervals with k points and calculating the star discrepancy are NP-hard problems. J. Complexity, 25:115--127, 2009. Google ScholarDigital Library
- M. Gnewuch, M. Wahlström, and C. Winzen. A new randomized algorithm to approximate the star discrepancy based on threshold accepting. SIAM J. Numer. Anal., 50:781--807, 2012. Google ScholarDigital Library
- D. E. Goldberg and K. Deb. A comparative analysis of selection schemes used in genetic algorithms. In Proc. of FOGA'90, pages 69--93. Morgan Kaufmann, 1990.Google Scholar
- D. E. Goldberg and R. Lingle. Alleles, loci, and the traveling salesman problem. In Proc. of ICGA'85, pages 154--159. Lawrence Erlbaum Associates, 1985. Google ScholarDigital Library
- J. H. Halton. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik, 2:84--90, 1960.Google ScholarDigital Library
- A. Hinrichs. Discrepancy, integration and tractability. Preprint, 2012. Available online on http://users.minet.uni-jena.de/~hinrichs/publicat.html.Google Scholar
- E. Hlawka. Funktionen von beschränkter Variation in der Theorie der Gleichverteilung. Ann. Mat. Pura Appl., 54:325--333, 1961.Google ScholarCross Ref
- J. Matoušek. Geometric Discrepancy. Springer, 2nd edition, 2010.Google Scholar
- H. Niederreiter. Discrepancy and convex programming. Ann. Mat. Pura Appl., 93:89--97, 1972.Google ScholarCross Ref
- H. Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods, volume 63 of SIAM CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM, 1992. Google ScholarDigital Library
- E. Novak and H. Woźniakowski. Tractability of Multivariate Problems. Vol. 2, Standard Information for Functionals. EMS Tracts in Mathematics. European Mathematical Society, 2010.Google Scholar
- S. Tezuka. Uniform Random Number: Theory and practice. The Kluwer International Series in Engineering and Computer Science. 315. Kluwer Academic Publishers, 1995.Google Scholar
- E. Thiémard. An algorithm to compute bounds for the star discrepancy. J. Complexity, 17:850--880, 2001.Google ScholarDigital Library
- E. Thiémard. Optimal volume subintervals with k points and star discrepancy via integer programming. Math. Meth. Oper. Res., 54:21--45, 2001.Google ScholarCross Ref
- J. G. van der Corput. Verteilungsfunktionen. In Akademie van Wetenschappen, volume 38, pages 813--821. KNAW, 1935.Google Scholar
- M. Wahlström. Implementations of the DEM- and the TA-algorithm. Available at http://www.mpi-inf.mpg.de/~wahl/.Google Scholar
Index Terms
- Constructing low star discrepancy point sets with genetic algorithms
Recommendations
Construction Algorithms for Digital Nets with Low Weighted Star Discrepancy
We introduce a new construction method for digital nets which yield point sets in the s-dimensional unit cube with low star discrepancy. The digital nets are constructed using polynomials over finite fields. It has long been known that there exist ...
Algorithmic construction of low-discrepancy point sets via dependent randomized rounding
We provide a deterministic algorithm that constructs small point sets exhibiting a low star discrepancy. The algorithm is based on recent results on randomized roundings respecting hard constraints and their derandomization. It is structurally much ...
Geometric discrepancy revisited
SFCS '93: Proceedings of the 1993 IEEE 34th Annual Foundations of Computer ScienceDiscrepancy theory addresses the general issue of approximating one measure by another one. Originally an offshoot of diophantine approximation theory, the area has expanded into applied mathematics, and now, computer science. Besides providing the ...
Comments