 |
    |
Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization
Chung-Yao Chuang and Stephen F. Smith
The Robotics Institute, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USAcychuang@cmu.edu
sfs@cs.cmu.edu
Abstract. In this paper, we describe our work on Estimation of Distribution Algorithms (EDAs) that address sequencing problems, i.e., the task of finding the best ordering of a set of items or an optimal schedule to perform a given set of operations. Specifically, we focus on the use of probabilistic models that are based on n-gram statistics. These models have been used extensively in modeling statistical properties of sequences. We start with an EDA that uses a bigram model, then extend this scheme to higher-order models. However, directly replacing the bigram model with a higher-order model often results in premature convergence. We give an explanation on why this is the case along with some empirical support for our intuition. Following that, we propose a technique that combines multiple models of different orders, which allows for smooth transition from lower-order models to higher-order ones. Furthermore, this technique can also be used to incorporate other heuristics and prior knowledge about the problem into the search mechanism.
LNCS 8672, p. 312 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014