Random Keys on ICE: Marginal Product Factorized Probability Distributions in Permutation Optimization
Peter A. N. Bosman, Dirk Thierens · Utrecht University Repository (Utrecht University) · 2002
In this paper, we discuss multivariately factorized probability distributions for permutation random variables and a greedy approach to estimating these probability distributions from data.We use the representation known as random keys for permutations.The major benefit of using random keys is that no infeasible solution can be generated if crossover is applied in an evolutionary algorithm (EA).The estimated multivariately factorized probability distribution can be used to construct a linkage friendly crossover operator with which new offspring can be generated.We call the EA that uses this technique to construct a crossover operator, ICE.This technical report specifically presents the details of estimating multivariately factorized probability distributions for permutations using the random keys representation.As such, this paper is a extension of an earlier publication in which experiments with an EA that follows this approach have been reported as well [7]. OutlineThis paper is organized as follows.In section 2 we discuss permutations and the random keys encoding of permutations.In section 3 we then define multivariately factorized probability distributions for permutation random variables and discuss a greedy approach to estimating such a probability distribution from data.Although this paper is not intended to be a fully self-contained EA paper in which the described algorithmics are brought into practice using a test-suite and new EAs (see [7] for a presentation of such results), we finish this paper with a brief presentation of the type of EAs in which the estimation of probability distributions plays a key role and specifically the ICE algorithm in which multivariately factorized probability distributions are used to construct a linkage friendly crossover operator.