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

July 2014

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

Authors:

C-Y. Chuang and S. F. Smith

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.
@conference{Chuang-2014-120544,
author = {C-Y. Chuang And S. F. Smith},
title = {Estimation of Distribution Algorithms based on n-gram Statistics for Sequencing and Optimization},
booktitle = {Proceedings Annual Genetic and Evolutionary Computation Conference (GECCO '14)},
year = {2014},
month = {July},
pages = {53 - 54},
}
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.