A Random Forest-Assisted Local Search for Expensive Permutation-based Combinatorial Optimization Problems

Many real-world applications involve expensive permutation-based combinatorial optimization problems (PCOPs), where the evaluation of solutions becomes a time-consuming process. However, the design of efficient surrogate-based optimizers remains challenging due to the difficulty of constructing surrogate models suitable for the permutation spaces. This paper presents a random forest-assisted local search algorithm for solving expensive PCOPs. Our main motivation for using a random forest model is, in the integer space, to build a surrogate model that learns various important substructures of permutations. In the proposed algorithm, permutation-based solutions are treated as integer vectors in training random forest regression models for the objective function. Then, a population-based local search is performed on the obtained models. Experimental results on benchmark problems with limited budgets of function evaluations show that the proposed algorithms are competitive with state-of-the-art algorithms adapted to expensive PCOPs. This observation suggests that surrogate models trained on the integer representation can be effective for estimating the quality of permutation-based solutions.