Estimation of Distribution Algorithms based on n-gram Statistics for Sequencing and Optimization

Abstract

This paper presents 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 using probabilistic models based on $n$-gram statistics. These models have been used extensively in modeling the 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 results in premature convergence. We give an explanation on this situation, along with some empirical support. We then introduce a technique for combining 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 as well as prior knowledge about the problem into the search process. Promising preliminary results on solving Traveling Salesman Problems (TSPs) are presented.