Homotopic Convex Transformation: A New Landscape Smoothing Method for the Traveling Salesman Problem
This paper proposes a novel landscape smoothing method for the symmetric Traveling Salesman Problem (TSP). We first define the Homotopic Convex (HC) transformation of a TSP as a convex combination of a well-constructed simple TSP and the original TSP. The simple TSP, called the convex-hull TSP, is constructed by transforming a known local or global optimum. We observe that controlled by the coefficient of the convex combination, with local or global optimum, (i) the landscape of the HC transformed TSP is smoothed in terms that its number of local optima is reduced compared to the original TSP; (ii) the fitness distance correlation of the HC transformed TSP is increased. Further, we observe that the smoothing effect of the HC transformation depends highly on the quality of the used optimum. A high-quality optimum leads to a better smoothing effect than a low-quality optimum. We then propose an iterative algorithmic framework in which the proposed HC transformation is combined within a heuristic TSP solver. It works as an escaping scheme from local optima aiming to improve the global search ability of the combined heuristic. Case studies using the 3-Opt and the Lin-Kernighan local search as the heuristic solver show that the resultant algorithms significantly outperform their counterparts and two other smoothing-based TSP heuristic solvers on most of the test instances with up to 20,000 cities.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
String Tightening as a Self-Organizing Phenomenon: Computation of Shortest Homotopic Path, Smooth Path, and Convex Hull
The phenomenon of self-organization has been of special interest to the neural network community for decades. In this paper, we study a variant of the Self-Organizing Map (SOM) that models the phenomenon of self-organiza…
Progressive Power Homotopy for Non-convex Optimization
We propose a novel first-order method for non-convex optimization of the form $\max_{\bm{w}\in\mathbb{R}^d}\mathbb{E}_{\bm{x}\sim\mathcal{D}}[f_{\bm{w}}(\bm{x})]$, termed Progressive Power Homotopy (Prog-PowerHP). The me…
Global Convergence of Sampling-Based Nonconvex Optimization through Diffusion-Style Smoothing
Sampling-based optimization (SBO), like cross-entropy method and evolutionary algorithms, has achieved many successes in solving non-convex problems without gradients, yet its convergence is poorly understood. In this pa…
Nash Equilibrium Existence without Convexity
In this paper, I prove the existence of a pure-strategy Nash equilibrium for a large class of games with nonconvex strategy spaces. Specifically, if each player's strategies form a compact, connected Euclidean neighborho…
Accelerate the Warm-up Stage in the Lasso Computation via a Homotopic Approach
In optimization, it is known that when the objective functions are strictly convex and well-conditioned, gradient-based approaches can be extremely effective, e.g., achieving the exponential rate of convergence. On the o…