Abstract
Efficient Latin hypercube designs (LHDs), including maximin distance LHDs, maximum projection LHDs, and orthogonal LHDs, are widely used in computer experiments. It is challenging to construct such designs with flexible sizes, especially for large ones. In the current literature, various algebraic methods and search algorithms have been proposed for identifying efficient LHDs, each having its own pros and cons. In this paper, we review, summarize, and compare some currently popular methods aiming to provide guidance for experimenters on what method should be used in practice. Using the R package we developed, which integrates and improves various algebraic and searching methods, many of the designs found in this paper are better than the existing ones. They are easy to use for practitioners and can serve as benchmarks for the future developments on LHDs.
Introduction
In fields such as engineering, climate science, and aerospace, researchers increasingly rely on complex computer simulations to model real-world systems. Unlike physical experiments, these simulations are typically deterministic—running the same input twice yields the exact same output. Consequently, traditional experimental designs that rely on replication are inefficient. To address this, researchers utilize Latin Hypercube Designs (LHDs), which ensure that input points are spread evenly across the experimental space, providing a "space-filling" property that is essential for accurate modeling.
However, the search for an "optimal" LHD—one that maximizes the distance between points (maximin) or achieves perfect orthogonality—is a massive combinatorial challenge. As the number of runs ($n$) and factors ($k$) increases, the number of possible designs grows at a rate of $(n!)^{k-1}$. Existing search algorithms frequently struggle with local optima or prohibitive computation times, while algebraic methods, though fast, are often restricted to very specific, rigid design sizes. This paper introduces a comprehensive toolkit and a new R package, LHD, designed to bridge these gaps.
Methodology and Innovation
This research evaluates and improves upon three primary categories of construction methods:
1. Search Algorithms and the GA Framework
The authors compare Simulated Annealing (SA), Particle Swarm Optimization (LaPSO), and Genetic Algorithms (GA). A key innovation presented is a novel GA framework specifically tailored for Maximum Projection (MaxPro) designs. Traditional algorithms often utilize element-wise swapping, which can be slow and prone to getting stuck in sub-optimal configurations. The proposed GA approach instead exchanges entire columns. This maintains the fundamental LHD structure while allowing the algorithm to explore the search space more efficiently, particularly for large-scale problems.
2. Algebraic Constructions
For specific design sizes, the paper summarizes "nearly free" mathematical shortcuts, such as the Williams transformation and Costas’ arrays. These algebraic methods can generate theoretically optimal designs almost instantaneously. While they lack the flexibility of search algorithms regarding run-sizes, they provide a gold standard for the specific dimensions they support.
3. The LHD R Package
To make these advancements accessible to practitioners, the authors integrated these improved algorithms into the LHD R package. This package serves as a unified interface, allowing users to generate high-quality designs without requiring deep expertise in experimental design theory.
Key Insights
Scalability and the GA Advantage
A primary finding is the superior scalability of the Genetic Algorithm. While element-wise swapping (common in SA and PSO) is effective for small designs, its performance degrades as $n$ and $k$ increase. The GA’s strategy of column exchange scales significantly better, making it the preferred choice for modern, high-dimensional computer experiments.
The Shift to Maximum Projection (MaxPro)
While maximin distance designs (which maximize the minimum distance between points) are widely used, the authors argue that MaxPro designs are often superior. MaxPro designs ensure that points are well-spread not only in the full $k$-dimensional space but also in every possible lower-dimensional sub-projection. This is critical in simulations where only a subset of factors may turn out to be truly influential.
Results and Performance
The performance of the LHD package was benchmarked against existing standard libraries, such as the MaxPro package, across various scales (from 6 runs/4 factors to 256 runs/16 factors):
- Efficiency: For maximin distance designs, the GA consistently identified better optimality values ($\phi_p$) than Simulated Annealing, often achieving a 5x to 10x speedup in CPU time for larger designs.
- Quality: In head-to-head MaxPro design tests, the GA framework found designs with lower $\psi$ values (indicating superior space-filling properties) than the current state-of-the-art tools.
- Orthogonality: For nearly orthogonal LHDs, SA remains competitive for very small designs ($n < 16$), but the GA becomes the clear winner as the design size grows.
Conclusion and Future Work
The research demonstrates that combining improved search heuristics with a unified software implementation significantly advances the state of the art in experimental design. While the current GA framework is highly efficient, the authors acknowledge that extremely high-dimensional spaces (thousands of factors) still present computational challenges.
Future developments for the LHD package will focus on:
- Supporting fractional factorial and supersaturated designs.
- Exploring order-of-addition designs, where the sequence of inputs is a critical variable.
- Further optimizing the underlying code through C++ integration to support "big data" simulation environments and even larger run sizes.
Summary updated