## 2 Background
### Full Factorial Design  
Methodologies from the field of design of experiments (DOE) have been modified for their application to algorithmic tuning [4]. Using DOE, the act of tuning is viewed as an experiment, with the parameters referred to as factors of the experiment. The effect of these factors must be investigated, and factorial designs are especially efficient for these types of experiments. This section presents a brief outline of the vast topic that is factorial design. Chapter 5 of [5] goes into great detail on the topic, and [4] provides a more in-depth discussion of the application of DOE to tuning.  
[PERSON] [5] defined factorial design as  
\"...in each complete trial or replicate of the experiment, all possible combinations of the levels of the factors are investigated.\"  
In this definition, factors are variables in the experiment that the researcher has control over. For the purposes of tuning, these are the control parameters. The possible values that the factors can take on are referred to as levels. The number of levels available for each factor is set by the experimenter. This allows the granularity of the search to be set at the discretion of the researcher. A given combination of levels of factors must produce some response. When tuning is considered, a level is given as the performance of the heuristic with respect to some objective when executed with some control parameter configuration. The effect of a given factor is then characterised by the change in response given a change in the level of the factor.  
The responses for each combination of factor levels are used to construct a response surface. The response surface models the effects that each factor has on the fitness of the heuristic. A linear regression model is used to construct the response surface. Given the response surface, the optimal control parameter configuration can be selected by finding optima in the response surface. This presents another optimisation problem. Fortunately, when using a known model (like linear regression), the optimisation can be performed using simple optimisation techniques such as the Nelder-Mead Simplex [4].  
[PERSON] [4] presented a method for tuning control parameters using DOE with respect to multiple performance objectives. When considering multiple objectives, multiple response surfaces, one for each objective, are constructed. [PERSON] [4] suggested setting up a desirability function \(d(Y)\) for each objective that, for some response \(Y\) from the response surface, a desirability value in the range \([0,1]\) is given. A desirability of \(d(Y)=0\) indicates a completely undesirable response, while a desirability of \(d(Y)=1\) indicates an ideal response. The geometric mean of each desirability function is then taken to form a single function by which the desirability of the heuristic is modelled with respect to multiple performance objectives.  
Full factorial design presents a major drawback: evaluation of all possible combinations of levels for all possible combinations of factors is computationally expensive, and in some cases infeasible. Methods have been proposed to reduce computational cost, such as \(2^{k}\) and \(3^{k}\) factorial design, and fractional factorial design [5]. The improvements in computation result in less coverage of the search space and often requires expert knowledge to identify promising regions within the parameter space.