Efficient bit labeling in factorization machines with annealing for traveling salesman problem

Abstract

Abstract To efficiently determine an optimum parameter combination in a large-scale problem, it is essential to convert the parameters into available variables in actual machines. Specifically, quadratic unconstrained binary optimization problems are solved using machine learning, for example, factorization machines with annealing, which convert a raw parameter to binary variables. This study investigates the dependence of the convergence speed and accuracy on the binary labeling method, which can influence the cost function shape and thus the probability of being captured at a local minimum solution. By exemplifying the traveling salesman problem (TSP), we propose and evaluate Gray labeling, which correlates the Hamming distance in binary labels with the traveling distance. Through numerical simulation of the TSP at a limited number of iterations, the Gray labeling shows fewer local minima percentages and shorter traveling distances compared with natural labeling.