September
2014
Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization
Authors:
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.
copied = false, 2000);
">
@conference{Chuang-2014-7941,
author = {Chung-Yao Chuang And Stephen Smith},
title = {Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization},
booktitle = {Proceedings 13th International Conference on Parallel Problem Solving from Nature (PPSN '14)},
year = {2014},
month = {September},
pages = {312 - 321},
}
author = {Chung-Yao Chuang And Stephen Smith},
title = {Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization},
booktitle = {Proceedings 13th International Conference on Parallel Problem Solving from Nature (PPSN '14)},
year = {2014},
month = {September},
pages = {312 - 321},
}