Calibrating Heuristics


Marianna Lyra


Differential Evolution, LMS, Response Surface Analysis.

Review Status


1. Problem Description/Overview

While Differential Evolution (DE), as any optimization heuristic technique, does not depend on the specific choice of starting values, the
optimal combination of the technical parameters, F and CR, can determine the speed of convergence to the global solution and the variability of the results, respectively. A simplified, but sometimes time consuming, way to select the parameters' value is to iteratively run the algorithm for different parameter values and then extract some descriptive statistics ( the statistical efficiency of each setting through descriptive statistics). Nonetheless, a regression analysis or an orthogonal or rotatable design (like the one applied in Response Surface Analysis) or a uniform design can also be tested. For a small number of parameters these are efficient and relatively fast tools to find optimal parameter settings for a heuristics algorithm. Here I present an application of Response Surface Analysis to the estimation of DE parameters. In higher dimensions (higher number of parameters) a heuristic tool can serve as a parameter optimization technique.

2. Solution/Guidelines

Response Surface Methodology (RSM) is applied for finding the optimal combination of DE technical parameters value that help obtaining the CAPM parameters to minimize the median of squares error. The purpose of RSM is that it can estimate the parameters value with little tuning and without precise prior knowledge of their optimum value.

RSM explores the relationship between several input variables (factors) and a response output. In our case the input variables are the (scaling) factor F, the crossover probability CR and the population size np. Note that for DE the product of the population size np and number of generations nG determines the computational complexity of the algorithm. Hence, the aim is to find the optimal combination of the parameters F, CR and np for a given computational load np X nG. For that, the computational load (np X nG) is constant.

RSM consists of three main stages. In the first stage, the input variables F, CR and np are initialized.
The initialization is based on a prior knowledge about the best combination of parameters that will minimize the objective function. These values constitute the reference or center points. Next, the experimental domain is specified based on orthogonal and rotatable experimental designs described in the following. Inside this domain the factors are assigned specific values (levels), at which the response variable is estimated. The response variable is the minimum value obtained for Least Median of Squares.

In the final stage, a second order polynomial is fitted using the designed experiments. After differentiation, this results in the optimal set of DE's parameters. The reason of choosing a polynomial relationship is that no prior information about the existing relationship between the input and the response variable is needed.

\begin{align} y_{i} = \beta_{0}+\sum\beta_{i}X_{i}+\beta_{ii}X_{i}^{2}+\beta_{ij}X_{i}X_{j}+\varepsilon\ \label{eq:SRSD} \end{align}

yi is the minimum median of squared residuals for i-th setup of input variables, $\beta's$ are the parameters of equation 1, X's are the input variables for setup i and $\varepsilon$ the residual.

A possible extension in this direction might be the alternative formulation of the relationship or a transformation of it.

Internal Links

Differential Evolution
Related Articles

External links


Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License