טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMargolin Leonid
SubjectCross-Entropy Method for Combinatorial Optimization
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Emeritus Reuven-Yacov Rubinstein (Deceased)
Professor Emeritus Ishay Weissman


Abstract

The cross-entropy method was pioneered and developed by Rubinstein for solving both continuous multi-extremal and discrete optimization problems. This method presents an adaptive stochastic procedure based on importance sampling and Kullback-Leibler cross entropy. While most of the stochastic algorithms for combinatorial optimization are based on local search (they employ local neighborhood structures), the cross-entropy method is a global random search procedure.

The idea of the cross-entropy method came from the simulation field. In fact, the method arises from the rare-event estimation framework and makes use of the same procedure that used for rare event probabilities estimation. The main idea of the cross-entropy method can be stated as follows.

First, we randomize our deterministic problem (by defining a probability density function on the set of all the possible solutions). Next, we define the following event: ``the optimal solution appears within sample of certain size (which is very small in comparison with the number of all the feasible solutions)''. Clearly, this event is rare, and to obtain it by sampling is a non-trivial problem. For this purpose we make adaptive changes of the probability density function according to the Kullback-Leibler cross-entropy approach. This procedure significantly increases the chances of the optimal solution (or an almost optimal) to appear within our sample.

In this work we give both mathematical foundation of the cross-entropy method and numerical results for several combinatorial problems. In addition, we present several modifications and generalization of the method and prove the asymptotic convergence for some particular cases. Also we explain how the cross-entropy method is related to the ant colony meta-heuristic.