Optimised U-Type Designs on Flexible Regions

Keywords

U-type Designs, Central Composite Discrepancy, Flexible Regions, Threshold Accepting

Unreviewed

Abstract

The concept of a ‘flexible region’ describes an infinite variety of symmetrical shapes to enclose a particular ‘region of interest’ within a space. In experimental design, the properties of a function on the ‘region of interest’ is analysed based on a set of design points. The choice of design points can be made based on some discrepancy criterion. In this article is discussed the generation of design points on a 'flexible region'. The Central Composite Discrepancy ($CCD$), a recently proposed discrepancy measure, is applied for measuring the 'evenness' in the distribution of design points over the 'flexible region'. Threshold Accepting (TA) is used to generate low discrepancy $U$-type designs. The results for the two dimensional case indicate that using an optimisation heuristic in combination with an appropriate discrepancy measure, it is possible to produce high quality experimental designs on ‘flexible regions’.

1. Introduction

The development by Draper and Guttman [2] of a ‘flexible region’ in experimental design built on their earlier work into other region shape types. The central question consists in understanding the effect of selecting particular points in the experimental domain (input space) for response surface analysis, where the functional relationship between input and output is not known. It is assumed that a desirable feature of the input space - that is, inputs that produce an output that meets some set objective - is localised. The sub-space selected for experimental examination is coined the ´region of interest', represented by a set of design points which are summarised in a design matrix.

The process of generating a good, low discrepancy design (using the $CCD$, as devised by Chuang and Hung [1]) is framed as a heuristic optimisation problem, with the $CCD$ the objective function to be minimised. Threshold Accepting is the heuristic technique implemented to obtain low discrepancy designs.

It has been applied to many experimental design problems (Fang et al [4], Fang et al [5] , and Winker, Ch. 11 [7]) and has a wide range of supporting research material. (See alsoFang [3] for a general overview on Experimental Design problems.)

2 Description of a Flexible Region

For any positive value of $m$, Draper and Guttman define a flexible region $R$ in dimension $s$ by the following constraint on the potential design points.

(1)
\begin{align} |x_{1}|^m + |x_{2}|^m + ,\cdots, + |x_{s}|^m \leq 1. \end{align}

By an adjustment of a single parameter, $m$, it becomes possible to obtain an infinite variety of intermediate symmetrical shapes. The approach is particularly useful as it offers the possibility for intuitive linguistic mapping to shape types. When applying a flexible region to a real problem Draper and Guttman point out that we do have some a priori knowledge as to what the region of interest should ‘look like’, which is first expressed in terms of natural language. For example, a specificiation in natural language maybe for a shape that, "covers the space around the corners but not right up to corners'' . This is mapped to a specific value $m$, for the shape of the ‘flexible region’. This process offers some intriguing research possibilities2. The graphs below show some examples for different values of $m$ in the two dimensional case.

This definition is for the hypercube $[-1,1]^{s}$, while in recent work on experimental design the hypercube $C^{s} = [0,1)^{s}$ is considered. Therefore, the following modification is made to the original definition: for a given shape parameter $m > 0$, the flexible $R_{m}$ is defined by,

(2)
\begin{align} R_{m} = {x{_2} [0, 1]{^s} | (| 2 (x{_1} {-} 0.5)|^m + \dots + | 2 (x{_s} {-} 0.5) | {^m}) \leq 1}. \end{align}

In reference to the concept of $U$-type designs, only design points lying on a grid over the unit cube are considered.

3 U-type Design

We define a $U$-type design $\mathcal{P}$ as a set of $n$ points, $\mathcal{P} = {x_{1}, \dots ,x_{n}}$, sampled from the $s$-dimensional unit cube $C{^s}$ on a grid with $q^{s}$ points. This set of points can also be described by a n × s design matrix $U$, where each row corresponds to one run and each column to one factor. Thereby, the factors can take on $l = 1, \dots , q$ different levels. The correspondance between the set of design point sets and the set of design matrices $U(n, q^{s})$ is given by
the transformation $\frac{2l−1}{2q} , l = 1, \dots , q$.

4 Central Composite Discrepancy

There are several common measures for uniformity, amongst which the Centered Discrepancy proposed by Hickernell [6] would appear at first glance to be a reasonable choice given that a flexible region is a symmetrical shape with its origin at the centre of the region of interest. However, in common with other discrepancy measures, the discrepancy value is for a cuboid shaped region and cannot be adapted for other shape types.

The principle idea of the $CCD$ - and the reason why it can be applied to flexible regions - is that measurement is not taken from one fixed point: every point in $R$ is considered a center point. This removes the constraint on the shape type and, hence, makes it possible to implement the idea of a flexible region.

The $CCD$ for a set of points $\mathcal{P}$ in a region of interest $R$ is defined by

(3)
\begin{align} CCD_{p}(n,\mathcal{P}) &=& \biggl\{ \frac{1}{v(D)} \int_D \frac{1}{2^{K}} \sum_{k=1}^{2^{K}}\biggl|{\frac{N(D_{k}(x),\mathcal{P})}{n} - \frac{v(D_{k}(x))}{v(D)}}\biggr|^{p} dx \biggr\}^{1/p}\,. \end{align}

An optimal $U$-type design on $R$ is obtained if the $n$ design points from $\mathcal{P}$ are distributed in $R$ in a way to minimise $CCD_{p}(n,P)$, or more formally,

(4)
\begin{align} \mathcal{P^{*}}&=& arg \min_{P \in Z(n)} CCD_{p}(n,\mathcal{P})\,. \end{align}

One drawback is that, at present, there is no general analytical formula for the $CCD$, and this imposes a limit on the number of dimensions the design can take.

5. Experiment Description and Results

Experiment Setup

For all designs $U(n, q^{s})$ in the experiment the dimensions are set to $s = 2$, and the number of levels $q = 31$.

A smaller number of levels would make the optimisation process a trivial task, especially for flexible regions with $m < 1$. The level needs to be of fine enough resolution to well cover smaller regions (for small values of $m$) and allow the optimisation process the opportunity to be effective in lowering the discrepancy once points are moved into the flexible region. Basically, for higher values of $q$, there are more points to choose from.

The number of runs (design points), $n$, is one of the two varying factors in the experiment. $n = \{5,7,9,11\}$.

The parameter characterising the shape of the flexible region, $m$, is the other varying factor. $m = \{9999,2,1,0.5,0.3\}$.

This represents a general sample of flexible region shape types. Note that due to the constraint on $U$-type designs on the $q^{s }$ grid, the first value results in a covering of all grid points for the given design parameters.