Algorithm

REVAC uses information theory to measure parameter relevance. Instead of estimating the performance of an EA for specific parameter values or ranges of values, REVAC estimates the expected performance when parameter values are chosen from specific probability density distributions. As these density distributions are meant to approximate the maximum entropy distribution for a given level of performance, their Shannon entropy can be used to measure the amount of information needed to reach this level of performance. The differential Shannon entropy of a distribution TeX Embedding failed! over the continuous interval TeX Embedding failed! is defined as

TeX Embedding failed!

As a simple rule of thumb, the sharper the peaks of the distribution, the lower the entropy. We have TeX Embedding failed! for the uniform distribution over TeX Embedding failed! and negative for any other distribution over TeX Embedding failed!. REVAC takes the distribution of this information over the different parameter values as an indicator of parameter relevance, i.e., how much information is needed to calibrate a particular parameter. In these terms the objectives of REVAC can be formulated as follows:

• the entropy of the distribution \calibration is as high as possible for a given level of performance
• the expected performance of the EA in question is as high as possible for a given level of Shannon entropy

Since REVAC is intended for the continuous domain, the choice of suitable EDAs is limited. The present algorithm is a variation of the Univariate Marginal Distribution Algorithm (Mühlenbein 1997). For efficiency, only a single parameter vector is replaced every generation, and not the whole population. Given an EA with TeX Embedding failed! parameters REVAC iteratively refines a joint distribution TeX Embedding failed! over possible parameter vectors TeX Embedding failed!. Beginning with a uniform distribution TeX Embedding failed! over the initial parameter space TeX Embedding failed!, REVAC gives a higher and higher probability to those regions of TeX Embedding failed! where the associated EA performs best, increasing the expected performance of the generated EAs. On the other hand, REVAC continuously smoothes the distribution TeX Embedding failed!, to reduce the variance of stochastic measurements and to prevent premature convergence. It is the combination of these two operators, selection and smoothing, that allows REVAC to approach the maximum entropy distribution. For a good understanding of how an EDA works it is helpful to distinguish two views on a set of parameter vectors as shown in Table 1. Taking a horizontal view on the table, a row is a parameter vector and we can see the table as TeX Embedding failed! of such vectors TeX Embedding failed!. Taking the vertical view on the columns, each of the TeX Embedding failed! columns shows TeX Embedding failed! values from the domain of the associated parameter TeX Embedding failed!. A table TeX Embedding failed! of TeX Embedding failed! vectors of TeX Embedding failed! parameters

TeX Embedding failed!

(1)

These TeX Embedding failed! values allow us to define a marginal density function TeX Embedding failed! over the domain of parameter TeX Embedding failed!, scaled to the unit range TeX Embedding failed!: provided there are no equal values, the TeX Embedding failed!values and the limits can be arranged such that they form TeX Embedding failed! non-overlapping intervals that completely cover the range TeX Embedding failed!. We define the density over any such interval TeX Embedding failed!, including limits, as

TeX Embedding failed!

satisfying TeX Embedding failed!. In this way the TeX Embedding failed! columns of Table 1 define TeX Embedding failed! marginal density functions TeX Embedding failed! which in turn define a joint density function TeX Embedding failed!. This definition of a density function can be extended to allow intervals to overlap, for example by taking intervals not between first neighbors along the domain of the parameter, but between second or third neighbors. The resulting distribution is a smoothed version of the original one and has a higher Shannon entropy. The more the intervals overlap, the higher the resulting Shannon entropy and Shannon entropy is maximized when all intervals overlap and form a uniform distribution.