Permutation Optimization by Iterated Estimation of Random Keys Marginal Product Factorizations. Parallel Problem Solving From Nature

Abstract. In IDEAs, the probability distribution of a selection of so-lutions is estimated each generation. From this probability distribution, new solutions are drawn. Through the probability distribution, various relations between problem variables can be exploited to achieve efficient optimization. For permutation optimization, only real valued probability distributions have been applied to a real valued encoding of permuta-tions. In this paper, we present two approaches to estimating marginal product factorized probability distributions in the space of permuta-tions directly. The estimated probability distribution is used to identify crossover positions in a real valued encoding of permutations. The re-sulting evolutionary algorithm (EA) is capable of more efficient scalable optimization of deceptive permutation problems of a bounded order of difficulty than when real valued probability distributions are used.