טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentUri Dubin
SubjectThe Cross-Entropy Method for Combinatorial Optimization with
Applications
DepartmentDepartment of Electrical Engineering
Supervisor Mr. Israeli Moshe (Deceased)


Abstract

The goal of this work is to study the application of the Cross-Entropy (CE) algorithm to problems in combinatorial optimization. This relatively new algorithm has been successfully   applied to the Maximum Cut, the Traveling Salesperson, the Shortest Path problems, to Network flows, Graph Coloring and other types of hard optimization problems.


The CE method is based on an adaptive generic randomized algorithm. It employs an auxiliary random mechanism (a distribution function) equipped with a set of parameters, which transforms the deterministic problem into a stochastic one. The CE algorithm is   a multiple iteration procedure, where each iteration involves two phases:


·         Generation of random solutions using a parametric auxiliary distribution followed by a calculation of the associated objective function.

·         Updating the parameter vector, on the basis of the best scoring solutions generated in the first phase


It has been found, that the parameters of the algorithm converge to a small subset, which correspond to the best possible solutions of the given problem.  The work consists of two major parts.


In the first part the question of convergence of the CE procedure is explored. Using tools from Information and Learning theories we try to understand the observed behavior of the algorithm. This leads to various modifications of the basic Cross-Entropy procedure.


The second part is more experimental. New applications of the CE for real-life problems are described. They include Markovian decision models, image matching, segmentation, clustering and different games. The generality and simplicity of the CE procedure allows an easy adaptation of the algorithm to a wide range of combinatorial problems. It may be considered as an alternative algorithm to many standard and
non-standard techniques for hard optimization problems.