Ph.D Thesis
Ph.D Student Yochai Gat Entropy Based Estimation of Distribution Algorithms for Combinatorial Optimization, Counting and Policy Search Department of Industrial Engineering and Management Professor Emeritus Rubinstein Reuven-Yacov (Deceased) Full Professor Mytnik Leonid

Abstract

Programs following the algorithm below can qualify as Evolutionary Computation (EC)

1.      Generate a population of structures

2.      Repeat

a.       Test the structures for quality

b.      Select structures to reproduce

c.       Produce new variations of selected structures

d.      Replace old structures with new ones

3.      Until satisfied

There are many ways to fill in the details of this algorithm. Moreover, there may be many ways to tackle any given problem using EC.

EC techniques incorporate variation operators, such as mutation and crossover, applied to one or two structures at a time. In the mid 1990s emerged Estimation of Distribution Algorithms (EDAs), which use a probabilistic model of the entire population or its elite to produce the new population, thus simultaneously mutating and recombining many structures.

One of the first EDAs developed is the Cross Entropy (CE) method. We present two new and similar EDAs: The Minimum Cross Entropy (MCE) method and the Elite Minimum Cross Entropy (EMCE) method. We apply them to several Combinatorial Optimization Problems. The results show that they are as accurate as the CE method, but the EMCE is somewhat slower and the MCE method is by far the slowest.

Next we show how these EDAs can be used in counting problems, where the object is to count the number of solutions of a certain kind. We harness the CE method for counting tours in graphs and for counting the number of Self Avoiding Walks, which are random walks of a predefined length on a two dimensional grid that do not visit any grid point more than once. We also explain how the MCE and EMCE methods can be used for counting. The results indicate that the CE method can be very useful for counting problems, which so far received very little attention.

Finally, we apply EDAs to policy search in Markov Decision Processes (MDPs). Specifically we employ the CE method for finding the shortest path through a maze. We also use a similar EDA based on the method of moments instead of CE minimization for finding a good policy for the well known Inventory Control Problem. The results suggest that our EDAs are faster than traditional gradient dependent methods.