The cross-entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling. Monte Carlo methods are a class of Computational Algorithms that rely on repeated Random sampling to compute their results Combinatorial optimization is a branch of optimization. Its domain is optimization problems where the set of Feasible solutions is discrete or can be reduced Continuous optimization is a branch of optimization in Applied mathematics. In Mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function In Statistics, importance sampling is a general technique for estimating the properties of a particular distribution, while only having samples generated from a different The method originated from the field of rare event simulation, where very small probabilities need to be accurately estimated, for example in network reliability analysis, queueing models, or performance analysis of telecommunication systems. The CE method can be applied to static and noisy combinatorial optimization problems such as the traveling salesman problem, the quadratic assignment problem, DNA sequence alignment, the max-cut problem and the buffer allocation problem, as well as continuous global optimization problems with many local extrema. The Travelling salesman problem ( TSP) in Operations research is a problem in discrete or Combinatorial optimization. The quadratic assignment problem ( QAP) is one of fundamental Combinatorial optimization problems in the branch of optimization or Operations research In Bioinformatics, a sequence alignment is a way of arranging the Primary sequences of DNA, RNA, or Protein to identify regions of In Graph theory, a cut is a partition of the vertices of a graph into two sets Global optimization is a branch of Applied mathematics and Numerical analysis that deals with the optimization of a function or a set In Mathematics, maxima and minima, known collectively as extrema, are the largest value (maximum or smallest value (minimum that
In a nutshell the CE method consists of two phases:
Consider the general problem of estimating the quantity , where H is some performance function and is a member of some parametric family of distributions. Using importance sampling this quantity can be estimated as , where is a random sample from . In Statistics, importance sampling is a general technique for estimating the properties of a particular distribution, while only having samples generated from a different For positive H, the theoretically optimal importance sampling density (pdf)is given by . In Mathematics, a probability density function (pdf is a function that represents a Probability distribution in terms of Integrals Formally a probability This, however, depends on the unknown . The CE method aims to approximate the optimal pdf by adaptively selecting members of the parametric family that are closest (in the Kullback-Leibler sense) to the optimal pdf g * . In Probability theory and Information theory, the Kullback–Leibler divergence (also information divergence, information gain, or relative
In several cases, the solution to step 3 can be found analytically. Situations in which this occurs are
The same CE algorithm can be used for optimization, rather than estimation. Suppose the problem is to maximize some function S(x), for example, . To apply CE, one considers first the associated stochastic problem of estimating for a given level , and parametric family , for example the 1-dimensional Gaussian distribution, parameterized by its mean and variance (so here). The normal distribution, also called the Gaussian distribution, is an important family of Continuous probability distributions applicable in many fields Hence, for a given , the goal is to find so that is minimized. This is done by solving the sample version (stochastic counterpart) of the KL divergence minimization problem, as in step 3 above. It turns out that parameters that minimize the stochastic counterpart for this choice of target distribution and parametric family are the sample mean and sample variance corresponding to the elite samples, which are those samples that have objective function value . The worst of the elite samples is then used as the level parameter for the next iteration. This yields the following randomized algorithm for this problem.
1. mu:=-6; sigma2:=100; t:=0; maxits=100; // Initialize parameters2. N:=100; Ne:=10; //3. while t < maxits and sigma2 > epsilon // While not converged and maxits not exceeded4. X = SampleGaussian(mu,sigma2,N); // Obtain N samples from current sampling distribution5. S = exp(-(X-2)^2) + 0. 8 exp(-(X+2)^2); // Evaluate objective function at sampled points6. X = sort(X,S); // Sort X by objective function values (in descending order)7. mu = mean(X(1:Ne)); sigma2=var(X(1:Ne)); // Update parameters of sampling distribution8. t = t+1; // Increment iteration counter9. return mu // Return mean of final sampling distribution as solution