Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization

September 2014

Evolving Mixtures of n-gram Models for Sequencing and Schedule Optimization


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.
@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},
}
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.