Paper: Using Optimal Dependency-Trees for Combinatorial Optimization

[Shumeet Baluja]

The following paper is available from:
http://www.cs.cmu.edu/~baluja/techreps.html
(CMU-CS-97-107)



Title:
Using Optimal Dependency-Trees for Combinatorial Optimization: 
Learning the Structure of the Search Space


Abstract:
Many combinatorial optimization algorithms have no mechanism to
capture inter-parameter dependencies. However, modeling such
dependencies may allow an algorithm to concentrate its sampling more
effectively on regions of the search space which have appeared
promising in the past. We present an algorithm which incrementally
learns second-order probability distributions from good solutions seen
so far, uses these statistics to generate optimal (in terms of maximum
likelihood) dependency trees to model these distributions, and then
stochastically generates new candidate solutions from these trees. We
test this algorithm on a variety of optimization problems. Our results
indicate superior performance over other tested algorithms that either
(1) do not explicitly use these dependencies, or (2) use these
dependencies to generate a more restricted class of dependency graphs.


By: 
Shumeet Baluja
 Justsystem Pittsburgh Research Center    School of Computer Science  
 4616 Henry St.                           Carnegie Mellon University  
 Pittsburgh, PA. 15213                    Pittsburgh, PA. 15213       

Scott Davies
 School of Computer Science
 Carnegie Mellon University
 Pittsburgh, PA. 15213



This work is an extension of the work presented in two papers at NIPS 1996:

Baluja, S., "Genetic Algorithms and Explicit Search Statistics"
to appear in Advances in Neural Information Processing Systems 1996.

De Bonet, J., Isbell, C., and Viola, P. (1997) "MIMIC: Finding Optima
by Estimating Probability Densities," to appear in Advances in Neural
Information Processing Systems 1996.



As always, comments and suggestion are most welcome.