On the Convergence of the Cross-Entropy Method

The cross-entropy method is a relatively new method for combinatorial optimization. The idea of this method came from the simulation field and then was successfully applied to different combinatorial optimization problems. The method consists of an iterative stochastic procedure that makes use of the importance sampling technique. In this paper we prove the asymptotical convergence of some modifications of the cross-entropy method.     

The Cross-Entropy Method for Network Reliability Estimation

Consider a network of unreliable links, modelling for example a communication network. Estimating the reliability of the network—expressed as the probability that certain nodes in the network are connected—is a computationally difficult task. In this paper we study how the Cross-Entropy method can be used to obtain more efficient network reliability estimation procedures. Three techniques of estimation are considered: Crude Monte Carlo and the more sophisticated Permutation Monte Carlo and Merge Process. We show that the Cross-Entropy method yields a speed-up over all three techniques.     

Solving the Vehicle Routing Problem with Stochastic Demands using the Cross-Entropy Method

An alternate formulation of the classical vehicle routing problem with stochastic demands (VRPSD) is considered. We propose a new heuristic method to solve the problem, based on the Cross-Entropy method. In order to better estimate the objective function at each point in the domain, we incorporate Monte Carlo sampling. This creates many practical issues, especially the decision as to when to draw new samples and how many samples to use. We also develop a framework for obtaining exact solutions and tight lower bounds for the problem under various conditions, which include specific families of demand distributions. This is used to assess the performance of the algorithm. Finally, numerical results are presented for various problem instances to illustrate the ideas.     

A Stochastic Minimum Cross-Entropy Method for Combinatorial Optimization and Rare-event Estimation*

We present a new method, called the minimum cross-entropy (MCE) method for approximating the optimal solution of NP-hard combinatorial optimization problems and rare-event probability estimation, which can be viewed as an alternative to the standard cross entropy (CE) method. The MCE method presents a generic adaptive stochastic version of Kull-backs classic MinxEnt method. We discuss its similarities and differences with the standard cross-entropy (CE) method and prove its convergence. We show numerically that MCE is a little more accurate than CE, but at the same time a little slower than CE. We also present a new method for trajectory generation for TSP and some related problems. We finally give some numerical results using MCE for rare-events probability estimation for simple static models, the maximal cut problem and the TSP, and point out some new areas of possible applications.AMS 2000 Subject Classification: 65C05, 60C05, 68W20, 90C59*This reseach was supported by the Israel Science Foundation (grant no 191-565).     

一种基于相对熵(CE)方法的新的随机水平值下降算法

为了使得随机积分水平集算法中的积分水平值能够更加有效地下降,使每次下降得到的参数更适应目标函数,本文将相对熵方法应用到随机积分水平集算法中来.利用相对熵中的ASP问题给出了一种新的参数更新方法,数值试验证明了其科学性.最后就该方法给出了更加一般的参数更新方法并给出了算法.     

Application of the Cross-Entropy Method to the Buffer Allocation Problem in a Simulation-Based Environment

The buffer allocation problem (BAP) is a well-known difficult problem in the design of production lines. We present a stochastic algorithm for solving the BAP, based on the cross-entropy method, a new paradigm for stochastic optimization. The algorithm involves the following iterative steps: (a) the generation of buffer allocations according to a certain random mechanism, followed by (b) the modification of this mechanism on the basis of cross-entropy minimization. Through various numerical experiments we demonstrate the efficiency of the proposed algorithm and show that the method can quickly generate (near-)optimal buffer allocations for fairly large production lines.     

Rare-Event Simulation of Non-Markovian Queueing Networks Using a State-Dependent Change of Measure Determined Using Cross-Entropy

A method is described for the efficient estimation of small overflow probabilities in nonMarkovian queueing network models. The method uses importance sampling with a state-dependent change of measure, which is determined adaptively using the cross-entropy method, thus avoiding the need for a detailed mathematical analysis. Experiments show that the use of rescheduling is needed in order to get a significant simulation speedup, and that the method can be used to estimate overflow probabilities in a two-node tandem queue network model for which simulation using a state-independent change of measure does not work well.     

The Cross-Entropy Method for Combinatorial and Continuous Optimization

We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.     

Managing Stochastic,Finite Capacity,Multi-Project Systems through the Cross-Entropy Methodology

This paper addresses the problem of loading a finite capacity, stochastic (random) and dynamic multi-project system. The system is controlled by keeping a constant number of projects concurrently in the system. A new approach, based on the Cross-Entropy (CE) method, is proposed to determine optimal loading of the system. Through numerical experiments, we demonstrate the CE method performance and show new insights into its behavior in a noisy system. Particularly, we suggest a trade-off between the convergence time, the number of iterations and the noise level. This research was partially supported by the Inga and Hal Marcus Research Fund     

一种无约束全局优化的水平值下降算法

