Node Histogram vs. Edge Histogram: A Comparison of Probabilistic Model-Building Genetic Algorithms in Permutation Domains

Abstract

Previous papers have proposed an algorithm called the edge histogram sampling algorithm (EHBSA) that models the relative relation between two nodes (edge) of permutation strings of a population within the PMBGA framework for permutation domains. This paper proposes another histogram based model we call the node histogram sampling algorithm (NHBSA). The NHBSA models node frequencies at each absolute position in strings of a population. Sampling methods are similar to that of EHBSA. Performance of NHBSA is compared with that of EHBSA using two types of permutation problems: the FSSP and the quadratic assignment problem (QAP). The results showed that the NHBSA works better than the EHBSA on these problems.