Relational Bayesian Optimization for Permutation
Bo-Wei Huang, Wen-Zhong Fang, Hsu-Chen Liao, Tian–Li Yu · 2023
Relational Bayesian optimization for permutation (RBOP) is a new permutation estimation of distribution algorithm proposed in this paper. RBOP uses binary relations to represent the common property in permutations. Inspired by the Bayesian optimization algorithm, RBOP first builds a Bayesian network using binary relations. Then, RBOP samples genes using the most certain edge in the Bayesian network. In the scenario of black-box optimization, RBOP aims to solve various permutation problems with a limited number of function evaluations. Experiments show that in terms of average relative percentage deviation, RBOP outperforms edge histogram-based sampling algorithm on quadratic assignment problems, permutation flow shop problems and linear ordering problems. Additionally, RBOP also outperforms both node histogram-based sampling algorithm and kernels of Mallows model using Cayley distance on traveling salesman problems, permutation flow shop problems, linear ordering problems and 6 out of 10 instances of quadratic assignment problems.