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