本文研究无约束全局优化问题,建立了一种新的水平值下降算法(Level-value Descent Method,LDM).讨论并建立了概率意义下取全局最小值的一个充分必要条件,证明了算法LDM是依概率测度收敛的.这种LDM算法是基于重点度取样(Improtance Sampling)和Markov链Monte-Carlo随机模拟实现的,并利用相对熵方法(TheCross-Entropy Method)自动更新取样密度,算例表明LDM算法具有较高的数值精度和较好的全局收敛性.     

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).     

一种新的求总极值的水平值估计算法

提出了一种求解总极值问题的新水平值估计算法. 为此, 引入一类变差函数并研究它的性质; 给出基于变差函数的全局最优性条件, 并构造出一种求总极值的水平值估计算法. 为了实现这种算法, 采用了基于重点样本技术的Monte-Carlo方法来计算变差,并利用相对熵算法的主要思想更新取样密度.初步的数值实验说明了算法的有效性.     

应用交替线性化方法解决支持向量机问题(英文)

提出了一种新的解决稀疏支持向量机的方法-基于经典增广拉格朗日框架的交替线性化法.数值结果证明我们方法的有效性.     

基于小波变换和改进萤火虫算法优化极限学习机的短期负荷预测

提出了一种基于小波变换和改进萤火虫优化极限学习机的短期负荷预测方法.通过小波分解和重构,对原始负荷序列进行降噪;在模型训练阶段利用改进的萤火虫算法优化极限学习机参数,获得各序列的最优模型;针对各子序列分别预测叠加得到最终预测值.通过在两种时间尺度的数据序列上进行数值计算,与传统的ARMA、BP神经网络、支持向量机及LSSVM等多种经典预测模型相比,模型预测效果更优.     

基于空间填充准则的交叉验证方法及其应用

在统计学与机器学习中,交叉验证被广泛应用于评估模型的好坏.但交叉验证法的表现一般不稳定,因此评估时通常需要进行多次交叉验证并通过求均值以提高交叉验证算法的稳定性.文章提出了一种基于空间填充准则改进的k折交叉验证方法,它的思想是每一次划分的训练集和测试集均具有较好的均匀性.模拟结果表明,文章所提方法在五种分类模型(k近邻,决策树,随机森林,支持向量机和Adaboost)上对预测精度的估计均比普通k折交叉验证的高.将所提方法应用于骨质疏松实际数据分析中,根据对预测精度的估计选择了最优的模型进行骨质疏松患者的分类预测.     

A Study of the Dennis-Wolkowicz Method on Convex Functions

In this paper, we analyze the global convergence of the least-change secant method proposed by Dennis and Wolkowicz, when applied to convex objective functions. One of the most distinguished features of this method is that the Dennis-Wolkowicz update doesn't necessarily belong to the Broyden convex family and can be close to the DFP update, but it still has the self-correcting property. We prove that, for convex objective functions, this method with the commonly used Wolfe line search is globally convergent. We also provide some numerical results.     

基于限制玻尔兹曼机的极限学习机方法

针对高维数据中存在冗余以及极限学习机(ELM)存在随机给定权值导致算法性能不稳定等问题,将限制玻尔兹曼机(RBM)与ELM相结合提出了基于限制玻尔兹曼机优化的极限学习机算法(RBM-ELM).通过限制玻尔兹曼机对原始数据进行特征降维的同时,得到ELM输入层权值和隐含层偏置的优化参数.实验结果表明,相比较随机森林,逻辑回归,支持向量机和极限学习机四种机器学习算法,RBM-ELM算法能获得较高的分类精度.     

A Two-Term PRP-Based Descent Method

In this paper, by the use of the project of the PRP (Polak–Ribiére–Polyak) conjugate gradient direction, we develop a PRP-based descent method for solving unconstrained optimization problem. The method provides a sufficient descent direction for the objective function. Moreover, if exact line search is used, the method reduces to the standard PRP method. Under suitable conditions, we show that the method with some backtracking line search or the generalized Wolfe-type line search is globally convergent. We also report some numerical results and compare the performance of the method with some existing conjugate gradient methods. The results show that the proposed method is efficient.     

一种调查敏感性问题的随机化方法

根据已有的调查定性敏感性问题的方法,本文提出了一种新的随机化调查方法,该方法得到的估计量在一定条件下具有较小的方差.     

基于蒙特卡罗方法的摩擦材料表面形貌分形插值模拟

通过对铜基复合材料表面形貌的分析和研究,利用分形统计方法,对表征微凸体的特征参数进行分布规律讨论,结合蒙特卡罗方法和分形理论建立了表征微凸体大小的特征参数的数学模型,讨论了分形插值理论中迭代函数系统(IFS)的构造,提出了易于计算机实现的摩擦材料表面形貌模拟算法.同时,对表征微凸体特征的模拟数据进行非参数假设检验,检验结果表明这种模拟摩擦材料表面形貌的方法是可行的.