M.Sc Thesis | |

M.Sc Student | Dubin Uri |
---|---|

Subject | The Cross-Entropy Method for Combinatorial Optimization with Applications |

Department | Department of Electrical and Computers Engineering |

Supervisor | PROF. Moshe Israeli (Deceased) |

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.