Fast Probabilistic Modeling for Combinatorial Optimization

Abstract

Probabilistic models have recently been utilized for the opti-mization of large combinatorial search problems. However, complex probabilistic models that attempt to capture inter-parameter 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 algo-rithms: hillclimbing and Population-based incremental learning (PBIL). The resulting algorithms maintain many of the benefits of probabilistic modeling, with far less computa-tional expense. Extensive empirical results are provided; COMIT has been successfully applied to jobshop schedul-ing, traveling salesman, and knapsack problems. This paper also presents a review of probabilistic modeling for combi-natorial optimization. 1