Using Optimal Dependency-Trees for Combinatorial Optimization: Learning the Structure of the Search Space
Shumeet Baluja, Scott Davies · 1997
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. Scott Davies was supported by a Graduate Student Research Fellowship from the National Science Foundation. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied of the National Science Foundation. Keywords:
Cited by 261 works.
Authors
References
- Genetic Algorithms in Search, Optimization and Machine Learning
- Shortest Connection Networks And Some Generalizations
- A Bayesian Method for the Induction of Probabilistic Networks from Data
- Approximating discrete probability distributions with dependence trees
- Uniform crossover in genetic algorithms
- Learning Bayesian Networks: The Combination of Knowledge and Statistical Data
- Removing the Genetics from the Standard Genetic Algorithm
- Learning Gaussian Networks
- MIMIC: Finding Optima by Estimating Probability Densities
- Learning Bayesian Networks: Search Methods and Experimental Results