Uri Dubin

Cross-entropy Method: Theory with Applications Uri Dubin

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 Travelling Salesperson, the Shortest Path problems, to Networks, 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: 1. Generation of random solutions using a parametric auxiliary distribution followed by a calculation of the associated objective function. 2. Updating the parameter vector, on the basis of the best scoring solutions generated. In the first part the question of convergence of the CE procedure is explored. Using tools from Information Geometry. The second part is more experimental. New applications of the CE for real-life problems are described.