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.