Keywords

1 Introduction

Response surface methodology is used in experiments in which the main interests are to determine the relationship between the response and the settings of a group of experimental factors and to find the combination of the factor levels that gives the best expected response. Response surfaces can also provide information about the rate of change of the response variable and indicate the interactions between the treatment factors. This class of designed experiments has a wide range of applications in industrial and chemical engineering, agricultural experiments and biotechnological processes [1, 10, 12, 13, 18, 25].

In this paper we focus on the construction of \(2^q\)-level response surface designs by emphasizing on an algorithmic perspective of the problem. In such designs the design matrix columns are constituted of combinations of \(2^q\) distinct symbols and correspond to the treatment factors, each at \(2^q\) equally spaced quantitative levels. Any combination of the levels of all factors under consideration is called a treatment combination. Let \(\mathbf {X} =[x_1,x_2,\ldots ,x_k]\) be the design matrix of the experiment in which, each row represents the \(n\) treatment combinations and each column gives the sequence of factor levels. For each factor, all level values are of equal interest and each experimental result should have equal influence. Thus we consider designs with the equal occurrence property, when for example we construct four-level designs we have that all columns consist of \(n/4\) elements equal to 1, \(n/4\) elements equal to \(-1\), \(n/4\) elements equal to \(1/3\), \(n/4\) elements equal to \(-1/3\), if \(n\) is a multiple of four. The designs with the equal occurrence property are called balanced designs. Although \(2^q\)-level factors appear often in experimental problems, a minor work has be done in this specific area of response surface designs [10, 12, 15, 24].

The paper is organized as follows. In Sect. 2 the concepts and the measures of rotatability and efficiency of response surface designs are defined. A genetic algorithm approach for the construction of \(2^q\)-level response surface designs is presented in Sect. 3, while the obtained results are given in Sect. 4.

2 Model and Design Optimality Criteria

Suppose we want to test the effects of \(k\) predictor variables, coded to \(x_1, x_2, \ldots , x_k\), on a response variable \(y\) subject to random error. Generally the first attempt is to approximate the shape of the response surface by fitting a first-order model to the response,

$$\begin{aligned} y = \beta _0 +\sum _{j=1}^k \beta _j x_j +\varepsilon , \end{aligned}$$
(1)

where \(\beta _0\), \(\beta _j\), \(j=1,\ldots ,k\) are unknown parameters and \(\varepsilon \) is a random error term. When the first-order model appears inadequate to describe the true relationship between the response and the predictor variables due to the existence of surface curvature, it is upgraded to a second-order model

$$\begin{aligned} y = \beta _0 +\sum _{j=1}^k \beta _j x_j + \sum _{j=1}^k \beta _{jj} x_j^2 + \underbrace{\sum _{i=1}^k \sum _{j=1}^k}_{i < j} \beta _{ij}x_i x_j + \varepsilon , \end{aligned}$$
(2)

where \(\beta _0\), \(\beta _j\), \(j=1,\ldots ,k\), \(\beta _{ij}\), \(i=1,\ldots ,k\), \(j=1,\ldots ,k\), are unknown parameters and \(\varepsilon \) is a random error term.

Two of the most important characteristics that a response surface design should possess is rotatability and efficiency.

The concept of rotatability was introduced by Box and Hunter [3]. A \(k\)-dimensional design is called rotatable if the variance of the response estimated by the fitted polynomial at the point \((x_1,...,x_k)\), \(\mathrm {Var}[\hat{Y}(\mathbf {x})]\), is a function only of \(\rho ^2=\sum _{i=1}^{k}x_{i}^{2}\). Such a design insures that the estimated response has a constant variance at all points that are equidistant from the design center. One of the desirable features of rotatability is that the quality of the prediction, as measured by the magnitude of \(\mathrm {Var}[\hat{Y}(\mathbf {x})]\), is invariant to any rotation of the coordinate axes in the space of the input variables. In cases where exact rotatability is unattainable, it is important to measure how rotatable a design is. Khuri [17], Draper and Guttman [8] and Draper and Pukelsheim [9] proposed measures to test the near rotatability of a design. In this framework we use the rotatability measure \(Q^*\) provided by Draper and Pukelsheim [9] and given by the equation

$$\begin{aligned} Q^*=\frac{||\bar{\mathbf {A}}-\mathbf {V_0}||^2}{||\mathbf {A}-\mathbf {V_0}||^2}= \frac{tr(\bar{\mathbf {A}}-\mathbf {V_0})^2}{tr(\mathbf {A}-\mathbf {V_0})^2}, \end{aligned}$$
(3)

