12:00, 19 Nov 1997, WeH 7220
Probabilistic Modeling for Combinatorial Optimization
Scott Davies
joint work with Shumeet Baluja
Most combinatorial optimization algorithms do not create exlicit
models of previously found solutions in order to generate promising
new candidate solutions. For example, hillclimbing and simulated
annealing only search around a single good solution. Genetic
algorithms maintain a population of solutions but use a randomized
recombination operator to generate new solutions rather than
explicitly extracting statistics to use for solution generation. In
this talk, I will describe approaches to combinatorial optimization
based on explicitly creating probabilistic models of the
high-evaluation solutions found during search. We explore a variety
of models, ranging from one that does not model any inter-parameter
dependencies to automatically learned Bayesian networks capable of
modeling complex dependencies. Empirical testing shows that
algorithms using these models to generate new candidate solutions
often significantly improve performance over a variety of other
optimization algorithms.