Algorithm details

REVAC starts from an initial table TeX Embedding failed! that was drawn from the uniform distribution over TeX Embedding failed!. The update process that creates a new table TeX Embedding failed! from a given TeX Embedding failed! can be described from both the horizontal and the vertical perspective. Looking at Table from the horizontal perspective we can identify two basic steps:

1. Evaluating parameter vectors: Given a parameter vector TeX Embedding failed! we can evaluate it: the utility of TeX Embedding failed! is the performance of the EA executed with these parameter values. The evaluation can be based on one or more replications
2. Generating parameter vectors: Given a set of parameter vectors with known utility we can generate new ones that have higher expected utility.

Step 1 is straightforward, let us only note that we call the performance that an EA achieves on a problem using parameters TeX Embedding failed! the response. Response TeX Embedding failed! is thus a function

TeX Embedding failed!

The surface of this function is called a response surface. As for step 2, we use a method that is evolutionary itself, (but should not be confused with the EA we are calibrating). We work with a population of TeX Embedding failed! parameter vectors. A new population is created by selecting TeX Embedding failed! parent vectors from the current population, recombining and mutating the selected parents to obtain a child vector, replacing one vector of the population.

We use a deterministic choice for parent selection as well as for survivor selection. The best TeX Embedding failed! vectors of the population are selected to become the parents of the new child vector, which always replaces the oldest vector in the population. Only one vector is replaced in every generation. Recombination is performed by a multi-parent crossover operator, uniform scanning, that creates one child from TeX Embedding failed! parents, cf. (Eiben and Smith 2003).

The mutation operator—applied to the offspring created by recombination—is rather complicated. It works independently on each parameter TeX Embedding failed! in two steps. First, a mutation interval is calculated, then a random value is chosen from this interval. To define the mutation interval for mutating a given TeX Embedding failed! all other values TeX Embedding failed!,...,TeX Embedding failed! for this parameter in the selected parents are also taken into account. After sorting them in increasing order, the begin point of the interval can be specified as the TeX Embedding failed!-th lower neighbor of TeX Embedding failed!, while the end point of the interval is the TeX Embedding failed!-th upper neighbor of TeX Embedding failed!. The new value is drawn from this interval with a uniform distribution.

From the vertical perspective we consider each iteration as constructing \parnum new marginal density functions from the old set TeX Embedding failed!. Roughly speaking, new distributions are built on estimates of the response surface that were sampled with previous density functions, each iteration giving a higher probability to regions of the response surface with higher response levels. Each density functions is constructed from TeX Embedding failed! uniform distributions over overlapping intervals. In this context, the rationale behind the complicated mutation operator is that it heavily smoothes the density functions. Like all evolutionary algorithms EDA is susceptible for converging on a local maximum. By consistently smoothing the distribution functions we force it to converge on a maximum that lies on a broad hill, yielding robust solutions with broad confidence intervals. But smoothing does more: it allows REVAC to operate under very noise conditions, it allows it to readjust and relax marginal distributions when parameters are interactive and the response surface has curved ridges, and it maximizes the entropy of the constructed distribution. Smoothing is achieved by taking not the nearest neighbor but the TeX Embedding failed!-th neighbors of TeX Embedding failed! when defining the mutation interval. At the edges of the parameter ranges are no neighbors. We solve this problem by mirroring neighbors and chosen values at the limits, similar to what is done in Fourier transformations.

Choosing a good value for TeX Embedding failed! is an important aspect when using REVAC. A large TeX Embedding failed! value can slow down convergence to the point of stagnation. A small TeX Embedding failed! value can produce unreliable results. We prefer TeX Embedding failed!.