where \(\bar{\mathbf {A}}\) is the rotatable component of the moment matrix \(\mathbf {A}=n^{-1}\mathbf {X'X}\) and \(\mathbf {V_0}\) consists of a one in the (1, 1) position and zeros elsewhere. It is \(Q^* \le 1\) and equality stands when the design is rotatable. For more details see [9].

Beyond testing the near rotatability of the designs in order to compare them, it is also needed to have an estimation efficiency measure for the same purpose. Box and Draper [4] discussed as a measure of design efficiency the choice of a design on the basis of maximizing the determinant of the information matrix. In this paper we adopt the following \(D\) criterion for determining the overall efficiency for estimating the set of the effects

$$\begin{aligned} |\mathbf {W'W}|^{1/k}, \end{aligned}$$
(4)

where \(\mathbf {W} = [x_0/||x_0||,x_1/||x_1||,\ldots , x_k/||x_k||]\), \(x_0\) stands for the vector with all elements equal to 1, and \(x_i\) is the coefficient vector of the \(i\)th effect, \(i=1,\ldots , k\). Since the columns of \(\mathbf {W}\) are standardized, the \(D\) criterion achieves its maximum value, which equals to 1, if and only if the \(x_i\) are orthogonal to each other. More details can be found in [26].

3 Optimization of Response Surface Designs by Means of Genetic Algorithms

Genetic algorithms form a powerful metaheuristic that mimicks processes from the Theory of Evolution to establish search algorithms by defining algorithmic analogues of biological concepts such as reproduction, crossover and mutation. Genetic Algorithms were introduced in 1970 by Holland [16] aiming to design an artificial system having properties similar to natural systems. In this paper, we assume some basic familiarity with Genetic Algorithm concepts. The concepts necessary for a description of the Genetic Algorithm (GA) can be found in Goldberg [14], in Forrest’s article [11] and in the Handbook of Genetic Algorithms edited by Davis [6].

GAs are attractive because of their robustness and flexibility in terms of a computer implementation and, mathematically, they do not require a differentiable objective function thereby reducing the chance of reporting local optima. Some earlier attempts utilizing a GA in the construction of response surface designs has been given by Drain et al. [7]. However, this approach, while promising, lacked of an efficient coding of the chromosomes i.e. the number of the experimental runs forming the design. In particular, the authors proposed utilizing and constructing the whole design; thus restricting the GA to evolve in finding optimal response surface designs in several cases. A successful reduction in terms of computational complexity of an efficient representation of the candidate design, has been proposed in [21–23] in a similar field of computational design theory with strong connection to statistical applications. In these applications, the authors integrated as a core ingredient of the GA the use of sequential juxtaposition of suitable generators, either forming circulant matrices [21] or block circulant matrices [22, 23].

3.1 A Genetic Algorithm Framework for Response Surface Designs

Chromosomes Representation

The respective generators considered in the case of response surface designs are the \(n/2^q\) column vectors which in the process form block circulant matrices of order \(k\), when constructing an \(n \times k\) response surface design. This construction, is valid when \(n\) is a multiple of \(2^q\). In particular, we form \(n/4\) and \(n/8\) column vectors when we consider four and eight-level response surface designs, respectively. However, in all previous constructions the generators, more precisely the genes forming a generator, consisted of binary variables since a two-level design was under development. In the case of response surface designs, the genes constitute of \(2^q\) possible values representing the \(2^q\)-levels of the designs.

Chromosomes Encoding and Decoding

A suitable encoding to binary variables was needed since the genetic operators behave better in binary arithmetic (Goldberg [14]). The answer to this vital question found in the field of Combinatorics and Computer Science in terms of representing a 2-bit Gray Code, \(GC_2=\{00,01,11,10\}\) when considering four-level designs; while in the case of eight-level designs we used a 3-bit Gray Code, \(GC_3=\{000,001,011,010,110,111,101,100\}\). For more details, on Gray Codes we refer the interested reader to Carla [5]. More precisely, we mapped each level of a four-level design to a codeword of the 2-bit Gray Code, i.e. \(\{-1,-1/3,1/3,1\} \rightarrow \{00,01,11,10\}\), and each level of an eight-level design to a codeword of the 3-bit Gray Code i.e. \(\{-1,-1/3,-1/6,-1/9,1/9,\) \(1/6,1/3,1\}\rightarrow \{000,001,011,010,\) \(110,111,101,100\}\), thus transforming the problem on its binary equivalent which allowed us to carry on with the next stages of utilizing a GA. It is made clear that we could repeat this procedure for \(2^q\)-level response surface designs by using a \(q\)-bit Gray Code. Details for constructing a \(q\)-bit Gray Code can be found in Knuth [19].

Initial Population

consists of random chromosomes. We found it useful to generate these chromosomes by retrieving samples of binary sequences, after random permutations where applied to each of them.

An Objective function for Response Surface Designs

The crucial choice of the objective function (OF) subject to be optimized arise naturally from the theoretical framework of rotatable and efficient designs. In particular, we have developed two versions of the algorithm each one depending on one of the two optimality design criteria, the rotatability measure \(Q^*\) and the \(D\) criterion. The genetic algorithm attempts in both cases to maximize the value of each criterion with respect to its upper bound which is equal to \(1\). Due to the theoretical background and statistical justifications when a value of \(Q^*\) was detected in the range of \([0.95,1.00]\) we considered we have found a global optimum solution, while in the case of \(D\) criterion we made some ramifications to accept a lower bound for the range of optimum solutions, i.e. \([0.65,1.00]\). Thus we were able to detect both rotatable and efficient designs. In the following figure we give a comparison of the genetic algorithm performance in terms of contrasting the \(Q^*\) versus the \(D\) criterion by scaling on the evolving generations. From the figure we can conclude that we can use the \(Q^*\) and \(D\) criterion interchangeably as objective functions, since the fitness values for each case are similar.

Fig. 1
figure 1

Symmetries on objectives functions for optimization of response surface designs

Full size image

We are now able to describe the three genetic operators of reproduction, crossover and mutation as specifically have been applied by the genetic algorithm we have used.

Crossover

We defined the basic genetic operation, crossover, that splits a pair of binary integers at a random position and combines the head of one with the tail of the other and vice versa.

Mutation

Additional operations, such as inverting a section of the binary representation (inversion) or randomly changing the state (0 or 1) of individual bits (mutation), also transform the population (Fig. 1).

Selection and Reproduction

Before each such cycle (generation), population members are selected on the basis of their fitness (the value of the objective function for that solution) to be the “parents” of the new generation.

Termination Condition

of the genetic algorithm was set a predefined number of evolved generations. This number of generations was proportional to the size of the response surface design that the genetic algorithm was searching for in each case. Thus the GA required only a few generations to find a small sized optimal response surface design, while a larger design required additional generations to be evolved. Since GA is a heuristic process, the time complexity of the algorithm was relatively small compared to exhaustive search algorithms.

4 New Four and Eight-Level Response Surface Designs

In this Section we present the results of the construction method for four and eight-level response surface designs as described previously.

4.1 New Four-Level Response Surface Designs

In Table 1, \(k\) stands for the number of the experimental factors and \(n\) for the number of the performed runs, while in the next two columns the achieved values for the \(Q^*\) and the \(D\) criterion are listed.

Table 1 Some new four-level response surface designs with \(k\) factors
Full size table

From the above results we note that the \(Q^*\) values fluctuate between \(95.67\,\%\) and \(99.06\,\%\) and the arithmetical mean equals to \(98.20\,\%\), while the maximum and the minimum values of the \(D\)-criterion are \(75.94\,\%\) and \(72.02\,\%\), respectively, with the arithmetical mean equal to \(74.36\,\%\). Also, Koshal’s designs (see [2, 20]) are occasionally of use in response surface work. For the third-order Koshal design in \(3\) four-level predictor variables with \(20\) runs, given in page 504 of [2], we calculate the corresponding values of \(Q^*\) and \(D\)-criterion, which are equal to 0.3150 and 0.2613, respectively. In general, high values of the two criteria, \(Q^*\) and \(D\), ensure that the designs are near-rotatable and efficient for estimating the set of the effects.

4.2 New Eight-Level Response Surface Designs

In this section we present the results of the construction method for eight-level response surface designs. In Table 2, \(k\) stands for the number of the experimental factors and \(n\) for the number of the performed runs, while in the next two columns the achieved values for the \(Q^*\) and the \(D\) criterion are listed.

Table 2 Some new eight-level response surface designs with \(k\) factors
Full size table

From the above results we note that the \(Q^*\) values fluctuate between \(95.30\,\%\) and \(99.99\,\%\) and the arithmetical mean equals to \(98.13\,\%\), while the maximum and the minimum values of the \(D\)-criterion are \(87.95\,\%\) and \(65.28\,\%\), respectively, with the arithmetical mean equal to \(78.06\,\%\).

As a conclusion, our construction method manages to generate near-rotatable and efficient response surface designs with a small number of required runs for both cases of four and eight-level designs thus demonstrating the efficiency of the genetic algorithm used. From these experimental results, it is anticipated that the proposed formulation for \(2^q\)-level response surface designs should produce similar results for higher number of levels when combined with a genetic algorithm utilized with the aid of a \(q\)-bit Gray Code.