Accession Number : ADA322735

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

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Baluja, Shumeet ; Davies, Scott

PDF Url : ADA322735

Report Date : JAN 1997

Pagination or Media Count : 20

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.

Descriptors :   *MATHEMATICAL MODELS, *ALGORITHMS, OPTIMIZATION, STOCHASTIC PROCESSES, MAXIMUM LIKELIHOOD ESTIMATION, PROBABILITY DISTRIBUTION FUNCTIONS, STATISTICAL SAMPLES, HEURISTIC METHODS, COMBINATORIAL ANALYSIS, STRUCTURED PROGRAMMING.

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE