The Cross-Entropy Method for Continuous Multi-Extremal Optimization

In recent years, the cross-entropy method has been successfully applied to a wide range of discrete optimization tasks. In this paper we consider the cross-entropy method in the context of continuous optimization. We demonstrate the effectiveness of the cross-entropy method for solving difficult continuous multi-extremal optimization problems, including those with non-linear constraints.      

Semi-Iterative Minimum Cross-Entropy Algorithms for Rare-Events,Counting, Combinatorial and Integer Programming

We present a new generic minimum cross-entropy method, called the semi-iterative MinxEnt, or simply SME, for rare-event probability estimation, counting, and approximation of the optimal solutions of a broad class of NP-hard linear integer and combinatorial optimization problems (COP’s). The main idea of our approach is to associate with each original problem an auxiliary single-constrained convex MinxEnt program of a special type, which has a closed-form solution. We prove that the optimal pdf obtained from the solution of such a specially designed MinxEnt program is a zero variance pdf, provided the “temperature” parameter is set to minus infinity. In addition we prove that the parametric pdf based on the product of marginals obtained from the optimal zero variance pdf coincides with the parametric pdf of the standard cross-entropy (CE) method. Thus, originally designed at the end of 1990s as a heuristics for estimation of rare-events and COP’s, CE has strong connection with MinxEnt, and thus, strong mathematical foundation. The crucial difference between the proposed SME method and the standard CE counterparts lies in their simulation-based versions: in the latter we always require to generate (via Monte Carlo) a sequence of tuples including the temperature parameter and the parameter vector in the optimal marginal pdf’s, while in the former we can fix in advance the temperature parameter (to be set to a large negative number) and then generate (via Monte Carlo) a sequence of parameter vectors of the optimal marginal pdf’s alone. In addition, in contrast to CE, neither the elite sample no the rarity parameter is needed in SME. As result, the proposed SME algorithm becomes simpler, faster and at least as accurate as the standard CE. Motivated by the SME method we introduce a new updating rule for the parameter vector in the parametric pdf of the CE program. We show that the CE algorithm based on the new updating rule, called the combined CE (CCE), is at least as fast and accurate as its standard CE and SME counterparts. We also found numerically that the variance minimization (VM)-based algorithms are the most robust ones. We, finally, demonstrate numerically that the proposed algorithms, and in particular the CCE one, allows accurate estimation of counting quantities up to the order of hundred of decision variables and hundreds of constraints. This research was supported by the Israel Science Foundation (grant No 191-565).     

Vague集信息熵测量及其应用

引入了区别于现有文献的Vague集信息熵和Vague集的关联熵的概念,给出了一种改进的测量方法,并讨论了它们之间的关系。进而,我们揭示了Vague集的熵和Fuzzy集的熵之间的关系,并分析了本文所定义熵的意义。最后,讨论了这种关联熵在模糊识别和医疗诊断上的应用。     

An information theory perspective on the balanced minimum evolution problem

We show that the Balanced Minimum Evolution Problem (BMEP) is a cross-entropy minimization problem. This new perspective both extends the previous interpretations of the BMEP length function described in the literature and enables the identification of an efficiently computable family of lower bounds on the value of the optimal solution to the problem.     

Cross-entropic learning of a machine for the decision in a partially observable universe

In this paper, we are interested in optimal decisions in a partially observable universe. Our approach is to directly approximate an optimal strategic tree depending on the observation. This approximation is made by means of a parameterized probabilistic law. A particular family of Hidden Markov Models (HMM), with input and output, is considered as a model of policy. A method for optimizing the parameters of these HMMs is proposed and applied. This optimization is based on the cross-entropic (CE) principle for rare events simulation developed by Rubinstein.     

An efficient surrogate-based method for computing rare failure probability

In this paper, we present an efficient numerical method for evaluating rare failure probability. The method is based on a recently developed surrogate-based method from Li and Xiu [J. Li, D. Xiu, Evaluation of failure probability via surrogate models, J. Comput. Phys. 229 (2010) 8966–8980] for failure probability computation. The method by Li and Xiu is of hybrid nature, in the sense that samples of both the surrogate model and the true physical model are used, and its efficiency gain relies on using only very few samples of the true model. Here we extend the capability of the method to rare probability computation by using the idea of importance sampling (IS). In particular, we employ cross-entropy (CE) method, which is an effective method to determine the biasing distribution in IS. We demonstrate that, by combining with the CE method, a surrogate-based IS algorithm can be constructed and is highly efficient for rare failure probability computation—it incurs much reduced simulation efforts compared to the traditional CE-IS method. In many cases, the new method is capable of capturing failure probability as small as 10⁻¹² ∼ 10⁻⁶ with only several hundreds samples.     

Convergence properties of the cross-entropy method for discrete optimization

We present new theoretical convergence results on the cross-entropy (CE) method for discrete optimization. We show that a popular implementation of the method converges, and finds an optimal solution with probability arbitrarily close to 1. We also give conditions under which an optimal solution is generated eventually with probability 1.     

The cross-entropy method in multi-objective optimisation: An assessment

Solving multi-objective problems requires the evaluation of two or more conflicting objective functions, which often demands a high amount of computational power. This demand increases rapidly when estimating values for objective functions of dynamic, stochastic problems, since a number of observations are needed for each evaluation set, of which there could be many. Computer simulation applications of real-world optimisations often suffer due to this phenomenon. Evolutionary algorithms are often applied to multi-objective problems. In this article, the cross-entropy method is proposed as an alternative, since it has been proven to converge quickly in the case of single-objective optimisation problems. We adapted the basic cross-entropy method for multi-objective optimisation and applied the proposed algorithm to known test problems. This was followed by an application to a dynamic, stochastic problem where a computer simulation model provides the objective function set. The results show that acceptable results can be obtained while doing relatively few evaluations.     

Application of the cross-entropy method to clustering and vector quantization

We apply the cross-entropy (CE) method to problems in clustering and vector quantization. The CE algorithm for clustering involves the following iterative steps: (a) generate random clusters according to a specified parametric probability distribution, (b) update the parameters of this distribution according to the Kullback–Leibler cross-entropy. Through various numerical experiments, we demonstrate the high accuracy of the CE algorithm and show that it can generate near-optimal clusters for fairly large data sets. We compare the CE method with well-known clustering and vector quantization methods such as K-means, fuzzy K-means and linear vector quantization, and apply each method to benchmark and image analysis data.