Fast Probabilistic Modeling for Combinatorial Optimization

July 1998

Fast Probabilistic Modeling for Combinatorial Optimization

Authors:

Shumeet Baluja and Scott Davies

Abstract:

Probabilistic models have recently been utilized for the optimization of large combinatorial search problems. However, complex probabilistic models that attempt to capture interparameter dependencies can have prohibitive computational costs. The algorithm presented in this paper, termed COMIT, provides a method for using probabilistic models in conjunction with fast search techniques. We show how COMIT can be used with two very different fast search algorithms: hillclimbing and Population-based incremental learning (PBIL). The resulting algorithms maintain many of the benefits of probabilistic modeling, with far less computational expense. Extensive empirical results are provided; COMIT has been successfully applied to jobshop scheduling, traveling salesman, and knapsack problems. This paper also presents a review of probabilistic modeling for combinatorial optimization.
@conference{Baluja-1998-16595,
author = {Shumeet Baluja And Scott Davies},
title = {Fast Probabilistic Modeling for Combinatorial Optimization},
booktitle = {Proceedings of 15th National Conference on Artificial Intelligence (AAAI '98)},
year = {1998},
month = {July},
pages = {469 - 476},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.