Algorithmic construction of optimal symmetric Latin hypercube designs

Abstract

We propose symmetric Latin hypercubes for designs of computer experiment. The goal is to offer a compromise between computing effort and design optimality. The proposed class of designs has some advantages over the regular Latin hypercube design with respect to criteria such as entropy and the minimum intersite distance. An exchange algorithm is proposed for constructing optimal symmetric Latin hypercube designs. This algorithm is compared with two existing algorithms by Park (1994. J. Statist. Plann. Inference 39, 95–111) and Morris and Mitchell (1995. J. Statist. Plann. Inference 43, 381–402). Some examples, including a real case study in the automotive industry, are used to illustrate the performance of the new designs and the algorithms.

Introduction

One of our recent projects is concerned with the thermal analysis of multi-layer electrical traces at a major automotive company. As more and more electronic devices are installed in vehicles, the peak temperature of electrical traces becomes a major concern in designing the instrument panels. The temperature of an electrical trace is largely determined by its width, its passing current strength, and its position in a stack of traces. The goal of this project is to provide guidelines for design engineers for width and passing current strength of multi-layer electrical traces. Physical experiments are inevitably very expensive and time consuming since a set of electrical traces has to be assembled in certain configurations for each test and measuring the temperature of each trace is difficult. Therefore, finite element analysis (FEA) models have been developed to simulate the thermal dynamics of electrical traces.

Using the computer model, the study starts from a simple case, in which there are two layers with three traces on each layer. One primary interest is the interaction between a center trace and an edge trace on two different layers since the heat coming off the center trace spreads out and affects the temperature at the edge. A center trace on layer 1 and an edge trace on layer 2 are selected in the study. The goal is to predict their peak temperatures (y₁ and y₂) based on four predictors: the width of the center trace (x₁), the applied current of the center trace (x₂), the width of the edge trace (x₃), and the applied current of the edge trace (x₄). Given a set of x_i-values, the computer model generates a deterministic peak temperature for each trace.

Though computer experiments are much cheaper and faster than physical experiments, each run is still time consuming and expensive. Thus, only a small number of combinations of the x_i can be tested. In this case, the experiment is to be conducted by another company which specializes in thermal dynamic computer models, and the budget only allows for 25 runs. A feasible approach is to establish a statistical model from the results of the 25 runs and then use it to predict peak temperatures for any given combinations of the x_i. An optimal Latin hypercube design was chosen for this experiment.

A Latin hypercube design (LHD) is an n×l matrix in which each column is a random permutation of {1,…,n} which can be mapped onto the actual range of the variables. It has good projection properties on any single dimension. Latin hypercube designs have been applied in many computer experiments since they were proposed by McKay et al. (1979). In practice, a LHD can be randomly generated, but a randomly selected LHD may have bad properties and act poorly in estimation and prediction. Another approach is to use optimal designs according to some criteria such as entropy (Shewry and Wynn, 1987), integrated mean-squared error (IMSE) (Sacks et al., 1989), and minimum intersite distance (Johnson et al., 1990). These designs have been shown to be efficient for certain models. However, the computational cost of obtaining these designs is high. In an attempt to offer a compromise between good projective properties of LHDs and a criterion, Park (1994) and Morris and Mitchell (1995) proposed optimal Latin hypercube designs. For an excellent review of design and analysis of computer experiments, see Koehler and Owen (1996).

One of the criteria considered in this paper is the entropy criterion, first proposed by Shewry and Wynn (1987) and then adopted by Currin et al. (1991). The response of a computer model is modeled by $\text{Y(}\text{x}\text{)=∑}{}_{\mathrm{j=1}}{}^{\mathrm{k}}\text{β}{}_{\mathrm{j}}\text{f}{}_{\mathrm{j}}\text{(}\text{x}\text{)+Z(}\text{x}\text{)}$, in which $\text{Z(}\text{x}\text{)}$ is a Gaussian process with mean zero and covariance

$$\text{R(}\text{s}\text{,}\text{t}\text{)=σ}{}^2\text{exp}\text{−θ}\text{∑}\text{j=1}\text{l}\text{|}\text{s}{}_{\mathrm{j}}\text{−}\text{t}{}_{\mathrm{j}}\text{|}{}^{\mathrm{q}}\text{,}\text{0<q⩽2}$$

between two l-dimensional inputs $\text{s}$ and $\text{t}$. The entropy criterion is equivalent to the minimization of $\text{−}\text{log}\text{|R|}$, where R is the covariance matrix of the design. The parameters θ and q determine the properties of Z(x). Throughout this paper, we set q=2 so that the correlation between two sites is a function of their L₂ distance.

The construction of an optimal LHD can still be time consuming. For example, to generate a maximum entropy 25×4 LHD using a columnwise–pairwise (CP) algorithm (discussed in Section 3), the whole procedure takes 3.3 h on a Sun SPARC 20 workstation, which appears to be quite long as the size of the design is moderate. The search for a larger design would take even longer, and may be computationally prohibitive. This situation motivated us to look for alternatives that require less computing time. The easiest method is to generate a large number of random LHDs and then choose the best one according to the criterion. For example, the generation of 1000 random LHDs takes only 14.7 s on the same machine. However, the best design obtained from these random designs is usually significantly inferior to that produced by the algorithmic search. In our example, the entropy value at θ=2 of the former is 25.26, compared with the latter's 20.48. To reduce the searching time and still generate competitive designs, our approach is to restrict the search within a subset of the general LHD. If this subset of designs has some desirable properties with respect to a criterion, then selecting a design from this group of designs may be more efficient.

In Section 2, we introduce a new class of LHD, the symmetric Latin hypercube design, whose geometric property enables us to find optimal LHDs more efficiently. Section 3 considers a simple exchange algorithm for constructing optimal symmetric LHDs. Its performance is compared with the existing algorithmic approaches of Park (1994), and Morris and Mitchell (1995). Section 4 demonstrates the performance of the new design with an example. A summary is given in Section 5.