On the convergence of the cross-entropy method

被引：65

作者：

Margolin, L ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Fac Ind Engn & Management, IL-32000 Haifa, Israel

来源：

ANNALS OF OPERATIONS RESEARCH | 2005年 / 134卷 / 01期

关键词：

combinatorial optimization; convergence; cross-entropy;

D O I：

10.1007/s10479-005-5731-0

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：201 / 214

页数：14

共 11 条

[1]

DUBIN U, 2002, THESIS TECHNION HAIF

[2] ACO algorithms with guaranteed convergence to the optimal solution [J].

Gutjahr, WJ .

INFORMATION PROCESSING LETTERS, 2002, 82 (03) :145-153

[3]

HOMEMDEMELLO T, 2002, UNPUB RARE EVENT EST

[4]

MARGOLIN L, 2002, THEIS TECHNION HAIFA

[5]

Rubinstein R., 1999, Methodology and computing in applied probability, V1, P127, DOI DOI 10.1023/A:1010091220143

[6] Cross-Entropy and Rare Events for Maximal Cut and Partition Problems [J].

Fac. of Indust. Eng. and Management, Technion - Israel Inst. of Technol., Haifa 32000, Israel ;

不详 .

ACM Transactions on Modeling and Computer Simulation, 2002, 12 (01) :27-53

[7]

Rubinstein R.Y., 2001, ENCY OPERATIONS RES, P102

[8] Optimization of computer simulation models with rare events [J].

Rubinstein, RY .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 99 (01) :89-112

[9]

Rubinstein RY, 2001, APPL OPTIMIZAT, V54, P303

[10]

RUBINSTEIN RY, 2004, CROSS ENTROPY

← 1 2 →