Convergence properties of the cross-entropy method for discrete optimization

被引：95

作者：

Costa, Andre ^{[1
]}

Jones, Owen Dafydd

Kroese, Dirk

机构：

[1] Univ Melbourne, Ctr Excellence Math & Stat Complex Syst, Melbourne, Vic 3010, Australia

[2] Univ Melbourne, Dept Math & Stat, Melbourne, Vic 3010, Australia

[3] Univ Queensland, Dept Math, Brisbane, Qld 4072, Australia

来源：

OPERATIONS RESEARCH LETTERS | 2007年 / 35卷 / 05期

基金：

澳大利亚研究理事会;

关键词：

cross-entropy method; discrete optimization; Stochastic search;

D O I：

10.1016/j.orl.2006.11.005

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2007 Elsevier B.V. All rights reserved.

引用

页码：573 / 580

页数：8

共 10 条

[1]

AARTS E, 1997, LOCAL SEARCH COMBINA

[2] A global search method for discrete stochastic optimization [J].

Andradottir, S .

SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (02) :513-530

[3]

[Anonymous], 1956, INFINITE SEQUENCES S

[4]

[Anonymous], 2000, Intelligent Optimisation Techniques

[5]

Holland JH, 1992, INTRO ANAL APPL BIOL

[6]

LARRANAGA P, 2001, ESTIMATION DISTRIBUT

[7] On the convergence of the cross-entropy method [J].

Margolin, L .

ANNALS OF OPERATIONS RESEARCH, 2005, 134 (01) :201-214

[8]

NEMHAUSER LG, 1988, INTEGER COMBINATORIA

[9]

Rubinstein R. Y., 2004, CROSS ENTROPY METHOD

[10]

Spall J. C., 2003, INTRO STOCHASTIC SEA, DOI [10.1002/0471722138, DOI 10.1002/0471722138]

← 1 →