Permutation Optimization Using Multivariate Dependent Estimation of Distribution Algorithm

Permutation optimization is essential in various fields, such as task scheduling, path planning. Considering the exploration ability of Estimation of Distribution Algorithms (EDAs), a multivariate dependent EDA (MEDA) is proposed in this paper. In MEDA, a probability model is designed and utilized that describes the relative position of the variables. Two local enhancement operators, including swap and insertion, are designed to improve the quality of the permutations. These operators are instrumental in refining the permutation and approximating optimal solutions. The algorithm's performance is benchmarked against existing EDAs developed for permutation optimization, including the Histogram-based Sampling Algorithm, Random Key-based EDA, Multi-objective Markov Network based EDA and Bayesian Optimization-based Algorithm, demonstrating MEDA's superiority in computational efficiency and good performance. Experiments on traveling salesman problems highlight MEDA's ability to reduce computational complexity and shorten execution time, making it a viable alternative for handling large-scale permutation challenges across various domains.